set V ; # set of nodes
set A within V cross V; # set of arcs
param c {A} ; # costs (e.g. given by distances) of arcs
param s symbolic in V ; # start node
param t symbolic in V ; # end node
var x {A} binary ; # 1 if arc in path, 0 otherwise
var p {V} in 1..card(V) ; # indicates the position of a node in our sequence (path)
# p-values of nodes should increase along the path
# p-variables take integer values between 1 and card(V), which is denoted by 'in 1..card(V)'.
# objective function: minimize the total cost of arcs used
minimize TotalCost: sum {(v,w) in A} c[v,w]*x[v,w] ;
# every node is left exactly once, except for the end node
s.t. OutArcs {v in V: v != t}: sum{(v,w) in A} x[v,w] = 1 ;
# every node is entered exactly once, except for the start node
s.t. InArcs {w in V: w != s}: sum {(v,w) in A} x[v,w] = 1 ;
# no arc can enter the start node
s.t. In_s: sum {(v,s) in A} x[v,s] = 0 ;
# no arc can leave the end node
s.t. Out_t: sum {(t,w) in A} x[t,w] = 0 ;
# optional constraints, fixing the position number of s and t
s.t. End: p[t] = card(V) ;
s.t. Start: p[s] = 1 ;
# this is the key constraint for eliminating subtours
# it essentially implements the logical condition
# (x[v,w] = 1) => (p[w] >= p[v] + 1), which ensures that position numbers
# strictly increase along arcs that are part of the solution;
# this makes directed cycles impossible
s.t. Connect {(v,w) in A}:
card(V)*x[v,w] - p[w] + p[v] <= card(V) - 1 ;