Probleme de bin packing

Problème de bin packing

Le problème de bin packing relève de la recherche opérationnelle et de l'optimisation combinatoire. Il s'agit de trouver le rangement le plus économique possible pour un ensemble d'articles dans des 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 être appliqué à 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 dimension :

• rangement d'objets dans des boîtes, des camions, etc...(avec superposition de boîtes)

Formulation du problème

Dans le problème classique, les données sont :

• un nombre infini de boîtes de taille C
• une liste $1,2,\ldots,n$ d'articles i de taille c_i.

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 à C.

Pour décrire une solution, on peut utiliser un codage binaire pour indiquer dans quel boîte j chaque objet i est rangé.

• La variable x_ij vaudra 1 si l'article i est rangé dans la boîte j, et 0 sinon.
• La variable binaire y_j est égale à 1 si la boîte j est utilisée, 0 sinon.

On cherche donc à minimiser le nombre de boîtes utilisées

$min \sum_{j=1}^n y_j$

Sous les contraintes suivantes :

$\sum_{i=1}^{n} c_i x_{ij} \leq C y_j, j=1,\ldots,n$

$\sum_{j=1}^{n} x_{ij} = 1, i=1,\ldots,n$

$x_{i,j} \in \{0,1\}, i=1,\ldots,n, j=1,\ldots,n$

$y_j \in \{0,1\}, j=1,\ldots,n$

La première inégalité signifie qu'on ne peut dépasser la taille d'une boîte pour un rangement. A noter que la partie droite de l'inégalité oblige y_j à prendre la valeur 1 dès qu'un article est rangé dans la boîte j. 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 et Wolfe.

NP-complétude

Article détaillé : théorie de la complexité.

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 la programmation linéaire.

Méthode heuristiques

Article détaillé : heuristique.

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 + 2 boîtes.

Une version plus efficace de FFD utilise au plus 71/60 OPT + 1 boîtes. ^[3]

Méthodes exactes

On utilise aujourd'hui essentiellement la programmation 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^[4], 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 faire d'ailleurs l'objet d'une conjecture, appelée MIRUP : si L est la la valeur de la solution de ce modèle en nombres réels et OPT la valeur de la solution en nombres entiers, alors on aurait $\lceil L \rceil + 1 \geq OPT$.

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.

Voir aussi

• problème du sac à dos
• liste de problèmes NP-complets

Notes

1. ↑ L.V. Kantorovich, Mathematical methods of organizing and planning production, Management Science, 6: 363-422, 1960
2. ↑ 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.
3. ↑ Michael R. Garey and David S. Johnson, "A 71/60 theorem for bin packing", Journal of Complexity, Vol. 1, pp. 65–106, 1985.
4. ↑ P. C. Gilmore, R. E. Gomory, A linear programming approach to the cuttingstock problem (part II), Operations Research 11, 363-888, 1963.

Ce document provient de « Probl%C3%A8me de bin packing ».