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.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Special issue on robust optimization. Math. Program. 107(1-2) (2006)
Aissi, H., Bazgan, C., Vanderpooten, D.: Approximation of min-max and min-max regret versions of some combinatorial optimization problems. Europ. J. of Oper. Res. 179(2), 281–290 (2007)
Bar-Yehuda, R., Rawitz, D.: Efficient algorithms for integer programs with two variables per constraint 1. Algorithmica 29(4), 595–609 (2001)
Ben-Tal, A., Nemirovski, A.: Robust convex optimization. Math. Oper. Res. 23(4), 769–805 (1998)
Ben-Tal, A., Nemirovski, A.: Robust solutions to uncertain linear programs. Oper. Res. Letters 25(1), 1–13 (1999)
Ben-Tal, A., Nemirovski, A.: Robust solutions of linear programming problems contaminated with uncertain data. Math. Program. 88(3), 411–424 (2000)
Bertsimas, D., Sim, M.: Robust discrete optimization and network flows. Math. Program. 98(1-3), 49–71 (2003)
Bertsimas, D., Sim, M.: The price of robustness. Oper. Res. 52(1), 35–53 (2004)
Feige, U., Jain, K., Mahdian, M., Mirrokni, V.: Robust Combinatorial Optimization with Exponential Scenarios. In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol. 4513, pp. 439–453. Springer, Heidelberg (2007)
Fischetti, M., Monaci, M.: Light Robustness. In: Ahuja, R.K., Möhring, R.H., Zaroliagis, C.D. (eds.) Robust and Online Large-Scale Optimization. LNCS, vol. 5868, pp. 61–84. Springer, Heidelberg (2009)
Goetzmann, K.-S., Stiller, S., Telha, C.: Optimization over integers with robustness in cost and few constraints. Technical Report 009-2011, Technische Universität Berlin (2011)
Hochbaum, D.: A nonlinear knapsack problem. Oper. Res. Lett. 17, 103–110 (1995)
Hochbaum, D., Megiddo, N., Naor, J., Tamir, A.: Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality. Math. Program. 62(1), 69–83 (1993)
Hochbaum, D., Naor, J.: Simple and fast algorithms for linear and integer programs with two variables per inequality. SIAM J. Comput. 23, 1179–1192 (1994)
Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22, 463–468 (1975)
Khandekar, R., Kortsarz, G., Mirrokni, V., Salavatipour, M.R.: Two-Stage Robust Network Design with Exponential Scenarios. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol. 5193, pp. 589–600. Springer, Heidelberg (2008)
Klopfenstein, O., Nace, D.: A note on polyhedral aspects of a robust knapsack problem (2007), http://www.optimization-online.org
Klopfenstein, O., Nace, D.: A robust approach to the chance-constrained knapsack problem. Oper. Res. Letters 36(5), 628–632 (2008)
Martello, S., Toth, P.: Knapsack Problems. Algorithms and Computer Implementations. John Wiley and Sons (1990)
Soyster, A.L.: Convex programming with set-inclusive constraints and applications to inexact linear programming. Oper. Res. 21(5), 1154–1157 (1973)
Yu, G.: On the max-min 0-1 knapsack problem with robust optimization applications. Oper. Res. 44(2), 407–415 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Goetzmann, KS., Stiller, S., Telha, C. (2012). Optimization over Integers with Robustness in Cost and Few Constraints. In: Solis-Oba, R., Persiano, G. (eds) Approximation and Online Algorithms. WAOA 2011. Lecture Notes in Computer Science, vol 7164. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29116-6_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-29116-6_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-29115-9
Online ISBN: 978-3-642-29116-6
eBook Packages: Computer ScienceComputer Science (R0)