The Robust Set Covering Problem with interval data

Jordi Pereira, Igor Averbakh

Research output: Contribution to journalArticlepeer-review

33 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)217-235
Number of pages19
JournalAnnals of Operations Research
Volume207
Issue number1
DOIs
StatePublished - Aug 2013
Externally publishedYes

Keywords

  • Benders decomposition
  • Branch-and-Cut
  • Combinatorial optimization
  • Genetic algorithms
  • Heuristics
  • Minmax regret optimization
  • Set Covering Problem

Fingerprint

Dive into the research topics of 'The Robust Set Covering Problem with interval data'. Together they form a unique fingerprint.

Cite this