On the generation of metric TSP instances with a large integrality gap by branch-and-cut
CC BY
Lưu vào:
| Tác giả chính: | , , |
|---|---|
| Định dạng: | Sách |
| Ngôn ngữ: | English |
| Nhà xuất bản: |
Springer
2023
|
| Chủ đề: | |
| Truy cập trực tuyến: | https://link.springer.com/article/10.1007/s12532-023-00235-7 https://dlib.phenikaa-uni.edu.vn/handle/PNK/7520 |
| Từ khóa: |
Thêm từ khóa
Không có từ khóa, Hãy là người đầu tiên đánh dấu biểu ghi này!
|
| 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 |