Abstract
We introduce the Minimum Flow Cost Hamiltonian Cycle Problem (FCHCP). Given a graph and positive flow between pairs of vertices, the FCHCP consists of finding a Hamiltonian cycle that minimizes the total flow cost between pairs of vertices through the shortest path on the cycle. We prove that the FCHCP is NP-hard and we study the polyhedral structure of its set of feasible solutions. In particular, we present five different mixed integer programming formulations which are theoretically and computationally compared. We also propose several families of valid inequalities for one of the formulations and perform some computational experiments to assess the performance of these inequalities.
Original language | English |
---|---|
Pages (from-to) | 140-154 |
Number of pages | 15 |
Journal | Discrete Applied Mathematics |
Volume | 187 |
DOIs | |
Publication status | Published - 31 May 2015 |
Funding
This research was partly funded by the Canadian Natural Sciences and Engineering Research Council under grants 418609-2012 and 39682-10 . This support is gratefully acknowledged. The authors thank two anonymous reviewers for their valuable comments.
Keywords
- Hamiltonian cycles
- MIP formulations
- Network design
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics