Experiments with LAGRASP heuristic for set k-covering

被引：0
作者：
Luciana S. Pessoa
Mauricio G. C. Resende
Celso C. Ribeiro
机构：
[1] Universidade Federal do Rio Grande do Norte,Department of Informatics and Applied Mathematics
[2] AT&T Labs Research,Algorithms and Optimization Research Department
[3] Universidade Federal Fluminense,Department of Computer Science
来源：
Optimization Letters | 2011年 / 5卷
关键词：
GRASP; Hybrid heuristics; Metaheuristics; Path-relinking; Lagrangean relaxation; Lagrangean heuristics; Local search; Set covering; Set multicovering; Set ; -covering;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The set k-covering problem (SCkP) is a variant of the classical set covering problem, in which each object is required to be covered at least k times. We describe a hybrid Lagrangean heuristic, named LAGRASP, which combines subgradient optimization and GRASP with path-relinking to solve the SCkP. Computational experiments carried out on 135 test instances show experimentally that by properly tuning the parameters of LAGRASP, it is possible to obtain a good trade-off between solution quality and running times. Furthermore, LAGRASP makes better use of the dual information provided by subgradient optimization and is able to discover better solutions and to escape from locally optimal solutions even after the stabilization of the lower bounds, whereas other strategies fail to find new improving solutions.
引用
收藏
页码：407 / 419
页数：12
相关论文
共 23 条
  • [1] Resende M.G.C.(2007)An optimizer in the telecommunications industry SIAM SIAG/Optim. Views News 18 8-19
  • [2] Hall N.G.(1992)The multicovering problem Eur. J. Oper. Res. 62 323-339
  • [3] Hochbaum D.S.(2009)Computational experience with general cutting planes for the Set Covering problem Oper. Res. Lett. 37 16-20
  • [4] Avella P.(1989)On the set covering polytope: I All the facets with coefficients in 0,1,2 Math. Program. Series A 43 57-69
  • [5] Boccia M.(1989)On the set covering polytope: II. Lifting the facets with coefficients in 0,1,2 Math. Program. Series A 45 1-20
  • [6] Vasilyev I.(1995)Greedy randomized adaptative search procedures J. Global Optim. 6 109-133
  • [7] Balas E.(2004)The Lagrangian relaxation method for solving integer programming problems Manag. Sci. 50 1861-1871
  • [8] Ng S.(1970)The traveling-salesman problem and minimum spanning trees Oper. Res. 18 1138-1162
  • [9] Balas E.(1971)The traveling-salesman problem and minimum spanning trees: Part II Math. Program. 1 6-25
  • [10] Ng S.(1987)An algorithm for set-covering problem Eur. J. Oper. Res. 31 85-93
123