An efficient cutting plane algorithm for the minimum weighted elementary directed cycle problem in planar digraphs
RAIRO - Operations Research - Recherche Opérationnelle, Volume 50 (2016) no. 3, pp. 665-675.

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.

DOI: 10.1051/ro/2015052
Classification: 90-XX
Keywords: Digraph, cycle, linear relaxation, valid inequality, polytope
Ibrahim, Mamane Souley 1; Maculan, Nelson 2; Ouzia, Hacène 3

1 Université A. Moumouni, Faculté des Sciences, BP 10.622, Niamey, Niger.
2 Federal University of Rio de Janeiro, Rio de Janeiro, Brazil.
3 Sorbonne Universités, UPMC University Paris 06, LIP6 UMR 7606, 4 place Jussieu, 75005 Paris .
@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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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, Volume 50 (2016) no. 3, pp. 665-675. doi : 10.1051/ro/2015052. http://archive.numdam.org/articles/10.1051/ro/2015052/

E. Balas and M. Oosten, On the cycle polytope of a directed graph. Networks 36 (2000) 34–46. | DOI | MR | Zbl

E. Balas and R. Stephan, On the cycle polytope of a directed graph and its relaxations. Networks 54 (2009) 47–55. | DOI | MR | Zbl

P. Bauer, A Polyhedral Approach to the Weighted Girth Problem. Dissertation, Institut fur informatik, Universitat zu Koln (1994).

D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions. J. Symbolic Comput. 9 (1990) 251–280. | DOI | MR | Zbl

C. Coullard and W.R. Pulleyblank, On cycle cones and polyhedra. Linear Algebra Appl. 114–115 (1989) 613–640. | DOI | MR | Zbl

S. Fortune, J. Hopcroft and J. Wyllie, The directed subgraph homeomorphism problem. Theoret. Comput. Sci. 10 (1980) 111–121. | DOI | MR | Zbl

V. Kaibel and R. Stephan, On cardinality constrained cycle and path polytopes. ZIB report (2007). | Zbl

M.S. Ibrahim, N. Maculan and H. Ouzia, A new class of valid inequalities for the minimum weighted elementary directed cycle problem in digraph. Submitted (2016). | Numdam | MR

M.S. Ibrahim, N. Maculan and M. Minoux, Strong flow-based formulation for the shortest path problem in digraphs with negative cycles. Int. Trans. Oper. Res. (ITOR) 16 (2009) 361–369. | DOI | MR | Zbl

M.S. Ibrahim, N. Maculan and M. Minoux, A note on the NP-hardness of the separation problem on some valid inequalities for the elementary shortest path problem. Pesquisa Operacional 34 (2014) 117–124. | DOI

M.S. Ibrahim, N. Maculan and M. Minoux, Valid inequalities and lifting procedures for the shortest path problem in digraphs with negative cycles. Optim. Lett. 9 (2015) 345–357. | DOI | MR | Zbl

A. Itai and M. Rodeh, Finding a minimum circuit in a graph. SIAM J. Comput. 7 (1978) 413–423. | DOI | MR | Zbl

A.N. Letchford and N.A. Pearson, A fast algorithm for minimum weight odd circuits and cuts in planar graphs. Oper. Res. Lett. 33 (2005) 625–628. | DOI | MR | Zbl

A. Lingas and E. Lundell, Efficient approximation algorithms for shortest cycles in undirected graphs. J. Inf. Process. Lett. 109 (2009) 493–498. | DOI | MR | Zbl

N. Maculan, G. Plateau and A. Lisser, Integer linear models with a polynomial number of variables and constraints for some classical combinatorial optimization problems. Pesquisa Operacional 23 (2003) 161–168. | DOI

M. Minoux and H. Ouzia, An Hierarchy of Strong Block-Decomposable Linear Relaxations for 0–1 MIPs. Discrete Appl. Math. 158 (2010) 2031–2048. | DOI | MR | Zbl

L. Roditty and V.V. Williams, Minimum weight cycles and triangles: equivalences and algorithms. Proc. of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS) (2011) 180–189. | MR | Zbl

R. Yuster and U. Zwick, Finding even cycles faster. SIAM. J. Discrete Math. 10 (1997) 209–222. | DOI | MR | Zbl

Cited by Sources: