NIMROp: New Interdiction Models for Robust Optimization

优化模型和算法已成为决策制定及其他方面的强大工具。经典的方法已经开发了乐观的情况下，决策问题的所有信息是可用的。在实践中，这种情况很少发生：未来是未知的，需要使用预测，测量数据是不精确的，中断可能会使计划变得无用。鲁棒优化（RO）提供了一种方法，可以预先考虑这些不确定性来做出决策。RO的核心是所使用的不确定性模型。在大多数RO方法中，解决方案需要考虑不确定性集中包含的所有场景，而不假设任何概率信息。这也可以被看作是一个两人博弈，对手试图用不确定性集合提供的选项来破坏解决方案。这意味着，如果不确定性集太大，解决方案将过于保守。不确定性的选择由于其影响所产生的RO问题的难度而额外复杂化。复杂的不确定性集合可能导致优化问题无法在合理的时间内解决，因此，一个能够在建模能力和复杂性之间提供良好平衡的不确定性集合核心列表已经成为鲁棒优化研究的驱动力。也许最流行的方法是预算的不确定性，其中一个单一的约束控制的偏差量的不确定coefficients.While考虑多技能的劳动力调度问题，我们意识到，目前可用的不确定性模型都不适合处理的情况下，有成本的对手与改变系数，其目的是破坏尽可能多的工作在预算约束下。我们称之为有界阻断的反渗透问题。这个为期18个月的项目的目的是对有界阻断问题进行详细的研究。我们分析了这类问题的复杂性，得到近似结果，开发紧凑的模型公式和精确解算法，扩展有界阻断更一般的设置，如两阶段的问题，并评估其性能与现实世界的数据sets.The预算的不确定性的引入已经对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.