pith. sign in

arxiv: 2604.03078 · v1 · submitted 2026-04-03 · 🧮 math.OC

The Quadratic Bin Packing Problem: Exact Formulations and Algorithm

V\'itor Gomes Chagas , Alberto Locatelli , Fl\'avio Keidi Miyazawa , Manuel Iori This is my paper

Pith reviewed 2026-05-13 18:37 UTC · model grok-4.3

classification 🧮 math.OC
keywords quadratic bin packingbin packing problemmixed integer programmingbranch and priceset partitioning formulationcluster analysis
0
0 comments X

The pith

The Quadratic Bin Packing Problem admits exact solutions via compact MILP formulations for small cases and a superior Branch-and-Price algorithm for larger instances.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces the Quadratic Bin Packing Problem, which extends classical bin packing by adding a cost for each used bin and pairwise costs or profits for items placed in the same bin. It proposes three compact mixed-integer linear programming formulations and one set-partitioning formulation to model this problem exactly. Each compact model receives an enhanced version with a stronger relaxation, and the set-partitioning model is solved using a specialized Branch-and-Price algorithm. Experiments on benchmark instances show that the Branch-and-Price method outperforms the compact approaches, particularly as instance size and difficulty increase, making it suitable for applications like cluster analysis.

Core claim

The central claim is that the QBPP can be solved to optimality using the proposed formulations, with the Branch-and-Price algorithm on the set-partitioning formulation providing the best computational performance on larger benchmark instances compared to solving enhanced compact MILP models with a standard solver.

What carries the argument

A set-partitioning formulation solved by Branch-and-Price, where columns represent feasible assignments of items to bins and the pricing subproblem accounts for the quadratic interaction costs.

Load-bearing premise

The benchmark instances used accurately represent the structure and computational difficulty of real-world QBPP applications.

What would settle it

A direct comparison of solution times and optimality gaps on a collection of new QBPP instances larger than those in the benchmarks would falsify the superiority claim if the compact formulations perform better or equally.

Figures

Figures reproduced from arXiv: 2604.03078 by Alberto Locatelli, Fl\'avio Keidi Miyazawa, Manuel Iori, V\'itor Gomes Chagas.

Figure 1
Figure 1. Figure 1: Overall performance on small-sized in￾stances for the compact formulations. 0 500 1000 1500 2000 2500 3000 3500 Time (seconds) 0 20 40 60 80 100 120 Number of solved instances FFGW+SB FEFGW F2A+SB FE2A FR FER In this first round of experiments, a clear effect of the parameter σ is also observed. In particular, instances with σ = − are consistently the most challenging ones across all tested algorithms, as … view at source ↗
Figure 2
Figure 2. Figure 2: Number of small-sized instances solved to proven optimality by the implemented compact formu [PITH_FULL_IMAGE:figures/full_fig_p016_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Number of small- to medium-sized instances solved to proven optimality by the compact enhanced [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Comparison of the two B&P implementations in terms of large-sized instances solved to proven [PITH_FULL_IMAGE:figures/full_fig_p019_4.png] view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper introduces the Quadratic Bin Packing Problem (QBPP) as a generalization of the classical bin packing problem incorporating fixed bin costs and pairwise costs or profits for co-packed items. It develops three compact mixed-integer linear programming formulations, along with strengthened versions featuring improved continuous relaxations, a set-partitioning formulation, and a Branch-and-Price algorithm. Computational experiments on benchmark instances indicate that the enhanced compact formulations are suitable for small instances via standard MILP solvers, while the Branch-and-Price method exhibits superior performance on larger and more difficult instances.

Significance. If the reported computational results are confirmed, the paper provides a solid foundation for solving the QBPP exactly, with potential impact on applications in cluster analysis and related fields. The explicit formulations and the tailored algorithm represent a contribution to the literature on quadratic extensions of packing problems. The use of standard techniques like linearization and column generation is appropriate, and the comparison of methods is a strength.

minor comments (2)
  1. [Abstract] The abstract could more precisely state the number of compact formulations proposed and the specific enhancements made to their relaxations.
  2. [Computational Experiments] It would be helpful to include details on the hardware used, solver settings, and time limits to allow for better reproducibility of the results.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the constructive and positive review, which recognizes the contributions of our work on the Quadratic Bin Packing Problem. The recommendation for minor revision is appreciated. No specific major comments were provided in the report, so we have no individual points to address point-by-point. We will incorporate any minor editorial or presentational improvements suggested during the revision process.

Circularity Check

0 steps flagged

No significant circularity detected in derivation chain

full rationale

The paper defines the QBPP directly from the classical bin packing problem by adding fixed bin costs and pairwise interaction terms. It then constructs three compact MILP formulations via standard linearization of the quadratic objective (explicitly stated as replacing pairwise products with auxiliary variables and big-M constraints). The set-partitioning formulation follows immediately from enumerating feasible item subsets, and the Branch-and-Price algorithm is obtained by applying column generation to that formulation with a standard pricing subproblem. No parameter is fitted to data and then re-used as a 'prediction'; no uniqueness theorem or ansatz is imported via self-citation; and the reported computational ordering is an empirical comparison on external benchmark instances rather than a self-referential claim. The entire modeling and algorithmic chain is therefore self-contained against the problem definition and standard OR techniques.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard mixed-integer programming theory and linearization of quadratic objectives; no new free parameters, ad-hoc axioms, or invented entities are introduced beyond the problem definition itself.

axioms (1)
  • standard math Standard assumptions and linearization techniques of mixed-integer linear programming suffice to model quadratic pairwise costs exactly.
    Invoked when converting the quadratic objective into linear constraints in the compact formulations.

pith-pipeline@v0.9.0 · 5470 in / 1131 out tokens · 37188 ms · 2026-05-13T18:37:23.996194+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

42 extracted references · 42 canonical work pages

  1. [1]

    W. P. Adams and H. D. Sherali. A tight linearization and an algorithm for zero-one quadratic programming problems. Management Science, 32: 0 1274--1290, 1986

    work page 1986

  2. [2]

    Baldacci, S

    R. Baldacci, S. Coniglio, J.-F. Cordeau, and F. Furini. A numerically exact algorithm for the bin-packing problem. INFORMS Journal on Computing, 36: 0 141 – 162, 2024

    work page 2024

  3. [3]

    D. Bergman. An exact algorithm for the quadratic multiknapsack problem with an application to event seating . INFORMS Journal on Computing, 31: 0 477 – 492, 2019

    work page 2019

  4. [4]

    Cacchiani, M

    V. Cacchiani, M. Iori, A. Locatelli, and S. Martello. Knapsack problems — an overview of recent advances. Part II: Multiple , multidimensional, and quadratic knapsack problems. Computers and Operations Research, 143: 0 105693, 2022

    work page 2022

  5. [5]

    Campêlo, V

    M. Campêlo, V. A. Campos, and R. C. Corrêa. On the asymmetric representatives formulation for the vertex coloring problem. Discrete Applied Mathematics, 156: 0 1097--1111, 2008

    work page 2008

  6. [6]

    Caprara, D

    A. Caprara, D. Pisinger, and P. Toth. Exact solution of the quadratic knapsack problem. INFORMS Journal on Computing, 11: 0 125--137, 1999

    work page 1999

  7. [7]

    Capua, Y

    R. Capua, Y. Frota, L. S. Ochi, and T. Vidal. A study on exponential-size neighborhoods for the bin packing problem with conflicts. Journal of Heuristics, 24: 0 667 – 695, 2018

    work page 2018

  8. [8]

    Ceselli and G

    A. Ceselli and G. Righini. An optimization algorithm for the ordered open-end bin-packing problem. Operations Research, 56: 0 425--436, 2008

    work page 2008

  9. [9]

    Chen and J.-K

    Y. Chen and J.-K. Hao. Iterated responsive threshold search for the quadratic multiple knapsack problem. Annals of Operations Research, 226: 0 101 – 131, 2015

    work page 2015

  10. [10]

    Clautiaux and I

    F. Clautiaux and I. Ljubić. Last fifty years of integer linear programming: A focus on recent practical advances. European Journal of Operational Research, 324: 0 707--731, 2025

    work page 2025

  11. [11]

    Clautiaux, M

    F. Clautiaux, M. Dell’Amico, M. Iori, and A. Khanafer. Lower and upper bounds for the bin packing problem with fragile objects. Discrete Applied Mathematics, 163: 0 73--86, 2014. Matheuristics 2010

    work page 2014

  12. [12]

    E. G. J. Coffman, M. R. Garey, and D. S. Johnson. Approximation algorithms for bin packing: A survey. In Approximation Algorithms for NP-hard Problems, pages 46--93. PWS Publishing Co., Boston, MA, USA, 1996

    work page 1996

  13. [13]

    H. V. da Silva, A. Locatelli, S. A. de Araujo, and M. Iori. Mathematical formulations for the robust bin packing problem with fragile objects. Optimization Letters, (forthcoming), 2025

    work page 2025

  14. [14]

    R. F. da Silva and R. C. Schouery. Solving cutting stock problems via an extended ryan-foster branching scheme and fast column generation. INFORMS Journal on Computing, (forthcoming), 2025

    work page 2025

  15. [15]

    V. L. de Lima, M. Iori, and F. K. Miyazawa. Exact solution of network flow models with strong relaxations. Mathematical Programming, 197 0 (2): 0 813 – 846, 2023

    work page 2023

  16. [16]

    Delorme and M

    M. Delorme and M. Iori. Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems. INFORMS Journal on Computing, 32: 0 101--119, 2020

    work page 2020

  17. [17]

    Delorme, M

    M. Delorme, M. Iori, and S. Martello. Bin packing and cutting stock problems: Mathematical models and exact algorithms. European Journal of Operational Research, 255: 0 1--20, 2016

    work page 2016

  18. [18]

    Dyckhoff

    H. Dyckhoff. A typology of cutting and packing problems. European Journal of Operational Research, 44 0 (2): 0 145 – 159, 1990

    work page 1990

  19. [19]

    Elhedhli, L

    S. Elhedhli, L. Li, M. Gzara, and J. Naoum-Sawaya. A branch-and-price algorithm for the bin packing problem with conflicts. INFORMS Journal on Computing, 23: 0 404--415, 2011

    work page 2011

  20. [20]

    Fan and P

    N. Fan and P. Pardalos. Linear and quadratic programming approaches for the general graph partitioning problem. J. Global Optimization, 48: 0 57--71, 09 2010

    work page 2010

  21. [21]

    Ferreira, A

    C. Ferreira, A. Martin, C. De Souza, R. Weismantel, and L. Wolsey. Formulations and valid inequalities for the node capacitated graph partitioning problem. Mathematical Programming, Series B, 74: 0 247 – 266, 1996

    work page 1996

  22. [22]

    K. Fleszar. A branch-and-bound algorithm for the quadratic multiple knapsack problem. European Journal of Operational Research, 298: 0 89 – 98, 2022

    work page 2022

  23. [23]

    F. D. Fomeni and A. N. Letchford. A dynamic programming heuristic for the quadratic knapsack problem. INFORMS Journal on Computing, 26: 0 173--182, 2014

    work page 2014

  24. [24]

    R. Fortet. L’algebre de boole et ses applications en recherche op \'e rationnelle. Trabajos de Estadistica, 11: 0 111--118, 1960

    work page 1960

  25. [25]

    Galli, S

    L. Galli, S. Martello, C. Rey, and P. Toth. Lagrangian matheuristics for the quadratic multiple knapsack problem. Discrete Applied Mathematics, 335: 0 36 – 51, 2023

    work page 2023

  26. [26]

    Galli, S

    L. Galli, S. Martello, and P. Toth. The quadratic knapsack problem. European Journal of Operational Research, 326: 0 1--12, 2025

    work page 2025

  27. [27]

    Gendreau, G

    M. Gendreau, G. Laporte, and F. Semet. Heuristics and lower bounds for the bin packing problem with conflicts. Computers and Operations Research, 31: 0 347 – 358, 2004

    work page 2004

  28. [28]

    Glover and E

    F. Glover and E. Woolsey. Converting the 0-1 polynomial programming problem to a 0-1 linear program. Operations Research, 22: 0 180--182, 1974

    work page 1974

  29. [29]

    Hansen and B

    P. Hansen and B. Jaumard. Cluster analysis and mathematical programming. Mathematical Programming, Series B, 79 0 (1-3): 0 191 – 215, 1997

    work page 1997

  30. [30]

    Hiley and B

    A. Hiley and B. A. Julstrom. The quadratic multiple knapsack problem and three heuristic approaches to it. volume 1, page 547 – 552, 2006

    work page 2006

  31. [31]

    A. Jain, M. Murty, and P. Flynn. Data clustering: A review. ACM Computing Surveys, 31: 0 264 – 323, 1999

    work page 1999

  32. [32]

    Jansen and S

    K. Jansen and S. Öhring. Approximation algorithms for time constrained scheduling. Information and Computation, 132: 0 85 -- 108, 1997

    work page 1997

  33. [33]

    L. V. Kantorovich. Mathematical methods of organizing and planning production. Management science, 6: 0 366--422, 1960

    work page 1960

  34. [34]

    Khanafer, F

    A. Khanafer, F. Clautiaux, and E.-G. Talbi. New lower bounds for bin packing problems with conflicts. European Journal of Operational Research, 206: 0 281 – 288, 2010

    work page 2010

  35. [35]

    J. M. Mulvey and M. P. Beck. Solving capacitated clustering problems. European Journal of Operational Research, 18: 0 339 – 348, 1984

    work page 1984

  36. [36]

    A. E. F. Muritiba, M. Iori, E. Malaguti, and P. Toth. Algorithms for the bin packing problem with conflicts. INFORMS J. on Computing, 22: 0 401--415, July 2010

    work page 2010

  37. [37]

    J. Qin, X. Xu, Q. Wu, and T. Cheng. Hybridization of tabu search with feasible and infeasible local searches for the quadratic multiple knapsack problem. Computers and Operations Research, 66: 0 199 – 214, 2016

    work page 2016

  38. [38]

    D. M. Ryan and B. A. Foster. An integer programming approach to scheduling. Computer Scheduling of Public Transport: Urban Passenger Vehicle and Crew Scheduling, 1: 0 269--280, 1981

    work page 1981

  39. [39]

    Sadykov and F

    R. Sadykov and F. Vanderbeck. Bin packing with conflicts: A generic branch-and-price algorithm. INFORMS Journal on Computing, 25: 0 244--255, 2013

    work page 2013

  40. [40]

    H. D. Sherali and W. P. Adams. A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics, 3: 0 411--430, 1990

    work page 1990

  41. [41]

    Soares and M

    P. Soares and M. Campêlo. t-linearization for the maximum diversity problem. Optimization Letters, 15: 0 2879 – 2895, 2021

    work page 2021

  42. [42]

    Theodoridis and K

    S. Theodoridis and K. Koutroumbas. Pattern Recognition. Elsevier Academic Press, Burlington, MA, USA, 4th edition, 2006

    work page 2006