NIMROp: New Interdiction Models for Robust Optimization

优化模型和算法已经成为决策和其他方面的强大工具。对于决策问题的所有信息都是可用的乐观情况，已经开发了经典的方法。在实践中，情况很少是这样的：未来是未知的，只能使用预测，测量的数据是不精确的，中断可能会使计划无效。鲁棒优化（RO）提供了一种预先考虑这些不确定性的决策方法。RO的核心是所使用的不确定性模型。在大多数RO方法中，解决方案需要考虑不确定性集合中包含的所有场景，而不假设任何概率信息。这也可以看作是一个双人游戏，其中对手试图用不确定性集合所呈现的选项来破坏解决方案。这意味着，如果不确定性集合太大，解决方案就会太保守。不确定度的选择由于影响所得RO问题的硬度而变得更加复杂。一个复杂的不确定性集可能导致优化问题无法在合理的时间内解决。由于这些原因，在建模能力和复杂性之间提供良好权衡的不确定性集的核心列表已经成为鲁棒优化研究的驱动因素。也许最流行的方法是预算不确定性，其中单个约束控制不确定系数的偏差量。在考虑多技能劳动力调度问题时，我们意识到当前可用的不确定性模型都不适合处理与变化系数相关的对手成本的情况，其目的是在预算约束下破坏尽可能多的工作。我们把它称为有界拦截的RO问题。这个为期18个月的项目的目的是对有界拦截问题进行详细研究。我们分析了这些问题的复杂性，推导了近似结果，开发了紧凑的模型公式和精确的解算法，将有界截断扩展到更一般的设置，如两阶段问题，并使用现实世界的数据集评估其性能。预算不确定性的引入对RO模型的研究和应用的影响显示了良好不确定性模型的效力。通过提出的方法，我们扩展了RO的能力来处理更广泛的决策问题，同时为进一步的方法研究开辟了一条有趣的途径。

Optimization models and algorithms have become powerful tools for decision making and beyond. Classic methods have been developed for the optimistic case that all information on the decision problem is available. In practice, that is rarely the case: The future is unknown and forecasts are used, measured data is imprecise, and disruptions may render a plan useless.Robust optimization (RO) offers an approach to make decisions where such uncertainties are taken into account beforehand. Central to RO is the model of uncertainty that is used. In most RO approaches, a solution needs to take all scenarios contained in an uncertainty set into account, without assuming any probability information. This can also be seen as a two-player game, where an adversary tries to disrupt a solution with the options presented by the uncertainty set. That means that if the uncertainty set is too large, a solution will be too conservative. The choice of uncertainty is additionally complicated by the fact that it influences the hardness of the resulting RO problem. A complex uncertainty set may result in optimization problems that cannot be solved in reasonable time.For these reasons, a core list of uncertainty sets which provide a good trade-off between modeling power and complexity have been a driver of robust optimization research. Perhaps the most popular approach is budgeted uncertainty, where a single constraint controls the amount of deviation for uncertain coefficients.While considering a multi-skilled workforce scheduling problem, we realized that none of the currently available uncertainty models are suitable to treat situations where there are costs for the adversary associated with changing coefficients, and the aim is to disrupt as many jobs as possible under a budget constraint. We refer to this as a RO problem with bounded interdiction.The aim of this 18-month project is to conduct a detailed study of bounded interdiction problems. We analyze the complexity of such problems, derive approximation results, develop compact model formulations and exact solution algorithms, extend bounded interdiction to more general settings such as two-stage problems, and evaluate its performance with real-world data sets.The impact that the introduction of budgeted uncertainties has had on the research on and application of RO models shows the potency of good uncertainty models. With the proposed approach we extend the capabilities of RO to handle a wider class of decision making problems, and simultaneously open an interesting avenue for further methodological research.