An algorithm for approximating the Pareto set of the multiobjective set covering problem

Lakmali Weerasena (), Margaret M. Wiecek and Banu Soylu
Additional contact information
Lakmali Weerasena: Clemson University
Margaret M. Wiecek: Clemson University
Banu Soylu: Erciyes University

Annals of Operations Research, 2017, vol. 248, issue 1, No 20, 493-514

Abstract: Abstract The multiobjective set covering problem (MOSCP), a challenging combinatorial optimization problem, has received limited attention in the literature. This paper presents a heuristic algorithm to approximate the Pareto set of the MOSCP. The proposed algorithm applies a local branching approach on a tree structure and is enhanced with a node exploration strategy specially developed for the MOSCP. The main idea is to partition the search region into smaller subregions based on the neighbors of a reference solution and then to explore each subregion for the Pareto points of the MOSCP. Numerical experiments for instances with two, three and four objectives set covering problems are reported. Results on a performance comparison with benchmark algorithms from the literature are also included and show that the new algorithm is competitive and performs best on some instances.

Keywords: Multiobjective set covering problem; Heuristics; Local branching; Tree-based search (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-016-2229-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:248:y:2017:i:1:d:10.1007_s10479-016-2229-x

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

DOI: 10.1007/s10479-016-2229-x

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 ().