Uma meta-heurística para o problema da mochila com penalidades

Abstract

The knapsack problem is among one of the most well-known combinatorial problems. Its potential for application and the numerous variations that exist make it a good model for various practical real-life problems. More specifically, this work addresses a variant of the problem, the Knapsack Problem with Forfeits (KPF). In this variant, a set of items and a conflict graph are provided, and the goal is to identify a collection of items that respects the knapsack’s capacity while maximizing the total value of the items minus the penalties for conflicting items. The KPF has garnered some attention both due to its proximity to other famous problems, such as the maximum weight independent set, and its applications. Some examples range from workforce organization on the factory floor to decision problems in investments. This work presents a new method for the problem using well-established tools, based on the hybridization of Iterated Local Search (ILS), Variable Neighborhood Descent (VND), and elements of Tabu Search. Our method takes into account four neighborhood structures, introduced with efficient data structures to explore them. Experimental results demonstrate that the proposed approach outperforms state-of-the-art algorithms in the literature. In particular, the proposed method provides superior solutions in significantly shorter computation times on all reference instances. An analysis of how the proposed data structures influenced both the quality of the solutions and the method’s execution time is also included.