Tractable algorithms for chance-constrained combinatorial problems. (English) Zbl 1173.90478
Summary: 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.
References:
| [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 · Zbl 0964.90025 · doi:10.1007/s101070000163 |
| [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 · Zbl 1064.90030 · doi:10.1080/1055678021000033937 |
| [4] | D. Bertsimas and M. Sim, Robust discrete optimization and network flows. Math. Program. (Ser. B)98 (2003) 49-71. · Zbl 1082.90067 · doi:10.1007/s10107-003-0396-4 |
| [5] | D. Bertsimas and M. Sim, The Price of Robustness. Oper. Res.52-1 (2004) 35-53. Zbl1165.90565 · Zbl 1165.90565 · doi:10.1287/opre.1030.0065 |
| [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). · Zbl 0892.90142 |
| [8] | G. Calafiore and M.C. Campi, Uncertain convex programs: randomized solutions and confidence levels. Math. Program. A102 (2005) 25-46. · Zbl 1177.90317 · doi:10.1007/s10107-003-0499-y |
| [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 · Zbl 1143.90021 · doi:10.1007/s10957-006-9084-x |
| [10] | A. Charnes and W.W. Cooper, Chance-constrained programming. Manage. Sci.5 (1959) 73-79. · Zbl 0995.90600 · doi:10.1287/mnsc.6.1.73 |
| [11] | X. Chen, M. Sim and P. Sun, A Robust optimization perspective of stochastic programming. Oper. Res. (2007) 55 1058-1071. Zbl1167.90608 · Zbl 1167.90608 · doi:10.1287/opre.1070.0441 |
| [12] | G.B. Dantzig, Linear programming under uncertainty. Manage. Sci.1 (1955) 179-206. · Zbl 0995.90589 · doi:10.1287/mnsc.1.3-4.197 |
| [13] | E. Erdoğan and G. Iyengar, Ambiguous chance constrained problems and robust optimization. Math. Program. Ser. B55 (20057) 37-61. · Zbl 1134.90028 · doi:10.1007/s10107-005-0678-0 |
| [14] | C. Grinstead and J. Snell, Introduction to probability. American Mathematical Society, Providence, Rhode Island (1994). · Zbl 0914.60004 |
| [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 · Zbl 0920.90110 |
| [16] | W. Hoeffding, Probability inequalities for sums of bounded random variables. Am. Stat. Assoc. J.58 (1963) 13-30. · Zbl 0127.10602 · doi:10.2307/2282952 |
| [17] | P. Kall and S.W. Wallace, Stochastic programming. Wiley, Chichester (1994). · Zbl 0812.90122 |
| [18] | O. Klopfenstein and D. Nace, A robust approach to the chance-constrained knapsack problem. to appear in Oper. Res. Lett. · Zbl 1210.90126 · doi:10.1016/j.orl.2008.03.006 |
| [19] | O. Klopfenstein, Tractable algorithms for chance-constrained combinatorial problems, (long version of the current paper). Zbl1173.90478 URIhttp://perso.rd.francetelecom.fr/klopfenstein/Papers/rmilp_online.pdf · Zbl 1173.90478 · doi:10.1051/ro/2009010 |
| [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 · Zbl 1126.90056 · doi:10.1137/050622328 |
| [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. · Zbl 1181.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 · Zbl 1065.90058 · doi:10.1007/s10107-002-0337-7 |
| [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. · Zbl 0839.90063 · doi:10.1007/BF01585566 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
