6533b82efe1ef96bd1293de2

RESEARCH PRODUCT

A note on the separation of subtour elimination constraints in elementary shortest path problems

Michael Drexl

subject

Mathematical optimizationInformation Systems and ManagementGeneral Computer ScienceDirected graphManagement Science and Operations ResearchHamiltonian pathTravelling salesman problemIndustrial and Manufacturing Engineeringsymbols.namesakeModeling and SimulationShortest path problemsymbolsGraph (abstract data type)Branch and cutTime complexityInteger programmingMathematicsofComputing_DISCRETEMATHEMATICSMathematics

description

Abstract This note proposes an alternative procedure for identifying violated subtour elimination constraints (SECs) in branch-and-cut algorithms for elementary shortest path problems. The procedure is also applicable to other routing problems, such as variants of travelling salesman or shortest Hamiltonian 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 maximum flow algorithms, and is easier to implement.

yearjournalcountryeditionlanguage
2013-09-01European Journal of Operational Research
https://doi.org/10.1016/j.ejor.2013.03.009