Volume 50, Number 3, July-September 2016
|Page(s)||665 - 675|
|Published online||04 August 2016|
An efficient cutting plane algorithm for the minimum weighted elementary directed cycle problem in planar digraphs
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 .
Received: 25 June 2015
Accepted: 11 November 2015
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.
Mathematics Subject Classification: 90-XX
Key words: Digraph / cycle / linear relaxation / valid inequality / polytope
© EDP Sciences, ROADEF, SMAI 2016
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.