Solving Elementary Shortest-Path Problems as Mixed-Integer Programs

Michael Drexl () and Stefan Irnich ()
Additional contact information
Michael Drexl: Johannes Gutenberg University Mainz
Stefan Irnich: Johannes Gutenberg University Mainz

No 1201, Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz

Abstract: Ibrahim, Maculan, and Minoux (International Transactions in Operational Research, vol. 16, 2009, pp. 361-369) presented and analyzed two integer programming formulations for the elementary shortest-path problem (ESPP), which is known to be NP-hard if the underlying digraph contains negative cycles. In fact, the authors showed that a formulation based on commodity flows possesses a significantly stronger LP-relaxation than a formulation based on arc flow variables. Since the ESPP is essentially an integer problem, the contribution of our paper lies in extending this research by comparing the formulations with regard to the computation time and memory requirements required for their integer solution. Moreover, we assess the quality of the lower bounds provided by an integer relaxation of the commodity flow formulation.

Keywords: Elementary shortest-path problem; Negative cycles; Mixed-integer programming (search for similar items in EconPapers)
Pages: 12 pages
Date: 2012-01-11
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1201.pdf First version, 2012 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:jgu:wpaper:1201

Access Statistics for this paper

More papers in Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz Contact information at EDIRC.
Bibliographic data for series maintained by Research Unit IPP ().