Abstract
M.Sc. (Computer Science)
The STSP (symmetric travelling salesman problem) involves finding the
cheapest tour through a number of cities. It is a difficult problem and until
recently algorithms for the TSP could not find the optimal tour in a
reasonable time if the number of cities exceeded 100. In 1987 Padberg and
Rinaldi published their computational experience with a new branch-and-cut
algorithm. They were able to solve problems with up to 2392 cities on a
CDC CYBER 205 supercomputer.
Padberg and Rinaldi used a standard LP (linear programming) solver in their
implementation of the branch-and-cut algorithm. The algorithm first solves
the continuous 2-matching problem (RMP2) using the LP solver. It then
repeatedly identifies constraints of the TSP which are not satisfied by the
current RMP2-solution and solve RMP2 with the identified TSP-constraints as
side constraints.
However, RMP2 is a linear programming problem with a very special
structure which we exploited in an implementation of the primal simplex
algorithm for RMP2. Our computational experience with this implementation
indicates that it is almost 400 times faster than a commercial LP solver on
problems with 200 cities.
We developed an implementation of the dual simplex algorithm which exploits
the special structure of both RMP2 and the side constraints identified in the
branch-and-cut algorithm. An existing set of side constraints for solving a
48-eity problem was used to test our implementation of the dual simplex
algorithm.
We implemented the procedure described by Padberg & Rinaldi to identify
subtour elimination side constraints (one type of side constraint) for the
48-eity problem. Our implementation of the identification procedure was then
used in conjunction with our implementation of the dual simplex algorithm.
The maximum flow problem has to be solved in the algorithm for
identification of subtour elimination constraints. We implemented the
Sleator-Tarjan algorithm for this purpose.