### Page Content

### to Navigation

## Publications

**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.

**Goetzmann, Kai-Simon**.

**The Power of Compromise. Reference Point Methods and Approximation in Multicriteria Optimization**.

Doctoral thesis, TU Berlin, 2013.

## Preprints

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 |

## Diploma Thesis

Kai-Simon Goetzmann

Robust Combinatorial Optimization.

Technische Universität Berlin, July 2010.

Supervisors: Rolf H. Möhring, Martin Skutella

## Talks & Workshops

Final presentation Diploma thesis, COGA-Seminar Sep 9, 2010:

Robust Combinatorial Optimization

Poster for assessment of the research training group MDS, October 2010:

Robust Combinatorial Optimization

Colloquium of the research training group MDS, Feb 7, 2011:

Multicriteria Optimization and Compromise Solutions

OR 2011 in Zurich, Aug 31, 2011:

Compromise Solutions

WAOA 2011 in Saarbrücken, Sept 8, 2011:

Optimization over Integers with Robustness in Cost and Few Constraints

ISAAC 2011 in Yokohama, Dec 7, 2011:

Optimal File Distribution in Peer-to-Peer Networks

Status workshop of the research training group MDS, Feb 11, 2012:

Compromise Solutions

SCOR 2012 in Nottingham, April 20, 2012:

Compromise Solutions

Colloquium of the research training group MDS, June 25, 2012:

Reference Point Methods and Approximation in Multicriteria Optimization

FRICO 2012 in Berlin, August 15, 2012:

The Power of Compromise

ISMP 2012 in Berlin, August 20, 2012:

Compromise Solutions and Approximation in Multicriteria Optimization

OR 2012 in Hannover, September 5, 2012:

Reference Point Methods and Approximation in Multicriteria Optimization