/* 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;