TRACTABLE ALGORITHMSFOR CHANCE-CONSTRAINED COMBINATORIAL PROBLEMS

This paper aims at proposing tractable algorithms to findeffectively good solutions to large size chance-constrained combinato-rial problems. A new robust model is introduced to deal with uncer-tainty in mixed-integer linear problems. It is shown to be stronglyrelated to chance-constrained programming when considering pure 0–1 problems. Furthermore, its tractability is highlighted. Then, an op-timization algorithm is designed to provide possibly good solutions tochance-constrained combinatorial problems. This approach is numer-ically tested on knapsack and multi-dimensional knapsack problems.The results obtained outperform many methods based on earlier liter-ature