Optimization Online


A hybrid Lagrangean heuristic with GRASP and path-relinking for set K-covering

Luciana S. Pessoa(lspessoa***at***gmail.com)
Mauricio G.C. Resende(mgcr***at***research.att.com)
Celso C. Ribeiro(celso***at***ic.uff.br)

Abstract: The set multicovering or set K-covering problem is an extension of the classical set covering problem, in which each object is required to be covered at least K times. The problem finds applications in the design of communication networks and in computational biology. We describe a GRASP with path-relinking heuristic for the set K-covering problem, as well as the template of a family of Lagrangean heuristics. The hybrid GRASP Lagrangean heuristic employs the GRASP with path-relinking heuristic using modified costs to obtain solutions for the Lagrangean relaxation problem. Computational experiments carried out on 135 test instances show experimentally that the Lagrangean heuristics performed consistently better than GRASP. By properly tuning the parameters of the GRASP Lagrangean heuristic, it is possible to obtain a good trade-off between solution quality and running times. Furthermore, the GRASP Lagrangean heuristic 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, when other strategies fail to find new improving solutions.

Keywords: GRASP, hybrid heuristics, metaheuristics, path-relinking, Lagrangean relaxation, Lagrangean heuristics, local search, set covering, set multicovering, set K-covering

Category 1: Combinatorial Optimization (Meta Heuristics )

Citation: AT&T Labs Research Technical Report, Florham Park, New Jersey, December 2010.

Download: [PDF]

Entry Submitted: 12/28/2010
Entry Accepted: 12/30/2010
Entry Last Modified: 12/28/2010

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 Programming Society