Fixed Set Search Matheuristic Applied to the min-Knapsack Problem with Compactness Constraints and Penalty Values

This paper introduces an extended version of the min-Knapsack problem with compactness constraints (mKPC). The idea is to define penalty values for certain items when they are not selected in the knapsack. In addition to cost, weight, and compactness constraints in the mKPC, which require selected items to remain within close proximity, the min-Knapsack problem with compactness constraints and penalty values (mKPCP) incorporates penalty values for excluding certain items. The method outlined in this study leverages the learning mechanism of a metaheuristic approach, Fixed Set Search, integrating it with integer programming to address partial solutions throughout the process. To enhance the learning mechanism process, the initial population of solutions is generated through an algorithm that randomly creates solutions considering the compactness constraint and the item sequences, with the aim of enhancing diversity. New instances are proposed to evaluate the proposed method on the mKPCP. The method is also tested on the mKCP to compare with existing methods. The experiments indicate that the proposed method yields promising outcomes across a diverse set of instances. The approach does not rely heavily on any unique characteristics of the problem and could be adapted to other binary problems, including the minimum vertex cover problem and the facility location problem, with small adjustments.