The Robust Set Covering Problem with interval data

The Robust Set Covering Problem with interval data

0.00 Avg rating0 Votes
Article ID: iaor20133914
Volume: 207
Issue: 1
Start Page Number: 217
End Page Number: 235
Publication Date: Aug 2013
Journal: Annals of Operations Research
Authors: ,
Keywords: heuristics: genetic algorithms
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.

Reviews

Required fields are marked *. Your email address will not be published.