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.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:uj/uj:12450 |
| Date | 30 September 2014 |
| Creators | Leenen, Louise |
| Source Sets | South African National ETD Portal |
| Detected Language | English |
| Type | Thesis |
| Rights | University of Johannesburg |
Page generated in 0.002 seconds