Le problème de bin packing
Pendant un déménagement, vous remplissez un carton après l'autre en vous demandant si un ordre plus astucieux en aurait demandé moins. C'est le problème de bin packing, et il est réputé difficile : même les ordinateurs ne trouvent le plus petit nombre de boîtes pour de grandes entrées qu'au prix d'une recherche astucieuse. Pourtant, des règles simples s'en approchent étonnamment.
Le problème
On a des objets de tailles données et des boîtes qui contiennent toutes la même quantité. Il faut mettre chaque objet dans une boîte sans qu'aucune boîte ne déborde, en utilisant le moins de boîtes possible. Les tailles peuvent représenter des poids, des longueurs, des durées ou des tailles de fichiers. Cela ressemble à une énigme pour un après-midi pluvieux, mais le problème est NP-difficile : on ne connaît aucune méthode qui trouve rapidement le plus petit nombre de boîtes pour toutes les entrées.
Les règles rapides
Next Fit remplit une boîte jusqu'à ce que l'objet suivant n'y rentre plus, puis commence une nouvelle boîte et ne revient jamais en arrière. First Fit garde toutes les boîtes ouvertes et met chaque objet dans la première boîte où il reste de la place. Best Fit met chaque objet dans la boîte la plus pleine qui a encore de la place. Les trois décident immédiatement, ce qui est utile quand les objets arrivent un par un et doivent être placés tout de suite.
Trier d'abord
Les gros objets sont les plus difficiles, car ils ont besoin de beaucoup de place libre. Trier les objets du plus grand au plus petit, puis appliquer First Fit ou Best Fit, fait entrer les gros objets pendant que les boîtes sont encore vides, et les petits comblent les trous. First Fit Decreasing n'utilise jamais plus de 11/9 du nombre minimal de boîtes, plus une constante, contre 1,7 fois pour First Fit sur des objets non triés.
Un exemple
Prenons des boîtes de taille 10 et les objets 2, 3, 2, 1, 3, 4, 5, 6, 7 et 7, qui font 40 au total. First Fit met 2, 3, 2 et 1 dans la première boîte et 3 et 4 dans la deuxième, puis 5, 6, 7 et 7 ont chacun besoin de leur propre boîte : 6 boîtes. Avec les objets triés du plus grand au plus petit, First Fit Decreasing fait 7 + 3, 7 + 3, 6 + 4 et 5 + 2 + 2 + 1 : 4 boîtes pleines, ce qui égale la borne inférieure de 40 / 10 = 4.
Trouver le plus petit nombre de boîtes
Pour un petit nombre d'objets, la réponse exacte peut être trouvée par programmation dynamique sur les sous-ensembles : pour chaque ensemble d'objets, le plus petit nombre de boîtes et la dernière boîte la plus vide qui le contiennent, calculés à partir des ensembles qui ont un objet de moins. Cela demande environ 2ⁿ·n étapes pour n objets. Les instances plus grandes se résolvent par séparation et évaluation (branch and bound) ou par programmation linéaire en nombres entiers, et la borne inférieure indique à quelle distance du meilleur un rangement peut se trouver.
Où on l'utilise
Charger des camions et des conteneurs, découper des tubes ou des rouleaux de papier dans des longueurs standard avec le moins de chutes possible (le problème de découpe), placer des machines virtuelles sur des serveurs, ranger des fichiers sur des disques : ce sont tous des problèmes de bin packing. En deux et trois dimensions, avec des cartons au lieu de nombres, le problème est encore plus difficile.
Questions fréquemment posées
Quelle est la différence entre bin packing en ligne et hors ligne ?
En ligne, chaque objet doit être placé dès son arrivée, sans connaître les suivants ; Next Fit, First Fit et Best Fit fonctionnent ainsi. Hors ligne, tous les objets sont connus à l'avance, on peut donc d'abord les trier, comme le fait First Fit Decreasing.
À quel point First Fit Decreasing s'approche-t-il du meilleur ?
Il utilise au plus 11/9 du nombre minimal de boîtes plus 6/9 d'une boîte, une borne dont György Dósa a prouvé en 2007 qu'elle est exacte. Sur des entrées typiques, il est en général optimal ou à une boîte près.
Le bin packing est-il la même chose que le problème du sac à dos ?
Ils sont liés, mais différents. Le sac à dos remplit un seul sac avec les objets les plus précieux ; le bin packing met chaque objet dans le moins de sacs possible. Les solveurs exacts de bin packing fonctionnent souvent en résolvant encore et encore des problèmes proches du sac à dos.
Pourquoi l'application n'accepte-t-elle que 12 objets ?
Parce que la réponse exacte examine chaque ensemble d'objets, et 12 objets font déjà 4 096 ensembles. Les règles rapides pourraient traiter des milliers d'objets, mais pas le dessin ni la comparaison avec la réponse exacte.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Essayer le bin packing