An improved configuration checking-based algorithm for the unicost set covering problem

Yiyuan Wang, Shiwei Pan, Sameh Al-Shihabi, Junping Zhou, Nan Yang and Minghao Yin

European Journal of Operational Research, 2021, vol. 294, issue 2, 476-491

Abstract: Configuration Checking (CC) is a simple tool that can be added to local search algorithms to prevent cycling. The generic forms of CC and local search may not be suitable to solve large-scale unicost set covering problem (USCP) instances. Thus, in this study, we introduce an improved CC-based algorithm to solve USCPs. Unlike previous CC implementations that only consider subset states to prevent cycling, the proposed algorithm also checks the element states to minimize the number of subsets, in order to cut down unnecessary search spaces. Therefore, we refer to this technique as the element-state configuration checking (ES-CC) algorithm. Moreover, in our proposed algorithm, the score value (a numerical measure to differentiate between subsets) considers multiple levels of element covering. This multi-level scoring (MLS) value is a new powerful contribution compared to the single-level scoring used in previous CC algorithms. Using these two novel ideas, MLS and ES-CC, we implement the new MLSES-CC algorithm to solve the USCP. The MLSES-CC algorithm also implements a more aggressive local search routine that simultaneously changes the status of the three subsets. We use the MLSES-CC algorithm to solve 176 USCP instances that belong to standard and novel benchmarking sets and compare our results to the best-known USCP algorithms, in terms of solution quality and computation time. Computational experiments indicate that the MLSES-CC algorithm can be considered as a new state-of-the-art algorithm to solve USCPs.

Keywords: Combinatorial optimization; Unicost set covering; Local search; Multi-level scoring function; Element state-based configuration checking (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722172100093X
Full text for ScienceDirect subscribers only

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:eee:ejores:v:294:y:2021:i:2:p:476-491

DOI: 10.1016/j.ejor.2021.02.015

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().