# American Institute of Mathematical Sciences

• Previous Article
Bilevel multi-objective construction site security planning with twofold random phenomenon
• JIMO Home
• This Issue
• Next Article
Optimality conditions for strong vector equilibrium problems under a weak constraint qualification
April  2015, 11(2): 575-594. doi: 10.3934/jimo.2015.11.575

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

 1 Sabancl University, Manufacturing Systems and Industrial Engineering, Orhanl1-Tuzla, 34956 Istanbul, Turkey 2 Sabanci University, Manufacturing Systems and Industrial Engineering, Orhanli-Tuzla, 34956 Istanbul, Turkey, Turkey

Received  September 2013 Revised  April 2014 Published  September 2014

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.
Citation: Belma Yelbay, Ş. İlker Birbil, Kerem Bülbül. The set covering problem revisited: An empirical study of the value of dual information. Journal of Industrial & Management Optimization, 2015, 11 (2) : 575-594. doi: 10.3934/jimo.2015.11.575
##### References:

show all references

##### References:
 [1] Juliang Zhang, Jian Chen. Information sharing in a make-to-stock supply chain. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1169-1189. doi: 10.3934/jimo.2014.10.1169 [2] Tuvi Etzion, Alexander Vardy. On $q$-analogs of Steiner systems and covering designs. Advances in Mathematics of Communications, 2011, 5 (2) : 161-176. doi: 10.3934/amc.2011.5.161 [3] Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119 [4] Guido De Philippis, Antonio De Rosa, Jonas Hirsch. The area blow up set for bounded mean curvature submanifolds with respect to elliptic surface energy functionals. Discrete & Continuous Dynamical Systems - A, 2019, 39 (12) : 7031-7056. doi: 10.3934/dcds.2019243

2019 Impact Factor: 1.366