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

DOI10.1007/S12532-023-00235-7MaRDI QIDQ6175708zbMATH OpenOpenAlexFDO

Authors Stefano Gualandi, Monaldo Mastrolilli, Luca Maria Gambardella

Publication date 24 July 2023

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

branch-and-cutinteger programmingintegrality gap analysismetric traveling salesman problem

Mathematics Subject Classification ID

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

Abstract: This paper introduces a computational method for generating metric Travelling Salesman Problem (TSP) instances having a large integrality gap. The method is based on the solution of an integer programming problem, called IH-OPT, that takes as input a fractional solution of the Subtour Elimination Problem (SEP) on a TSP instance and computes a TSP instance having an integrality gap larger than or equal to the integrality gap of the first instance. The decision variables of IH-OPT are the entries of the TSP cost matrix, and the constraints are defined by the intersection of the metric cone with an exponential number of inequalities, one for each possible TSP tour. Given the very large number of constraints, we have implemented a branch-and-cut algorithm for solving IH-OPT. Then, by sampling cost vectors over the metric polytope and by solving the corresponding SEP, we can generate random fractional vertices of the SEP polytope. If we solve the IH-OPT problem for every sampled vertex using our branch-and-cut algorithm, we can select the generated TSP instance (i.e., cost vector), yielding the longest runtime for Concorde, the state-of-the-art TSP solver. Our computational results show that our method is very effective in producing challenging instances. As a by-product, we release the Hard-TSPLIB, a library of 41 small metric TSP instances which have a large integrality gap and are challenging in terms of runtime for Concorde.

Recommendations

• Hard to solve instances of the Euclidean traveling salesman problem
• Generating Travelling-Salesman Problems with Known Optimal Tours
• The saleman's improved tours for fundamental classes
• scientific article; zbMATH DE number 2086915
• Finding the exact integrality gap for small traveling salesman problems

Cites work

• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• A cutting plane algorithm for a clustering problem
• A polynomial algorithm for a constrained traveling salesman problem
• A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded Regions
• Facet identification for the symmetric traveling salesman polytope
• Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
• Finding the exact integrality gap for small traveling salesman problems
• General \(k\)-opt submoves for the Lin-Kernighan TSP heuristic
• Graphic vertices of the metric polytope
• Hard to solve instances of the Euclidean traveling salesman problem
• Heuristic analysis, linear programming and branch and bound
• Hit-and-run mixes fast
• scientific article; zbMATH DE number 2064412 (Why is no real title available?)
• Improving branch-and-cut performance by random sampling
• Integer Programming Formulation of Traveling Salesman Problems
• On the integrality ratio of the subtour LP for Euclidean TSP
• On the solution of traveling salesman problems
• Simulated annealing for constrained global optimization
• Solution of a Large-Scale Traveling-Salesman Problem
• Solving convex programs by random walks
• Structure of the extreme points of the subtour elimination polytope of the STSP
• The convex-hull-and-line traveling salesman problem: A solvable case
• The ellipsoid method and its consequences in combinatorial optimization
• The Steiner problem with edge lengths 1 and 2
• The traveling salesman problem. A computational study.
• TSP on cubic and subcubic graphs
• TSPLIB—A Traveling Salesman Problem Library
• Weighted k‐cardinality trees: Complexity and polyhedral structure

Cited in

(3)

• Traveling salesman problem with drone and bicycle: multimodal last-mile e-mobility
• On the integrality gap of small asymmetric traveling salesman problems: a polyhedral and computational approach
• The integrality gap of the traveling salesman problem is \(\frac{4}{3}\) if the LP solution has at most \(n + 6\) non-zero components

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

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