-

 

 

 




Optimization Online





 

Generating subtour constraints for the TSP from pure integer solutions

Ulrich Pferschy (pferschy***at***uni-graz.at)
Rostislav Staněk (rostislav.stanek***at***uni-graz.at )

Abstract: The traveling salesman problem (TSP) is one of the most prominent combinatorial optimization problems. Given a complete graph G = (V, E) and nonnegative real edge distances d, the TSP asks for a shortest tour through all vertices with respect to the distances d. The method of choice for solving the TSP to optimality is a branch-and-bound-and-cut approach. Usually the integrality constraints are relaxed first and all separation processes to identify violated inequalities are done on fractional solutions. In our approach we try to exploit the impressive performance of current ILP-solvers and work only with integer solutions without ever interfering with fractional solutions. We stick to a very simple ILP-model and relax the subtour constraints only. The resulting problem is solved to integer optimality, violated constraints (which are trivial to find) are added and the process is repeated until a feasible solution is found. In order to speed up the algorithm we pursue several attempts to find as many relevant subtours as possible, without adding too many irrelevant subtour constraints. These attempts are mainly based on the clustering of vertices with additional insights gained from empirical observations and random graph theory. Computational results are performed on test instances taken from the TSPLIB95 and on random Euclidean graphs.

Keywords: traveling salesman problem, subtour constraint, ILP solver

Category 1: Combinatorial Optimization

Category 2: Integer Programming

Citation:

Download: [PDF]

Entry Submitted: 02/27/2014
Entry Accepted: 02/28/2014
Entry Last Modified: 08/28/2015

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society