# 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] Fengmin Wang, Dachuan Xu, Donglei Du, Chenchen Wu. Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 91-100. doi: 10.3934/naco.2015.5.91 [2] Jen-Yen Lin, Hui-Ju Chen, Ruey-Lin Sheu. Augmented Lagrange primal-dual approach for generalized fractional programming problems. Journal of Industrial & Management Optimization, 2013, 9 (4) : 723-741. doi: 10.3934/jimo.2013.9.723 [3] Gianni Di Pillo, Giampaolo Liuzzi, Stefano Lucidi. A primal-dual algorithm for nonlinear programming exploiting negative curvature directions. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 509-528. doi: 10.3934/naco.2011.1.509 [4] Kai Wang, Deren Han. On the linear convergence of the general first order primal-dual algorithm. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021134 [5] Yu-Hong Dai, Xin-Wei Liu, Jie Sun. A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs. Journal of Industrial & Management Optimization, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190 [6] Xiaojing Ye, Haomin Zhou. Fast total variation wavelet inpainting via approximated primal-dual hybrid gradient algorithm. Inverse Problems & Imaging, 2013, 7 (3) : 1031-1050. doi: 10.3934/ipi.2013.7.1031 [7] Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211 [8] Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37 [9] Yixuan Yang, Yuchao Tang, Meng Wen, Tieyong Zeng. Preconditioned Douglas-Rachford type primal-dual method for solving composite monotone inclusion problems with applications. Inverse Problems & Imaging, 2021, 15 (4) : 787-825. doi: 10.3934/ipi.2021014 [10] Yu-Hong Dai, Zhouhong Wang, Fengmin Xu. A Primal-dual algorithm for unfolding neutron energy spectrum from multiple activation foils. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2367-2387. doi: 10.3934/jimo.2020073 [11] Guoqiang Wang, Zhongchen Wu, Zhongtuan Zheng, Xinzhong Cai. Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101 [12] Nadia Hazzam, Zakia Kebbiche. A primal-dual interior point method for $P_{\ast }\left( \kappa \right)$-HLCP based on a class of parametric kernel functions. Numerical Algebra, Control & Optimization, 2021, 11 (4) : 513-531. doi: 10.3934/naco.2020053 [13] Masaaki Harada, Akihiro Munemasa. On the covering radii of extremal doubly even self-dual codes. Advances in Mathematics of Communications, 2007, 1 (2) : 251-256. doi: 10.3934/amc.2007.1.251 [14] Tsan-Ming Choi. Quick response in fashion supply chains with dual information updating. Journal of Industrial & Management Optimization, 2006, 2 (3) : 255-268. doi: 10.3934/jimo.2006.2.255 [15] Mingyong Lai, Hongzhao Yang, Erbao Cao, Duo Qiu, Jing Qiu. Optimal decisions for a dual-channel supply chain under information asymmetry. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1023-1040. doi: 10.3934/jimo.2017088 [16] Chunrong Chen, Shengji Li. Upper Hölder estimates of solutions to parametric primal and dual vector quasi-equilibria. Journal of Industrial & Management Optimization, 2012, 8 (3) : 691-703. doi: 10.3934/jimo.2012.8.691 [17] Darryl D. Holm, Cornelia Vizman. Dual pairs in resonances. Journal of Geometric Mechanics, 2012, 4 (3) : 297-311. doi: 10.3934/jgm.2012.4.297 [18] Paul Skerritt, Cornelia Vizman. Dual pairs for matrix groups. Journal of Geometric Mechanics, 2019, 11 (2) : 255-275. doi: 10.3934/jgm.2019014 [19] Andrzej Nowakowski, Jan Sokolowski. On dual dynamic programming in shape control. Communications on Pure & Applied Analysis, 2012, 11 (6) : 2473-2485. doi: 10.3934/cpaa.2012.11.2473 [20] Alexis Eduardo Almendras Valdebenito, Andrea Luigi Tironi. On the dual codes of skew constacyclic codes. Advances in Mathematics of Communications, 2018, 12 (4) : 659-679. doi: 10.3934/amc.2018039

2020 Impact Factor: 1.801