Operations Research 2025
Abstract Submission

68. Analyzing Subtour Elimination Strategies for the Travelling Salesman Problem using Branch-and-Cut

Invited abstract in session WB-4: Network Optimization, stream Discrete and Combinatorial Optimization.

Wednesday, 10:45-12:15
Room: H6

Authors (first author is the speaker)

1. Tobias Klein
Institute for Operations Research and Information Systems, Hamburg University of Technology (TUHH)
2. Kathrin Fischer
Institute for Operations Research and Information Systems, Hamburg University of Technology (TUHH)

Abstract

The Travelling Salesman Problem (TSP) is an NP-hard optimization problem that seeks a minimum-cost Hamiltonian cycle over a set of nodes. In this work, the TSP is solved exactly by first relaxing both the integrality and subtour elimination constraints of its MILP formulation. This relaxation may result in a disconnected tour or a non-integer solution, rendering it infeasible for the TSP. To ensure feasibility, the Branch-and-Cut method is employed in this work, incorporating separation algorithms to detect violated subtour constraints. These separation algorithms are applied at every node in the branch-and-bound tree that is not yet fathomed, ensuring that the feasible region is incrementally refined until an optimal solution is achieved.
A key research gap in this process is determining the optimal number and selection strategy for violated subtour constraints to reintroduce at each iteration. The larger the number of constraints, the more restricted the solution space becomes, potentially increasing computational complexity due to the enlarged problem size, whereas a smaller number of constraints may slow down convergence. It is, therefore, crucial to optimize constraint addition for efficiency.
In this study, several strategies for adding subtour elimination constraints are implemented and evaluated using the Gurobi solver and the TSPLIB. The performance of these strategies is evaluated in terms of solution time and simplex iterations. The results obtained from this study offer insights into the effects of different strategies on the Branch-and-Cut algorithm's performance, contributing to enhanced efficiency in solving the TSP and similar routing problems.

Keywords

Status: accepted

Back to the list of papers