NIMROp: New Interdiction Models for Robust Optimization

• Applicant: Professor Dr. Marc Goerigk
• Subject Area: Accounting and Finance ; Theoretical Computer Science
• Term: from 2021 to 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 459533632

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.

• DFG Programme: Research Grants