Finding violated cut constraints for the STSP using a decomposition approach

Abstract

The Symmetric Travelling Salesman Problem (STSP) is to find a minimum cost Hainiltonian cycle in the weighted complete graph on n nodes. A well known relaxation (of this problem is the Subtour Elimination Problem (SEP) which provides very good lower bounds for the STSP. In this thesis, we develop a new parallel cutting plane approach for solving the SEP. In this approach, many violated cuts are found at each stage by decomposing the current solution into a set of nicely structured points, and then searching for violations in these points in parallel by using an algorithm which exploits this nice structure. Many ideas presented in this thesis could be adapted to other separation problems in combinatorial optimization. We also discuss several enhancements and heuristics which help speed up our implementation of this new parallel cutting plane framework for solving the SEP. We test our implementation and provide results that we believe demonstrate the usefulness of this new parallel algorithm for finding violated cut constraints each stage of the cutting plane process.