Result: Two-phase method and Lagrangian relaxation to solve the Bi-Objective Set Covering Problem
Title:
Two-phase method and Lagrangian relaxation to solve the Bi-Objective Set Covering Problem
Contributors:
Gavrysiak, Daniel, Laboratoire d'Optimisation des Systèmes Industriels (LOSI), Institut Charles Delaunay (ICD), Université de Technologie de Troyes (UTT)-Centre National de la Recherche Scientifique (CNRS)-Université de Technologie de Troyes (UTT)-Centre National de la Recherche Scientifique (CNRS)
Source:
Annals of Operations Research
Annals of Operations Research, 2006, 147 (1), pp.23-41. ⟨10.1007/s10479-006-0060-5⟩
Annals of Operations Research, 2006, 147 (1), pp.23-41. ⟨10.1007/s10479-006-0060-5⟩
Publisher Information:
Springer Science and Business Media LLC, 2006.
Publication Year:
2006
Subject Terms:
0211 other engineering and technologies, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], 02 engineering and technology, Multi-objective combinatorial optimization, Lagrangean relaxation, [INFO.INFO-RO] Computer Science [cs]/Operations Research [math.OC], Set covering problem
Document Type:
Academic journal
Article
Language:
English
ISSN:
1572-9338
0254-5330
0254-5330
DOI:
10.1007/s10479-006-0060-5
Access URL:
https://ideas.repec.org/a/spr/annopr/v147y2006i1p23-4110.1007-s10479-006-0060-5.html
https://econpapers.repec.org/RePEc:spr:annopr:v:147:y:2006:i:1:p:23-41:10.1007/s10479-006-0060-5
https://link.springer.com/content/pdf/10.1007%2Fs10479-006-0060-5.pdf
https://dblp.uni-trier.de/db/journals/anor/anor147.html#PrinsPC06
https://link.springer.com/article/10.1007/s10479-006-0060-5
https://utt.hal.science/hal-02525221
https://econpapers.repec.org/RePEc:spr:annopr:v:147:y:2006:i:1:p:23-41:10.1007/s10479-006-0060-5
https://link.springer.com/content/pdf/10.1007%2Fs10479-006-0060-5.pdf
https://dblp.uni-trier.de/db/journals/anor/anor147.html#PrinsPC06
https://link.springer.com/article/10.1007/s10479-006-0060-5
https://utt.hal.science/hal-02525221
Rights:
Springer TDM
Accession Number:
edsair.doi.dedup.....30f88c80e374e7ab0a91451c28c8f4be
Database:
OpenAIRE
Further Information
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.