Optimization Online


The Set Covering Problem Revisited: An Empirical Study of the Value of Dual Information

Belma Yelbay (byelbay***at***su.sabanciuniv.edu)
S. Ilker Birbil (sibirbil***at***sabanciuniv.edu)
Kerem Bulbul (bulbul***at***sabanciuniv.edu)

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 successful results on the set covering problem. Our results demonstrate that the use of dual information significantly improves the efficacy of the heuristic in terms of both solution time and accuracy.

Keywords: Heuristics, set covering, primal-dual heuristic, LP relaxation, dual information

Category 1: Integer Programming

Citation: Yelbay, B., Birbil, S. I., and Bulbul, K. (2015). The Set Covering Problem Revisited: An Empirical Study of the Value of Dual Information. Journal of Industrial and Management Optimization, 11(2): 575-594. http://dx.doi.org/10.3934/jimo.2015.11.575

Download: [PDF]

Entry Submitted: 11/14/2010
Entry Accepted: 11/14/2010
Entry Last Modified: 09/21/2015

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