Two-phase method and Lagrangian relaxation to solve the Bi-Objective Set Covering Problem

Christian Prins (), Caroline Prodhon () and Roberto Calvo ()

Annals of Operations Research, 2006, vol. 147, issue 1, 23-41

Abstract: This paper deals with the Bi-Objective Set Covering Problem, which is a generalization of the well-known Set Covering Problem. The proposed approach is a two-phase heuristic method which has the particularity to be a constructive method using the primal-dual Lagrangian relaxation to solve single objective Set Covering problems. The results show that this algorithm finds several potentially supported and unsupported solutions. A comparison with an exact method (up to a medium size), shows that many Pareto-optimal solutions are retrieved and that the other solutions are well spread and close to the optimal ones. Moreover, the method developed compares favorably with the Pareto Memetic Algorithm proposed by Jaszkiewicz. Copyright Springer Science + Business Media, LLC 2006

Keywords: Multi-objective combinatorial optimization; Lagrangean relaxation; Set covering problem (search for similar items in EconPapers)
Date: 2006
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-006-0060-5 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:147:y:2006:i:1:p:23-41:10.1007/s10479-006-0060-5

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-006-0060-5

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().