/* Shortest Path Probelem: 0-1 IP version */ param N integer, > 0; /* # nodes */ param s integer, > 0; /* ID source */ param t integer, > 0; /* ID terminal */ set V := 1..N; set E within {V, V}; param w{E}; /* weight (cost) of edge */ /* decision variables */ var x{E}, binary; /* 0-1 */ /* var x{E}, >= 0, <= 1; 0-1 */ /* Objective function */ minimize z: sum{i in V} ( sum{j in V} ( w[i, j] * x[i, j] ) ); /* Constraints */ s.t. SOURCE{s}: sum{j in V: j != s} (x[s, j]) - sum{j in V: j != s} (x[j, s]) = 1; /* s.t. TERMINAL{t}: sum{j in V} (x[t, j]) - sum{j in V} (x[j, t]) = -1; */ /* redundant! */ s.t. INTERNAL{i in V: i != s && i != t}: sum{j in V: i != j} (x[i, j]) - sum{j in V: i != j} (x[j, i]) = 0; end;