Discussion :

[Boulette67]

Bonjour à toutes et tous,

J'espère être au bon endroit pour l'ouverture de cette discussion. Mon utilisation de CPLEX est dans un cadre scolaire et j'ai un comportement étrange, enfin pour moi il semble étrange. Mon approche est peut-être mauvaise du coup.


Mes contraintes sont les suivantes :
- la somme de chaque ligne doit avoir identique aux autres
- la somme de chaque colonne doit être différentes des autres


Le modèle :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using CP;
 
int N = 8;
range rangeN = 0..N-1;
dvar int x[rangeN][rangeN] in 0..1;
dvar int+ sumColumns[rangeN];
 
maximize 0;
subject to{
 
	forall(i in rangeN: i > 0){
		constraint1: sum(j in rangeN) x[i][j] == sum(j in rangeN) x[i-1][j];
	}
 
	forall(j2 in rangeN){
		sumColumns[j2] <= sum(i2 in rangeN) x[i2][j2];
	}
	constraint2: allDifferent(sumColumns);	
 
}

J'ai créé un execute pour mieux visualiser les résultats et je ne comprend pas pourquoi mon tableau intermédiaire sumColumns a de bonnes valeurs mais si on additionne les colonnes de x[][]

1 0 1 0 0 1 1 0 = 4
0 1 0 1 1 0 1 0 = 4
0 0 1 1 0 1 1 0 = 4
1 0 0 1 0 1 1 0 = 4
0 0 1 0 1 1 1 0 = 4
0 0 1 1 0 1 1 0 = 4
1 1 0 1 0 0 1 0 = 4
1 1 0 0 0 1 0 1 = 4

4 3 4 5 2 6 7 1 : total colonnes
4 1 3 5 2 6 7 0 : sumColumns

Si commente le premier forall() (égalité entre les sommes des lignes)
1 0 0 0 1 1 1 0 = 4
1 0 0 0 0 0 0 0 = 1
0 0 0 0 0 1 0 0 = 1
1 1 1 1 1 1 0 0 = 6
1 0 1 1 1 0 0 0 = 4
1 0 0 0 1 1 0 0 = 3
1 0 0 1 1 1 0 0 = 4
1 0 1 1 1 0 1 0 = 5

7 1 3 4 6 5 2 0 : total colonnes
7 1 3 4 6 5 2 0 : sumColumns

si commente le deuxième forall() (différence entre les sommes de toutes les colonnes) on a seulement des 0 mais parce que cette solution est valide pour cette contrainte



Pourquoi ???? Pourquoi j'ai une différence entre mon tableau intermédiaire sumColumns et la réalité ?

S'il vous est possible de me donner une piste d'explication sans me donner la solution (j'aime comprendre par moi même) cela serait super. En tout cas je remercie par avance les personnes qui prendront du temps pour me lire et peut-être m'apporter un éclaircissement.

Belle journée à tout le monde

[dourouc05]

C'est normal que tu définisses une somme comme inférieure ou égale, au lieu d'une égalité pure et simple ? sumColumns[j2] <= sum(i2 in rangeN) x[i2][j2]

[Boulette67]

Salut dourouc05,

C'est normal que tu définisses une somme comme inférieure ou égale, au lieu d'une égalité pure et simple ? sumColumns[j2] <= sum(i2 in rangeN) x[i2][j2]

J'espère ne pas m'être loupé dans le copier/coller pour faire le tableau

col0	col1	col2	col3	col4	col5	col6	col7
1	0	1	0	0	1	1	0
0	1	0	1	1	0	1	0
0	0	1	1	0	1	1	0
1	0	0	1	0	1	1	0
0	0	1	0	1	1	1	0
0	0	1	1	0	1	1	0
1	1	0	1	0	0	1	0
1	1	0	0	0	1	0	1

Alors si j'ai bien compris et vu <= permet de faire une affectation de valeur :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
 
sumColumns[0] <= sum(i2 in 0..7) x[i2][0];  // 1+0+0+1+0+0+1+1
sumColumns[1] <= sum(i2 in 0..7) x[i2][1];  // 0+1+0+0+0+0+1+1
...

Ne sachant pas comment faire la somme de chaque colonne ET valider que ces sommes sont toutes différentes entre elles je suis passé par un tableau contenant justement ces sommes et ensuite je pratique un ALLDIFFERENT() dessus

[dourouc05]

… sauf que tu ne peux pas faire de "contrainte d'affectation" (du moins, pas dans ce sens-là). Il faut penser déclaratif plutôt qu'impératif : tu ne dis jamais à CPLEX comment tu veux qu'il fasse un truc, tu lui dis les contraintes qui doivent être respectées. Ici, a priori, tu veux que sumColumns[0] ait toujours la même valeur que sum(i2 in 0..7) x[i2][0], d'où une égalité (ce que tu fais d'ailleurs pour les lignes).

[Boulette67]

Ce n'est pas tout à fait ça.
Je souhaite que sumColumns[0] soit différent de tous les autres c'est à dire sumColumns[1..7], ensuite sumColumns[1] soit différent de sumColumns[0] && sumColumns[2..7] etc...

d'où le alldifferent

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
subject to{
 
	forall(i in rangeN: i > 0){
		constraint1: sum(j in rangeN) x[i][j] == sum(j in rangeN) x[i-1][j];
	}
 
	forall(j2 in rangeN){
		sumColumns[j2] <= sum(i2 in rangeN) x[i2][j2];
	}
	constraint2: allDifferent(sumColumns);	
 
}

Je vais regarder encore, tes explications m'ont données une ou deux pistes à étudier . Je te remercie pour ton aide.

[Boulette67]

Je pense que j'ai compris le souci.
Il faut que mon tableau de sommes des colonnes se fassent en dehors du subject to pour ensuite mettre une contrainte sur ce tableau.

Le hic c'est que je ne sais pas faire ça. J'ai tenté avec int sumColumns[rangeN] = sum(j, i in rangeN) x[i][j];, dexpr, dvar etc... int sumColumns[0..7] mais j'ai tout le temps des erreurs...

[dourouc05]

Pour que tes sumColumns soient tous différents, il faut déjà que leur valeur soit en bijection avec ton tableau x, ce qui n'est pas le cas avec une inégalité comme tu l'écris. Si je prends ton modèle du début et que je le lance, j'obtiens cette solution (après une overdose de caféine le tant qu'Eclipse se charge…) :

x = [[1 0 1 0 0 1 1 0]
             [0 1 0 1 1 0 1 0]
             [0 0 1 1 0 1 1 0]
             [1 0 0 1 0 1 1 0]
             [0 0 1 0 1 1 1 0]
             [0 0 1 1 0 1 1 0]
             [1 1 0 1 0 0 1 0]
             [1 1 0 0 0 1 0 1]];
sumColumns = [4 1 3 5 2 6 7 0];

La contrainte allDifferent est bien respectée, mais les valeurs de sumColumns n'ont rien à voir avec le contenu du tableau : sur la dernière colonne, les éléments ont une somme de 1, pas 0… Au contraire, si je mets une égalité :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
using CP;
 
int N = 8;
dvar int x[0..N-1][0..N-1] in 0..1;
dvar int+ sumColumns[0..N-1];
 
subject to{
	forall(i in 1..N-1){
		sum(j in 0..N-1) x[i][j] == sum(j in 0..N-1) x[i-1][j];
	}
	forall(j2 in 0..N-1){
		sumColumns[j2] == sum(i2 in 0..N-1) x[i2][j2];
	}
	allDifferent(sumColumns);	
}

alors la solution a du sens (chaque ligne a une somme de 4) :

x = [[0 1 0 0 1 1 0 1]
             [0 1 0 0 1 1 0 1]
             [0 1 0 0 1 1 0 1]
             [0 0 0 1 1 1 0 1]
             [0 1 1 0 1 1 0 0]
             [0 0 0 1 1 1 0 1]
             [0 1 0 1 1 0 0 1]
             [0 0 1 0 1 0 1 1]];
sumColumns = [0 5 2 3 8 6 1 7];

Sinon, pour améliorer la performance de ton modèle à plus grande échelle, je pense qu'il faut réécrire ta contrainte d'égalité sur les lignes, avec une nouvelle variable sl (mais je suis plus habitué aux formulations MILP que CP…) :

[Boulette67]

J'ai réellement compris le sens de ta phrase "tu ne dis jamais à CPLEX comment tu veux qu'il fasse un truc, tu lui dis les contraintes qui doivent être respectées."
On dit que :
sumColumns[0] == sum(i2 in 0..N-1) x[i2][0];
sumColumns[1] == sum(i2 in 0..N-1) x[i2][1];
...

mais on ne peut pas lui forcer la valeur.


Mille mercis à toi, je n'aurai jamais trouvé.