NIMROp: New Interdiction Models for Robust Optimization

优化模型和算法已经成为决策和其他方面的强大工具。经典的方法已经被开发用于乐观的情况，即关于决策问题的所有信息都是可用的。在实践中，这种情况很少发生：未来是未知的，使用的是预测，测量的数据不准确，中断可能使计划毫无用处。目标优化(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.