Solving the Set Covering Problem with Conflicts on Sets: A new parallel GRASP
研究了一种新的带冲突集合覆盖问题，其中冲突子集需支付罚金才能共存，提出了整数线性规划和二次规划模型，并设计了一种并行GRASP算法，在不到六分之一的时间内优于Gurobi。
In this paper, we analyze a new variant of the well-known NP-hard Set Covering Problem, characterized by pairwise conflicts among subsets of items. Two subsets in conflict can belong to a solution provided that a positive penalty is paid. The problem looks for the optimal collection of subsets representing a cover and minimizing the sum of covering and penalty costs. We introduce two integer linear programming mathematical formulations and a quadratic one for the problem and provide a parallel GRASP (Greedy Randomized Adaptive Search Procedure) that, through parallel executions of the same basic procedure, shares information among threads. We tailor such a parallel processing to address the specific problem in an innovative way that allows us to prevent redundant computations in different threads, ultimately saving time. To evaluate the performance of our algorithm, we conduct extensive experiments on a large set of new instances obtained by adapting existing instances for the Set Covering Problem. Computational results show that the proposed approach is extremely effective and efficient providing better results than Gurobi (tackling three alternative mathematical formulations of the problem) in less than 1/6 of the computational time.