Improved Handling of Uncertainty and Robustness in Set Covering Problems

Pascal Lutter, Dirk Degel, Christina Büsing, Arie Koster, Brigitte Werners

Abstract

Set Covering Problems are one of the classical combinatorial optimization problems and part of many different practical applications, e.g., the location of emergency service facilities. 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 non-compact 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 for the location of emergency service facilities highlights the benefits of our approach in comparison to a formulation neglecting these uncertainties.