Tractable algorithms for chance-constrained combinatorial problems

 Access to full text

 Full (PDF)

 Access to full text

 Full (PDF)

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.  
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.  
4. D. Bertsimas and M. Sim, Robust discrete optimization and network flows. Math. Program. (Ser. B)98 (2003) 49–71.  
5. D. Bertsimas and M. Sim, The Price of Robustness. Oper. Res.52-1 (2004) 35–53.  
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).  
8. G. Calafiore and M.C. Campi, Uncertain convex programs: randomized solutions and confidence levels. Math. Program. A102 (2005) 25–46.  
9. G. Calafiore and L. El Ghaoui, Distributionally robust chance-constrained linear programs with applications. J. Optim. Theor. Appl.130 (2006) 1–22.  
10. A. Charnes and W.W. Cooper, Chance-constrained programming. Manage. Sci.5 (1959) 73–79.  
11. X. Chen, M. Sim and P. Sun, A Robust optimization perspective of stochastic programming. Oper. Res. (2007) 55 1058–1071.  
12. G.B. Dantzig, Linear programming under uncertainty. Manage. Sci.1 (1955) 179–206.  
13. E. Erdoğan and G. Iyengar, Ambiguous chance constrained problems and robust optimization. Math. Program. Ser. B55 (20057) 37–61.  
14. C. Grinstead and J. Snell, Introduction to probability. American Mathematical Society, Providence, Rhode Island (1994).  
15. 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
16. W. Hoeffding, Probability inequalities for sums of bounded random variables. Am. Stat. Assoc. J.58 (1963) 13–30.  
17. P. Kall and S.W. Wallace, Stochastic programming. Wiley, Chichester (1994).  
18. O. Klopfenstein and D. Nace, A robust approach to the chance-constrained knapsack problem. to appear in Oper. Res. Lett. 
19. 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
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.  
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.  
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.  
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.