# Tractable algorithms for chance-constrained combinatorial problems

RAIRO - Operations Research (2009)

- Volume: 43, Issue: 2, page 157-187
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topKlopfenstein, Olivier. "Tractable algorithms for chance-constrained combinatorial problems." RAIRO - Operations Research 43.2 (2009): 157-187. <http://eudml.org/doc/250652>.

@article{Klopfenstein2009,

abstract = {
This paper aims at proposing tractable algorithms to find effectively good solutions to large size chance-constrained combinatorial problems. A new robust model is introduced to deal with uncertainty in mixed-integer linear problems. It is shown to be strongly related to chance-constrained programming when considering pure 0–1 problems. Furthermore, its tractability is highlighted. Then, an optimization algorithm is designed to provide possibly good solutions to chance-constrained combinatorial problems. This approach is numerically tested on knapsack and multi-dimensional knapsack problems. The results obtained outperform many methods based on earlier literature.
},

author = {Klopfenstein, Olivier},

journal = {RAIRO - Operations Research},

keywords = {Integer linear programming; chance constraints; robust optimization; heuristic.; integer linear programming; heuristic},

language = {eng},

month = {4},

number = {2},

pages = {157-187},

publisher = {EDP Sciences},

title = {Tractable algorithms for chance-constrained combinatorial problems},

url = {http://eudml.org/doc/250652},

volume = {43},

year = {2009},

}

TY - JOUR

AU - Klopfenstein, Olivier

TI - Tractable algorithms for chance-constrained combinatorial problems

JO - RAIRO - Operations Research

DA - 2009/4//

PB - EDP Sciences

VL - 43

IS - 2

SP - 157

EP - 187

AB -
This paper aims at proposing tractable algorithms to find effectively good solutions to large size chance-constrained combinatorial problems. A new robust model is introduced to deal with uncertainty in mixed-integer linear problems. It is shown to be strongly related to chance-constrained programming when considering pure 0–1 problems. Furthermore, its tractability is highlighted. Then, an optimization algorithm is designed to provide possibly good solutions to chance-constrained combinatorial problems. This approach is numerically tested on knapsack and multi-dimensional knapsack problems. The results obtained outperform many methods based on earlier literature.

LA - eng

KW - Integer linear programming; chance constraints; robust optimization; heuristic.; integer linear programming; heuristic

UR - http://eudml.org/doc/250652

ER -

## References

top- R. Aringheri, A Tabu search algorithm for solving chance-constrained programs, Note del Polo 73, DTI – University of Milano (2005), available at http://www.crema.unimi.it/Biblioteca/SchedaNota.asp?Nota=92.
- A. Ben-Tal and A. Nemirovski, Robust solutions of linear programming problems contamined with uncertain data. Math. Program. (Ser. A)88 (2000) 411–424.
- P. Beraldi and A. Ruszczyński, A branch and bound method for stochastic integer problems under probabilistic constraints. Optim. Methods Softw.17 (2002) 359–382.
- D. Bertsimas and M. Sim, Robust discrete optimization and network flows. Math. Program. (Ser. B)98 (2003) 49–71.
- D. Bertsimas and M. Sim, The Price of Robustness. Oper. Res.52-1 (2004) 35–53.
- L. Bianchi, M. Dorigo, L.M. Gambardella and W.J. Gutjahr, Metaheuristics in stochastic combinatorial optimization: a survey, technical report IDSIA-08-06, IDSIA, available at www.idsia.ch/idsiareport/IDSIA-08-06.pdf (2006).
- J.R. Birge and F. Louveaux, Introduction to stochastic programming. Springer-Verlag (1997).
- G. Calafiore and M.C. Campi, Uncertain convex programs: randomized solutions and confidence levels. Math. Program. A102 (2005) 25–46.
- G. Calafiore and L. El Ghaoui, Distributionally robust chance-constrained linear programs with applications. J. Optim. Theor. Appl.130 (2006) 1–22.
- A. Charnes and W.W. Cooper, Chance-constrained programming. Manage. Sci.5 (1959) 73–79.
- X. Chen, M. Sim and P. Sun, A Robust optimization perspective of stochastic programming. Oper. Res. (2007) 55 1058–1071.
- G.B. Dantzig, Linear programming under uncertainty. Manage. Sci.1 (1955) 179–206.
- E. Erdoğan and G. Iyengar, Ambiguous chance constrained problems and robust optimization. Math. Program. Ser. B55 (20057) 37–61.
- C. Grinstead and J. Snell, Introduction to probability. American Mathematical Society, Providence, Rhode Island (1994).
- W.K. Klein Haneveld and M.H. van der Vlerk, Stochastic integer programming: state of the art (1998), available at . URIhttp://citeseer.ist.psu.edu/kleinhaneveld98stochastic.html
- W. Hoeffding, Probability inequalities for sums of bounded random variables. Am. Stat. Assoc. J.58 (1963) 13–30.
- P. Kall and S.W. Wallace, Stochastic programming. Wiley, Chichester (1994).
- O. Klopfenstein and D. Nace, A robust approach to the chance-constrained knapsack problem. to appear in Oper. Res. Lett.
- O. Klopfenstein, Tractable algorithms for chance-constrained combinatorial problems, (long version of the current paper). URIhttp://perso.rd.francetelecom.fr/klopfenstein/Papers/rmilp_online.pdf
- A.M. Mood and F.A. Graybill, Introduction to the theory of statistics. McGraw-Hill Book Company Inc., New York (1963).
- A. Nemirovski and A. Shapiro, Convex Approximations of chance constrained programs. SIAM J. Optim.17-4 (2006) 969–996.
- A. Nemirovski and A. Shapiro, Scenario approximations of chance constraints, in Probabilistic and Randomized Methods for Design under Uncertainty, edited by G. Calafiore and F. Dabbene. Springer, London (2005) 3–48.
- Y. Nikulin, Robustness in combinatorial optimization and scheduling theory: an annotated bibliography, www.optimization-online.org/DB_FILE/2004/11/995.pdf (2004).
- A. Ruszczyński, Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra. Math. Program. A93 (2002) 195–215.
- N.V. Sahinidis, Optimization under uncertainty: state-of-the-art and opportunities. Comput. Chem. Eng.28 (2004) 971–983.
- S.R. Tayur, R.R. Thomas and N.R. Natraj, An algebraic geometry algorithm for scheduling in the presence of setups and correlated demands. Math. Program.69-3 (1995) 369–401.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.