Présentation

Le problème du rangement de boîtes (bin packing) est un des classiques de l'optimisation combinatoire. Dans ce problème, on veut ranger un ensemble de boîtes, de volumes variés, dans des conteneurs ayant tous le même volume.

On se propose d'étudier diverses propriétés du rangement optimal. L'obtention d'un tel rangement optimal constitue un problème NP-complet.

On analyse ensuite diverses stratégies (ou heuristiques) donnant un résultat pas trop éloigné de l'optimum: rangement séquentiel, puis stratégie first fit. Le cas où cette dernière stratégie est appliquée à une entrée décroissante fait l'objet d'une étude particulière.

Les premières parties s'inspirent d'un sujet de l'option Mathématiques de l'Informatique de l'Agrégation de Mathématiques (session de 1987). Plusieurs questions complémentaires proviennent des manuels d'informatique de Sara Baase et d'Udi Manber (publiés tous deux par Addison-Wesley).

Ce texte a été soumis à la sagacité des étudiants le mardi 25 janvier 2000.