Fixed set search matheuristic applied to the min-Knapsack problem with compactness constraints and an extension incorporating penalty values
本文提出一种固定集搜索元启发式与整数规划结合的数学启发式方法，求解带紧凑性约束和惩罚值的最小背包问题扩展版本，实验表明该方法在多种实例上表现良好且可推广到其他二元优化问题。
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.