Chapitre 18. Le problème du bin-packing

Supposons que nous ayons n objets, chacun d’une taille donnée, et des boîtes de même capacité. On veut ranger les objets dans les boîtes, en utilisant le moins de boîtes possible. Bien entendu, la taille totale des objets affectés à une boîte ne doit pas dépasser sa capacité.
Sans perte de généralité, on suppose que la capacité des boîtes est égale à 1. Alors le problème peut être formulé de la manière suivante :
Peu de problèmes d’optimisation combinatoire ont un intérêt pratique aussi évident. Par exemple, la version la plus simple du problème de découpe est équivalente au problème du bin-packing : étant donné des poutres de longueurs égales (disons 1 mètre) et des nombres a1, … , an, on veut couper en morceaux aussi peu de poutres que possible de façon à obtenir finalement des poutres de longueur a1, …, an.
Bien qu’une instance I soit une liste ordonnée de nombres qui peuvent apparaître plusieurs fois, on écrit x ∈ I pour un élément de la liste I qui est égal à x. On note |I| le nombre d’éléments de la liste I. Nous utiliserons aussi l’abréviation SUM(a1, …, an) ≔ . Cela constitue une borne inférieure évidente : l’inégalité [SUM(I)] ≤ OPT(I) est vérifiée par toute instance I.
Nous prouvons au paragraphe 18.1 que le problème du bin-packing est fortement NP-difficile et présentons quelques algorithmes d’approximation simples. Nous verrons qu’aucun algorithme ne peut atteindre un rapport de performance meilleur que (à moins que P = NP). Cependant, on peut atteindre asymptotiquement un rapport de performance arbitrairement bon : aux paragraphes 18.2 et 18.3 nous décrivons un schéma d’approximation asymptotique entièrement polynomial…