Taming the set covering problem: the value of dual information
Yelbay, Belma and Birbil, Ş. İlker and Bülbül, Kerem (2010) Taming the set covering problem: the value of dual information. (Submitted)
We offer a fresh perspective on solving the set covering problem to near optimality with off-the-shelf methods. We formulate minimizing the gap of a generic primal-dual heuristic for the set covering problem as an integer program and analyze its performance. The empirical insights from this analysis lead to a simple and powerful primal-dual approach for solving the set covering problem to near optimality with a state-of-the-art standard solver. We demonstrate the effectiveness of this approach on a rich set of benchmark instances compiled from the literature. We conclude that set covering problems of various characteristics and sizes may reliably solved to near optimality without resorting to custom solution methods.
Available Versions of this Item
Repository Staff Only: item control page