Voir la notice de l'article provenant de la source Numdam
In this paper, we study the efficiency (both theoretically and computationally) of a class of valid inequalities for the minimum weighted elementary directed cycle problem (MWEDCP) in planar digraphs with negative weight elementary directed cycles. These valid inequalities are called cycle valid inequalities and are parametrized by an integer called inequality’s order. From a theoretical point of view, we prove that separating cycle valid inequalities of order 1 in planar digraph can be done in polynomial time. From a computational point of view, we present a cutting plane algorithm featuring the efficiency of a lifted form of the cycle valid inequalities of order 1. In addition to these lifted valid inequalities, our algorithm is also based on a mixed integer linear formulation of the MWEDCP. The computational results are carried out on randomly generated planar digraph instances of the MWEDCP. For all 29 instances considered, we obtain in average 26.47 gap improvement. Moreover, for some of our instances the strengthening process directly displays the optimal integer elementary directed cycle.
Ibrahim, Mamane Souley 1 ; Maculan, Nelson 2 ; Ouzia, Hacène 3
@article{RO_2016__50_3_665_0,
author = {Ibrahim, Mamane Souley and Maculan, Nelson and Ouzia, Hac\`ene},
title = {An efficient cutting plane algorithm for the minimum weighted elementary directed cycle problem in planar digraphs},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {665--675},
publisher = {EDP-Sciences},
volume = {50},
number = {3},
year = {2016},
doi = {10.1051/ro/2015052},
mrnumber = {3538846},
zbl = {1349.90815},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2015052/}
}
TY - JOUR AU - Ibrahim, Mamane Souley AU - Maculan, Nelson AU - Ouzia, Hacène TI - An efficient cutting plane algorithm for the minimum weighted elementary directed cycle problem in planar digraphs JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2016 SP - 665 EP - 675 VL - 50 IS - 3 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro/2015052/ DO - 10.1051/ro/2015052 LA - en ID - RO_2016__50_3_665_0 ER -
%0 Journal Article %A Ibrahim, Mamane Souley %A Maculan, Nelson %A Ouzia, Hacène %T An efficient cutting plane algorithm for the minimum weighted elementary directed cycle problem in planar digraphs %J RAIRO - Operations Research - Recherche Opérationnelle %D 2016 %P 665-675 %V 50 %N 3 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro/2015052/ %R 10.1051/ro/2015052 %G en %F RO_2016__50_3_665_0
Ibrahim, Mamane Souley; Maculan, Nelson; Ouzia, Hacène. An efficient cutting plane algorithm for the minimum weighted elementary directed cycle problem in planar digraphs. RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 3, pp. 665-675. doi: 10.1051/ro/2015052
Cité par Sources :