 | The ACM Journal of Experimental Algorithmics |
Volume 5, Article 6, 2000
Finding the Right Cutting Planes for the TSP
by
http://www.jea.acm.org/2000/LevineCutting/
Abstract:
Given an instance of the Traveling Salesman Problem (TSP), a
reasonable way to get a lower bound on the optimal answer is to
solve a linear programming relaxation of an integer programming
formulation of the problem. These linear programs typically have an
exponential number of constraints, but in theory they can be solved
efficiently with the ellipsoid method as long as we have an
algorithm that can take a solution and either declare it feasible or
find a violated constraint. In practice, it is often the case that
many constraints are violated, which raises the question of how to
choose among them so as to improve performance. For the simplest
TSP formulation it is possible to efficiently find all the
violated constraints, which gives us a good chance to try to answer
this question empirically. Looking at random two dimensional
Euclidean instances and the large instances from TSPLIB, we ran
experiments to evaluate several strategies for picking among the
violated constraints. We found some information about which
constraints to prefer, which resulted in modest gains, but were
unable to get large improvements in performance.
- Keywords: Combinatorial optimization, Cutting plane, Minimum cut, Traveling Salesman Problem
- CR Categories:
G.1.6 Optimization [Integer programming],
G.2.2 Graph Theory [Graph Algorithms],
G.4 Efficiency
- Sources:
- The LaTeX
version of the article;
this is a Unix file that contains the LaTeX source;
note that you must be a subscriber (institutional or individual) to access
this file.
- The Postscript
version or PDF
version of the article;
note that you must be a subscriber (institutional or individual) to access
these files.
- The HTML version
of the article;
note that you must be a subscriber (institutional or individual) to access
this file.
- The software suite accompanying the artic
le;
this is a large Unix tar file, which includes the source code, a Makefile,
and the test files used in the article; note that the source includes
the CONCORDE
software suite, which requires a license for any commercial use.
- The bibliography given in the article.
Received
|
Accepted
|
Final Revision
|
Published
|
July 11, 1999
|
|
February 16, 2000
|
January 11, 2001
|
Last updated and validated January 11, 2001, by editor@jea.acm.org