Mixed-integer programming formulations for the quadratic bin packing problem: linearization, hybridization, and enhancements

The quadratic bin packing problem (QBPP) extends the classical bin packing problem by incorporating pairwise dissimilarity values between items assigned to the same bin. The objective is to minimize the total cost, composed of the cost associated with the number of bins used and the sum of pairwise dissimilarity values for items assigned to the same bin, subject to the bin-capacity constraints. We study the quadratic programming formulation together with a broad family of equivalent mixed-integer linear programming (MILP) formulations for the QBPP based on classical linearization techniques. We analyze the relationships among the linear programming relaxations of the MILP formulations and strengthen several of these relaxations by exploiting the structure of the QBPP. We further introduce the first hybrid exact formulation for the QBPP that combines elements of two distinct modeling approaches. In particular, we show that the combination of explicit bin patterns and assignment-based representation performs particularly well. For the hybrid formulation, we investigate the effect of item selection, and for both the hybrid and non-hybrid formulations, we study the impact of item ordering on formulation size, relaxation strength and computational performance. Although a recently introduced tailored branch-and-price algorithm remains the state-of-the-art for the QBPP, we show that the proposed ordering-based non-hybrid and hybrid formulations substantially improve computational performance over the best MILP formulation known to the literature, in addition of solving 33 new benchmark instances to optimality.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-18
DOI
https://doi.org/10.48550/arxiv.2611.24245
Primary Topic
Optimization and Packing Problems
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Mixed-integer programming formulations for the quadratic bin packing problem: linearization, hybridization, and enhancements

Maxence Delorme, Renata Sotirov, Fatih Burak Akçay
arXiv (Cornell University)
Optimization and Packing Problems
preprint

Mixed-integer programming formulations for the quadratic bin packing problem: linearization, hybridization, and enhancements

Maxence Delorme, Renata Sotirov, Fatih Burak Akçay
preprint en

Abstract

The quadratic bin packing problem (QBPP) extends the classical bin packing problem by incorporating pairwise dissimilarity values between items assigned to the same bin. The objective is to minimize the total cost, composed of the cost associated with the number of bins used and the sum of pairwise dissimilarity values for items assigned to the same bin, subject to the bin-capacity constraints. We study the quadratic programming formulation together with a broad family of equivalent mixed-integer linear programming (MILP) formulations for the QBPP based on classical linearization techniques. We analyze the relationships among the linear programming relaxations of the MILP formulations and strengthen several of these relaxations by exploiting the structure of the QBPP. We further introduce the first hybrid exact formulation for the QBPP that combines elements of two distinct modeling approaches. In particular, we show that the combination of explicit bin patterns and assignment-based representation performs particularly well. For the hybrid formulation, we investigate the effect of item selection, and for both the hybrid and non-hybrid formulations, we study the impact of item ordering on formulation size, relaxation strength and computational performance. Although a recently introduced tailored branch-and-price algorithm remains the state-of-the-art for the QBPP, we show that the proposed ordering-based non-hybrid and hybrid formulations substantially improve computational performance over the best MILP formulation known to the literature, in addition of solving 33 new benchmark instances to optimality.

arXiv (Cornell University)
Optimization and Packing Problems
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon