Tractable algorithms for chance-constrained combinatorial problems

Olivier Klopfenstein

RAIRO - Operations Research (2009)

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

Abstract

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

How to cite

top

Klopfenstein, 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
  1. 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.  
  2. A. Ben-Tal and A. Nemirovski, Robust solutions of linear programming problems contamined with uncertain data. Math. Program. (Ser. A)88 (2000) 411–424.  Zbl0964.90025
  3. 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.  Zbl1064.90030
  4. D. Bertsimas and M. Sim, Robust discrete optimization and network flows. Math. Program. (Ser. B)98 (2003) 49–71.  Zbl1082.90067
  5. D. Bertsimas and M. Sim, The Price of Robustness. Oper. Res.52-1 (2004) 35–53.  Zbl1165.90565
  6. 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).  
  7. J.R. Birge and F. Louveaux, Introduction to stochastic programming. Springer-Verlag (1997).  Zbl0892.90142
  8. G. Calafiore and M.C. Campi, Uncertain convex programs: randomized solutions and confidence levels. Math. Program. A102 (2005) 25–46.  Zbl1177.90317
  9. G. Calafiore and L. El Ghaoui, Distributionally robust chance-constrained linear programs with applications. J. Optim. Theor. Appl.130 (2006) 1–22.  Zbl1143.90021
  10. A. Charnes and W.W. Cooper, Chance-constrained programming. Manage. Sci.5 (1959) 73–79.  Zbl0995.90600
  11. X. Chen, M. Sim and P. Sun, A Robust optimization perspective of stochastic programming. Oper. Res. (2007) 55 1058–1071.  Zbl1167.90608
  12. G.B. Dantzig, Linear programming under uncertainty. Manage. Sci.1 (1955) 179–206.  Zbl0995.90589
  13. E. Erdoğan and G. Iyengar, Ambiguous chance constrained problems and robust optimization. Math. Program. Ser. B55 (20057) 37–61.  Zbl1134.90028
  14. C. Grinstead and J. Snell, Introduction to probability. American Mathematical Society, Providence, Rhode Island (1994).  Zbl0914.60004
  15. W.K. Klein Haneveld and M.H. van der Vlerk, Stochastic integer programming: state of the art (1998), available at .  Zbl0920.90110URIhttp://citeseer.ist.psu.edu/kleinhaneveld98stochastic.html
  16. W. Hoeffding, Probability inequalities for sums of bounded random variables. Am. Stat. Assoc. J.58 (1963) 13–30.  Zbl0127.10602
  17. P. Kall and S.W. Wallace, Stochastic programming. Wiley, Chichester (1994).  Zbl0812.90122
  18. O. Klopfenstein and D. Nace, A robust approach to the chance-constrained knapsack problem. to appear in Oper. Res. Lett. Zbl1210.90126
  19. O. Klopfenstein, Tractable algorithms for chance-constrained combinatorial problems, (long version of the current paper).  Zbl1173.90478URIhttp://perso.rd.francetelecom.fr/klopfenstein/Papers/rmilp_online.pdf
  20. A.M. Mood and F.A. Graybill, Introduction to the theory of statistics. McGraw-Hill Book Company Inc., New York (1963).  
  21. A. Nemirovski and A. Shapiro, Convex Approximations of chance constrained programs. SIAM J. Optim.17-4 (2006) 969–996.  Zbl1126.90056
  22. 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.  Zbl1181.90248
  23. Y. Nikulin, Robustness in combinatorial optimization and scheduling theory: an annotated bibliography, www.optimization-online.org/DB_FILE/2004/11/995.pdf (2004).  
  24. A. Ruszczyński, Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra. Math. Program. A93 (2002) 195–215.  Zbl1065.90058
  25. N.V. Sahinidis, Optimization under uncertainty: state-of-the-art and opportunities. Comput. Chem. Eng.28 (2004) 971–983.  
  26. 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.  Zbl0839.90063

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.