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 home symbolic in V ; # start and end node, can be chosen arbitrarily
var x {A} binary ; # 1 if arc in cycle, 0 otherwise
var p {V} in 1..card(V) ; # indicates the position of a node in our sequence (path)
# objective function: minimize the total cost of arcs used
minimize TotalWeight: sum {(v,w) in A} c[v,w]*x[v,w] ;
# every node is left exactly once
s.t. OutArcs {v in V}: sum{(v,w) in A} x[v,w] = 1 ;
# every node is entered exactly once
s.t. InArcs {w in V}: sum {(v,w) in A} x[v,w] = 1 ;
# optional constraint, fixes the position number of the home node
s.t. DefHome: p[home] = 1 ;
# this is the key constraint for eliminating subtours
# it ensures that position numbers strictly increase along arcs
# However, we waive the condition for arcs entering the home node in order to allow closing
# the full Hamiltonian cycle
# unintended cycles, that do not use the home node, are prevented
s.t. Connect {(v,w) in A: w != home}:
card(V)*x[v,w] - p[w] + p[v] <= card(V) - 1 ;