A Note on the Separation of Subtour Elimination Constraints in Asymmetric Routing Problems

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

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

Abstract: This note proposes an alternative procedure for identifying violated subtour elimination constraints (SECs) in branch-and-cut algorithms for routing problems, such as variants of travelling salesman, shortest Hamiltonian path, or elementary shortest path problems, on directed graphs. The proposed procedure is based on computing the strong components of the support graph. The procedure possesses a better worst-case time complexity than the standard way of separating SECs, which uses minimum cut algorithms, and is easier to implement.

Keywords: Integer programming; Branch-and-cut; Separation; Subtour elimination constraints; Strong components (search for similar items in EconPapers)
Pages: 9 page
Date: 2012-03-08
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1205.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:1205

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 ().