The Minimum Flow Cost Hamiltonian Cycle Problem: A comparison of formulations

Camilo Ortiz-Astorquiza, Ivan Contreras, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

5 Citations (SciVal)

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 languageEnglish
Pages (from-to)140-154
Number of pages15
JournalDiscrete Applied Mathematics
Volume187
DOIs
Publication statusPublished - 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

Fingerprint

Dive into the research topics of 'The Minimum Flow Cost Hamiltonian Cycle Problem: A comparison of formulations'. Together they form a unique fingerprint.

Cite this