Tractable algorithms for chance-constrained combinatorial problems
RAIRO - Operations Research - Recherche Opérationnelle, Volume 43 (2009) no. 2, pp. 157-187.

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.

DOI: 10.1051/ro/2009010
Classification: 90C10, 90C15
Keywords: integer linear programming, chance constraints, robust optimization, heuristic
@article{RO_2009__43_2_157_0,
     author = {Klopfenstein, Olivier},
     title = {Tractable algorithms for chance-constrained combinatorial problems},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {157--187},
     publisher = {EDP-Sciences},
     volume = {43},
     number = {2},
     year = {2009},
     doi = {10.1051/ro/2009010},
     mrnumber = {2527861},
     zbl = {1173.90478},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro/2009010/}
}
TY  - JOUR
AU  - Klopfenstein, Olivier
TI  - Tractable algorithms for chance-constrained combinatorial problems
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2009
SP  - 157
EP  - 187
VL  - 43
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro/2009010/
DO  - 10.1051/ro/2009010
LA  - en
ID  - RO_2009__43_2_157_0
ER  - 
%0 Journal Article
%A Klopfenstein, Olivier
%T Tractable algorithms for chance-constrained combinatorial problems
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2009
%P 157-187
%V 43
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro/2009010/
%R 10.1051/ro/2009010
%G en
%F RO_2009__43_2_157_0
Klopfenstein, Olivier. Tractable algorithms for chance-constrained combinatorial problems. RAIRO - Operations Research - Recherche Opérationnelle, Volume 43 (2009) no. 2, pp. 157-187. doi : 10.1051/ro/2009010. http://archive.numdam.org/articles/10.1051/ro/2009010/

[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. | MR | Zbl

[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. | MR | Zbl

[4] D. Bertsimas and M. Sim, Robust discrete optimization and network flows. Math. Program. (Ser. B) 98 (2003) 49-71. | MR | Zbl

[5] D. Bertsimas and M. Sim, The Price of Robustness. Oper. Res. 52-1 (2004) 35-53. | MR | Zbl

[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). | MR | Zbl

[8] G. Calafiore and M.C. Campi, Uncertain convex programs: randomized solutions and confidence levels. Math. Program. A 102 (2005) 25-46. | MR | Zbl

[9] G. Calafiore and L. El Ghaoui, Distributionally robust chance-constrained linear programs with applications. J. Optim. Theor. Appl. 130 (2006) 1-22. | MR | Zbl

[10] A. Charnes and W.W. Cooper, Chance-constrained programming. Manage. Sci. 5 (1959) 73-79. | MR | Zbl

[11] X. Chen, M. Sim and P. Sun, A Robust optimization perspective of stochastic programming. Oper. Res. (2007) 55 1058-1071. | MR | Zbl

[12] G.B. Dantzig, Linear programming under uncertainty. Manage. Sci. 1 (1955) 179-206. | MR | Zbl

[13] E. Erdoğan and G. Iyengar, Ambiguous chance constrained problems and robust optimization. Math. Program. Ser. B 55 (20057) 37-61. | MR | Zbl

[14] C. Grinstead and J. Snell, Introduction to probability. American Mathematical Society, Providence, Rhode Island (1994). | Zbl

[15] W.K. Klein Haneveld and M.H. Van Der Vlerk, Stochastic integer programming: state of the art (1998), available at http://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. | MR | Zbl

[17] P. Kall and S.W. Wallace, Stochastic programming. Wiley, Chichester (1994). | MR | Zbl

[18] O. Klopfenstein and D. Nace, A robust approach to the chance-constrained knapsack problem. to appear in Oper. Res. Lett. | MR

[19] O. Klopfenstein, Tractable algorithms for chance-constrained combinatorial problems, http://perso.rd.francetelecom.fr/klopfenstein/Papers/rmilp_online.pdf (long version of the current paper).

[20] A.M. Mood and F.A. Graybill, Introduction to the theory of statistics. McGraw-Hill Book Company Inc., New York (1963). | MR | Zbl

[21] A. Nemirovski and A. Shapiro, Convex Approximations of chance constrained programs. SIAM J. Optim. 17-4 (2006) 969-996. | MR | Zbl

[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. A 93 (2002) 195-215. | MR | Zbl

[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. | MR | Zbl

Cited by Sources: