Problème de bin packing
En recherche opérationnelle et en optimisation combinatoire, le bin packing est un problème algorithmique. Il s'agit de ranger des objets dans un nombre minimum de boîtes. Le problème classique se définit en une dimension, mais il existe de nombreuses variantes en deux ou trois dimensions.
Applications pratiques
Le problème de bin packing peut s'appliquer à un grand nombre de secteurs industriels ou informatiques.
Pour la version classique en une dimension :
- rangement de fichiers sur un support informatique ;
- découpe de câbles ;
- remplissage de camions ou de containers avec comme seule contrainte le poids ou le volume des articles.
Pour la version en deux dimensions :
- découpe de matière première ;
- placement de boîtes sur une palette (sans superposition de boîtes) ;
- placement dans un entrepôt (sans superposition de boîtes).
Pour la version en trois dimensions :
- rangement d'objets physiques dans des boîtes, un entrepôt, des camions, etc. (avec superposition de boîtes, de palettes, etc.).
Formulation du problème
Dans sa forme générale le Bin-Packing est un problème d'optimisation, on a une population d'objets à ranger avec des contraintes dans le moins de boîtes identiques possibles (appelées bins).
En une dimension
Formulation mathématique
Lorsqu'il n'y a qu'une dimension, il n'y a pas de problème de placement au départ, voici la formulation du problème.
Soit , des réels positifs tous non nuls, trouver et une fonction d'assignation tels que :
(la somme des tailles des objets de chaque bin n'excède pas sa capacité), de façon que soit minimal.
Ici on a opéré une normalisation de la capacité de chaque boîte pour avoir moins de variables entrant en jeu.
On peut noter qu'une solution n'est pas unique, sauf si : en introduisant la relation d'équivalence entre deux solutions non nécessairement optimales :
, qui veut dire que deux solutions sont égales à permutation des indices des bins près, on montre qu'il y a une multitude de solutions possibles, ainsi pour les rechercher, il sera utile de quotienter l'ensemble des solutions admissibles mais pas optimales par cette relation d'équivalence, afin de n'avoir qu'un représentant de chaque classe à gérer.
On remarque également que si la taille de tous les objets est , il y a une solution non optimale triviale : , donc une solution minimale existe.
Formulation itérative
Il existe une version plus itérative et propre à la programmation :
- un nombre infini de boîtes de taille ;
- une liste d'articles de taille .
On cherche à trouver le rangement valide pour tous ces articles qui minimise le nombre de boîtes utilisées. Pour qu'un rangement soit valide, la somme des tailles des articles affectés à une boîte doit être inférieure ou égale à .
Pour décrire une solution, on peut utiliser un codage binaire pour indiquer dans quelle boîte chaque objet est rangé.
- La variable vaudra si l'article est rangé dans la boîte , et sinon.
- La variable binaire est égale à si la boîte est utilisée, sinon.
On cherche donc à minimiser le nombre de boîtes utilisées
Sous les contraintes suivantes :
La première inégalité signifie qu'on ne peut dépasser la taille d'une boîte pour un rangement. À noter que la partie droite de l'inégalité oblige à prendre la valeur dès qu'un article est rangé dans la boîte . La deuxième inégalité impose à tous les objets d'être rangés dans une boîte et une seule. Toute solution pour laquelle la famille d'équations précédente est vérifiée est dite réalisable.
La modélisation décrite plus haut a été proposée par Leonid Kantorovich[1] en 1960. Il existe d'autres formulations linéaires pour ce problème, sous forme d'un problème de flot maximum dans un graphe, ou utilisant une décomposition de Dantzig-Wolfe (en).
NP-complétude
Ce problème fait partie de la classe des problèmes NP-difficiles. Sauf si P = NP, on ne peut pas le résoudre à l'aide d'un algorithme de complexité polynomiale. La preuve de ce résultat se fait par réduction à partir du problème de bipartition.
Méthodes de résolution
Le problème de bin packing a été largement étudié dans la communauté de recherche opérationnelle. Il existe des heuristiques très efficaces pour le résoudre, et une modélisation très efficace utilisant l'optimisation linéaire.
Méthode heuristiques
Pour résoudre le problème de bin packing, on utilise souvent des algorithmes simples comme first-fit decreasing (FFD) ou best-fit decreasing (BFD). Les deux méthodes fonctionnent suivant un principe similaire : on trie la liste d'articles par ordre décroissant de taille, puis on range chaque article dans l'ordre. Dans first-fit, on range l'article courant dans la première boîte qui peut le contenir. Dans best-fit, on range l'article dans la boîte la mieux remplie qui puisse le contenir. Ces algorithmes ne sont pas optimaux, mais ils permettent d'obtenir de très bons résultats en pratique.
Les algorithmes Best Fit Decreasing et First Fit Decreasing n'utilisent jamais plus de 11/9 OPT + 1 boîtes (où OPT est le nombre optimal de boîtes dans une solution optimale)[2]. La procédure de tri est la partie la plus coûteuse de l'algorithme, mais sans elle, la qualité de la méthode est beaucoup moins bonne. On obtient dans ce cas des solutions utilisant au pire 17/10 OPT[3].
Une version plus efficace de FFD utilise au plus 71/60 OPT + 1 boîtes[4].
Méthodes exactes
On utilise aujourd'hui essentiellement l'optimisation linéaire en nombres entiers pour résoudre ce problème. Lorsque l'instance traitée est de faible taille, la formulation de Kantorovich peut être utilisée. Lorsque le nombre d'articles est grand, on utilise plutôt une résolution par génération de colonnes utilisant le modèle de Gilmore et Gomory[5], ou des modèles reposant sur la résolution d'un problème de flot maximal. La grande qualité des méthodes obtenues est due à l'excellente relaxation linéaire du modèle. La qualité de cette relaxation fait d'ailleurs l'objet d'une conjecture, appelée MIRUP : si est la valeur de la solution de ce modèle en nombres réels et la valeur de la solution en nombres entiers, alors on aurait .
Extensions, généralisations
Le problème de bin packing a de fortes connexions avec le problème du sac à dos (knapsack). Ces deux problèmes sont les représentants les plus connus de ce qu'on appelle dans la communauté de recherche opérationnelle les problèmes de découpe et de conditionnement (cutting and packing).
Il existe de nombreuses extensions pour le problème de bin packing basique. On peut considérer ces articles possédant deux ou trois dimensions, interdire à certains articles d'être rangés dans la même boîte, ou autoriser l'usage de boîtes de tailles différentes. Les objets peuvent prendre des formes différentes : rectangles (pavés), cercles (sphères). Lorsque les formes ne sont pas convexes, on parlera plutôt de problème de nesting.
La version du problème où l'on ne connaît pas la liste d'objets par avance a été longuement étudiée. On parle de version on-line du problème.
Lorsque des articles de même taille apparaissent de nombreuses fois dans le problème, on parlera plutôt de problème de cutting-stock.
Notes et références
- ↑ L.V. Kantorovich, Mathematical methods of organizing and planning production, Management Science, 6: 363-422, 1960
- ↑ M. Yue, "A simple proof of the inequality FFD(L) ≤ (11/9)OPT(L) + 1, for all L, for the FFD bin-packing algorithm", Acta Mathematicae Applicatae Sinica 7, pp. 321–331, 1991.
- ↑ First Fit bin packing: A tight analysis. György Dósa, and Jiri Sgall. STACS, volume 20 of LIPIcs, page 538-549. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, (2013)
- ↑ Michael R. Garey and David S. Johnson, "A 71/60 theorem for bin packing", Journal of Complexity, Vol. 1, pp. 65–106, 1985.
- ↑ P. C. Gilmore, R. E. Gomory, A linear programming approach to the cuttingstock problem (part II), Operations Research 11, 363-888, 1963.
Articles connexes
- Empilement compact
- Problème du sac à dos
- Liste de problèmes NP-complets
v · m Empilement | |
---|---|
Empilement de cercles | |
Empilement de sphères | |
Empilement de carrés | |
Autres empilements |
|
Puzzles |
Portail de l'informatique théorique