# tsp3.run
model tsp.mod;
#data germany_part.dat;
data ger_part.dat;

for {i in V, j in V : i > j} {		# distance matrix must be symmetric
  let d[i,j] := d[j,i];
}

option solver cplex;
option solver_msg 0; 			# don't print CPLEX messages
ption cplex_options "primalopt";
#option cplex_options "dualopt timing=1";


let subtours := 0;			# data structures required for the algorithm
param current >= 0, integer;
param kcs >= 0, integer;
param newsubtours default 0;
set T default V;
param termination binary default 0;

repeat while (termination = 0) {	# iterative part
  solve;				# solve the problem

  let T:=V;
  let newsubtours := 0;

  repeat until card(T)=0 {		# until there are subtours
	for {i in T} {			# take the first node not taken before
            let nextv:=i; break;}
	let subtours := subtours + 1;
	let S[subtours] := {};
 	let current := nextv;

	repeat {
	    let S[subtours] := S[subtours] union {current};
	    let current := sum{j in V} j * x[current,j];	# the sum gives j where x[current,j]==1.
	  } until (current = nextv);
	let T:=T diff S[kiskorok]; 
        let newsubtours := newsubtours +1;
 }

  if (card(S[subtours]) >= n) then {	# termination condition
    let termination := 1;
    printf "Hamilton tour: "    
  }
  else {
    printf "Subtours: "
  }

  for {j in 1..newsubtours} {
	printf "(sub)tour: (";		
	for {i in S[subtours-j+1]} {
	printf "%d -> ", i ;
	}
	printf "..\n";
  }

}
printf "travelled distance in the optimal tour: %f\n", distance;