Traveling Salesman TSP

Traveling Salesman Problem

In this example the (symmetric) Traveling Salesman Problem (TSP) is formulated using subtour elimination constraints. The amount of subtour elimination constraints is exponential, and therefore they are added using a lazy constraint callback. Lazy constraints are constraints that should be satisfied by any solution to the problem, but they are not generated upfront. The lazy constraint callback checks whether the incumbent solution found by the solver contains subtours. If yes, then subtour elimination constraints are added that forbid these subtours. If not, then the incumbent solution forms a true solution of the TSP problem, as it contains only one tour.

This example contains several euclidean TSP instances from TSPLIB at:

Keywords

Lazy constraint callback, subtour elimination constraints, GMP, network object.

Problem Type

MIP (medium - hard)

References

Applegate, D.L., R. E. Bixby, V. Chvátal, and W. J. Cook, The Traveling Salesman Problem: A Computational Study, Princeton University Press, Princeton, 2007. 

Note

The lazy constraint callback is only supported by CPLEX and Gurobi.

Download

A zip file with this example can be downloaded here.