# From http://www.ampl.com/FAQ/tsp.mod, modified by John F. Raffensperger, 11 March 2006.
# DFJ formulation for the TSP, with all subtour breaking constraints.
param N integer > 2; # Number of nodes
set Nodes ordered := {1..N};
set Arcs := {i in Nodes, j in Nodes: i < j};

# This is *all* the subtours! Best for N <= 15 or so. Try a bigger one and JUST SEE what happens.
set S ordered := 1 .. (2**N - 1);
set Cutset {k in S} := {i in Nodes: (k div 2**(ord(i)-1)) mod 2 = 1};

param xcoord {Nodes};
param ycoord {Nodes};

# Use this definition for Euclidean models, where the data gives point coordinates.
# param length {(i,j) in Arcs} := sqrt((xcoord[i] - xcoord[j])^2 + (ycoord[i] - ycoord[j])^2);

# Use this definition for asymmetric models, where the data gives length explicitly.
param length {(i,j) in Arcs};

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

minimize Tourlength: sum {(i,j) in Arcs} length[i,j] * x[i,j];

subject to Degrees {i in Nodes}: sum {(i,j) in Arcs} x[i,j] + sum {(j,i) in Arcs} x[j,i] = 2;

# Type 1.
subject to Cutsubtours {k in S: card(Cutset[k]) >= 3 and card(Cutset[k]) <= N/2}:
	sum {(i,j) in Arcs: (i in Cutset[k]) and (j in Cutset[k])} x[i,j] <= card(Cutset[k])-1;

# Or Type 2. They do the same thing.
#subject to Cutsubtours {k in S: card(Cutset[k]) >= 3 and card(Cutset[k]) <= N/2}:
#	sum {(i,j) in Arcs: (i in Cutset[k]) and (j not in Cutset[k])} x[i,j]
#	+ sum {(i,j) in Arcs: (i not in Cutset[k]) and (j in Cutset[k])} x[i,j] >= 2;