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

Voir la notice de l'article provenant de la source Numdam

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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :