#Problème du voyageur de commerce
#Modélisation par les arêtes
#Les contraintes interdisant les sous-tours 
#correspondent à l'instance "instance_pvc.txt"

#données
param n;
param d{1..n, 1..n};

#variables
var x{1..n, 1..n} binary; 
#on ne considerera que les variables x_ij avec i<j

#fonction objectif
minimize distance : sum{i in 1..n, j in 1..n : i<j} d[i,j] * x[i,j];

#contraintes

subject to

c1: sum{i in 1..n, j in 1..n : i<j} x[i,j] = n; #on doit selectionner n arêtes

continuite{i in 1..n} : sum{j in 1..n : j>i} x[i,j] + sum{j in 1..n : j<i} x[j,i] = 2;
#chaque sommet est visité une unique fois, deux arêtes sélectionnees lui sont adjacentes

sous_tour1 : x[1,2] + x[2,3] + x[1,3] <= 2;


#lancement de la résolution
solve;

#affichages
for{i in 1..n} {
	for{j in 1..n : ((x[i,j] == 1) && (i<j))} {
		printf i;
		printf " ";
		printf j;
		printf("\n");
	}
}