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.
Mots clés : 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://www.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://www.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://www.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, Tome 43 (2009) no. 2, pp. 157-187. doi : 10.1051/ro/2009010. http://www.numdam.org/articles/10.1051/ro/2009010/
[1] , 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] and , Robust solutions of linear programming problems contamined with uncertain data. Math. Program. (Ser. A) 88 (2000) 411-424. | MR | Zbl
[3] and , A branch and bound method for stochastic integer problems under probabilistic constraints. Optim. Methods Softw. 17 (2002) 359-382. | MR | Zbl
[4] and , Robust discrete optimization and network flows. Math. Program. (Ser. B) 98 (2003) 49-71. | MR | Zbl
[5] and , The Price of Robustness. Oper. Res. 52-1 (2004) 35-53. | MR | Zbl
[6] , , and , 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] and , Introduction to stochastic programming. Springer-Verlag (1997). | MR | Zbl
[8] and , Uncertain convex programs: randomized solutions and confidence levels. Math. Program. A 102 (2005) 25-46. | MR | Zbl
[9] and , Distributionally robust chance-constrained linear programs with applications. J. Optim. Theor. Appl. 130 (2006) 1-22. | MR | Zbl
[10] and , Chance-constrained programming. Manage. Sci. 5 (1959) 73-79. | MR | Zbl
[11] , and , A Robust optimization perspective of stochastic programming. Oper. Res. (2007) 55 1058-1071. | MR | Zbl
[12] , Linear programming under uncertainty. Manage. Sci. 1 (1955) 179-206. | MR | Zbl
[13] and , Ambiguous chance constrained problems and robust optimization. Math. Program. Ser. B 55 (20057) 37-61. | MR | Zbl
[14] and , Introduction to probability. American Mathematical Society, Providence, Rhode Island (1994). | Zbl
[15] and , Stochastic integer programming: state of the art (1998), available at http://citeseer.ist.psu.edu/kleinhaneveld98stochastic.html.
[16] , Probability inequalities for sums of bounded random variables. Am. Stat. Assoc. J. 58 (1963) 13-30. | MR | Zbl
[17] and , Stochastic programming. Wiley, Chichester (1994). | MR | Zbl
[18] and , A robust approach to the chance-constrained knapsack problem. to appear in Oper. Res. Lett. | MR
[19] , Tractable algorithms for chance-constrained combinatorial problems, http://perso.rd.francetelecom.fr/klopfenstein/Papers/rmilp_online.pdf (long version of the current paper).
[20] and , Introduction to the theory of statistics. McGraw-Hill Book Company Inc., New York (1963). | MR | Zbl
[21] and , Convex Approximations of chance constrained programs. SIAM J. Optim. 17-4 (2006) 969-996. | MR | Zbl
[22] and , 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] , Robustness in combinatorial optimization and scheduling theory: an annotated bibliography, www.optimization-online.org/DB_FILE/2004/11/995.pdf (2004).
[24] , Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra. Math. Program. A 93 (2002) 195-215. | MR | Zbl
[25] , Optimization under uncertainty: state-of-the-art and opportunities. Comput. Chem. Eng. 28 (2004) 971-983.
[26] , and , An algebraic geometry algorithm for scheduling in the presence of setups and correlated demands. Math. Program. 69-3 (1995) 369-401. | MR | Zbl
Cité par Sources :
