MLQCC: an improved local search algorithm for the set k‐covering problem

• Date: 01 May 2019
• Author: Huanyao Sun,Minghao Yin,Chenxi Li,Yiyuan Wang,Jiejiang Chen
• DOI: http://doi.org/10.1111/itor.12614
• Published date: 01 May 2019

Intl. Trans. in Op. Res. 26 (2019) 856–887

DOI: 10.1111/itor.12614

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

MLQCC: an improved local search algorithm for the set

k-covering problem

Yiyuan Wang, Chenxi Li, Huanyao Sun, Jiejiang Chen and Minghao Yin

School of Computer Science and Information Technology, Northeast Normal University, Changchun130117, China

E-mail: yiyuanwangjlu@126.com [Wang]; licx935@nenu.edu.cn [Li]; sunh0056@nenu.edu.cn [Sun];

chenjj016@nenu.edu.cn [Chen]; ymh@nenu.edu.cn [Yin]

Received 8 January 2018; received in revised form 29 July 2018; accepted 24 October 2018

Abstract

The set k-covering problem (SKCP) is NP-hard and has important real-world applications. In this paper, we

propose several improvements over typical algorithms for its solution. First, we present a multilevel (ML)

score heuristic that reflects relevantinformation of the currently selected subsets inside or outside a candidate

solution. Next, we propose QCC to overcomethe cycling problem in local search. Based on the ML heuristic

and QCC strategy, we propose an effective subset selection strategy. Then, we integrate these methods into a

local search algorithm, which we called MLQCC. In addition, we propose a preprocessing method to reduce

the scale of the original problem before applying MLQCC. We further enhance MLQCC for large-scale

instances using a low-time-complexity initialization algorithm to determine an initial candidate solution,

obtaining the MLQCC +LI algorithm. The performance of the proposed MLQCC and MLQCC +LI is

verified through experimental evaluationson both classical and large-scale benchmarks. The results show that

MLQCC and MLQCC +LI notably outperform several state-of-the-art SKCP algorithms on the evaluated

benchmarks.

Keywords:set k-covering problem; local search; multilevel score heuristic; quantitative configurationchecking

1. Introduction

1.1. Problem statement

The set covering problem (SCP) can be viewed as an optimization of the unicost SCP. Given set

U={v1,v2,...,vn}and set S={S1,S2,...,Sm},Si⊆U, of subsets from U, where each Siis

associated with the positive weight w(Si), the SCP aims to determine a subset CS of Sthat covers

all the elements and has minimum weight, that is, min Sj∈CS w(Sj). A generalization of the SCP

is the set k-covering problem (SKCP) whose goal is to determine a subset CS of Sthat covers

all the elements at least ktimes and minimizes the weight of CS, which is equivalent to the SCP,

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

Y. Wanget al. / Intl. Trans. in Op. Res. 26 (2019) 856–887 857

except that it covers all the elements at least ktimes. This difference has a considerable impact on

the performance of SKCP solvers. Therefore, extensive research has been conducted on developing

such solvers given the SKCP difficulty, and many efforts are being devoted to guarantee suitable

and efficient solutions.

From a practical point of view, the SKCP appears in a wide variety of applications. In fact,

problem encoding into the SKCP is more direct, natural, and compact than that into both SCP

and unicost SCP for applications such as crew scheduling problem (Marsten and Shepardson,

1981), maintaining communications in radio-based systems (Tutschku, 1998), information retrieval

systems (Fisher and Kedia, 1990), and facility location (Vasko and Wilson, 1984). For instance,

to improve service reliability when locating telecommunications infrastructure, Resende (2007)

proposes the redundant points-of-presence placement problem, which requires coverage for each

customer by at least kpoints and can be modeled as an SKCP. Likewise, an SKCP arising in

bioinformatics is the robusttagging of single-nucleotide polymorphisms to determine the minimum

number of polymorphisms such that every pair of haplotype patterns is distinguished by at least k

polymorphisms (Huang et al., 2005; Chang et al., 2006).

1.2. Related work

The SKCP, a generalization of the SCP, has been proved to be NP-hard (Huang et al., 2005). There

are several exact SKCP algorithms whose aim is to determine the optimal solution within a prespec-

ified time limit. For instance, Hua et al. (2009) apply the inclusion–exclusion principle to solve the

SKCP and develop the corresponding family of exact algorithms. The resulting exact set multicov-

ering algorithm takes O∗((a+1)n)space and O∗((2a)n)time, where ais the maximum value in the

coverage requirement set. By considering different tradeoffs between time and space complexities,

the authors derive other three exact algorithms. In Nederlof (2008), the authors propose a solution

based on a novel counting formulation running in O∗((a+1)n|F|)time with polynomial space,

where |F|is the total number of sets. In addition, Hua et al. (2010) combine dynamic programming

and the inclusion–exclusion principle to exactly solve the SKCP with no multiplicity constraint in

O∗((a+2)n)time, and present another solution with multiplicity constraints inO∗((a+1)n)space

and O∗((a+1)n|F|)time.

Although exact algorithms havebeen demonstrated to be successful in solving the SKCP, they fail

to provide a solution within reasonable time, especially for large-scale instances, as these algorithms

perform a systematic search over the whole solution space. An alternative to solve the SKCP is

local search. As a well-known method for solving some combinatorial optimization problems, local

search allows the determination of either an approximate or even the optimal solution in short time.

Furthermore, local search maintains the previous best solution, thus being an anytime algorithm

(Zilberstein, 1996) that retrieves better solutions as the running time increases. Therefore, when

solutions demand a short time limit, local search is an effective algorithm suitable for various

real-world applications.

Local search has shown high performance for solving the unicost SCP, with several algorithms

available (Yagiura et al., 2006; Bautista and Pereira, 2007; Kinney et al., 2007; Gao et al., 2015).

Most of these algorithms can be easily adapted to the SCP. In addition, local search algorithms

specific for SCP have been proposed (Jacobs and Brusco, 1995; Caserta, 2007). In particular, a

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation of OperationalResearch Societies

858 Y. Wanget al. / Intl. Trans. in Op. Res. 26 (2019) 856–887

state-of-the-art local search algorithm for SCP was developed by Gao et al. (2014), whose ex-

perimental results show a high performance, as it can determine either every optimal solution or

retrieve the current best solution within a short time limit. Although some methods to solve the

SCP can be applied to the SKCP, they cannot achieve the performance of specialized SKCP solvers

given the SKCP requirement to cover all the elements at least ktimes. Therefore, to develop lo-

cal search algorithms for the SKCP, it is necessary to address the differences between the SKCP

and SCP.

There are few local search algorithms forSKCP,see Pessoa et al. (2013), Al-Shihabi, (2016), Wang

et al. (2017b). One of the earliest works is the hybridGRASP Lagrangean heuristic algorithm, called

LAGRASP, which employs the GRASP with path-relinking heuristic and modified costs to obtain

approximatesolutions for the original SKCP (Pessoa et al., 2013). Next, Al-Shihabi(2016) proposes

a hybrid algorithm called LP-MMAS-LS, which uses linear programming, max-min ant system,

and local search for solving large-scale instances. Likewise, Wang et al. (2017b) propose an effective

local search algorithm called DLLccsm, which is considered as a benchmark SKCP solver. This

algorithm uses the SKCPconfiguration checking to overcome the cycling problem, whichis a serious

concern arising in local search, and defines a heuristic called cost scheme to determine different

high-quality possible solutions. In fact, experiments show that DLLccsm outperforms other SKCP

solvers in terms of solution quality.

1.3. Main contributions

In this paper, we propose several improvements to the DLLccsm solver. Specifically, we design two

local search algorithms for the SKCP, called MLQCC and MLQCC +LI, where the latter is an

extension of the former for large-scale instances.

The first and more important improvement we present is a subset property called subscore,which

redefines property score (Wang et al., 2017b), as score measures some elements (i.e., uncovered or

covered ktimes) by adding or removing subsets, whereas subscore considers some elements that are

covered more than ktimes. Accordingly, we develop a new multilevel (ML) score heuristic, which is

a linear combination of subscore and score.

Next, we propose a new strategy called quantitative configuration checking (QCC), whose origi-

nal version was proposed by Cai et al. (2011), and aims to effectively overcome the cycling problem

of local search. In fact, our proposed QCC strategy is a quantitative version of the previous con-

figuration checking approach (Wang et al., 2017b), because when updating the candidate solution

by removing or adding one subset, QCC fosters to visit the subset with the smallest configuration

value, unlikethe previous strategy that only considers two configurationstates, namely, true or false.

Therefore, the proposed QCC strategy exploresthe structure of different subsets, and thus it is more

likely to visit better solution spaces.

Finally, we propose an effective subset selection strategy based on the two abovementioned

improvements. The resulting algorithm timely decides which subset should be selected. Hence, a

high-quality solution can be obtained within a reasonable time. In addition, we develop a prepro-

cessing stage that is necessary to reduce the scale of the input instances.

We combine all the above-mentioned improvements to design the MLQCC local search

algorithm. Experimental results show that the MLQCC considerably outperforms several

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies