TY - JOUR

T1 - The Robust Set Covering Problem with interval data

AU - Pereira, Jordi

AU - Averbakh, Igor

N1 - Funding Information:
Acknowledgements The research of the first author has been partially supported through the Spanish CI-CYT grant DPI2007-63026. The research of the second author was supported by a discovery grant from the Natural Sciences and Engineering Research Council (NSERC) of Canada.

PY - 2013/8

Y1 - 2013/8

N2 - We study the Set Covering Problem with uncertain costs. For each cost coefficient, only an interval estimate is known, and it is assumed that each coefficient can take on any value from the corresponding uncertainty interval, regardless of the values taken by other coefficients. It is required to find a robust deviation (also called minmax regret) solution. For this strongly NP-hard problem, we present and compare computationally three exact algorithms, where two of them are based on Benders decomposition and one uses Benders cuts in the context of a Branch-and-Cut approach, and several heuristic methods, including a scenario-based heuristic, a Genetic Algorithm, and a Hybrid Algorithm that uses a version of Benders decomposition within a Genetic Algorithm framework.

AB - We study the Set Covering Problem with uncertain costs. For each cost coefficient, only an interval estimate is known, and it is assumed that each coefficient can take on any value from the corresponding uncertainty interval, regardless of the values taken by other coefficients. It is required to find a robust deviation (also called minmax regret) solution. For this strongly NP-hard problem, we present and compare computationally three exact algorithms, where two of them are based on Benders decomposition and one uses Benders cuts in the context of a Branch-and-Cut approach, and several heuristic methods, including a scenario-based heuristic, a Genetic Algorithm, and a Hybrid Algorithm that uses a version of Benders decomposition within a Genetic Algorithm framework.

KW - Benders decomposition

KW - Branch-and-Cut

KW - Combinatorial optimization

KW - Genetic algorithms

KW - Heuristics

KW - Minmax regret optimization

KW - Set Covering Problem

UR - http://www.scopus.com/inward/record.url?scp=84880512762&partnerID=8YFLogxK

U2 - 10.1007/s10479-011-0876-5

DO - 10.1007/s10479-011-0876-5

M3 - Article

AN - SCOPUS:84880512762

SN - 0254-5330

VL - 207

SP - 217

EP - 235

JO - Annals of Operations Research

JF - Annals of Operations Research

IS - 1

ER -