Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2022;83(1):111-141.
doi: 10.1007/s10589-022-00391-x. Epub 2022 Jul 15.

Robust min-max regret covering problems

Amadeu A Coco  1 , Andréa Cynthia Santos  1 , Thiago F Noronha  2
Affiliations

Robust min-max regret covering problems

Amadeu A Coco et al. Comput Optim Appl. 2022.

Abstract

This article deals with two min-max regret covering problems: the min-max regret Weighted Set Covering Problem (min-max regret WSCP) and the min-max regret Maximum Benefit Set Covering Problem (min-max regret 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 Σ p 2 -Hard, (ii) a mathematical formulation for the min-max regret MSCP, (iii) exact and (iv) heuristic algorithms for the min-max regret WSCP and the min-max regret MSCP. We reproduce the main exact algorithms for the min-max regret 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 min-max regret 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.

Keywords: Covering problems; Exact methods; Heuristics; Robust optimization; Uncertainties.

PubMed Disclaimer

Conflict of interest statement

Conflict of interestThe authors declare that they have no conflict of interest.

Figures

Fig. 1
Fig. 1
An example of a min-max regret WSCP instance. The solutions X and Ys(X) are highlighted on tables a and b, respectively
Fig. 2
Fig. 2
Convergence of AMU, SBA, PR, LPH and PM for min-max regret WSCP to the instance scp43-2-1000
Fig. 3
Fig. 3
Convergence of AMU, SBA, PR, LPH and PM to min-max regret MSCP to the instance scp41-2-1000 with T = 0.1×M
See this image and copyright information in PMC

References

    1. Aissi H, Bazgan C, Vanderpooten D. Min-max and min-max regret versions of combinatorial optimization problems: A survey. Eur. J. Oper. Res. 2009;197:427–438.
    1. Assunção L, Santos AC, Noronha TF, Andrade R. A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs. Comput. Oper. Res. 2017;81:51–66.
    1. Averbakh I, Berman O. Minmax regret p-center location on a network with demand uncertainty. Locat. Sci. 1997;5:247–254.
    1. Beasley JE. A lagrangian heuristic for set-covering problems. Nav. Res. Logist. 1990;37(1):151–164.
    1. Beasley JE. OR-library: distributing test problems by electronic mail. J. Oper. Res. Soc. 1990;41:1069–1072.

LinkOut - more resources