Primal Cutting Plane Methods for the Traveling Salesman Problem

[摘要] Most serious attempts at solving the traveling salesman problem (TSP)are based on the dual fractional cutting plane approach, whichmoves from one lower bound to the next.This thesis describes methods for implementing a TSPsolver based on a primal cutting plane approach, which movesfrom tour to tour with non-degenerate primal simplex pivots andso-called primal cutting planes. Primal cuttingplane solution of the TSP has received scant attention in theliterature; this thesis seeks to redress this gap, and its findingsare threefold.Firstly, we develop some theory around the computation ofnon-degenerate primal simplex pivots, relevant to general primalcutting plane computation. This theory guides highly efficientimplementation choices, a sticking point in prior studies.Secondly, we engage in a practical study of several existing primal separationalgorithms for finding TSP cuts. These algorithms areall conceptually simpler, easier to implement, orasymptotically faster than their standard counterparts.Finally, this thesis may constitute the firstcomputational study of the work of Fleischer, Letchford, and Lodion polynomial-time separation of simple domino parityinequalities. We discuss exact and heuristic enhancements, including ashrinking-style heuristic which makes the algorithm more suitable forapplication on large-scale instances.The theoretical developments of this thesis are integrated into abranch-cut-price TSP solver which is used to obtain computationalresults on a variety of test instances.

[发布机构] University of Waterloo

[效力级别] traveling salesman problem

[关键词] TSP;traveling salesman problem;cutting planes;primal algorithms;integer programming