NIMROp: New Interdiction Models for Robust Optimization
Theoretical Computer Science
Final Report Abstract
Robust optimization has become a leading methodology to treat decision-making problems under uncertainty. It allows decision makers to include uncertainty proactively, so that a solution can be found which still performs well, even if problem parameters deviate from their expected values. Part of the success of robust optimization is that it is relatively easy to apply. We do not need to know the probability distribution over problem parameters, which is often now available in practice. We only need to decide a set of scenarios against we wish to protect our decision, the so-called uncertainty set. The complexity of the robust problem depends on what kind of uncertainty set is used. A list of scenarios, for example, is often easy to determine, but has the disadvantage that the resulting problem is difficult to solve. With the introduction of budgeted uncertainty sets, a modeling tool has become available that is both easy to interpret, intuitive to define, and results in tractable robust problems. The knowledge about such types of uncertainty sets has thus been a central driver in the success of robust optimization. In this project, we consider an alternative to such sets that applies to cardinality terms that occur either in the objective or in the constraints of the problem. The uncertainty means that some of the items we would like to pack become unavailable later (e.g., a worker in a team assigned to perform some job becomes unavailable for a time). The uncertainty set is defined by a single budget constraint. We can find a worst-case scenario for this setting in very similar ways as in classic budgeted uncertainty sets. The questions we study are thus if we can determine how complex the resulting robust optimization problems are, and what the best way to solve them is. We have been able to settle the question of complexity in a negative way, by showing that the problem is not only hard to solve in general, but does not even allow any approximation algorithm. To solve the problem, we introduced several different problem reformulations which can then be easily used in connection with off-the-shelf solver software. These models also extend to cardinality constraints that occur in more complex settings, such as in problems where there are exponentially many such constraints. We have been able to demonstrate that our solution methods can treat problems of reasonable size, despite the theoretical hardness of the problem.
Publications
-
Robust combinatorial optimization problems under budgeted interdiction uncertainty. OR Spectrum, 47(1), 255-285.
Goerigk, Marc & Khosravi, Mohammad
