Coupling scenario-based heuristics to exact methods for the robust weighted set covering problem with interval data*

In this study, we investigate the minmax regret Robust Weighted Set Covering problem with Interval Data (RSCP), which is the robust counterpart of the Weighted Set Covering Problem (WSCP) where uncertain data are modeled using interval data. RSCP is NP-Hard and can provide foundations for solving several minmax regret covering problems. Moreover, RSCP encloses several challenges in terms of computer science and mathematical formulations. The challenges involve the development of innovative algorithms since solving the RSCP for a unique scenario implies to solve an NP-Hard problem. The exact algorithms in the literature rely on decomposition algorithms and cutting plane procedures since the mathematical formulation of RSCP contains an exponential number of constraints. In this study, scenario-based heuristics are used to generate additional cuts in order to reduce the average optimality gaps on the instances not solved to optimality.