Abstract:
This paper introduces an extended version of the min-Knapsack Problem with Compactness Constraints (mKPC), referred to as the min-Knapsack Problem with Compactness Constraints and Penalty Values (mKPCP). In this extension, penalty values are assigned to specific items that incur additional cost when excluded from the knapsack. Alongside the cost, weight, and compactness constraints of the original mKPC, which enforce proximity among selected items, the mKPCP integrates these penalties as soft constraints to reflect the importance of certain items. To solve the mKPCP, we propose a matheuristic method that combines the learning mechanism of the Fixed Set Search (FSS) metaheuristic with integer programming (IP) to improve partial solutions throughout the search process. A greedy randomized algorithm is employed to generate the initial population, promoting both diversity and solution quality. New instances are generated to evaluate the performance of the proposed method on the mKPCP. In addition, the method is tested on the mKPC and compared with existing mixed-integer programming (MIP) based techniques, such as compact MIP and branch-and-cut algorithms. Experimental results demonstrate that the proposed approach yields competitive performance across a wide range of instances. Furthermore, the method is problem-independent in nature and can be adapted to other binary optimization problems, such as the minimum vertex cover and facility location problems, with very little modifications.
