Mathematical formulations for the robust bin packing problem with fragile objects

Abstract

Motivated by a frequency assignment problem arising in the telecommunications field, this study introduces the robust bin packing problem with fragile objects (RBPPFO). The RBPPFO generalizes the well-known bin packing problem with fragile objects (pack a set of items, each with a weight and fragility, into the minimum number of bins ensuring that in any bin their total weight does not exceed their smallest fragility), by incorporating a budgeted uncertainty set to model data uncertainties caused by signal power fluctuations that frequently occur in many telecommunication systems. To address the RBPPFO, we propose a compact mixed-integer linear programming formulation, an arc-flow formulation, and a constraint programming formulation. We also introduce upper bounding techniques, along with a valid lower bound obtained by transforming the RBPPFO into a corresponding BPPFO and subsequently applying the fractional lower bound from the literature to the latter problem. The solutions generated by the heuristics are used to initialize the formulations, so as to improve their convergence. We evaluate the effectiveness of the proposed solution methods through extensive computational tests on instances adapted from the literature to cover a variety of relevant scenarios. The results demonstrate that the arc-flow formulation performs well across the different scenarios, highlighting its potential for applications beyond the RBPPFO to other packing problems under uncertainty.