Pseudo-Polynomial Models for the Colored Bin Packing Problem

• Yulle G. F. Borges UNICAMP http://orcid.org/0000-0002-1865-4104
• Rafael C. S. Schouery UNICAMP http://orcid.org/0000-0002-0472-4810

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

Abstract

The Colored Bin Packing Problem consists in packing a set of items, each with a size and a color, into the minimum amount of bins of a given capacity, such that no two items from the same color appear consecutively in the same bin. We propose pseudo-polynomial Integer Programming formulations that solve randomly generated instances of up to 500 items and 15 colors in a matter of seconds.

Keywords: Combinatorial Optimization, Mathematical Programming

References

Balogh, J., Békési, J., Dósa, G., Epstein, L., Kellerer, H., Levin, A., e Tuza, Z. (2015). Offline black and white bin packing. Theoretical Computer Science, 596:92–101.

Balogh, J., Békési, J., Dosa, G., Kellerer, H., e Tuza, Z. (2013). Black and white bin packing. In Proceedings of the 10 th International Workshop on Approximation and Online Algorithms, pages 131–144.

Böhm, M., Dósa, G., Epstein, L., Sgall, J., e Veselý, P. (2018). Colored bin packing: Online algorithms and lower bounds. Algorithmica, 80(1):155–184.

Christofides, N. e Whitlock, C. (1977). An algorithm for two-dimensional cutting problems. Operations Research, 25(1):30–44.

Dolan, E. D. e Moré, J. J. (2002). Benchmarking optimization software with performance profiles. Mathematical programming, 91(2):201–213.

Gurobi Optimization, L. (2020). Gurobi optimizer reference manual.

Herz, J. (1972). Recursive computational procedure for two-dimensional stock cutting. IBM Journal of Research and Development, 16(5):462–469.

Kantorovich, L. V. (1939). The mathematical method of production planning and organization. Management Science, 6:363–422.

Valério De Carvalho, J. (1999). Exact solution of bin-packing problems using column generation and branch-and-bound. Annals of Operations Research, 86:629-659.