Skip to Main content Skip to Navigation
Journal articles

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

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.
Document type :
Journal articles
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02525221
Contributor : Daniel Gavrysiak <>
Submitted on : Monday, March 30, 2020 - 6:25:24 PM
Last modification on : Wednesday, May 20, 2020 - 11:58:04 AM

Links full text

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

Christian Prins, Caroline Prodhon, Roberto Wolfler Calvo. Two-phase method and Lagrangian relaxation to solve the Bi-Objective Set Covering Problem. Annals of Operations Research, Springer Verlag, 2006, 147 (1), pp.23-41. ⟨10.1007/s10479-006-0060-5⟩. ⟨hal-02525221⟩

Share

Metrics

Record views

16