An Integer Linear Programming Based Heuristic for the Min-Sum Packing Problem

• Rafael C. S. Schouery UNICAMP

DOI: https://doi.org/10.5753/etc.2022.223073

Abstract

We consider the Min-Sum Packing Problem, in which, given a set of items with their respective weights, we want to pack them into bins of limited capacity to minimize the sum, over all items, of the index of the bin where the item was packed. We present a heuristic based on Integer Linear Programming that, even with a time limit of just one minute, was able to find solutions with an average gap of only 1.15% for approximately 64% of the considered instances. For the remaining instances, where it was not possible to calculate an upper bound, the heuristic was able to improve the solution by 13% on average when compared with the initial heuristic used.

Keywords: Packing, Heuristic, Column Generation

References

Delorme, M., Iori, M., and Martello, S. (2016). Bin packing and cutting stock problems: Mathematical models and exact algorithms. European Journal of Operational Research, 255(1):1–20.

Delorme, M., Iori, M., and Martello, S. (2022). BPPLIB –– A Bin Packing Problem Library. http://or.dei.unibo.it/library/bpplib. Accessed: 2022-0315.

Epstein, L., Johnson, D. S., and Levin, A. (2018). Min-sum bin packing. Journal of Combinatorial Optimization, 36:508–531.

Gilmore, P. C. and Gomory, R. E. (1961). A linear programming approach to the cuttingstock problem. Operations Research, 9(6):849–859.