Implementação da meta-heurística de busca em vizinhanças variáveis (VNS) na solução do Problema da Mochila Multidimensional

Abstract

Combinatorial optimization, one of the primary branches of computing, addresses complex challenges, among which the multidimensional knapsack problem stands out. Despite its diverse practical applications, this problem is classified as NP-Hard, implying the absence, to date, of a polynomial algorithm capable of finding an exact solution to the problem. Faced with this scenario, there is a need to develop techniques that provide effective solutions in a short amount of time, and it is in this context that metaheuristics play a crucial role, showcasing their ability to achieve optimal results. This work presents the implementation and analysis of a metaheuristic based on a well-known neighborhood search called Variable Neighborhood Search (VNS), applied to solving the multidimensional knapsack problem.