Discussion :

[Patriarch24]

Bonjour à tous !
Voici mon problème : je dispose d'un ensemble fini d'éléments entiers non nuls. Je souhaite partitionner cet ensemble en p partitions (p variable) tel que la somme des éléments de toutes les partitions sont égales, à plus ou moins n% (n variable). On s'autorise à ne pas utiliser tous les éléments de l'ensemble initial (on parle de rejet). L'objectif est de maximiser la somme des partitions, et de diminuer les rejets.

Ex :
ensemble initial = {5,5,7,8,9,10,1,2,2} ; p = 2, n = 5%
partitions = {8,2,7,2,5}, {5,10,9,1} ; déchet = {}

autre Ex :
ensemble initial = {35,11,5,6} ; p = 2, n = 5%
partitions = {11}, {6,5} ; déchet = {35}

J'ai bien commencé à chercher, mais je n'arrive pas à trouver un algorithme correct. Quelques pistes seraient les bienvenues (ps : je ne demande pas de preuve pour l'algo ).

[pseudocode]

A première vue, ca ne m'a pas l'air évident comme problème.

Les tailles des ensembles et les valeurs p, n sont de quel ordre ?

Parce que si c'est assez petit, on peut faire une exploration totale des possibilités ( = (p+1)^taille(Ensemble) )

Code java :

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
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
public static void main(String[] args) {
	int[] E = {5,5,7,8,9,10,1,2,2};
	int p = 2;
	double n=0.05;
 
	// meilleur résultat trouvé
	int bestsum=0, bestreject=E.length;
 
	// table d'assignation d'un élément aux Sets
	int[] assign = new int[E.length];
 
	// somme des Sets
	int[] sum = new int[p];
 
	while(true) {
 
		// nouvelle assignation des elements aux Sets (= compteur en base p+1)
		int k=0;
		while( k<E.length && assign[k]==p  ) assign[k++]=0;
		if (k>=E.length) break;
		assign[k]++;
 
		// calcul la somme dans chaque Set
		int rejectcount=0;
		for(int i=0;i<p;i++) sum[i]=0;
		for(int i=0;i<E.length;i++)
			if (assign[i]<p) sum[assign[i]]+=E[i];
			else rejectcount++;
 
		// Test de la tolerance sur les sommes 
		double min=sum[0], max=min;
		for(int i=1;i<p;i++) {
			if (sum[i]<min) min=sum[i];
			if (sum[i]>max) max=sum[i];
		}
		double tolerance = (max!=0) ? (max-min)/max : 0;
		if (tolerance>n) continue;
 
		// Conserve le meilleur résultat
		if (rejectcount>bestreject) continue;
		if (min<bestsum) continue;
		if (rejectcount==bestreject && min==bestsum) continue;
 
		// On a un nouveau gagnant
		bestreject=rejectcount;
		bestsum = (int)min;
 
		// affichage
		print(E,p,assign,sum);
	}
}
 
public static void print(int[] E, int p, int[] assign, int[] sum) {
	List[] Sets = new List[p];
	for(int i=0;i<p;i++) Sets[i] = new ArrayList();
	List Reject = new ArrayList();
	for(int i=0;i<E.length;i++)
		if (assign[i]<p) Sets[assign[i]].add(E[i]); else Reject.add(E[i]);
 
	for(int i=0;i<p;i++)
		System.out.printf("%s=%s , ", Arrays.toString(Sets[i].toArray()), sum[i]);
	System.out.printf("rejet=%s\n",Arrays.toString(Reject.toArray()));
}

Résultat du programme:

[9, 10, 1, 2, 2]=24 , [5, 5, 7, 8]=25 , rejet=[]

[JeitEmgie]

l'exploration de toutes les possibilités explose hélas très vite :

pour E = {5,5,7,8,9,10,1,2,2}

Code :

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

1
2
3
4
5
6
7
 
time java Partition
[9, 10, 1, 2, 2]=24 , [5, 5, 7, 8]=25 , rejet=[]
 
real	0m0.163s
user	0m0.115s
sys	0m0.033s

pour E = {5,5,7,8,9,10,1,2,2,5,5,7,8,9,10,1,2,2}

Code :

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

1
2
3
4
5
6
7
8
 
time java Partition
[1, 5, 5, 7, 8, 9, 10, 1, 2, 2]=50 , [5, 5, 7, 8, 9, 10, 2, 2]=48 , rejet=[]
[5, 5, 7, 8, 9, 10, 1, 2, 2]=49 , [5, 5, 7, 8, 9, 10, 1, 2, 2]=49 , rejet=[]
 
real	1m4.928s
user	1m4.876s
sys	0m0.045s

peut-être une stratégie visant à augmenter une solution petit à petit :

trier E
P bags vides : Bag[1..P]

prendre les P plus grands éléments de E
et en ajouter 1 à chaque bag en les distribuant par ordre croissant de Somme(Bag[i])
autrement dit mettre le plus grand dans le bag le moins "lourd" (rééquilibrage)
(et au premier tour, les bags sont vides…)

si il existe un Bag i telle que la somme des éléments restant de E + S(Bi) < max(S(Bi)) :
solution impossible : backtrack en enlevant le plus grand élément parmi ceux que l'on vient de placer
(autrement dit si le bag le plus léger ne peut pas rattraper le plus lourd en mettant ce qui reste : pas de solution)

s'il ne reste plus d'éléments de E à placer : condition de fin
vérifier la plus grande différence des S(Bi) par rapport à la tolérance
soit on a une solution soit il faut revenir en arrière en éliminant le plus grand élément placé à la dernière étape

sinon E étant maintenant E \ {les P éléments qu'on vient de placer} on "itère" à nouveau

si E contient des entiers négatifs il faudra modifier le test de la solution impossible,
car il faut examiner la possibilité de ré-équilibrage en donnant du "négatif" au bag trop chargé

[pseudocode]

l'exploration de toutes les possibilités explose hélas très vite

Oui, ca explose très vite. D'où ma question sur le dimensionnement du problème.

Il faut dire aussi que j'ai codé ca rapidement, donc on peut sans doute optimiser deux ou trois choses.

peut-être une stratégie visant à augmenter une solution petit à petit

Je ne sais pas si on peut trouver une heuristique qui nous garantisse de trouver la (une) solution optimale. Mais ca mérite d'y réfléchir.

[JeitEmgie]

Oui, ca explose très vite. D'où ma question sur le dimensionnement du problème.

vu la vitesse à laquelle cela explose… on risque d'être à plus d'une heure pour quelques dizaines d'entiers dans E…

Il faut dire aussi que j'ai codé ca rapidement, donc on peut sans doute optimiser deux ou trois choses.

un test pour détecter vite qu'on ne peut plus rien trouver… sans doute en travaillant sur un E trié pour le faciliter…

Je ne sais pas si on peut trouver une heuristique qui nous garantisse de trouver la (une) solution optimale. Mais ca mérite d'y réfléchir.

un premier essai incomplet (ne s'occupe pas de la précision…) de ce que j'expliquais plus haut fonctionne…
mais pour trouver la solution "optimale" (ou toutes les solutions) çà va consommer pas mal de mémoire sur de grands E… (pour le backtracking…) on risque donc d'avoir un autre genre d'explosion…

[10_GOTO_10]

C'est une variante du problème du sac à dos: pour un nombre p de partitions, il s'agit de trouver le meilleur remplissage de la partition de taille = somme totale / p (le sac à dos). Déjà là, c'est un problème NP complet. Et en plus, il faut réitérer pour les nombres restants, puis pour tous les p possibles (ou du moins les plus probables). Bon courage.

[AlGo66]

peut-être une stratégie visant à augmenter une solution petit à petit :

trier E
P bags vides : Bag[1..P]

prendre les P plus grands éléments de E
et en ajouter 1 à chaque bag en les distribuant par ordre croissant de Somme(Bag[i])
autrement dit mettre le plus grand dans le bag le moins "lourd" (rééquilibrage)
(et au premier tour, les bags sont vides…)

si il existe un Bag i telle que la somme des éléments restant de E + S(Bi) < max(S(Bi)) :
solution impossible : backtrack en enlevant le plus grand élément parmi ceux que l'on vient de placer
(autrement dit si le bag le plus léger ne peut pas rattraper le plus lourd en mettant ce qui reste : pas de solution)

s'il ne reste plus d'éléments de E à placer : condition de fin
vérifier la plus grande différence des S(Bi) par rapport à la tolérance
soit on a une solution soit il faut revenir en arrière en éliminant le plus grand élément placé à la dernière étape

sinon E étant maintenant E \ {les P éléments qu'on vient de placer} on "itère" à nouveau

si E contient des entiers négatifs il faudra modifier le test de la solution impossible,
car il faut examiner la possibilité de ré-équilibrage en donnant du "négatif" au bag trop chargé

J'ai un problème similaire, je dois répartir 24 entiers en 6 groupes de 4 éléments, la somme de chaque groupe devant être le plus proche possible.

Je cherche la "meilleure" solution mais les (environ)10 meilleurs solutions m'intéressent. En effet la valeur des éléments résultant d'une fonction d'évaluation contenant plus de 10 paramètres, cette fonction d'évaluation comporte une part de subjectivité. En ce sens je ne peux pas affirmer que l'élément 1192 est toujours meilleur que le 1191, par contre il est clair que 1897 est de l'ordre de 3 fois meilleur que 622.

Mon but est de proposer a des utilisateurs des lots de groupes équilibrés et qu'ils choisissent celui qui leur convient le mieux en fonction d'autres paramètres personnels et subjectifs. Pour l'instant ma meilleur solution donne un écart de 72.

E= {1897, 1605, 1427, 1422, 1399, 1374, 1308, 1192, 1191, 1146, 1125, 1037, 1032, 1024, 982, 901, 875, 784, 770, 769, 749, 659, 622, 541 }

Je code en Java avec Eclipse. en suivant la méthode gloutonne de JeitEmgie, j'obtiens à la première itération:

Code :

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

1
2
3
4
5
6
1897	1605	1427	1422	1399	1374
1037	1125	1146	1191	1192	1308
784	875	1032	982	1024	901
541	659	749	769	622	770
somme des groupes:				
4259	4264	4354	4364	4237	4353  écart max 127

Après, je ne comprends pas très bien la phrase :

soit on a une solution soit il faut revenir en arrière en éliminant le plus grand élément placé à la dernière étape

dois je revenir au rang 3, enlever l'élément 1032, et recommencer à remplir les sacs avec 1024.

Quid de 1032, dois je le replacer en toute fin de la liste des éléments restants, ou bien après avoir rempli le rang 3, dois je le replacer en tête de liste.

D'une manière générale faut il faire les différents tests après le placement de chaque élément ou après avoir placer un nombre d'élément identique dans chaque bag.

Je me demande si l'algorithme glouton marche bien avec mon jeu de donnée, compte tenu du faible nombre d'éléments par rapport à la différence de valeur entre les éléments. Je suis en train d'étudier l'algorithme de différenciation de Karmarkar-Karp pour voir si j'obtiens de meilleur résultat.