IDEAS home Printed from https://ideas.repec.org/a/spr/joheur/v31y2025i1d10.1007_s10732-025-09552-7.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Ye Zhang & Jinlong He & Yupeng Zhou & Shuli Hu & Dunbo Cai & Naiyu Tian & Minghao Yin, 2025. "An effective population-based approach for the partial set covering problem," Journal of Heuristics, Springer, vol. 31(1), pages 1-32, March.
  • Handle: RePEc:spr:joheur:v:31:y:2025:i:1:d:10.1007_s10732-025-09552-7
    DOI: 10.1007/s10732-025-09552-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10732-025-09552-7
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10732-025-09552-7?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Gao, Chao & Yao, Xin & Weise, Thomas & Li, Jinlong, 2015. "An efficient local search heuristic with row weighting for the unicost set covering problem," European Journal of Operational Research, Elsevier, vol. 246(3), pages 750-761.
    2. López-Ibáñez, Manuel & Dubois-Lacoste, Jérémie & Pérez Cáceres, Leslie & Birattari, Mauro & Stützle, Thomas, 2016. "The irace package: Iterated racing for automatic algorithm configuration," Operations Research Perspectives, Elsevier, vol. 3(C), pages 43-58.
    3. Wang, Yiyuan & Pan, Shiwei & Al-Shihabi, Sameh & Zhou, Junping & Yang, Nan & Yin, Minghao, 2021. "An improved configuration checking-based algorithm for the unicost set covering problem," European Journal of Operational Research, Elsevier, vol. 294(2), pages 476-491.
    4. Ran, Yingli & Zhang, Ying & Zhang, Zhao, 2021. "Parallel approximation for partial set cover," Applied Mathematics and Computation, Elsevier, vol. 408(C).
    5. Alberto Caprara & Paolo Toth & Matteo Fischetti, 2000. "Algorithms for the Set Covering Problem," Annals of Operations Research, Springer, vol. 98(1), pages 353-371, December.
    6. Masoud Yaghini & Mohammad Karimi & Mohadeseh Rahbar, 2015. "A set covering approach for multi-depot train driver scheduling," Journal of Combinatorial Optimization, Springer, vol. 29(3), pages 636-654, April.
    7. Beasley, J. E. & Jornsten, K., 1992. "Enhancing an algorithm for set covering problems," European Journal of Operational Research, Elsevier, vol. 58(2), pages 293-300, April.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Wang, Yiyuan & Pan, Shiwei & Al-Shihabi, Sameh & Zhou, Junping & Yang, Nan & Yin, Minghao, 2021. "An improved configuration checking-based algorithm for the unicost set covering problem," European Journal of Operational Research, Elsevier, vol. 294(2), pages 476-491.
    2. Lan, Guanghui & DePuy, Gail W. & Whitehouse, Gary E., 2007. "An effective and simple heuristic for the set covering problem," European Journal of Operational Research, Elsevier, vol. 176(3), pages 1387-1403, February.
    3. Patrizia Beraldi & Andrzej Ruszczyński, 2002. "The Probabilistic Set-Covering Problem," Operations Research, INFORMS, vol. 50(6), pages 956-967, December.
    4. Nguyen, Tri-Dung, 2014. "A fast approximation algorithm for solving the complete set packing problem," European Journal of Operational Research, Elsevier, vol. 237(1), pages 62-70.
    5. S. Haddadi, 2017. "Benders decomposition for set covering problems," Journal of Combinatorial Optimization, Springer, vol. 33(1), pages 60-80, January.
    6. Mehdi Firoozbakht & Hamidreza Vosoughifar & Alireza Ghari Ghoran, 2019. "Coverage intensity of optimal sensors for common, isolated, and integrated steel structures using novel approach of FEM-MAC-TTFD," International Journal of Distributed Sensor Networks, , vol. 15(8), pages 15501477198, August.
    7. Andreas M. Tillmann, 2019. "Computing the spark: mixed-integer programming for the (vector) matroid girth problem," Computational Optimization and Applications, Springer, vol. 74(2), pages 387-441, November.
    8. J. E. Beasley, 2024. "An optimal algorithm for variable knockout problems," 4OR, Springer, vol. 22(4), pages 419-433, December.
    9. Gao, Chao & Yao, Xin & Weise, Thomas & Li, Jinlong, 2015. "An efficient local search heuristic with row weighting for the unicost set covering problem," European Journal of Operational Research, Elsevier, vol. 246(3), pages 750-761.
    10. Coslovich, Luca & Pesenti, Raffaele & Ukovich, Walter, 2006. "Minimizing fleet operating costs for a container transportation company," European Journal of Operational Research, Elsevier, vol. 171(3), pages 776-786, June.
    11. Asghari, Mohammad & Jaber, Mohamad Y. & Mirzapour Al-e-hashem, S.M.J., 2023. "Coordinating vessel recovery actions: Analysis of disruption management in a liner shipping service," European Journal of Operational Research, Elsevier, vol. 307(2), pages 627-644.
    12. Alex Gliesch & Marcus Ritt, 2022. "A new heuristic for finding verifiable k-vertex-critical subgraphs," Journal of Heuristics, Springer, vol. 28(1), pages 61-91, February.
    13. Carolina G. Marcelino & João V. C. Avancini & Carla A. D. M. Delgado & Elizabeth F. Wanner & Silvia Jiménez-Fernández & Sancho Salcedo-Sanz, 2021. "Dynamic Electric Dispatch for Wind Power Plants: A New Automatic Controller System Using Evolutionary Algorithms," Sustainability, MDPI, vol. 13(21), pages 1-20, October.
    14. Elisama Araújo Silva Oliveira & Elizabeth Wanner & Elisangela Martins Sá & Sérgio Ricardo Souza, 2025. "A local branching-based solution for the multi-period cutting stock problem with tardiness, earliness, and setup costs," Journal of Heuristics, Springer, vol. 31(1), pages 1-57, March.
    15. Arda, Yasemin & Cattaruzza, Diego & François, Véronique & Ogier, Maxime, 2024. "Home chemotherapy delivery: An integrated production scheduling and multi-trip vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 317(2), pages 468-486.
    16. İbrahim Muter & Ş. İlker Birbil & Güvenç Şahin, 2010. "Combination of Metaheuristic and Exact Algorithms for Solving Set Covering-Type Optimization Problems," INFORMS Journal on Computing, INFORMS, vol. 22(4), pages 603-619, November.
    17. Véronique François & Yasemin Arda & Yves Crama, 2019. "Adaptive Large Neighborhood Search for Multitrip Vehicle Routing with Time Windows," Transportation Science, INFORMS, vol. 53(6), pages 1706-1730, November.
    18. Ofer M. Shir & Xi. Xing & Herschel. Rabitz, 2021. "Multi-level evolution strategies for high-resolution black-box control," Journal of Heuristics, Springer, vol. 27(6), pages 1021-1055, December.
    19. R. Baldacci & E. Hadjiconstantinou & A. Mingozzi, 2004. "An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation," Operations Research, INFORMS, vol. 52(5), pages 723-738, October.
    20. Beasley, J. E. & Chu, P. C., 1996. "A genetic algorithm for the set covering problem," European Journal of Operational Research, Elsevier, vol. 94(2), pages 392-404, October.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:joheur:v:31:y:2025:i:1:d:10.1007_s10732-025-09552-7. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.