title   
  

The set covering problem revisited: an empirical study of the value of dual information

Yelbay, Belma and Birbil, Ş. İlker and Bülbül, Kerem (2012) The set covering problem revisited: an empirical study of 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
371Kb

Abstract

This paper investigates the role of dual information on the performances of heuristics designed for solving the set covering problem. After solving the linear programming relaxation of the problem, the dual information is used to obtain the two main approaches proposed here: (i) The size of the original problem is reduced and then the resulting model is solved with exact methods. 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 be solved to near optimality without resorting to custom solution methods. (ii) The dual information is embedded into an existing heuristic. This approach is demonstrated on a well-known local search based heuristic that was reported to obtain the most successful results on the set covering problem to this day. Our results demonstrate that the use of dual information significantly improves the efficacy of the heuristic both in terms of solution time and accuracy.

Item Type:Article
Uncontrolled Keywords:Heuristics, set covering, primal-dual heuristic, LP relaxation, dual information
Subjects:T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering > T57.6-57.97 Operations research. Systems analysis
ID Code:19359
Deposited By:Kerem Bülbül
Deposited On:27 Sep 2012 23:22
Last Modified:15 Jan 2014 20:51

Repository Staff Only: item control page