Thumbnail Image

Optimization over Integers with Robustness in Cost and Few Constraints

Goetzmann, Kai-Simon; Stiller, Sebastian; Telha, Claudio

Inst. Mathematik

Robust optimization is an approach for optimization under uncertainty that has recently attracted attention both from theory and practitioners. While there is an elaborate and powerful machinery for continuous robust optimization problems, results on robust combinatorial optimization and robust linear integer programs are still rare and hardly general. In a seminal paper Bertsimas and Sim (2003) show that for an arbitrary, linear 0-1-problem, over which one can optimize, one can also optimize the cost-robust counterpart. They explicitly note that this method is confined to binary problems. We present a result of this type for general integer programs. Further, we extend the result to integer programs with uncertainty in one constraint.