Problème de bin packing

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 ${\displaystyle a_{1},\dots ,a_{n}}$, des réels positifs tous non nuls, trouver ${\displaystyle k\in \mathbb {N^{*}} }$et une fonction d'assignation ${\displaystyle f:\{1,\dots ,n\}\mapsto \{1,\dots ,k\}}$tels que:

${\displaystyle \forall j\in \{1,\dots ,k\},\,\sum \limits _{i\in f^{-1}(\{j\})}a_{i}\leq 1}$ (la somme des tailles des objets de chaque bin n'excède pas sa capacité), de façon que ${\displaystyle k}$ 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 ${\displaystyle k=1}$: en introduisant la relation d'équivalence entre deux solutions non nécessairement optimales:

${\displaystyle (k_{1},f_{1})\sim (k_{2},f_{2})\Leftrightarrow k_{1}=k_{2}=k\ et\ \exists \sigma \in {\mathfrak {S}}_{k}\vert f_{1}=\sigma \circ f_{2}}$, 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 ${\displaystyle \leqslant 1}$, il y a une solution non optimale triviale: ${\displaystyle (n,f:i\in \{1,\dots ,n\}\mapsto i)}$, donc une solution minimale existe.

Il existe une version plus itérative et propre à la programmation :

• un nombre infini de boîtes de taille ${\displaystyle C}$ ;
• une liste ${\displaystyle 1,2,\ldots ,n}$ d'articles ${\displaystyle i}$ de taille ${\displaystyle 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 à ${\displaystyle C}$.

Pour décrire une solution, on peut utiliser un codage binaire pour indiquer dans quelle boîte ${\displaystyle j}$ chaque objet ${\displaystyle i}$ est rangé.

• La variable ${\displaystyle x_{ij}}$ vaudra ${\displaystyle 1}$ si l'article ${\displaystyle i}$ est rangé dans la boîte ${\displaystyle j}$, et ${\displaystyle 0}$ sinon.
• La variable binaire ${\displaystyle y_{j}}$ est égale à ${\displaystyle 1}$ si la boîte ${\displaystyle j}$ est utilisée, ${\displaystyle 0}$ sinon.

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

${\displaystyle min\sum _{j=1}^{\infty }y_{j}}$

Sous les contraintes suivantes :

${\displaystyle \sum _{i=1}^{\infty }c_{i}x_{ij}\leq Cy_{j},j=1,\ldots ,n}$

${\displaystyle \sum _{j=1}^{\infty }x_{ij}=1,i=1,\ldots ,n}$

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

${\displaystyle 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. À noter que la partie droite de l'inégalité oblige ${\displaystyle y_{j}}$ à prendre la valeur ${\displaystyle 1}$ dès qu'un article est rangé dans la boîte ${\displaystyle 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-Wolfe (en).

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].

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 ${\displaystyle L}$ est la valeur de la solution de ce modèle en nombres réels et ${\displaystyle OPT}$ la valeur de la solution en nombres entiers, alors on aurait ${\displaystyle \lceil L\rceil +1\geq OPT}$.