A Novel Continuous Optimization Approach for the 0-1 Knapsack Problem

Felipe Ferreira Lopes; Alireza Mohebi Ahstiani

doi:10.20906/CPS/SICITE2015-0052

Resumo

Nesse trabalho propormos uma nova abordagem contínua de resolução de um dos problemas de optimização combinatória mais estudados, o problema de mochila 0-1. Problemas de mochila são uma classe de problemas de optimização combinatória, que tem sido estudados desde o fim dos anos 50 com o trabalho pioneiro de Dantzig devido a suas possíveis aplicações na indústria e na área de administração. Essa classe de problemas recebe esse nome devido ao exemplo clássico do mochileiro. Suponha que um mochileiro queira encher sua mochila com itens necessários para levar a sua viajem e para tal deve escolher dentre um conjunto de objetos, cada um com um valor (um "conforto" que pode proporcionar), aqueles que lhe serão mais úteis. No problema de mochila 0-1 cada item é único. No espaço contínuo. o problema foi reformulado como um problema de multiplicativo convexo generalizado, uma classe especial de problemas não convexos que envolve a minimização de uma soma finita de produtos de funções convexas sobre um arranjo convexo não-vazio. O produto de quaisquer duas funções positivas não é necessariamente convexo ou quase convexo, e, portanto o problema contínuo pode ter soluções óptimas locais que não são necessariamente soluções óptimas globais. No espaço dos resultados, esse problema pode ser eficientemente resolvido por um algoritmo que combine a técnica de relaxação com o procedimento branch-and-bound . Algumas experiências computacionais foram realizadas e seus resultados foram apresentados no escopo desse trabalho.

Palavras-chave: Problema de Mochila; Optimização Combinatória; Optimização Global; Programação Multiplicativa