An effective population-based approach for the partial set covering problem

Ye Zhang (), Jinlong He (), Yupeng Zhou (), Shuli Hu (), Dunbo Cai (), Naiyu Tian () and Minghao Yin ()
Additional contact information
Ye Zhang: Northeast Normal University
Jinlong He: Northeast Normal University
Yupeng Zhou: Northeast Normal University
Shuli Hu: Northeast Normal University
Dunbo Cai: China Mobile (Suzhou) Software Technology Company Ltd.
Naiyu Tian: Nanjing Research Institute of Electronic Engineering
Minghao Yin: Northeast Normal University

Journal of Heuristics, 2025, vol. 31, issue 1, No 17, 32 pages

Abstract: Abstract The partial set covering problem (PSCP) is a significant combinatorial optimization problem that finds applications in numerous real-world scenarios. The objective of PSCP is to encompass a minimum number of subsets while ensuring the coverage of at least n elements. Due to its NP-hard nature, solving large-scale PSCP efficiently remains a critical issue in computational intelligence. To effectively tackle this challenge, we delve into a population-based approach that incorporates a modified tabu search, thereby striking a delicate balance between exploration and exploitation. To further enhance its efficacy, we employ the multiple path-relinking strategy and the fix-and-optimize process. Finally, the dynamic resource allocation scheme is utilized to save computing efforts. Comparative experiments of the proposed algorithm were conducted against three state-of-the-art competitors, across two distinct categories, encompassing 150 instances. The results significantly underscore the profound effectiveness of our proposed algorithm, as evidenced by the updating of 67 best-known solutions. Moreover, we conduct an in-depth analysis of the key components inherent to the algorithm, shedding light on their respective influences on the whole performance.

Keywords: Partial set covering; Tabu search; Multiple path-relinking; Fix-and-optimize; Dynamic resource allocation (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-025-09552-7 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:joheur:v:31:y:2025:i:1:d:10.1007_s10732-025-09552-7

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

DOI: 10.1007/s10732-025-09552-7

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

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