TY - GEN

T1 - Optimization over integers with robustness in cost and few constraints

AU - Goetzmann, Kai Simon

AU - Stiller, Sebastian

AU - Telha, Claudio

PY - 2012

Y1 - 2012

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

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

KW - Integer Programming

KW - Integer Programs with two variables per inequality

KW - Robust Optimization

KW - Total Unimodularity

KW - Unbounded Knapsack

UR - http://www.scopus.com/inward/record.url?scp=84859359632&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-29116-6_8

DO - 10.1007/978-3-642-29116-6_8

M3 - Conference contribution

AN - SCOPUS:84859359632

SN - 9783642291159

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 89

EP - 101

BT - Approximation and Online Algorithms - 9th International Workshop, WAOA 2011, Revised Selected Papers

T2 - 9th International Workshop on Approximation and Online Algorithms, WAOA 2011

Y2 - 8 September 2011 through 9 September 2011

ER -