Uma Heurística Baseada em Programação Linear Inteira para o Problema do Empacotamento de Soma Mínima

• Rafael C. S. Schouery UNICAMP

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

Resumo

Consideramos o Problema do Empacotamento de Soma Mínima, em que, dado um conjunto de itens com os seus respectivos pesos, desejamos empacotá-los em recipientes de capacidade limitada com o objetivo de minimizar a soma, sobre todos os itens, do índice do recipiente onde o item foi empacotado. Apresentamos uma heurística baseada em Programação Linear Inteira que mesmo com um tempo limite de um minuto foi capaz de encontrar soluções com um gap médio de 1,15% para 64% das instâncias consideradas. Para as instâncias restantes, onde não foi possível calcular um limitante superior a tempo, a heurística foi capaz de melhorar a solução em 13% em média quando comparado com a heurística inicial utilizada.

Palavras-chave: Empacotamento, Heurística, Geração de Colunas

Referências

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.