Item Infomation


Title: 
On the generation of metric TSP instances with a large integrality gap by branch-and-cut
Authors: 
Eleonora, Vercesi
Stefano, Gualandi
Monaldo, Mastrolilli
Issue Date: 
2023
Publisher: 
Springer
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.
Description: 
CC BY
URI: 
https://link.springer.com/article/10.1007/s12532-023-00235-7
https://dlib.phenikaa-uni.edu.vn/handle/PNK/7520
Appears in Collections
OER - Khoa học Tự nhiên
ABSTRACTS VIEWS

15

FULLTEXT VIEWS

42

Files in This Item: