Coco Amadeu A, Santos Andréa Cynthia, Noronha Thiago F
UNIHAVRE, UNIROUEN, INSA Rouen, LITIS, Normandie Université, Le Havre, France.
Computer Science Department, Federal University of Minas Gerais, Belo Horizonte, Brazil.
Comput Optim Appl. 2022;83(1):111-141. doi: 10.1007/s10589-022-00391-x. Epub 2022 Jul 15.
This article deals with two min-max regret covering problems: the min-max regret Weighted Set Covering Problem ( WSCP) and the min-max regret Maximum Benefit Set Covering Problem ( MSCP). These problems are the robust optimization counterparts, respectively, of the Weighted Set Covering Problem and of the Maximum Benefit Set Covering Problem. In both problems, uncertainty in data is modeled by using an interval of continuous values, representing all the infinite values every uncertain parameter can assume. This study has the following major contributions: (i) a proof that MSCP is -Hard, (ii) a mathematical formulation for the MSCP, (iii) exact and (iv) heuristic algorithms for the WSCP and the MSCP. We reproduce the main exact algorithms for the WSCP found in the literature: a Logic-based Benders decomposition, an extended Benders decomposition and a branch-and-cut. In addition, such algorithms have been adapted for the MSCP. Moreover, five heuristics are applied for both problems: two scenario-based heuristics, a path relinking, a pilot method and a linear programming-based heuristic. The goal is to analyze the impact of such methods on handling robust covering problems in terms of solution quality and performance.
极小极大遗憾加权集合覆盖问题（WSCP）和极小极大遗憾最大效益集合覆盖问题（MSCP）。这些问题分别是加权集合覆盖问题和最大效益集合覆盖问题的鲁棒优化对应问题。在这两个问题中，数据的不确定性通过使用连续值区间来建模，该区间表示每个不确定参数可以假设的所有无限值。本研究有以下主要贡献：（i）证明MSCP是NP难的，（ii）给出MSCP的数学公式，（iii）针对WSCP和MSCP的精确算法，以及（iv）启发式算法。我们重现了文献中找到的WSCP的主要精确算法：基于逻辑的Benders分解、扩展的Benders分解和分支切割算法。此外，这些算法已被改编用于MSCP。此外，针对这两个问题应用了五种启发式算法：两种基于场景的启发式算法、路径重连、一种引导方法和一种基于线性规划的启发式算法。目标是从解决方案质量和性能方面分析这些方法对处理鲁棒覆盖问题的影响。
