Abstract:
The multistage insertion formulation (MI) is a compact model for the traveling salesman problem (TSP). The MI formulation has given rise to a combinatorial object called pedigree, and a combinatorial polytope called the pedigree polytope. Previous studies have shown some characteristics of the MI formulation and the pedigree polytope. However, very limited computational experiments have been done on this formulation. In this thesis, we perform some empirical studies on the pedigree polytope and the MI formulations for the symmetric TSP (STSP), and the asymmetric TSP (ATSP). Given a solution to the LP relaxation of the MI formulation, a necessary condition for membership of the solution in the pedigree polytope can be associated with the maximum multicommodity flow in some layered network being equal to one. Using a numerical example, we illustrate a procedure for checking this necessary condition. We answer the question of the necessary condition being sufficient in the negative by providing a numerical example. We compare the performance of the LP relaxation of the MI formulation with those of various TSP formulations by solving some STSP and ATSP instances from the TSP Library (TSPLIB). We also solve some problems by Papadimitriou and Steiglitz called diamond instances. The LP relaxation of the MI formulation finds the integer solution to these diamond instances in all the cases. We find the MI formulation to perform better than other formulations in terms of solution time or LP relaxation value for both STSP and ATSP. We develop some branching rules using the structure of the MI formulation to be used in a branch and bound method, and find that compared to other formulations the MI formulation provides smaller branching trees and requires less solution time. Using the structure of pedigrees, we suggest five heuristics for the STSP. We compare their performance with some other existing TSP heuristics through solving some TSPLIB instances. We find two of these heuristics to perform better than other TSP heuristics.
