Optimization Online


Improved Handling of Uncertainty and Robustness in Set Covering Problems

Pascal Lutter (pascal.lutter***at***gmail.com)
Dirk Degel (dirk.degel***at***rub.de)
Christina Büsing (buesing***at***math2.rwth-aachen.de)
Arie Koster (koster***at***math2.rwth-aachen.de)
Brigitte Werners (or***at***rub.de)

Abstract: This paper studies the emergency service facility location problem in an uncertain environment. The main focus is the integration of uncertainty regarding the covered area due to uncertain traveling times. Previous approaches only consider either probabilistic or fuzzy optimization to cope with uncertainty. However, in many real-world problems the required statistical parameters are not precisely known and the obtained solutions may reveal a non-adequate performance. We introduce a robust formulation of the uncertain/probabilistic set covering problem which combines the concepts of robust and probabilistic optimization by introducing ’􀀀-robust -covering’ constraints. This robust uncertain set covering problem can be stated as a compact mixed-integer linear programming model. Additionally, two noncompact integer linear model formulations are developed. As the strength of these formulations is not known a priori, we analyze the performance of these formulations in an extensive computational study. A case study highlights the benefits of our approach in comparison to a formulation neglecting these uncertainties.

Keywords: Set Covering Problem, Robust Optimization, Emergency Medical Services, Cutting plane algorithm

Category 1: Robust Optimization

Category 2: Applications -- OR and Management Sciences

Category 3: Integer Programming (Cutting Plane Approaches )



Entry Submitted: 08/21/2016
Entry Accepted: 08/21/2016
Entry Last Modified: 04/25/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society