Description

This is the second problem in a series of traveling salesman
problems. The formulation in this model uses subtour elimination
constraints of the form

   u(i) - u(j) + n*x(i,j) <= n - 1

Additional information can be found at:

http://www.gams.com/modlib/adddocs/tsp2doc.htm

Large Model of Type : MIP

Category : GAMS Model library

Main file : tsp2.gms   includes :  br17.inc

$title Traveling Salesman Problem - Two (TSP2,SEQ=178)

$onText
This is the second problem in a series of traveling salesman
problems. The formulation in this model uses subtour elimination
constraints of the form

   u(i) - u(j) + n*x(i,j) <= n - 1

Additional information can be found at:

http://www.gams.com/modlib/adddocs/tsp2doc.htm


Kalvelagen, E, Model Building with GAMS. forthcoming

de Wetering, A V, private communication.

Keywords: mixed integer linear programming, traveling salesman problem, Miller-
          Tucker-Zemlin subtour elimination
$offText

$eolCom //

$include br17.inc

Set ij(ii,jj) 'exclude first row and column';
ij(ii,jj) = ord(ii) > 1 and ord(jj) > 1;

Variable u(ii)     'subtour elimination strategy 3';

Equation se(ii,jj) 'subtour elimination constraints';

se(ij(i,j)).. u(i) - u(j) + card(i)*x(i,j) =l= card(i) - 1;

Model tsp / objective, rowsum, colsum, se /;

* Try a small problem first - first six cities
i(ii) = ord(ii) <= 6;

option optCr = 0.05;

solve tsp min z using mip;

display x.l;

* Try a bit larger problem - 10 cities
i(ii) = ord(ii) <= 10;

option limCol = 0, limRow = 0;

solve tsp min z using mip;