On the generation of metric TSP instances with a large integrality gap by branch-and-cut

DOI10.1007/s12532-023-00235-7arXiv2109.02454OpenAlexW3196973566MaRDI QIDQ6175708

Luca Maria Gambardella, Stefano Gualandi, Unnamed Author, Monaldo Mastrolilli

Publication date: 24 July 2023

Published in: Mathematical Programming Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2109.02454

zbMATH Keywords

integer programmingbranch-and-cutintegrality gap analysismetric traveling salesman problem

Mathematics Subject Classification ID

Integer programming (90C10) Mixed integer programming (90C11) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improving branch-and-cut performance by random sampling
• Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
• Facet identification for the symmetric traveling salesman polytope
• General \(k\)-opt submoves for the Lin-Kernighan TSP heuristic
• A cutting plane algorithm for a clustering problem
• The Steiner problem with edge lengths 1 and 2
• On the solution of traveling salesman problems
• The ellipsoid method and its consequences in combinatorial optimization
• The convex-hull-and-line traveling salesman problem: A solvable case
• Simulated annealing for constrained global optimization
• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• On the integrality ratio of the subtour LP for Euclidean TSP
• Graphic vertices of the metric polytope
• Hit-and-run mixes fast
• Hard to solve instances of the Euclidean traveling salesman problem
• A polynomial algorithm for a constrained traveling salesman problem
• TSP on Cubic and Subcubic Graphs
• Finding the Exact Integrality Gap for Small Traveling Salesman Problems
• Integer Programming Formulation of Traveling Salesman Problems
• Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded Regions
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Heuristic analysis, linear programming and branch and bound
• TSPLIB—A Traveling Salesman Problem Library
• Weighted k‐cardinality trees: Complexity and polyhedral structure
• A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem
• Solution of a Large-Scale Traveling-Salesman Problem
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Solving convex programs by random walks

This page was built for publication: On the generation of metric TSP instances with a large integrality gap by branch-and-cut