Problème d'optimisation combinatoire. Enfin je crois

Bonjour,

J’aimerais que vous m’aiguilliez sur un algo pouvant résoudre mon problème, voir de reformuler le problème plus simplement :

http://img510.imageshack.us/img510/6379/algojn2.gif

J'ai des boules de Couleurs différentes (une 20aine de couleurs possibles maxi). Pour chaque couleur, j’ai 10 boules de poids et valeurs différentes par exemple :

Code:

---

1 2 3 4 5 6

Bnoires : Valeurs : 2, 4, 6, 8, 10, 12, 14, 18, 20, 22. Poids : 1, 2, 3, 5, 7, 9, 11, 13, 15, 17. Brouges : Valeurs : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Poids : 1, 5, 10, 15, 20, 25, 30, 35, 40, 45.

---

(pour toutes les couleurs, le poids croît avec les valeurs mais ne sont pas liés par une relation).


J’ai aussi n Conteneurs de 4 emplacements (n variant de 0 à 10 maxi), et pouvant supporter un POIDS_MAX (le même pour tous les conteneurs).

Le but de l’algo serait de remplir chaque Conteneur avec 4 boules sachant que :
1) les Conteneurs disposent d’un Tas de boules distinct, et tous les tas sont identiques ;
2) un Conteneur ne peut pas avoir 2 boules d’une même couleur ;
3) on doit maximiser la somme des Valeurs de tous les Conteneurs (une fonction g permet d'évaluer la valeur d'un Conteneur) ;
4) on doit répondre au mieux à des contraintes du type : ‘il faut une Valeur cumulée de Bnoires = x’ ET ‘il faut une Valeur cumulée de Bvertes = y’ etc…


Dans un 1er temps je comptais faire :
- pour chaque Tas d’un Conteneurs :
- lister toutes les combinaisons 4 Couleurs dans l’ensemble des nbCouleurs.
- pour chaque combinaison de 4 Couleurs, lister toutes les combinaisons de Poids possible en éliminant les combinaisons ou f(Poids) > POIDS_MAX (f étant une fonction qui évalue le poids de 4 boules).

A partir de là on a pour chaque Conteneur une liste de combinaison de couleurs/poids possible. Il faudrait lister toutes les combinaisons pour les n Conteneur, maximiser la somme des valeurs des conteneurs en répondant au mieux aux contraintes du 4).


Donc je me demandais si un algo particulier (j’imagine d’optimisation combinatoire) pouvait répondre plus simplement à mon problème sans avoir à lister des combinaisons de combinaisons qui vont me donner un nombre de solution énorme à évaluer.

Je pensais à un recuit simulé mais j’ai pas envi de m’y lancer pour me rendre compte à la fin qu’il y à plus adapté, ou qu'il ne répond pas à mon problème.

Salut,
Je ne comprends pas bien la contrainte 1)

Citation:

---

Envoyé par Arpivu

1) les Conteneurs disposent d’un Tas de boules distinct, et tous les tas sont identiques ;

---

Citation:

---

Envoyé par Arpivu

Je pensais à un recuit simulé mais j’ai pas envi de m’y lancer pour me rendre compte à la fin qu’il y à plus adapté, ou qu'il ne répond pas à mon problème.

---

Le recuit peut te donner un résultat si tu parviens à définir un voisinage à une solution de ton problème. Par contre il ne te garantira jamais de tomber sur un optimum global.
Je suppose que si tu connais le recuit tu sais ce qu'est un voisinage. Si ce n'est pas le cas je peux essayer de te l'expliquer.

Bon courage

J'aurais tendance à te conseiller un algo génétique, en faisant bien attention de conserver à chaque génération les X meilleurs ainsi que les X plus mauvais individus, de sorte à éviter le piège des optimums locaux.

Ainsi, tu auras un grand ensemble de solutions testées sans trop de difficulté (à part la définition des critères de l'algo ;) )

Citation:

---

Envoyé par Arpivu

1) les Conteneurs disposent d’un Tas de boules distinct, et tous les tas sont identiques ;

---

Ils sont identiques sur quel(s) critère(s) ?

• poids total ?
• nombre de boules ?
• valeur totale ?
• autre ?

Citation:

---

Envoyé par tomtom7

Salut,
Je ne comprends pas bien la contrainte 1)

---

Si je reprends mon dessin, il y à 1 tas de boules.

Pour chaque conteneur je dispose d'un tas de boules, c à d que si j'ai 3 Conteneurs (C1, C2, C3) j'ai 3 Tas (T1, T2, T3). Pour remplir C1 je pioches des boules dans T1, ..., pour Cn je pioche dans Tn.

On à T1, T2, ..., Tn qui sont tous identiques.

Il semble donc que tu as n problèmes indépendants si on ignore la "contrainte 4", c'est-à-dire qu'on a intérêt à maximiser la valeur de chaque conteneur et que les choix faits pour un conteneur n'influent pas les choix faits pour les autres.

Je te conseillerais donc de faire une relaxation lagrangienne de cette contrainte. Ainsi, les n sous-problèmes obtenus sont très proches du problème de sac à dos et peuvent se résoudre par programmation dynamique.