title   
  

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)

WarningThere is a more recent version of this item available.

[img]
Preview
PDF (This is a RoMEO green publisher -- author can archive pre-print (ie pre-refereeing)) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
308Kb

Abstract

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.

Item Type:Article
Uncontrolled Keywords:set covering, exact method, primal-dual heuristic, LP, relaxation, dual information, empirical study
Subjects:Q Science > QA Mathematics
T Technology > TA Engineering (General). Civil engineering (General)
ID Code:15108
Deposited By:Kerem Bülbül
Deposited On:09 Nov 2010 14:44
Last Modified:27 Sep 2012 23:22

Repository Staff Only: item control page