The minimum flow cost Hamiltonian cycle problem: a comparison of formulations

DOI10.1016/J.DAM.2015.01.035MaRDI QIDQ2348064zbMATH OpenOpenAlexFDO

Authors Camilo Ortiz-Astorquiza, G. Laporte, Ivan Contreras

Publication date 10 June 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2015.01.035

zbMATH Keywords

Hamiltonian cyclesMIP formulationsnetwork design

Mathematics Subject Classification ID

Flows in graphs (05C21) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Recommendations

• A branch-and-cut algorithm for the minimum labeling Hamiltonian cycle problem and two variants
• A comparison of several models for the Hamiltonian \(p\)-median problem
• A new formulation for the traveling deliveryman problem
• A branch-and-price algorithm for solving the Hamiltonian p-median problem
• New models for and numerical tests of the Hamiltonian p-median problem

Cites work

• 0-1 reformulations of the multicommodity capacitated network design problem
• A branch‐and‐cut algorithm for the single‐commodity, uncapacitated, fixed‐charge network flow problem
• A comparative analysis of several asymmetric traveling salesman problem formulations
• A new exact discrete linear reformulation of the quadratic assignment problem
• A note on two problems in connexion with graphs
• Assignment Problems and the Location of Economic Activities
• Dual track and segmented single track bidirectional loop guidepath layout for AGV systems
• Exact and Heuristic Algorithms for the Optimum Communication Spanning Tree Problem
• Exact and heuristic approaches for the cycle hub location problem
• Exact and heuristic procedures for the material handling circular flow path design problem
• General network design: a unified view of combined location and network design problems
• scientific article; zbMATH DE number 3470175 (Why is no real title available?)
• scientific article; zbMATH DE number 1102774 (Why is no real title available?)
• Improved discrete reformulations for the quadratic assignment problem
• Integer Programming Formulation of Traveling Salesman Problems
• Lagrangean bounds for the optimum communication spanning tree problem
• Locating a cycle in a transportation or a telecommunications network
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Maximum matching and a polyhedron with 0,1-vertices
• Network flows. Theory, algorithms, and applications.
• On a routing problem
• On Optimal Solutions for the Optimal Communication Spanning Tree Problem
• On the quadratic assignment problem
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Optimizing a ring-based private line telecommunication network using tabu search
• Optimum Communication Spanning Trees
• Scheduling and routing algorithms for AGVs: A survey
• Solution of a Large-Scale Traveling-Salesman Problem
• The complexity of the network design problem
• The traveling salesman problem. A computational study.
• Three Ideas for the Quadratic Assignment Problem
• Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems

Cited in

(4)

• Exact and heuristic approaches for the cycle hub location problem
• The capacitated directed cycle hub location and routing problem under congestion
• Asymmetric probabilistic minimum-cost Hamiltonian cycle problem considering arc and vertex failures
• A branch-and-cut algorithm for the minimum labeling Hamiltonian cycle problem and two variants

Describes a project that uses

Uses Software

• Concorde

This page was built for publication: The minimum flow cost Hamiltonian cycle problem: a comparison of formulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2348064)