Tractable algorithms for chance-constrained combinatorial problems
France Télécom R&D, 38-40 rue du gl Leclerc, 92130 Issy-les-Moulineaux, France; firstname.lastname@example.org
2 Université de Technologie de Compiègne, Laboratoire Heudiasyc UMR CNRS 6599, 60205 Compiègne Cedex, France
Accepted: 15 July 2008
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.
Mathematics Subject Classification: 90C10 / 90C15
Key words: Integer linear programming / chance constraints / robust optimization / heuristic.
© EDP Sciences, ROADEF, SMAI, 2009