tsp2.gms : Traveling Salesman Problem - Two

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:

```

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:

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;
``````
GAMS Development Corp.
GAMS Software GmbH

General Information and Sales
U.S. (+1) 202 342-0180
Europe: (+49) 221 949-9170