Optimization over integers with robustness in cost and few constraints

Kai Simon Goetzmann*, Sebastian Stiller, Claudio Telha

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

16 Scopus citations

Abstract

We consider robust counterparts of integer programs and combinatorial optimization problems (summarized as integer problems in the following), i.e., seek solutions that stay feasible if at most Γ-many parameters change within a given range. While there is an elaborate machinery for continuous robust optimization problems, results on robust integer problems are still rare and hardly general. We show several optimization and approximation results for the robust (with respect to cost, or few constraints) counterpart of an integer problem under the condition that one can optimize or approximate the original integer problem with respect to a piecewise linear objective (respectively piecewise linear constraints). For example, if there is a ρ-approximation for a minimization problem with non-negative costs and non-negative and bounded variables for piecewise linear objectives, then the cost robust counterpart can be ρ(1+ε)-approximated. We demonstrate the applicability of our approach on two classes of integer programs, namely, totally unimodular integer programs and integer programs with two variables per inequality. Further, for combinatorial optimization problems our method yields polynomial time approximations and pseudopolynomial, exact algorithms for Robust Unbounded Knapsack Problems.

Original languageEnglish
Title of host publicationApproximation and Online Algorithms - 9th International Workshop, WAOA 2011, Revised Selected Papers
Pages89-101
Number of pages13
DOIs
StatePublished - 2012
Externally publishedYes
Event9th International Workshop on Approximation and Online Algorithms, WAOA 2011 - Saarbrucken, Germany
Duration: 8 Sep 20119 Sep 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7164 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th International Workshop on Approximation and Online Algorithms, WAOA 2011
Country/TerritoryGermany
CitySaarbrucken
Period8/09/119/09/11

Keywords

  • Integer Programming
  • Integer Programs with two variables per inequality
  • Robust Optimization
  • Total Unimodularity
  • Unbounded Knapsack

Fingerprint

Dive into the research topics of 'Optimization over integers with robustness in cost and few constraints'. Together they form a unique fingerprint.

Cite this