Discussion :

[Sylentheal]

Bonjour,

Après avoir passé plusieurs jours sur ce problème (sans succès :'( ), je viens vous poser la question :
Etant donnés n pierres précieuses (v,b) (de valeur v et se trouvant dans une boite b), comment les répartir en m lots de valeur totale V.
Certaines pierres sont des diamants, il ne peut y avoir qu'un diamant par lot au maximum. Une contrainte supplémentaire est que le nombre de boite d'origine d'un même lot doit rester inférieur à B.

J'ai commencé en rangeant les pierres dans un ordre décroissant de valeur, et en les répartissant dans les lots en respectant les différentes contraintes.
Résultat : on obtient des lots incomplets
J'ai ensuite essayé en donnant les diamant, puis en remplissant chaque lot un par un, pour un même résultat.

En fouillant sur le net, j'ai remarqué que ce problème ressemble au problème du sac à dos, et qu'une programmation dynamique permettrait de le résoudre en temps pseudo-polynomial.
Le hic, c'est que je n'y connais pas grand chose en programmation dynamique et que je ne sais pas par où commencer

Merci d'avance pour votre aide,

--
Syl

[lautrec1]

Bonjour,

Etant donnés n pierres précieuses (v,b) (de valeur v et se trouvant dans une boite b), comment les répartir en m lots de valeur totale V.
Certaines pierres sont des diamants, il ne peut y avoir qu'un diamant par lot au maximum. Une contrainte supplémentaire est que le nombre de boite d'origine d'un même lot doit rester inférieur à B.

En fouillant sur le net, j'ai remarqué que ce problème ressemble au problème du sac à dos

Je suppose que V et B sont donnés.

Il y a beaucoup plus de contraintes que pour le problème du knapsack, qui consiste à déterminer les objets devant se trouve dans LE lot, sous contrainte que la somme de leur taille est inférieure (ET PAS EGALE! inférieure!) à la taille du sac. Par exemple, la valeur totale des différents lots est une constante prédéfinie.
Contrairement au knapsack, les contraintes donc se présentent ici sous forme d'égalité, et pas d'inégalités. Trouver une solution réalisable sera déjà un challenge, avant de trouver LA solution optimale. De plus, il n'y a rien à "optimiser", pas de fonction objectif. Le problème est B ici.

Pour formaliser :

i=1...n pierres avec v(i) sa valeur, b(i) sa boite d'origine, d(i) valant 1 si c'est un diamant, 0 sinon. (on peut ajouter un indice virtuel j qui ne change rien)
j=1...m lots
x(i,j) vaut 1 si la pierre i va dans le lot j, 0 sinon.


pour tout j : somme(i=1..n) v(i,j)x(i,j) = V
pour tout j : somme(i=1..n) d(i,j)x(i,j) = 1
pour tout j : somme(i=1..n) x(i,j) <= B
-> tu peux créer une fonction objectif max MB-somme(j=1..m)somme(i=1..n) x(i,j) en gardant les deux premières contraintes, et prier pour avoir un résultat positif.

--> Tu peux transformer ces contraintes pour avoir un membre de droite égal à 1. Tu aurais un "assignment problem" solvable avec l'algo dit hongrois (cfr wiki).

Ensuite, si malheureusement tu tombes sur une solution par réalisable pour la 3è condition, tu ajoutes une contrainte.

Si c'est dans un contexte pro, des logiciels comme AMPL ou XPRES pourront résoudre ça en entrant la première formulation (avec une fonction objectif quelconque..) avec l'option branch-and-cut.

Bien à toi et bon courage !

[dourouc05]

Pour ajouter quelques détails à la réponse de lautrec, il serait probablement plus simple de ne pas coder un algorithme spécifique pour ton problème, mais bien d'utiliser un formalisme existant (comme la programmation en nombres entiers proposée par lautrec, voire la programmation par contraintes si tu préfères).

Niveau logiciel, pour la résolution du problème, tu peux regarder SCIP et ZIMPL, parmi les meilleurs dans le domaine du gratuit et libre (http://scip.zib.de/ et http://zimpl.zib.de/). ZIMPL est un dérivé libre d'AMPL, tandis que SCIP remplace Xpress. Tu peux aussi regarder GLPK https://www.gnu.org/software/glpk/, qui a une licence différemment permissive et nettement plus lent d'ailleurs que SCIP (il fut inclus sur la comparaison de la page d'accueil de SCIP jusque récemment, mais finissait toujours bon dernier, aux alentours de cinq fois plus lent que SCIP).

[Sylentheal]

Merci beaucoup pour vos réponses

Je n'ai pas trop le temps de regarder pour l'instant, mais je le fais asap !

Je vous tiens au courant,

Syl