TU Berlin

Kai-Simon GoetzmannPublications & Talks

Page Content

to Navigation


Goetzmann, Kai-Simon and Stiller, Sebastian and Telha, Claudio.
Optimization over Integers with Robustness in Cost and Few Constraints.
In Solis-Oba, Roberto and Persiano, Giuseppe (ed.)Approximation and Online Algorithms (WAOA 2011), pp. 89-101, Springer Berlin / Heidelberg, 2012.

To top


Optimization over Integers with Robustness in Cost and Few Constraints
Citation key Report-009-2011
Author Kai-Simon Goetzmann and Sebastian Stiller and Claudio Telha
Year 2011
Number 009
Institution Technische Universität Berlin, Institut für Mathematik
Abstract 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. We show that one can optimize a not necessarily binary, cost robust problem, for which one can optimize a slightly modified version of the deterministic problem. Further, in case there is a rho-approximation for the modified deterministic problem, we give a method for the cost robust counterpart to attain a (rho+epsilon)-approximation (for minimization problems; for maximization we get a 2rho-approximation), or again a rho-approximation in a slightly more restricted case. We further show that general integer linear programs where a single or few constraints are subject to uncertainty can be solved, in case the problem can be solved for constraints on piecewise linear functions. In case the programs are again binary, it suffices to solve the underlying non-robust program n+1 times. To demonstrate the progress achieved by our general techniques for non-binary integer programs, we apply them to two classes of integer programs, namely, totally unimodular integer programs and integer programs with two variables per inequality. We also exemplify the power of our approach for combinatorial optimization problems. Here the method yields polynomial time approximations and pseudopolynomial, exact algorithms for Unbounded Knapsack Problems. We derive an algorithm for problems with both cost and constraint robustness. As the general results of this paper could be applied so broadly and quickly already here, we believe they will also be a fruitful method for future research in robust optimization over integers.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry

To top

Diploma Thesis

Kai-Simon Goetzmann
Robust Combinatorial Optimization.
Technische Universität Berlin, July 2010.
Supervisors: Rolf H. Möhring, Martin Skutella

To top

To top


Quick Access

Schnellnavigation zur Seite über Nummerneingabe