The overflowing bin packing problem: theoretical results and compact ILP formulations

Abstract We study the overflowing bin packing problem (OBPP), a recently proposed one-dimensional packing problem with notable conceptual ties to the field of (just-in-time) scheduling. In this scenario, we are required to pack items of known sizes into bins of known capacities so that, in broad terms, each bin’s total load comes as close as possible to its capacity. To establish its status as an independent research branch, the OBPP is first distinguished from related optimization problems. We then review an assignment model from the literature and analyze its theoretical properties, providing a closed-form expression for the associated LP bound and characterizing its worst-case performance ratio. In the second part, we introduce a new flow-based approach for the OBPP and examine both its theoretical and numerical advantages, the latter based on extensive computational experiments with diverse benchmark sets. Overall, the new flow formulation consistently produces high-quality—mostly optimal—solutions in short computation times, significantly outperforming previous state-of-the-art methods.