Metaheurísticas para o problema da mochila multidimensional

Abstract

O problema da mochila multidimensional ´e amplamente conhecido na área de otimização combinatória e possui diversas aplicações práticas, tais como, dimensionamento de cargas, orçamento de capital, alocação de recursos em sistemas distribuídos, entre outros. Apesar de sua popularidade, sua solução não é trivial, de fato, ele pertence a uma classe de problemas conhecidos como NP-difíceis, para os quais não são conhecidos algoritmos polinomiais capazes de obter uma solução exata para todas as instancias. Essa situação motiva a busca por técnicas alternativas para obter soluções em menor tempo, ainda que aproximadas e, nesse cenário, as metaheurısticas têm se mostrado de especial interesse, pois são capazes de alcançar soluções de boa qualidade para uma ampla variedade de problemas. Entretanto, mesmo as metaheurısticas podem ser relativamente demoradas, em especial para instâncias de tamanho grande, o que encoraja a aplicação de t´técnicas, como as estratégias de paralelização, para reduzir os seus tempos de execução ou, ainda, melhorar a qualidade das soluções. Neste trabalho, apresenta-se o estudo, implementação e análise de um conjunto de metaheurısticas para a solução do problema da mochila multidimensional. São apresentadas e avaliadas diferentes alternativas para a paralelização e os resultados obtidos são comparados com os de outros trabalhos da literatura pesquisada. Para comprovar que os bons resultados possibilitados pelo uso das metaheurısticas estudadas não foram obtidos ao acaso, as soluções foram validadas com a utilização de testes estatísticos.

ABSTRACT - The 0-1 multidimensional knapsack problem (0-1 MKP) is widely known in combinatorial optimization with numerous practical applications, such as cargo loading, capital budgeting, resource allocation in distributed systems, among others. Despite its popularity, it is not a trivial problem, in fact, 0-1 MKP belongs to NP-hard class of problems, for which there are not polynomial-time algorithms capable of obtaining exact solutions for every possible instance. This situation motivates the search for alternative techniques aiming to achieve solutions in reduced execution time, albeit approximate and, in this case, metaheuristics have become specially attractive since they can lead to good quality solutions to a wide range of problems. However, even metaheuristics can be relatively slow, specially with large size instances, which encourages the application of techniques, such as parallelization strategies, aiming to reduce execution times or even improve the quality of solutions. In this work, we present the study, implementation and analysis of a set of metaheuristics for the solution of the 0-1 multidimensional knapsack problem. Different approaches for parallelization are presented and evaluated and the achieved results are compared to other works. Achieved solutions were validated with application of statistical tests, in order to show that the good quality solutions obtained by the metaheuristics were not obtained by chance.