# Génération de colonnes pour le Bin-Packing avec seuils

Ernest Foussard, Gérémi Bridonneau, Marie-Laure Espinouse, Grégory

Mounié, Margaux Nattaf

► To cite this version:

Ernest Foussard, Gérémi Bridonneau, Marie-Laure Espinouse, Grégory Mounié, Margaux Nattaf. Génération de colonnes pour le Bin-Packing avec seuils. ROADEF 2023 - 24ème congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Rennes School of Business, Feb 2023, Rennes, France. hal-04009192

HAL Id: hal-04009192

https://hal.science/hal-04009192

Submitted on 1 Mar 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Génération de colonnes pour le Bin-Packing avec seuils *

Ernest Foussard¹,²

Gérémi Bridonneau¹

Marie-Laure Espinouse¹

Grégory Mounié²

Margaux Nattaf¹

¹ Univ. Grenoble Alpes, CNRS, Grenoble INP, G-SCOP, 38000 Grenoble, France
{ernest.foussard,marie-laure.espinouse, margaux.nattaf}@grenoble-inp.fr

² Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France
gregory.mounie@imag.fr

**Mots-clés** : Bin-Packing, Génération de colonnes, Contrainte de seuils

**Introduction** Le Bin-Packing est un problème classique en optimisation combinatoire, dans lequel des items de poids variés doivent être regroupés dans des boîtes de capacité limitée de sorte que le nombre de boîtes utilisées est minimal. Nous proposons une extension de ce problème en introduisant une nouvelle contrainte de seuils. Chaque item possède un seuil, et les items au sein de chaque boîte doivent être ordonnés de manière à ce que la capacité restante avant de placer chaque item soit supérieure à son seuil. En tant que généralisation directe du Bin-Packing classique, ce problème est NP-difficile au sens fort.

Le problème de Bin-Packing avec seuils apparaît notamment dans un problème d'ordonnancement conjoint de la production et de la maintenance avec prise en compte de la santé des équipement [1], où les tâches de productions causent de l'usure sur l'équipement qui peut être réparé au moyen de maintenance [4, 5]. L'affectation des tâches entre deux maintenances, sous des contraintes de santé minimale de l'équipement pour l'exécution des tâches, correspond au problème de bin-packing avec seuils.

La génération de colonnes basée sur la formulation exponentielle proposée par Gilmore et Gomory (1961) [3] est l'élément central des méthodes Branch-and-Price, très performantes pour le Bin-Packing classique. Nous proposons une extension de cette méthode afin de prendre en compte la contrainte de seuil.

**Définition du problème** Le problème consiste à partitionner un ensemble d'items $\mathcal{N} = \{1, ..., n\}$ en un ensemble de boîtes $\mathcal{B} = \{B_1, ..., B_n\}$ de cardinalité minimale. Chaque item $i$ possède un poids $w_i \in \mathbb{N}$ et un seuil $t_i \in \mathbb{N}$, et les boîtes ont une capacité $c \in \mathbb{N}$. En plus des contraintes classiques de Bin-Packing, l'ordre de remplissage est également contraint : au moment de placer le $k$-ième item dans la boîte, la capacité restante doit être

<figure><img src="image_2.png" /><figcaption>(a) Solution réalisable</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>(b) Solution avec $B_2$ non-réalisable</figcaption></figure>

FIG. 1 – Deux solutions pour une même instance

<footnote>*Ce travail a bénéficié d'aides de L'État gérées par l'Agence Nationale de la Recherche au titre du programme «Investissements d'avenir» Persyval-Lab portant les références ANR-11-LABX-0025-01</footnote>
supérieure au seuil $t_k$. Pour illustrer, deux solutions d'une même instance sont représentés dans la FIG. 1. Chaque item est représenté par un rectangle où la hauteur de la partie foncée correspond au poids de l'item, et la hauteur totale du rectangle est égale au seuil. Pour une affectation donnée, une solution optimale est obtenue en triant les items dans chaque boîte selon l'ordre $t_i - w_i$. Cette preuve est réalisée par argument d'échange [1].

## Génération de colonnes
La procédure de généra-tions de colonnes proposée repose sur la formulation exponentielle représentée dans la FIG. 2. B désigne l'ensemble des colonnes, c'est-à-dire les combinaisons d'items dans une boîte qui respectent les contraintes de seuils et de capacité. Chaque booléen $a_i^b$ indique si l'item $i$ est contenu dans la colonne $b$. Une variable booléenne $y^b$ est associée à chaque colonne $b$. La contrainte (2) impose que chaque item $i$ apparaisse exactement une fois dans l'ensemble des colonnes sélectionnées.

La méthode consiste à calculer efficacement une solution de la relaxation linéaire de cette formulation en générant dynamiquement un sous-ensemble $B'$ de $B$ afin de contourner la difficulté posée par le nombre de variables. Ce nouveau problème est connu sous le nom de *Restricted Master Problem* (RMP). A chaque itération, le RMP est résolu puis une nouvelle colonne minimisant le coût réduit $r = 1 - \sum_{i \in N} v_i a_i^b$, où $v_i$ sont les variables duales associées à l'ensemble des contraintes (2), est trouvée. Le calcul de cette nouvelle colonne consiste à résoudre une variante du problème du sac à dos par programmation dynamique. Le processus est répété jusqu'à ce que le coût réduit optimal soit non-négatif, ou autrement dit, quand il n'existe plus de colonne améliorant la solution. La solution obtenue est optimale pour la relaxation linéaire de la formulation exponentielle. Une borne supérieure est ensuite calculée en résolvant le PLNE avec l'ensemble de colonnes restreint $B'$.

L'efficacité de la méthode a été évaluée sur des jeux d'instances adaptés à partir de [2] en ajoutant des seuils proportionnels ou inversement proportionnels à l'usure, ou alors tirés aléatoirement. Pour des instances de grande taille (allant jusqu'à $n = 1000$ et $c = 1000$), la génération de colonnes permet d'obtenir des solutions avec un gap absolu très faible voire optimales pour des temps de calcul de l'ordre de la dizaine de secondes. En comparaison, pour l'adaptation du modèle linéaire classique du bin-packing, le solveur vient à manquer de mémoire dès $n = 500$. La présentation à la conférence inclura une présentation détaillée des résultats expérimentaux obtenus.

$$ \min \sum_{b \in B} y^b \qquad (1) $$

$$ \text{s.t.} \quad \sum_{b \in B} a_i^b y^b = 1 \quad \forall i \in N \qquad (2) $$

$$ y^b \in \{0,1\} \quad \forall b \in B \qquad (3) $$

<caption>FIG. 2 – Formulation exponentielle</caption>

## Références

[1] Bridonneau, G : Joint Production/Maintenance scheduling with consideration of the Health Index (Master thesis). Univ. Grenoble-Alpes (2022).

[2] Delorme, M., Iori, M., Martello, S. : Bin packing and cutting stock problems : Mathematical models and exact algorithms. Eur J Oper Res 255(1), 1–20 (2016).

[3] Gilmore, P.C., Gomory, R.E. : A Linear Programming Approach to the Cutting-Stock Problem. Oper Res 9(6), 849–859 (1961).

[4] Foussard, E., Espinouse, M-L., Mounié, G., Nattaf, M. : Ordonnancement de la production et de la maintenance sur une machine multicomposant : étude de complexité. ROADEF 2022.

[5] Penz L., Dauzère-Pérès S., Nattaf M. : Minimizing the sum of completion times on a single machine with health index and flexible maintenance operations. Comput Oper Res 106092 (2022).