Algorithme de tri : Bin Packing 1D (Sac à dos)

Version imprimable

23/06/2009, 13h34
fredschmidt

Algorithme de tri : Bin Packing 1D (Sac à dos)

Bonjour,
étant débutant en programmation, je fais actuellement un programme pour le problème du sac à dos 1D, également connu sous le nom de Bin Packing 1D, avec lequel j'ai un problème ...

Ce programme consiste a trier des valeurs (de n'importe quel type) de façon à avoir un gain de place ou de matière sur le principe du Bin Packing 1D.

Exemple:
Je dispose de données informatiques de différentes tailles que je veux mettre sur CD, j'essai donc d'optimiser la place afin d'utiliser le moins de CD possible:

Données de 500mo, 400mo , 300mo et 100mo.
Place sur CD 700mo.

Il est donc logique de placer 400 et 300 ensemble pour remplir un CD et 500 et 100 ensemble pour le second.
Dans ce cas j'utilise 2 cd, pour les autres solutions au moins 3.

Voir également http://fr.wikipedia.org/wiki/Probl%C...de_bin_packing
et http://fr.wikipedia.org/wiki/Probl%C...sac_%C3%A0_dos*.

Dans mon cas, je créé ce programme pour optimiser la découpe de barre (comme en menuiserie).

J'ai des barres standard de 2500mm et j'aimerai les découper en barres de différentes longueurs (exemple 1000, 1345, 537 ,886... dans des quantités plus importantes (>1000)) en utilisant le moins de barres standard possible.

J'utilise donc la méthode Deacrising First Fit (qui consiste a trier les longueurs dans l'ordre décroissant puis de les ranger au fur a mesure dans la 1ere barre ou il y a de la place).

En reprenant l'exemple du CD.

Dans l'ordre décroissant j'ai 500,400,300,100

CD1 je place 500.
400 ne rentre plus de CD1 (400+500>700), je créé donc un CD2 pour le placer dedans.
300 ne rentre pas dans CD1, 300 rentre dans CD2. On rajoute 300 au CD2.
100 rentre dans CD1, on le rajoute au CD1.

J'utilise également la méthode du Deacrising Best Fit qui est plus précise, mais je n'ai pas de réèl intérêt à prendre ce dernier car mon programme est utilisé pour des grandes séries de barres (plus de 1000 fois la même valeur).
Je trouve donc le même résultat qu'en Next Fit mais en un temps beaucoup plus important.

Mon problème
Mon problème est que je ne trouve pas , dans de rare cas, une solution suffisament proche de l'optimale.

Exemple: j'ai des barres standard de 2500, j'aimerai 10 barres de 1000 et 20 de 700.

L'optimale est d'avoir 10 barres standard de 2500 qu'on découpe en 1000+700+700 = 2400.

Mais en Decreasing First Fit ou Next Fit je me retrouve avec 5 barres standard découpé en 1000+1000=2000 et 6 barres standard en 700+700+700 = 2100 et 1 barre standard en 700+700=1400.

Soit un surplus de 20% (12 barres standard au lieu de 10).

Je sais que ma méthode est heuristique (permet de trouver rapidement un résultat approché de l'optimal), mais je sais également qu'il est possible d'avoir un tri plus approché dans le cas ci dessus, seulement je ne sais pas comment faire.

Je cherche donc a améliorer ma méthode de tri, mais je ne sais pas comment m'y prendre.
Pouvez vous m'aider?

Merci
23/06/2009, 15h02
cedriku

Bonjour,

tout d'abord je tiens a preciser que le probleme de bin packing 1D n'est pas le meme probleme que celui du sac a dos 1D (meme s'il existe un lien forte entre ces deux problemes)!!!
En effet, dans ton exemple, le bin packing 1D consiste a determiner le nombre minimum de CD qui puisse contenir tous tes fichiers alors que le sac a dos 1D consiste a determiner le "maximum" qui puisse rentrer dans UN CD, maximum pouvant etre le nombre de fichier ou bien la quantite occupe sur le CD ou tout autre critere d'optimisation...
C'est pas du tout le meme probleme !!!!
Si je suis ton exemple de CD, le probleme qui t'interesse c'est le bin packing 1D et non le probleme du sac a dos (tu cherches le nombre minimum de CD pouvant contenir tes fichiers et pas combien tu peux en rentrer sur un CD).

De plus, il faut noter que resoudre le probleme bin packing 1D ne revient pas a resoudre le probleme sac a dos sur chaque CD. Admettons que tu applique un sac a dos sur le 1er CD (donc tu remplit optimalement ton premier CD), jusque la pas de probleme. Ensuite, si tu applique un sac a dos sur le 2eme CD et 3eme CD, tu n'es pas certain que la repartition sur ces 3CD est optimale (en d'autres mots, il se peut qu'il y ait une solution en 2CD) alors que tu as resolu optimalement chaque CD.

Ensuite en ce qui concerne les heuristiques que tu as essaye, il est clair qu'elles ont l'avantage de trouver une solution rapidement mais suivant les tailles des fichiers, elle peuvent etre tres loin de l'optimal. Ces heuristiques datent des annees 70 si je ne me trompe pas et il y a eu entre temps des heuristiques de bien meilleur qualité. Tu peux lire les travaux de Martello, Vigo et Pisinger sur des calculs de bornes inferieures au probleme de bin packing 3D (mais elle s'adaptent egalement pour le cas 1D). Ce sont des papiers de 2000 et 1998 (il y a "Three-Dimensional Bin Packing Problem" ou "Exact Solution of the two-dimensional finite bin packing problem"). C'est assez technique mais ces bornes vont en fait t'assurer que tu ne peux trouver de solution optimale avec moins de X CD. Et ils se servent de ces bornes pour trouver le nombre de CD necessaires.

Bon courage pour la suite.
23/06/2009, 15h10
Mac LAK

Déjà, ce n'est pas un tri, mais un problème d'optimisation... :mouarf:

Pour résoudre ce genre de problèmes, tu as deux solutions qui doivent être choisies en fonction de tes besoins :
- Méthodes heuristiques,
- Méthodes exactes.

Une méthode heuristique est souvent proche de l'optimal, sans toutefois jamais garantir qu'il est atteint (sauf coup de bol, bien sûr).
Une méthode exacte te garantit qu'il n'existe aucune meilleure solution que celle trouvée, qui est donc optimale.

Avec tes algos, tu ne peux pas trouver l'optimal "tel quel", car ils sont heuristiques. On tente UN SEUL rangement, suivant une méthode donnée (pas trop débile de préférence), et on considère - à raison - que l'on approche de l'optimal : c'est résumé brutalement, mais c'est pourtant bien ça.

Comme ce genre d'algo est souvent très rapide, tu peux tenter de le dérouler suivant plusieurs fits, et prendre le meilleur possible, tout comme tu peux tenter de piocher tes valeurs de façon alternée (un coup la plus grande, un coup la plus petite). Une fois combiné, tu devrais avoir 6 à 10 méthodes heuristiques déroulées, dans laquelle une a produit un meilleur résultat que les autres.

Déjà, tu devrais certainement observer un gain par rapport à une méthode heuristique unique "figée dans le marbre", et pour un temps de calcul plutôt ridicule car le tri initial des données n'est fait qu'une seule fois. Il te faut bien sûr optimiser aussi cette partie (tri QuickSort au minimum) afin de ne pas exploser ton temps de calcul à cause de ça...

Si cela te convient, tu peux arrêter à ce stade et fournir le résultat. Tout dépend du pourcentage de pertes toléré...

En méthode exacte, on passe dans un tout autre domaine, à savoir la RO (Recherche Opérationnelle) dans toute sa splendeur. Tes données étant, finalement, relativement petites pour un PC moderne, je te conseille d'aller voir du côté de la Programmation Dynamique, sachant qu'il devrait être possible de partir de la solution heuristique (optimisée ou non) comme base de départ.

Histoire de mieux voir par où démarrer :
http://www.labri.fr/perso/robson/cours/AlgAv_TD5.html
http://www.labri.fr/perso/robson/cou...D5corrige.html

Attention toutefois : là, le temps de calcul est rarement négligeable, mais c'est le prix à payer pour trouver LA solution... Sinon, il faudra se contenter d'une solution approchée, avec un pourcentage de pertes donné.

Tu peux aussi tenter une méthode hybride : à partir de l'optimal absolu (somme des longueurs demandée, habituellement impossible à atteindre donc), tu peux raffiner le processus au fur et à mesure jusqu'à tomber sur perte réelle (pourcentage de différence entre la longueur des barres requises et la somme mathématique des longueurs utiles) qui sera tolérable, par exemple 15% de perte réelle.

Si ton heuristique trouve une solution convenable, tu t'arrêtes. Sinon, tu tentes une heuristique optimisée, et si ça foire, tu tentes une recherche exacte.

Là, on arrive aussi dans une approche pragmatique : de combien de temps disposes-tu pour donner la solution, après réception d'une commande, avant que le client ne décide d'aller voir le concurrent ? :mrgreen:

Si ton patron veut la réponse en 30 secondes maximum, à toi de lancer un max de calculs en même temps (vive les multi-cœurs...) afin de chercher une solution, et au bout du temps fatidique, tu donnes la meilleure solution trouvée, qu'elle soit optimale ou non.
Si ton patron est radin et veut absolument la solution optimale, alors pas le choix : laisse tomber les heuristiques (sauf pour servir de "point de départ"), et passe directement en méthode exacte. Préviens-le avant que ça peut prendre plusieurs heures pour avoir la réponse... Ce qui pourrait très bien n'avoir aucune importance s'il a un PC dédié à ça qui bosse la nuit pour les commandes du lendemain !!
24/06/2009, 11h22
pseudocode

Citation:

Envoyé par fredschmidt

Mon problème
Mon problème est que je ne trouve pas , dans de rare cas, une solution suffisament proche de l'optimale.

Exemple: j'ai des barres standard de 2500, j'aimerai 10 barres de 1000 et 20 de 700.

L'optimale est d'avoir 10 barres standard de 2500 qu'on découpe en 1000+700+700 = 2400.

Mais en Decreasing First Fit ou Next Fit je me retrouve avec 5 barres standard découpé en 1000+1000=2000 et 6 barres standard en 700+700+700 = 2100 et 1 barre standard en 700+700=1400.

Dans ce cas particulier, tu peux énumérer les différentes configurations de découpage possibles pour une barre:

config #1 : 2500 = 2*1000 + 0*700 + 500
config #2 : 2500 = 1*1000 + 2*700 + 100
config #3 : 2500 = 0*1000 + 3*700 + 400

Et ensuite faire une exploration de l'arbre des solutions possibles pour chaque objectif/contrainte (branch & bound), en utilisant le score (nb de barres utilisées) pour elaguer l'arbre.

10 barres de 1000 =>

5 * config #1 => manque 20 barres de 700
4 * config #1 + 2 * config #2 => manque 16 barres de 700
3 * config #1 + 4 * config #2 => manque 12 barres de 700
2 * config #1 + 6 * config #2 => manque 8 barres de 700
1 * config #1 + 8 * config #2 => manque 4 barres de 700
0 * config #1 + 10 * config #2 => manque 0 barres de 700

etc.
25/06/2009, 10h18
fredschmidt

Bonjour,
merci pour vos réponses.

J'ai choisis la méthode de pseudocode, cette dernière est la plus facile à coder et la plus rapide.

Je ne cherche pas la solution optimale, mon unique problème reste le souci du genre 1000+700+700, qui est trop éloigné de ce que je cherche.

Pour la réponse de cedriku, comme il l'a mentionné, c'est technique, et surtout un peu trop pour moi, j'ai déjà fait du Bin packing 2D en utilisant simplement les méthode Decreasing First et Next Fit en Height et Widht, mais la c'est vraiment trop technique (je manque de pratique en algo, je suis débutant et je ne fais pas d'informatique dans ma formation).
L'anglais ne me rebute pas, c'est plutôt les formules mathématiques (je ne vois pas le rapport avec l'algo).
Merci également de m'avoir corrigé (pour moi sac a dos et Bin packing étaient pareil).

Pour répondre à Mac LAK, la méthode de tester plusieurs algo me semble être une fausse bonne idée, j'y ai déjà pensé avant.
J'ai tester les first, next, best et worst fit en normal et en decreasing, et d'un algo à l'autre les résultats sont meilleur ou pire, mais aucun de ces algo me permet de résoudre l'histoire des 1000+700+700.
Pour la programmation dynamique, je laisse tomber, c'est trop compliqué pour moi, d'autant plus que les PC utilisés ne sont pas tout neuf et que le temps n'est pas à négliger.

Etant donné que j'ai toujours une quantité importante de barres de mêmes longueurs (après découpe), j'ai pensé que la meilleur solution est de vérifier toutes les solutions possibles en additionnant les longueurs de barres souhaités après découpe entre elles (en restant < 2500), puis de prendre la 1ere solution la plus proche de 2500, jusqu'à épuisement d'une des longueurs, puis de choisir la solution suivante la plus proche de 2500, et ainsi de suite, jusqu'à avoir tout découpé.

Exemple:

j'ai 5 barres de 1200, 10 de 1000 et 14 de 700.

Les solutions possible sont:
1)1200 + 1200 = 2400
2)1200+1000=2200
3)1200+700=1900
4)1000+1000=2000
5)1000+700+700=2400
6)700+700+700=2100

Dans un 1er temps, j'utilise la solution1) (1er solution la plus proche de 2500 en 1ere position), je découpe dans une barre standard 1200+1200, je fais ça 2 fois de façon à ne plus avoir assez de barre pour la solution 1.
Il me reste 1x1200

Puis je passe a la solution 5) (1ere solution la plus proche de 2500, 2eme position), je découpe 7 barres de 1000+700+700, jusqu'à épuisement des barres de 700.
Il me reste 3 barres de 1000.

Je passe à la solution 2) (2eme solution la plus proche de 2500, 1ere position).
Je découpe 1x 1200+1000.
Il me reste 2 x 1000.

Et pour finir, je passe à la solution 4) (4eme solution la plus proche, 1ere position), et je finis avec 1000+1000.

Mon problème est que je n'arrive pas a faire l'algo qui va me donner toutes les positions possibles.

Comme valeur de départ, j'ai les longueurs souhaitées, et les quantités de chaque longueurs.

Pouvez-vous m'aider?

Merci
25/06/2009, 10h41
Mac LAK

Citation:

Envoyé par fredschmidt

J'ai tester les first, next, best et worst fit en normal et en decreasing, et d'un algo à l'autre les résultats sont meilleur ou pire, mais aucun de ces algo me permet de résoudre l'histoire des 1000+700+700.

Tu as essayé en prenant alternativement la plus grande et la plus petite ? Ou la valeur "médiane" (= en milieu de tableau) ?

Dans ton cas de figure, cela se résume (une fois trié) à prendre une barre de 1000, puis une barre de 700, puis une barre de 1000, puis une de 700, etc. jusqu'à épuisement des barres de 1000 où piocher alternativement ne se "verra" plus... En fonction du "fit" utilisé, tu devrais normalement plus ou moins tomber sur l'optimal, avec plusieurs essais de différentes méthodes.

Et au moins, ça reste "générique", et sur un truc qui est déjà fait ou presque.
25/06/2009, 11h03
fredschmidt

Je ne suis pas sur de bien te suivre, j'ai l'impression que tu crois que je n'ai que 2 longueurs de barres différentes à placer, mais je peux en avoir plus que 2.

En fait , je ne vois pas ce que tu veux dire par valeur médiane.

Si je comprends bien, au lieu de d'abord trier les valeurs par ordre décroissant, je les tris par ordre décroissant par couche ( au lieu d'avoir 1200 1200 1200 1200... 1000 1000 1000 1000... 950 950 950... 750 750 750... j'ai 1200 1000 950 750 1200 1000 950 750...)? c'est ça?

Merci
25/06/2009, 11h22
Mac LAK

Non, du tout. Prenons un jeu de longueurs comme exemple :
100 150 300 400 900 1200 1200 1800 1900 2000 2200 2200

En prenant alternativement, tu vas avoir les valeurs suivantes, en prenant une fois en début de tableau, une fois en fin de tableau, en début, etc.

=> 100 2200 150 2200 300 2000 400 1900 900 1800 1200 1200

En valeur médiane, tu prends la valeur en milieu de tableau :

=> 1200 900 1200 400 1800 300 1900 150 2000 100 2200 2200

C'est plus clair ? Bien sûr, tu laisses ton tableau trié "tel quel", c'est juste ta boucle de parcours qui devient différente, pas le tri.

Citation:

Envoyé par fredschmidt

J'ai choisis la méthode de pseudocode, cette dernière est la plus facile à coder et la plus rapide.

Je ne cherche pas la solution optimale, mon unique problème reste le souci du genre 1000+700+700, qui est trop éloigné de ce que je cherche.

(...)

J'ai tester les first, next, best et worst fit en normal et en decreasing, et d'un algo à l'autre les résultats sont meilleur ou pire, mais aucun de ces algo me permet de résoudre l'histoire des 1000+700+700.

:koi: ?

Bah, mon algo fait une exploration totale donc il trouve forcément l'optimal.

Citation:

j'ai 5 barres de 1200, 10 de 1000 et 14 de 700.

Les solutions possible sont:
1)1200 + 1200 = 2400
2)1200+1000=2200
3)1200+700=1900
4)1000+1000=2000
5)1000+700+700=2400
6)700+700+700=2100

Exact. Il faut alors alors explorer les solutions qui permettent d'avoir 5 barres de 1200, et d'y ajouter celles qui permettent d'avoir 10 barres de 1000, ...

Ca donne assez vite le résultat sur mon PC : il faut 11 barres.
Code:

1 2 3 4 5 6 7 8 config #0 : 0*1200 0*1000 3*700 config #1 : 0*1200 1*1000 2*700 config #2 : 0*1200 2*1000 0*700 config #3 : 1*1200 0*1000 1*700 config #4 : 1*1200 1*1000 0*700 config #5 : 2*1200 0*1000 0*700 Target : [5, 10, 14] Solution : 7*(#1) 3*(#4) 1*(#5) = [5, 10, 14]

27/06/2009, 09h52
cedriku

Dans le cas du probleme de fredschmidt, on est d'accord que l'algo Pseudocode est plutot bien adapté et simple.

Mais je pense qu'il faut tout de meme preciser, que lister les configurations possibles revient a trouver toutes les solutions maximales d'un probleme de sac a dos 1D ce qui est deja NP-Dur.
Dans le cas du probleme de fredschmidt, il est clair que le nombre de configurations est limité pour deux raisons :

1) le nombre de taille differentes est faible (700, 1000, 1200)
2) Les tailles sont tres grandes compare a la taille maximale 2500.

Je dis ca juste pour que fredschmidt se rende compte de la complexité et que si ca marche bien dans ce cas la, ca ne sera pas forcement le cas s'il a des tailles petites par rapport a 2500 et beaucoup de tailles differentes.

Mais sinon +1 pour la solution de pseudocode lol :ccool:
27/06/2009, 13h11
pseudocode

Citation:

Envoyé par cedriku

Mais je pense qu'il faut tout de meme preciser, que lister les configurations possibles revient a trouver toutes les solutions maximales d'un probleme de sac a dos 1D ce qui est deja NP-Dur.

C'est clair que ca ne fait pas de miracle. Je n'ai pas encore réussit a transformer NP en P. :aie:

Cela dit, travailler sur les "configurations" plutot que sur les éléments découpés permet de réduire la taille des solutions a explorer. D'autant plus si on peut réduire la cible en la factorisant : Solution([500, 1000, 1400]) = 100 * Solution([5, 10, 14]) = 100*11 = 1100 barres
27/06/2009, 21h31
cedriku

Citation:

Envoyé par pseudocode

C'est clair que ca ne fait pas de miracle. Je n'ai pas encore réussit a transformer NP en P. :aie:

Ah bon ? lol. Je trouve qu'un million de dollars c'est pas assez payé pour celui qui demontrerait NP egal ou different de P !!

Citation:

Envoyé par pseudocode

Cela dit, travailler sur les "configurations" plutot que sur les éléments découpés permet de réduire la taille des solutions a explorer.

Tout a fait, il faut juste faire attention au cout de la recherche de ces configurations et au nombre de configurations !

Citation:

Envoyé par pseudocode

D'autant plus si on peut réduire la cible en la factorisant : Solution([500, 1000, 1400]) = 100 * Solution([5, 10, 14]) = 100*11 = 1100 barres

Ben la factorisation permet de "diminuer" la complexite, grosse modo au lieu d'etre exponentiel en le nombre de barre, tu deviens exponentiel en le nombre de types de barres... mais comme dans le pire des cas il y a autant de types de barres que de barres... mais sur le fond je suis entierement d'accord avec toi.

Et une telle factorisation est deja beaucoup plus difficile a mettre en oeuvre a partir de 2 dimensions ! Bon ok la c'est hors sujet. :roll:
27/07/2009, 14h45
fredschmidt

:mrgreen:
Merci pour votre aide, j'ai gardé la solution à pseudocode, et ça marche nickel en un temps relativement faible (< 1sec).

Merci:ccool:
22/01/2015, 16h35
sami_c

Bonjour,
Tu peux stp détailler l'algorithme complet ?
23/01/2015, 12h50
anapurna
salut ,

Tu n'a pas compris quoi dans l'algo proposé par pseudo code ?

sachant que tu a une longueur de barre de 2500
donc lgb = 2500
on lui commande
5 barre de 1200
10 barre de 1000
14 barre de 700
donc
Code:

1 2 3 [1200][05] [1000][10] [0700][14]
on en défini les longueur de coupe possible

Code:

[1200][1000][0700]

a partir de la on recherche toute les combinaison possible ne dépassant pas 2500
Code:

1 2 3 4 5 6 1)[1200][1200] =[2400] 2)[1200][1000] =[2200] 3)[1200][0700] =[1900] 4)[1000][1000] =[2000] 5)[1000][700][700] =[2400] 6)[700][700][700] =[2100]
bon a ce stade moi je tri par résultat max,lg max
Code:

1 2 3 4 5 6 1)[1200][1200] =[2400] 5)[1000][700][700] =[2400] 2)[1200][1000] =[2200] 6)[700][700][700] =[2100] 4)[1000][1000] =[2000] 3)[1200][0700] =[1900]
un fois que tu as fait ton trie il suffit de décrémenter tes compteur de commande
Code:

1 2 3 [1200][05] [1000][10] [0700][14]
tu vois que pour les barres de 1200 tu en as 5
la première solution te permet de débiter 2 barre
donc on a 1200*5 = (1200+1200)*2 +1200 => reste [1200][1]
à la troisième occurrence tu aurais -1 au compteur ... on reste donc a deux
on passe à la suite

l'autre solution a 2400 est => [1000][700][700]
à chaque fois que tu vas couper tu vas donc décrémenter 2 compteur le compteur de 1000 et celui de 700
à la première passe tu auras donc
[1000][9] et [0700][12]
...
en le faisant 7 fois tu arrive
[1000][3] et [0700][0]
tu n'as donc pus besoin des coupes de 700
on passe donc au choix suivant

cela tombe pas mal
c'est => [1200][1000]
on sais qu'il nous reste [1000][3] et [1200][1]
donc on peut le réaliser une fois
le résultat deviens donc
[1000][2] et [1200][0]

le choix suivant est [700][700][700] =[2100]
celui-ci ne nous intéresse pas on a plus de barre de 700 à découper
on passe au suivant
[1000][1000] =[2000]

c'est sympa c'est tout juste ce qu'il me reste à faire ;)

résultat des course on a donc
Code:

1 2 3 4 [1200][1200] = 2 [1000][700][700] = 7 [1200][1000] = 1 [1000][1000] = 1
soit au total 11 barres de 2500 la perte seras donc
de (11*2500) - ((2*2400)+(7*2400)+(1*2200)+(1*2000))

en espérant avoir été claire