The Quadratic Bin Packing Problem: Exact Formulations and Algorithm

Vítor Gomes Chagas, Alberto Locatelli, Flávio Keidi Miyazawa, Manuel Iori

arXivarxiv/2604.03078Apr 3, 2026math.OCscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2604.03078
curl -X POST /api/v1/records/arxiv/2604.03078/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.03078/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'