EUVIMEDScopri EUVIMED
Crossref

The quadratic bin packing problem: exact formulations and algorithms

Vítor G. Chagas, Alberto Locatelli, Flávio K. Miyazawa, Manuel Iori

International Transactions in Operational Research · 2026-07-27

DOI: 10.1111/itor.70237 ↗

At a glance

Journal article in International Transactions in Operational Research, published online on 2026-07-27. Written by Vítor G. Chagas and 3 co-authors. 46 references. Funded by: Coordenação de Aperfeiçoamento de Pessoal de Nível Superior, Conselho Nacional de Desenvolvimento Científico e Tecnológico, European Social Fund Plus.

AbstractDati bibliograficiCiteRelated studies

Abstract (original language)

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.

Funding

  • Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
  • Conselho Nacional de Desenvolvimento Científico e Tecnológico
  • European Social Fund Plus
  • Fundação de Amparo à Pesquisa do Estado de São Paulo

Cite

APA

Chagas, V. G., Locatelli, A., Miyazawa, F. K., & Iori, M. (2026). The quadratic bin packing problem: exact formulations and algorithms. International Transactions in Operational Research. https://doi.org/10.1111/itor.70237

Vancouver

Chagas VG, Locatelli A, Miyazawa FK, Iori M. The quadratic bin packing problem: exact formulations and algorithms. International Transactions in Operational Research. 2026. doi:10.1111/itor.70237

BibTeX
@article{Chagas2026,
  author = {Chagas, Vítor G. and Locatelli, Alberto and Miyazawa, Flávio K. and Iori, Manuel},
  title = {The quadratic bin packing problem: exact formulations and algorithms},
  journal = {International Transactions in Operational Research},
  year = {2026},
  doi = {10.1111/itor.70237}
}
Start for free →