betaFeedback

WorksMathematics

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

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.

Paper details

vlnc:W_ywwx66zp
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…