Voir la notice de l'article provenant de la source Numdam
We present a Branch-and-Cut algorithm where the volume algorithm is applied instead of the traditionally used dual simplex algorithm to the linear programming relaxations in the root node of the search tree. This means that we use fast approximate solutions to these linear programs instead of exact but slower solutions. We present computational results with the Steiner tree and Max-Cut problems. We show evidence that one can solve these problems much faster with the volume algorithm based Branch-and-Cut code than with a dual simplex based one. We discuss when the volume based approach might be more efficient than the simplex based approach.
@article{RO_2006__40_1_53_0,
author = {Barahona, Francisco and Lad\'anyi, L\'aszl\'o},
title = {Branch and cut based on the volume algorithm : {Steiner} trees in graphs and max-cut},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {53--73},
publisher = {EDP-Sciences},
volume = {40},
number = {1},
year = {2006},
doi = {10.1051/ro:2006010},
mrnumber = {2248422},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro:2006010/}
}
TY - JOUR AU - Barahona, Francisco AU - Ladányi, László TI - Branch and cut based on the volume algorithm : Steiner trees in graphs and max-cut JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2006 SP - 53 EP - 73 VL - 40 IS - 1 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro:2006010/ DO - 10.1051/ro:2006010 LA - en ID - RO_2006__40_1_53_0 ER -
%0 Journal Article %A Barahona, Francisco %A Ladányi, László %T Branch and cut based on the volume algorithm : Steiner trees in graphs and max-cut %J RAIRO - Operations Research - Recherche Opérationnelle %D 2006 %P 53-73 %V 40 %N 1 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro:2006010/ %R 10.1051/ro:2006010 %G en %F RO_2006__40_1_53_0
Barahona, Francisco; Ladányi, László. Branch and cut based on the volume algorithm : Steiner trees in graphs and max-cut. RAIRO - Operations Research - Recherche Opérationnelle, Tome 40 (2006) no. 1, pp. 53-73. doi: 10.1051/ro:2006010
Cité par Sources :