We consider a recently proposed one-dimensional packing problem, called the overflowing bin packing problem (OBPP). In this scenario, we are given a set of items (of known sizes) and a set of bins (of known capacities). Roughly speaking, the task is to assign the items to the bins in such a way that the total load of every bin is as close as possible to its capacity. In this article, we first separate the problem under consideration from related partitioning problems, thus justifying its status as an independent branch of research. Subsequently, we review an assignment model known from the literature and investigate its theoretical properties. As a main result, we give a closed-form term for the associated LP bound and specify its worst-case performance ratio. In the second part, we then present a new flow-based approach for the OBPP and discuss its theoretical and numerical benefits, the latter being based on extensive computational tests with different benchmark sets. Overall, the new flow formulation typically leads to good-quality (mostly even optimal) solutions in short time, clearly outperforming the previous state of the art.
Citation
Preprint MATH-NM-01-2024, Technische Universität Dresden