TSP is a well known and well studied combinatorial optimisation problem. In this presentation we will combine the original cost matrix with the so called saving matrices in a special way, showing that the same TSP instance can be solved with different input matrices. This also opens up for finding lower bounds for the TSP problem in several new ways. These lower bounds are easy to find and are based on and comparable with bounds found by minimal spanning trees or one-trees. Further, introducing and combining the saving matrices makes it possible to obtain lower bounds for the original TSP instance by solving knap-sack problems rather. The tecniques will be illustrated by some simple examples.

Øyvind Halskau

Molde 9.10.00