Discussion :

[lepatantpato]

Bonjour tout le monde

Voici un problème que je sais résoudre par analyse de toutes les combinaisons, mais qui peut prendre beaucoup de temps selon la quantité de données ...
je chercher un algo capable de l'améliorer. Le problème est le suivant:
J'ai 4 produits A B C et D.
J'ai 5 articles 1 2 3 4 et 5, utilisant, avec quantité fournie, 1 ou 2 ou 3 ou 4 produits.
Tous les articles doivent être traités.
Je cherche à utiliser, pour les 5 articles, le moins de produits possibles, sachant que la totalité de chaque produit ne peut dépasser 5.
Exemple :


un bon résultat serait :


Si on regarde les colonnes B et C, toutes les contraintes sont respectées :
- à la fois tous les articles (les lignes) sont traités,
- le total de chaque colonne est <=5
- un minimum de produits (ici 2, B et C) . Donc B et C sont un bon résultat.
Par contre, A C et D sont aussi un résultat, mais avec 3 produits, donc moins intéressant.
Quelqu'un aurait une piste d'algo à m'indiquer (ou à quel type de problème se rattache le mien ) ?
Merci !

[Trap D]

Une bonne solution serait de se tourner vers la programmation par contraintes, en Prolog par exemple mais il existe aussi des bibliothèques en Java

[lepatantpato]

Bonjour
Oui, je connais Prolog, j'ai bien aimé à l'époque (il y a longtemps...).
Mais bon, pour l'instant, peux tu m'en dire plus sur les bibliothèques java ?
cdt

[Trap D]

La aussi ça date un peu, j'ai un peu utilise choco, mais je ne sais pas si c'est maintenu.
Pour en revenir à Prolog, il y a un interface JPL entre Java avec SWI-Prolog qui fonctionne très bien (une fois les problèmes de CLASSPATH résolus).
[EDIT] Ca fonctionne toujours et apparemment ça a pris de l'ampleur : http://www.choco-solver.org/ [/EDIT]

[lepatantpato]

En fait , je cherche un algo pour l'adapter dans mon langage de programmation, ou bien encore une piste de recherche..
Merci !

[anapurna]

salut

en regardant sans trop réfléchir
la première étape serais de trier tes colonne du plus petit nombre d’éléments au plus grand nombre
et du score mini au sore maxi

dans ton exemple on a donc
D (1,1)
C(2,3)
B(3,4)
A(3,5)

ensuite tu vérifie que N ne peut pas appartenir aux groupe supérieur ou dans une colonne Résume qui comporte les élément que l'on sélectionne
donc pour D c'est un cas particulier ce n'est que le cas supérieur
on vois qu'il se trouve dans B on supprime D
on passe a C on vois bien qu'il a un élément qui se trouve nulle part on remplit notre colonne Résume (-,1,-,2,-)
on passe a B pareille que pour C il y a un élément qui n'est pas indiqué (3) puisque l'on supprimé la colonne D
on remplit a nouveau notre colonne Résume (1,1,1,2,2)
on passe a la colonne A tous les éléments se trouvent dans la colonne résume on peut l'effacer

au final il nous reste donc C et D voila

[tbc92]

Dans l'exemple que tu donnes, tu as 5 lignes et 5 colonnes, c'est des petits nombres, et donc un parcours de toutes les solutions est quasi instantané.

Dans la pratique, on parle de combien de lignes et combien de colonnes.

Idem, dans cet exemple, la contrainte 'Le total de chaque colonne est <=5' n'intervient pas. Dans la pratique, est-ce que cette contrainte va peser un peu, ou beaucoup ?

[Flodelarab]

Bonjour

Par contre, A C et D sont aussi un résultat, mais avec 3 produits, donc moins intéressant.

Selon quel critère est-ce moins intéressant ?

[anapurna]

salut flo

si j'ai bien tout compris il veut remplir les lignes avec le moins de colonne possible

[lepatantpato]

Bonjour
Merci à tous.

Anapurna :
je vais regarder ton algo.

tbc92
Oui, on peut avoir 15 ou 20 ou peut etre 50 lignes max et 10 colonnes max.
Mais cela fait déja beaucoup de combinaisons.
Oui; la contrainte <=5 est obligatoire (la valeur 5 peut être différente par colonne)

Flodelarab
Comme il faut respecter toutes les contraintes, le (ou les) meilleur résultat contient le moins de colonnes possibles.
Il peut exister par exemple 10 résultats, dont 3 avec 2 colonnes, 4 avec 4 colonnes etc...
Seuls les 3 avec 2 colonnes sont intéressants.

[nono_31]

Bonjour,

Je crois qu'il sera plus facile d'écrire un modèle en programmation linéaire ou par contraintes que ton propre programme.
N'importe quel outil décent sera en mesure de résoudre le problème en quelques secondes max, notamment choco en java.

[anapurna]

salut

effectivement c'est une problème d'optimisation classique
il existe surement une solution en programmation linéaire ou par contraintes
mais n'ayant pas tout les éléments en mains il est difficile de définir une solution approprié pour le sujet

les seul contraintes connue sont : Somme des colonnes <= 5
et L > 0

avec ça on va pas loin

[nono_31]

En effet, la première tâche est de décrire clairement l'énoncé du problème.

[lepatantpato]

Je réécris le problème :
Tableau du haut
Les contraintes dans la colonne Somme de chaque ligne, et le total de chaque colonne
Tableau du bas
Exemple optimal :
Seules 2 colonnes (produits) sont utilisées, et les contraintes sont respectées.




Merci !

[Trap D]

Voilà ce que donnerait ton programme en Prolog avec la bibliothèque de contraintes clpfd :

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
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
:- use_module(library(clpfd)).
:- use_module(library(lambda)).
 
/* exemple sans solution
articles([[1,1,0,0,2], [0,0,1,0,2], [0,1,0,1,0], [2,0,2,0,0],[0,0,0,0,2]]).
*/
 
/* exemple avec solution */
articles([[1,1,0,0], [0,0,1,0], [0,1,0,1], [2,0,2,0],[2,2,0,0]]).
 
 
 
solve :-
	articles(Lst_Art),
	transpose(Lst_Art, Lst_Prod),
	% on affecte à chaque produit un coefficient
	length(Lst_Prod, Len_Prod),
	length(Coef_Prod, Len_Prod),
	Coef_Prod ins 0..1,
	sum(Coef_Prod, #=, Som_Prod),
	% calcul des contraintes
	post_constraint(Lst_Art, 1, Coef_Prod, [], Mat),
	% on impose un minimum de 5 au colonnes
	numlist(1, Len_Prod, NL),
	maplist(set_colonnes(Mat), NL),
 
	labeling([min(Som_Prod)], Coef_Prod),
	writeln(Coef_Prod).
 
 
post_constraint([], _, _, Mat, Mat).
 
post_constraint([Art | T], N, Coef_Prod, Cur_Mat, Mat) :-
	foldl(\A^B^Y^Z^(C #= A*B, append(Y, [C], Z)), Art, Coef_Prod, [], New_Line),
	sum(New_Line, #>, 0),
	append(Cur_Mat, [New_Line], New_Mat),
	N1 is N+1,
	post_constraint(T, N1, Coef_Prod, New_Mat, Mat).
 
% le total des colonnes doit être inférieur à 5
set_colonnes(Mat, Num):-
	foldl(Num +\X^Y^Z^(element(Num, X, Value), Z #=Value + Y), Mat, 0, R),
	R #=< 5.

La première solution fournie est [0,1,1,0] qui veut dire que les colonnes B et C sont valides.

[lepatantpato]

Bonsoir
Merci Trap D ! Le Prolog me rappelle ma jeunesse. D'ailleurs, la solution que j'ai trouvée se base sur l'analyse par ligne/colonne et backtracking (le terme m'est resté). Mais l'inconvénient (si je puis dire) est que je programme en Windev....
Donc je tente une autre approche et j'essaie d"utiliser la programmation linéaire telle que ceci (pour la réécrire en windev)
mais c'est pas terrible (je teste avec un solveur) :

Min: 5x1 + 5x2 + 5x3 + 5 x4 ;

1x1+1x2 =1;
1x3 =1;
1x2 +1x4 =1;
2x1 +2x3 =2;
2x1+2x2 =2;

x1 >=0;
x2 >=0;
x3 >=0;
x4 >=0;


INT
x1 , x2 , x3 , x4 ;

Cela demande des compétences que je n'ai pas.... (haha); si qq pouvait m'orienter ...