Uma Heurística Baseada em Programação Linear Inteira para o Problema do Empacotamento de Soma Mínima - Schouery, Rafael C. S. (Anais do Encontro de Teoria da Computação (ETC); 2022: Anais do VII Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2022.223073, 2022)
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.