API choco solver

Version imprimable

13/07/2012, 10h02
devhercule

API choco solver

Bonjour,

J'utilise le solveur de contraintes Choco, et j'ai un problème à résoudre

étant donné un tableau T de n entiers, retourner toutes les combinaisons possibles dont la sommes des entiers retournées est egale à X

exemple:

tab=[5 3 8 13 1 2 9 4], X=13
les solutions possibles sont :
• 13
• 8+5
• 9+4
• 8+3+2
• Etc…

et c'est en utilisant Choco, j'ai commencer à y reflechir mais je suis bloqué mnt, voici un bout du code qui fonctionne pas mais qui pourrait aider.

Model m = new CPModel();

int [] T = {.....};

IntegerVariable[] vars = new IntegerVariable[5];

for (int i = 0; i < 5; i++)
vars[i] = Choco.makeIntVar("p" + i, l'ensemble de valeur de T);

m.addConstraint(Choco.leq(Choco.sum(vars), 13));

Merci d'avance pour votre aide

Citation:

et c'est en utilisant Choco, j'ai commencer à y reflechir mais je suis bloqué mnt, voici un bout du code qui fonctionne pas mais qui pourrait aider.

Et donc la question est ?

(ton code la n'est pas vraiment complet non plus)

A tout fin utile, voici un exemple qui résouds le problème (mais qui a mon avis ne respecte pas tout ce qu'il devrait....)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
	int solution = 13;
		int[] varsM = new int[] {5, 3, 8, 13, 1, 2, 9, 4};
 
		for (int k = 1; k < varsM.length; k++)
		{
			System.err.println("Nombre de termes : "+k);
			Model m = new CPModel();
			Solver s = new CPSolver();
 
			IntegerVariable[] vars = Choco.makeIntVarArray("Vars", k, varsM);
			m.addConstraint(Choco.allDifferent(vars));
			m.addConstraint(Choco.eq(solution, Choco.sum(vars)));
 
			s.read(m);
			s.solve();
			if (s.isFeasible())
			{
				int cpt =1;
				do
				{
					System.out.print((cpt++)+ " - "+ solution+" = " + s.getVar(vars[0]).getVal());
					for (int i = 1; i < vars.length; i++)
					{
						System.out.print(" + " + s.getVar(vars[i]).getVal());
					}
					System.out.println();
				}
				while (s.nextSolution()!=false);
			} else
				System.err.println("Impossible");
		}

13/07/2012, 11h52
devhercule

Merci comme meme :)

c'est pas exactement ce que je cherche, mais ça peut etre une bonne piste.

j'ai pensé à ajouter le 0 dans le tableau, et ca marche mieux en donnant toutes les combinaisons possibles. puisque il trouve 0 :
int[] varsM = new int[] {5, 3, 8, 13, 1, 2, 9, 4, 0};

Pour améliorer le résultat est ce que tu peux m'aider pour assurer ces deux contraintes:

1) un entier ne doit figurer ds la solution qu’une seule fois au max (sauf le zero bien sur, il peut se repeter) -normallement alldifferent-
2) l'ordre des entiers n'intervient pas ds la solution : exp: 4=1,0,0,3 et 4= 1,3,0,0 et 4=0,0,3,1 ... représentent la même solution.

Merci bcp pour votre aide, c tré gentl
13/07/2012, 11h55
wax78

Pour le point

1) oui Alldifferent semble fonctionner (comme tu px le voir dans mon code que j'ai reposté 1 minutes avant que tu écrives), mis a part pour l'histoire du 0 (entre nous ca ne sert a rien d'avoir le 0 mais bon admettons)
2) aucune idée je ne suis pas dutout specialiste de choco, jme suis juste amusé avec quelques fois pour résoudre des petits truc du genre du tiens.
13/07/2012, 12h12
devhercule

Nickel :)

Je suis d'accord avec toi pa rapport au truc de l'ajout de 0. c'était util avant ta modification.

ca resoud le premier problème et ça donne les résultats souhaités, merciiiiii

Il ne me reste que l'ordre des termes retournés pour chaque solutions, ca peut etre resolu en imposant que l'indice des entiers retournés soit croissant.

si tu peux introduir cette nouvelle contrainte ds le code je serais très reconnaissant, sinon merciiiiiiiiii bcp :)
13/07/2012, 15h45
wax78

Je pense que tu abuses un peu la, je ne suis pas non plus la pour faire ton travail ;)

Un indice : increasingSum devrait faire toutes les contraintes d'un coup.

Edit : A essayer, car ca fonctionne, mais apres 3 termes ca ne boucle dans le vide donc je me pose des question aussi mtn :)
13/07/2012, 15h52
devhercule

si j'avais la solution j'aurais pas demandé l'aide, je suis pas expert du domaine donc il vaut mieux demander les connaisseurs et c ce que je fais ;)

merciiii je vais essayer ca

Sauf que j'y connais rien, je lis la doc ^^.

Je poste quand meme le code mais je dis !WARNING! car je ne suis vraiment pas sure de mon coup au vu des resultats :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int solution = 13;
		int[] varsM = new int[] {5, 3, 8, 13, 1, 2, 9, 4};
		IntegerVariable sum = Choco.makeIntVar("s", 13, 13);
 
		for (int k = 1; k < varsM.length; k++)
		{
			System.err.println("Nombre de termes : "+k);
			Model m = new CPModel();
			Solver s = new CPSolver();
 
			IntegerVariable[] vars = Choco.makeIntVarArray("Vars", k, varsM);
			//		m.addConstraint(Choco.allDifferent(vars));
			//m.addConstraint(Choco.eq(solution, Choco.sum(vars)));
 
			m.addConstraint(Choco.increasingSum(vars, sum));
 
			s.read(m);
			s.solve();
			if (s.isFeasible())
			{
				int cpt =1;
				do
				{
					System.err.print((cpt++)+ " - "+ solution+" = " + s.getVar(vars[0]).getVal());
					for (int i = 1; i < vars.length; i++)
						System.err.print(" + " + s.getVar(vars[i]).getVal());
					System.err.println();
				}
				while (s.nextSolution()!=false);
			} else
				System.err.println("Impossible");
		}

et une autre avec une la fonction increasingNValue

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public static void main(String args[])
	{
		int solution = 13;
		int[] varsM = new int[] {5, 3, 8, 13, 1, 2, 9, 4};
		IntegerVariable sum = Choco.makeIntVar("s", 1, 7);
 
		for (int k = 1; k < varsM.length; k++)
		{
			System.err.println("Nombre de termes : "+k);
			Model m = new CPModel();
			Solver s = new CPSolver();
 
			IntegerVariable[] vars = Choco.makeIntVarArray("Vars", k, varsM);
			m.addConstraint(Choco.allDifferent(vars));
			m.addConstraint(Choco.eq(solution, Choco.sum(vars)));
			//	m.addConstraint(Choco.increasingSum(vars, sum));
			m.addConstraint(Choco.increasingNValue(sum, vars));
 
			s.read(m);
			s.solve();
			if (s.isFeasible())
			{
				int cpt =1;
				do
				{
					System.err.print((cpt++)+ " - "+ solution+" = " + s.getVar(vars[0]).getVal());
					for (int i = 1; i < vars.length; i++)
						System.err.print(" + " + s.getVar(vars[i]).getVal());
					System.err.println();
				}
				while (s.nextSolution()!=false);
			} else
				System.err.println("Impossible");
		}
	}

mais il faudrait un expert pour eclairez nos lanternes (j'aime bien choco dans le principe, dommage de ne pas mieux le maitriser)

13/07/2012, 16h03
Robin56

Citation:

Envoyé par devhercule

si j'avais la solution j'aurais pas demandé l'aide, je suis pas expert du domaine donc il vaut mieux demander les connaisseurs et c ce que je fais ;)

Il faut demander à des gens qui connaissent pour s'aiguiller ou se débloquer, pas pour faire le travail à ta place.

Et quand je lis cette phrase :

Citation:

si tu peux introduir cette nouvelle contrainte ds le code je serais très reconnaissant

Ça ressemble plus à de la demande à faire son travail qu'à des soucis techniques.
13/07/2012, 16h15
devhercule

Merci wax78
Je vais essayer ca et bon weekend ;)
16/07/2012, 16h05
devhercule

Bonjour
@ wax : j'ai repris votre code, j'avais besoin de quelques trucs et ça m'a énormément aider.
Par contre, j'ai une petite remarques
m.addConstraint(Choco.allDifferent(vars)); n'est pas la bonne solution car dans le cas ou on aura deux cases dans le tableau, il va éliminer une, or on doit les considérer différemment.

est ce qu'on peut appliquer alldifferent sur l'indice de la case recupérée et non pas sur la valeur,

i need help pls :)

thank you
19/07/2012, 16h46
fraisa1985

A mon avis, ce que vous voulez faire n'est pas faisable
essayez de reformuler votre pb ça sera plus simple