Um Algoritmo Exato de Programação Dinâmica e uma Heurística GRASP para o Problema da Mochila com Descontos Progressivos em Pilhas

Este trabalho estuda uma variação do Problema da Mochila, denominada Problema da
Mochila com Descontos Progressivos em Pilhas. Nesse problema, os itens estão organizados em
pilhas, e o custo associado a cada item é reduzido progressivamente à medida que um maior número
de seus predecessores na mesma pilha é selecionado, em conformidade com práticas comerciais que
oferecem descontos por quantidade, como em compras no atacado ou pacotes de serviços. Além
disso, são consideradas restrições de precedência entre os itens, representando cenários nos quais
a seleção de determinados elementos depende da escolha prévia de outros. Para a resolução do
problema são propostas duas abordagens: um algoritmo exato baseado em programação dinâmica
com complexidade pseudo-polinomial e uma heurística GRASP. Os experimentos computacionais
realizados demonstram que a heurística apresentou um gap médio inferior a 5% em relação às
soluções ótimas obtidas para as instâncias avaliadas.