Cover Image

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

CC BY

Saved in:
Bibliographic Details
Main Authors: Eleonora, Vercesi, Stefano, Gualandi, Monaldo, Mastrolilli
Format: Book
Language:English
Published: Springer 2023
Subjects:
Travelling Salesman Problem
IH-OPT
Online Access:https://link.springer.com/article/10.1007/s12532-023-00235-7
https://dlib.phenikaa-uni.edu.vn/handle/PNK/7520
Tags: Add Tag
No Tags, Be the first to tag this record!
id oai:localhost:PNK-7520
record_format dspace
spelling oai:localhost:PNK-75202023-04-05T02:03:26Z On the generation of metric TSP instances with a large integrality gap by branch-and-cut Eleonora, Vercesi Stefano, Gualandi Monaldo, Mastrolilli Travelling Salesman Problem IH-OPT CC BY 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. 2023-04-05T02:03:26Z 2023-04-05T02:03:26Z 2023 Book https://link.springer.com/article/10.1007/s12532-023-00235-7 https://dlib.phenikaa-uni.edu.vn/handle/PNK/7520 en application/pdf Springer
institution Digital Phenikaa
collection Digital Phenikaa
language English
topic Travelling Salesman Problem
IH-OPT
spellingShingle Travelling Salesman Problem
IH-OPT
Eleonora, Vercesi
Stefano, Gualandi
Monaldo, Mastrolilli
On the generation of metric TSP instances with a large integrality gap by branch-and-cut
description CC BY
format Book
author Eleonora, Vercesi
Stefano, Gualandi
Monaldo, Mastrolilli
author_facet Eleonora, Vercesi
Stefano, Gualandi
Monaldo, Mastrolilli
author_sort Eleonora, Vercesi
title On the generation of metric TSP instances with a large integrality gap by branch-and-cut
title_short On the generation of metric TSP instances with a large integrality gap by branch-and-cut
title_full On the generation of metric TSP instances with a large integrality gap by branch-and-cut
title_fullStr On the generation of metric TSP instances with a large integrality gap by branch-and-cut
title_full_unstemmed On the generation of metric TSP instances with a large integrality gap by branch-and-cut
title_sort on the generation of metric tsp instances with a large integrality gap by branch-and-cut
publisher Springer
publishDate 2023
url https://link.springer.com/article/10.1007/s12532-023-00235-7
https://dlib.phenikaa-uni.edu.vn/handle/PNK/7520
_version_ 1762365498377371648
score 8.881002

Similar Items