/* TSP, Traveling Salesman Problem */

/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */

/* The Traveling Salesman Problem (TSP) is stated as follows.

   Let a directed graph G = (V, E) be given, where V = {1, ..., n} is

   a set of nodes, E <= V x V is a set of arcs. Let also each arc

   e = (i,j) be assigned a number c[i,j], which is the length of the

   arc e. The problem is to find a closed path of minimal length going

   through each node of G exactly once. */

param n, integer, >= 3;

/* number of nodes */

set V := 1..n;

/* set of nodes */

set E, within V cross V;

/* set of arcs */

param c{(i,j) in E};

/* distance from node i to node j */

var x{(i,j) in E}, binary;

/* x[i,j] = 1 means that the salesman goes from node i to node j */

minimize total: sum{(i,j) in E} c[i,j] * x[i,j];

/* the objective is to make the path length as small as possible */

s.t. leave{i in V}: sum{(i,j) in E} x[i,j] = 1;

/* the salesman leaves each node i exactly once */

s.t. enter{j in V}: sum{(i,j) in E} x[i,j] = 1;

/* the salesman enters each node j exactly once */

/* Constraints above are not sufficient to describe valid tours, so we

   need to add constraints to eliminate subtours, i.e. tours which have

   disconnected components. Although there are many known ways to do

   that, I invented yet another way. The general idea is the following.

   Let the salesman sells, say, cars, starting the travel from node 1,

   where he has n cars. If we require the salesman to sell exactly one

   car in each node, he will need to go through all nodes to satisfy

   this requirement, thus, all subtours will be eliminated. */

var y{(i,j) in E}, >= 0;

/* y[i,j] is the number of cars, which the salesman has after leaving

   node i and before entering node j; in terms of the network analysis,

   y[i,j] is a flow through arc (i,j) */

s.t. cap{(i,j) in E}: y[i,j] <= (n-1) * x[i,j];

/* if arc (i,j) does not belong to the salesman's tour, its capacity

   must be zero; it is obvious that on leaving a node, it is sufficient

   to have not more than n-1 cars */

s.t. node{i in V}:

/* node[i] is a conservation constraint for node i */

      sum{(j,i) in E} y[j,i]

      /* summary flow into node i through all ingoing arcs */

      + (if i = 1 then n)

      /* plus n cars which the salesman has at starting node */

      = /* must be equal to */

      sum{(i,j) in E} y[i,j]

      /* summary flow from node i through all outgoing arcs */

      + 1;

      /* plus one car which the salesman sells at node i */

solve;

printf "Optimal tour has length %d\n",

   sum{(i,j) in E} c[i,j] * x[i,j];

printf("From node   To node   Distance\n");

printf{(i,j) in E: x[i,j]} "      %3d       %3d   %8g\n",

   i, j, c[i,j];

data;

/* These data correspond to the symmetric instance ulysses16 from:

   Reinelt, G.: TSPLIB - A travelling salesman problem library.

   ORSA-Journal of the Computing 3 (1991) 376-84;

   http://elib.zib.de/pub/Packages/mp-testdata/tsp/tsplib */

/* The optimal solution is 6859 */

param n := 16;

param : E : c :=

    1  2   509

    1  3   501

    1  4   312

    1  5  1019

    1  6   736

    1  7   656

    1  8    60

    1  9  1039

    1 10   726

    1 11  2314

    1 12   479

    1 13   448

    1 14   479

    1 15   619

    1 16   150

    2  1   509

    2  3   126

    2  4   474

    2  5  1526

    2  6  1226

    2  7  1133

    2  8   532

    2  9  1449

    2 10  1122

    2 11  2789

    2 12   958

    2 13   941

    2 14   978

    2 15  1127

    2 16   542

    3  1   501

    3  2   126

    3  4   541

    3  5  1516

    3  6  1184

    3  7  1084

    3  8   536

    3  9  1371

    3 10  1045

    3 11  2728

    3 12   913

    3 13   904

    3 14   946

    3 15  1115

    3 16   499

    4  1   312

    4  2   474

    4  3   541

    4  5  1157

    4  6   980

    4  7   919

    4  8   271

    4  9  1333

    4 10  1029

    4 11  2553

    4 12   751

    4 13   704

    4 14   720

    4 15   783

    4 16   455

    5  1  1019

    5  2  1526

    5  3  1516

    5  4  1157

    5  6   478

    5  7   583

    5  8   996

    5  9   858

    5 10   855

    5 11  1504

    5 12   677

    5 13   651

    5 14   600

    5 15   401

    5 16  1033

    6  1   736

    6  2  1226

    6  3  1184

    6  4   980

    6  5   478

    6  7   115

    6  8   740

    6  9   470

    6 10   379

    6 11  1581

    6 12   271

    6 13   289

    6 14   261

    6 15   308

    6 16   687

    7  1   656

    7  2  1133

    7  3  1084

    7  4   919

    7  5   583

    7  6   115

    7  8   667

    7  9   455

    7 10   288

    7 11  1661

    7 12   177

    7 13   216

    7 14   207

    7 15   343

    7 16   592

    8  1    60

    8  2   532

    8  3   536

    8  4   271

    8  5   996

    8  6   740

    8  7   667

    8  9  1066

    8 10   759

    8 11  2320

    8 12   493

    8 13   454

    8 14   479

    8 15   598

    8 16   206

    9  1  1039

    9  2  1449

    9  3  1371

    9  4  1333

    9  5   858

    9  6   470

    9  7   455

    9  8  1066

    9 10   328

    9 11  1387

    9 12   591

    9 13   650

    9 14   656

    9 15   776

    9 16   933

   10  1   726

   10  2  1122

   10  3  1045

   10  4  1029

   10  5   855

   10  6   379

   10  7   288

   10  8   759

   10  9   328

   10 11  1697

   10 12   333

   10 13   400

   10 14   427

   10 15   622

   10 16   610

   11  1  2314

   11  2  2789

   11  3  2728

   11  4  2553

   11  5  1504

   11  6  1581

   11  7  1661

   11  8  2320

   11  9  1387

   11 10  1697

   11 12  1838

   11 13  1868

   11 14  1841

   11 15  1789

   11 16  2248

   12  1   479

   12  2   958

   12  3   913

   12  4   751

   12  5   677

   12  6   271

   12  7   177

   12  8   493

   12  9   591

   12 10   333

   12 11  1838

   12 13    68

   12 14   105

   12 15   336

   12 16   417

   13  1   448

   13  2   941

   13  3   904

   13  4   704

   13  5   651

   13  6   289

   13  7   216

   13  8   454

   13  9   650

   13 10   400

   13 11  1868

   13 12    68

   13 14    52

   13 15   287

   13 16   406

   14  1   479

   14  2   978

   14  3   946

   14  4   720

   14  5   600

   14  6   261

   14  7   207

   14  8   479

   14  9   656

   14 10   427

   14 11  1841

   14 12   105

   14 13    52

   14 15   237

   14 16   449

   15  1   619

   15  2  1127

   15  3  1115

   15  4   783

   15  5   401

   15  6   308

   15  7   343

   15  8   598

   15  9   776

   15 10   622

   15 11  1789

   15 12   336

   15 13   287

   15 14   237

   15 16   636

   16  1   150

   16  2   542

   16  3   499

   16  4   455

   16  5  1033

   16  6   687

   16  7   592

   16  8   206

   16  9   933

   16 10   610

   16 11  2248

   16 12   417

   16 13   406

   16 14   449

   16 15   636

;

end;