The Quadratic Bin Packing Problem: Exact Formulations and Algorithm
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910100501823488 |
|---|---|
| author | Chagas, Vítor Gomes Locatelli, Alberto Miyazawa, Flávio Keidi Iori, Manuel |
| author_facet | Chagas, Vítor Gomes Locatelli, Alberto Miyazawa, Flávio Keidi Iori, Manuel |
| contents | In this article, we introduce and study the Quadratic Bin Packing Problem (QBPP), which generalizes the classical bin packing problem by introducing a fixed cost for each used bin and a pairwise cost (or profit) incurred whenever two items are packed together. Beyond its theoretical relevance, the QBPP is of practical interest due to its numerous real-world applications, mainly related to cluster analysis. To address the QBPP, we propose three compact mixed-integer linear programming (MILP) formulations, along with a set-partitioning formulation. For each compact model, we present an enhanced version with a strengthened continuous relaxation, while, for the set-partitioning formulation, we develop a tailored Branch-and-Price algorithm. Computational experiments on benchmark instances demonstrated that, while the enhanced compact formulations can be effectively solved by a standard MILP solver for small-sized instances, the Branch-and-Price approach delivered superior performance overall, especially on larger and more challenging instances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_03078 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Quadratic Bin Packing Problem: Exact Formulations and Algorithm Chagas, Vítor Gomes Locatelli, Alberto Miyazawa, Flávio Keidi Iori, Manuel Optimization and Control 90C10, 90C11 In this article, we introduce and study the Quadratic Bin Packing Problem (QBPP), which generalizes the classical bin packing problem by introducing a fixed cost for each used bin and a pairwise cost (or profit) incurred whenever two items are packed together. Beyond its theoretical relevance, the QBPP is of practical interest due to its numerous real-world applications, mainly related to cluster analysis. To address the QBPP, we propose three compact mixed-integer linear programming (MILP) formulations, along with a set-partitioning formulation. For each compact model, we present an enhanced version with a strengthened continuous relaxation, while, for the set-partitioning formulation, we develop a tailored Branch-and-Price algorithm. Computational experiments on benchmark instances demonstrated that, while the enhanced compact formulations can be effectively solved by a standard MILP solver for small-sized instances, the Branch-and-Price approach delivered superior performance overall, especially on larger and more challenging instances. |
| title | The Quadratic Bin Packing Problem: Exact Formulations and Algorithm |
| topic | Optimization and Control 90C10, 90C11 |
| url | https://arxiv.org/abs/2604.03078 |