Tight Lower Bound for the Sparse Travelling Salesman Problem

The Sparse Travelling Salesman Problem (Sparse TSP) which is a variant of the classical Travelling Salesman Problem (TSP) is the problem of finding the shortest route of the salesman when visiting cities in a region making sure that each city is visited at least once and returning home at the end. In the Sparse TSP, the distance between cities may not obey the triangle inequality; this makes the use of algorithms and formulations designed for the TSP to require modifications in order to produce near-optimal results. A lower bound for optmisation problems gives us the quality guarantee of the near-optimal solution obtained by using heuristic methods. In this paper we propose two methods of finding tight lower bound for the Sparse TSP. The first method uses the integer linear programming relaxation for the Sparse TSP and the Embedded Flow Formulation (EFF) for the Sparse TSP. The second method proposes a strategy for quickly generating some of the violated arc-cutset constraints which we call an Arc-cutset Partial Enumeration Strategy (APES).