A GRASP-based scheme for the set covering problem

Abstract

In this work we present a greedy randomized adaptive search procedure (GRASP)-based strategy for the set covering problem. The goal of this problem is to find a subset of columns from a zero-one matrix in order to cover all the rows with the minimal possible cost. The GRASP is a technique that through a sequential and finite number of steps constructs a solution using a set of simple randomized rules. Additionally, we also propose an iterated local search and reward/penalty procedures in order to improve the solutions found by the GRASP. Our approach has been tested using the well-known 65 non-unicost SCP benchmark instances from OR-library showing promising results.

1 Introduction

The non-unicost set covering problem (SCP) is a combinatorial problem that can be described as the problem of finding a subset of columns x from a m-row, n-column zero-one matrix A such that they cover all the rows of A at minimal cost. The SCP can be formulated as follows:

$$\begin{aligned} \begin{aligned} \text {minimize}&\quad \sum _{j=1}^{n} c_{j}x_{j} \\ \text {subject to}&\quad \sum _{j=1}^{n} a_{ij}x_{j}\ge 1, \; i \in \{1,2,\ldots ,m\}, \\&\quad x_{j} \in \{0,1\}. \end{aligned} \end{aligned}$$

where $c_{j}$ is a n-size vector that represents the cost of each column in A. The SCP is an NP-hard problem (Garey and Johnson 1979) that can be used to model many different problems such as crew scheduling (Bartholdi 1981), data bases (Munagala et al. 2005), vehicle routing (Bramel and Simchi-Levi 1997), among others. Several kind of algorithms have been developed for solving SCP instances. Preliminary works used exact algorithms, such as branch and bound and branch and cut strategies (Balas and Carrera 1996; Beasley 1987), however large SCP instances were intractable for them. Greedy algorithms (Chvatal 1979) are a good approach for large SCP instances, but they rarely generate good solutions because of its myopic and deterministic nature. Nevertheless, a greedy algorithm proposed in Lan and DePuy (2006) addresses these problems by incorporating randomization and memory to the process. Metaheuristics, such as genetic algorithms (Beasley and Chu 1996; Solar et al. 2002), simulated annealing (Brusco et al. 1999), ant colonies (Crawford et al. 2014), have been the most common approach to solve SCP instances. Also, modern metaheuristics (García et al. 2017, 2019; Crawford et al. 2016, 2015; Lu and Vasko 2015) have been used in the recent years.

In this work we present a greedy randomized adaptive search procedure (GRASP) (Resende and Ribeiro 2010) strategy for solving the SCP. GRASP is a random iterative optimization procedure that works in two phases: a constructive and a local search phase. At the constructive phase, the procedure uses a randomized greedy heuristic in order to obtain an initial solution. For instance, unlike deterministic greedy heuristics, at each step the procedure selects one of the most promising columns from a set with size defined by the user. This can be seen as an exploration phase. On the other hand the local search phase allows the algorithm to exploit the neighborhood of the initial solution hoping to find much higher quality solutions. For instance, a swap method can be performed between an instantiated and an uninstantiated column.

Besides the SCP, GRASP-based techniques have been used extensively to solve similar operational research problems, such as the unicost SCP (Bautista and Pereira 2007), the maximum covering problem (Resende 1998), the max−min diversity problem (Resende et al. 2010), the set-k covering (Pessoa et al. 2013), among others. Despite the difference between these problems, the GRASP phases are quite similar. At the constructive phase most of the approaches construct a limited list of promising columns, assigning a probability to each of them according to a certain rule, varying from the number of uncovered rows to more sophisticated functions. On the other hand, at the local search phase, most techniques are based on 0–1 swap movements between columns. Additionally, penalizing procedures for the columns are very common in order to retrieve information at the local search phase.

Meta-RaPS is one of the most well-known GRASP-based solvers used to solve SCP instances (Lan et al. 2007). At the beginning, Meta-RaPS constructs a solution by introducing randomness using two rule parameters: $\%$priority and $\%$restriction. The first one determines the percentage of time that the best feasible element will be chosen. The remaining time, the element added to the solution will be randomly chosen from a candidate list. The second rule is used to determine the level of acceptance and thus the size of the candidate list. A set of rules are used to evaluate each column. After a feasible solution is constructed, a local search method is a applied in order to improve the current solution. A number of columns are removed from the solution while the other are fixed by using a user-defined parameter. Finally, it uses adaptive memory mechanisms, that is, save information from the construction phase in order to obtain better solutions. This last procedure can be seen as elite methods used in genetic algorithms for the columns.

Unlike other techniques, our approach first selects the uncovered row with the smallest number of columns that can cover this row. Then we use the same set of rules as Meta-RaPS for evaluating these columns, instantiating one of them according to a probability. The process is repeated until a solution is fully generated. In the local search phase we perform an iterated local search (ILS) to the found solution. The process is based in a divide and conquer scheme, i.e, we divide the solution in two random halves, we reset one of them (perturbation) and restart the construction from this partial solution. Additionally, we use a reward/penalty procedure to each column after the second phase is applied. This last procedure is used to improve the rate of convergence of our approach. We think that the main differences of our approach, related to other GRASP-based approaches, are:

• 1. It does not require an additional user-defined parameter for restricting the size of the list of promising columns.

• 2. It does not require any parameter besides the reward/penalty procedure.

• 3. Compared to modern metaheuristics our approach does not demands high tuning effort of its parameters for an optimal performance.

Although our approach is simpler and more general than other state-of-the-art algorithms, it still offers competitive and promising results in well-known set of SCP instances from OR-library and in a new set of large instance SCPs proposed in Umetani (2017).

The rest of the paper is organized as follows. In Sect. 2 we describe our approach in detail. In Sect. 3 we show the experimental results using our approach and in Sect. 4 we present the conclusions and our future work.

2 A GRASP-based technique for the SCP

In this section we describe in detail our approach for solving and finding quality solutions for the SCP. The algorithm works in two phases. The first phase consists in constructing iterative a solution using a set of simple rules for evaluating and instantiating the columns of the input matrix A. After the solution is constructed we proceed to repair it by using an iterated local search procedure. In this phase we use a divide and conquer scheme for dividing the solution, resetting a part of it and starting the search again from this point. The whole procedure is repeated until reaching a time limit.

Additionally, we use a reward/penalty mechanism for penalizing the columns of the matrix in order to accelerate the convergence of the whole strategy.

2.1 Constructing a random solution

In this section we describe how our algorithm constructs a solution. First, we construct a map structure that maps each row to the set of columns that cover it. We sort this mapping from the lowest to the highest number of columns. For example, if we use the following A input matrix and the vector cost c:

$$\begin{aligned} A= \begin{bmatrix} 1&0&0&1&0&0&1 \\ 0&1&1&0&0&0&0 \\ 0&1&0&1&1&0&0 \\ 1&0&1&0&1&0&1 \\ 0&0&0&1&1&0&1 \\ \end{bmatrix} ;\quad c = \begin{bmatrix} 1&2&3&4&5&6&2 \end{bmatrix} \end{aligned}$$

(1)

We obtain the following map:

$$\begin{aligned} {\begin{matrix} r_{2} \rightarrow &{} 2,3\\ r_{1} \rightarrow &{} 1,4,7\\ r_{3} \rightarrow &{} 2,4,5\\ r_{5} \rightarrow &{} 4,5,7\\ r_{4} \rightarrow &{} 1,3,5,7\\ \end{matrix}} \end{aligned}$$

(2)

The rows are then covered in the order disposed by the structure. For each uncovered row, we instantiate one column to cover it. For rows that may be covered by only one column, we simply instantiate the corresponding column (see Sect. 2.4). For each row with two or more columns, we evaluate its columns j by using a function f(j) selected randomly from a set of six evaluation functions proposed in Lan and DePuy (2006): $c_{j}/p_{j}$, $c_{j}/\log {(1+p_{j})}$, $c_{j}/\sqrt{p_{j}}$, $c_{j}/p_{j}^{2}$, $\sqrt{c_{j}}/p_{j}$ , $c_{j}/p_{j}\log {p_{j}}$; where $c_{j}$ is the cost of the column j and $p_{j}$ represents the number of rows that may be covered by the column j (not counting the already covered rows). The idea of such amount of functions is to maintain diversity among the solutions constructed in this phase. Once we evaluate the columns, we propose two criteria to select the column to instantiate:

• Instantiate the column j with probability proportional to $-f(j)$

• Instantiate the column j minimizing f(j)

Note that, according to the evaluation functions and the selection criteria, columns that covers more rows with a low cost are more likely to be instantiated.

The first criterion is applied with a probability of $\frac{1}{\#cols}$ and the second one with a probability of $1-\frac{1}{\#cols}$, where $\#cols$ is the number of columns that can cover the current row. After instantiating a column, all the rows covered by this column are also removed from the map (2).

Going back to our example, we have to select one of the columns (2 or 3) in order to cover the row $r_{2}$ [see (2)]. Suppose that the function $f(j)=c_{j}/p_{j}$ is selected, thus evaluating the columns we obtain $f(2)=1$ and $f(3)=1.5$. The first selection criterion would select the column 2 with a probability of 0.6 and the column 3 with a probability 0.4. On the other hand, the second criterion would select the second column.

Algorithm 1 shows the procedure related to this phase, where:

• The method create-pairs generates the sorted map (2) by using the input matrix A.

• The while loop is performed until the map is empty, i.e., all the rows are covered.

• The procedure $\text{ random-function }$ selects one of the six random evaluation functions.

2.2 Iterated local search (ILS)

Although using the procedure random-greedy leads to quality solutions, there is still a considerable gap between the solution fitness and optimum (see Fig. 1). Thus, we propose a method for improving the generated solutions.

Algorithm 2 shows the procedure. The idea is to take the solution and reset a random part of it, i.e. setting some variables $x_{j}$ to 0, and solving the problem again from this state. To do that, first we group randomly the variables into two lists: $L_1$ and $L_2$ (line 6). These lists are also put into a queue of lists Q. We pop a list L from Q and each $x_{j}$ in this list is set to 0. Then, we reuse the procedure random-greedy to complete the solution. We apply the procedure with some minor modifications:

• The columns in the map are restricted to the corresponding variables in L.

• In each iteration we simply select the column minimizing the value $c_{j}/p_{j}$, i.e., lines 6–11 are replaced by line 10 with $f(j)=c_{j}/p_{j}$.

If the new generated solution $x'$ is better than the previous one, then we replace the previous solution and the variables in L are grouped into two new lists. These new lists are pushed into Q. If the new solution $x'$ does not show any improvements to the solution, it is simply discarded. Then the process is repeated until Q is empty. If any of the lists of the current queue Q produces an improvement of the solution, then the whole process is repeated.

2.3 The reward/penalty procedure

As is explained above, the construction and ILS procedures are repeated until a time limit is reached. Then, the best solution found so far is returned. One issue related to this strategy is that no information about the good or bad decisions is extracted or used during the search.

Thus, in this section we propose a simple reward—penalty procedure for extracting and using information during the search. This mechanism hopefully will allow us to improve the process for generating quality solutions.

Our reward/penalty procedure simply assigns a penalty to each column of the matrix. At the beginning of the search, the penalty of each column is initialized to 1. If the method ILS improves the solution quality, then the penalties are updated in the following way:

• If the column j is instantiated in the last reported solution, then its penalty $p_j$ decreases in $\alpha >0$.

• If the column j is not instantiated in the last reported solution, then its penalty $p_j$ increases in $\beta >0$

Finally, instead of using the value of f(j), we use $p_{j}*f(j)$ for selecting the next column in the methods random-greedy and random-greedy$^{*}$. Note that high values of $p_j$ decreases the likelihood of selecting the column j and vice versa. In order to avoid local optima we have limited the value of each penalty to the interval [min, max].

2.4 Pre-processing

In order to reduce the size of the different SCP instances, we used two well known pre-processing procedures before the actual search: column domination and column inclusion (Fisher and Kedia 1990).

2.4.1 Column domination

If the set of rows covered by a column j is also covered by another column $j'$ with a lower cost, then we said that j is dominated by $j'$. Dominated columns are removed from A.

2.4.2 Column inclusion

If a row is only covered by one column, then this column is included in every solution.

3 Experiments

Our proposal has been implemented in C++,¹ on an 2.4GHz CPU Intel Core i7-4700MQ with 8GB RAM computer using Ubuntu 16.04 LTS x86_64. In order to test the proposal, we used the 65 non-unicost SCP instances from OR-library² which are described in Table 1. Optimal solutions are known for all of these instances. The results of the experiments are evaluated using: the mean value, the standard deviation and the relative percentage deviation (RPD). The RPD quantifies the deviation of the objective value x from the best known value $x^{*}$. This value is computed as follows:

$$\begin{aligned} RPD=\left( \frac{x-x^{*}}{x^{*}}\right) \times 100 \end{aligned}$$

Strategies were run 30 times on each instance. On each table we show the best known solution (column Best-sol), the mean cost of the solutions found by our approach (column mean), the standard deviation of the costs (column $\sigma$), the minimum cost found considering all the runs (column min) and the RPD related to the minimum cost. The algorithm stops when 20 seconds pass since the last best solution was found.

Table 1 Detail of the test instances

3.1 Measuring the solution quality from the construction phase

As a first experiment, we would like to measure the solution quality (cost) generated by our random greedy approach.

Fig. 1

Quality of solutions generated by the random greedy

In Fig. 1 we show the RPD corresponding to the random greedy for each of the 65 instances. As it can be seen the greedy by itself can not reach to any optimum solution in these instances. However, we expect that the ILS algorithm can improve the generated solutions, converging to the optimum in a reasonable time.

3.2 Measuring the impact of the ILS algorithm

In this section we show the improving provided by the ILS process.

As a first experiment we show the importance of using a grouping list of size 2, as is shown in the algorithm 2. In Fig. 2 we show the comparison between using 2,3,4 and 5 grouping lists.

Fig. 2

Comparison of different sizes of repairing lists. The y-axis shows the accumulative RPD value while the x-axis indicates to the instance set

From this result, we can see that increasing the number of initial partitions has a negative outcome on the quality of the solution provided from our approach. This can be explained because as we increment the number of initial partitions the ILS process has less impact as a more local search is performed, i.e., it is more difficult to leave local optima. Additionally, we also report that the convergence is in average a $25\%$ slower w.r.t. a grouping of size 2.

Table 2 reports the results using the construction and ILS process explained in Sect. 2, using a grouping list of size 2. Note that the first number or letter of each instance corresponds to the set. The best results were obtained when three of the six evaluation functions were used (i.e., $c_{j}/p_{j}$, $c_{j}/\log {(1+p_{j})}$ and $c_{j}/\sqrt{p_{j}}$),

In 47/65 instances the RPD is equal to 0. Also for 19 of these instances we report a $\sigma$ equal to 0, which means that we reach the optimal value in each of the 30 runs. On the other hand, for the rest of the instances, we report results that are very close to the optimal costs. Finally, note that the standard deviation is small for all the instances, highlighting the stability of the approach.

Table 2 Results using the ILS procedure

In Fig. 3 we show a comparison between using and not using the ILS algorithm. Note that using this algorithm outperforms significantly the previous results.

Fig. 3

Comparison of our approach using and not using the ILS process. The y-axis shows the accumulative RPD value while the x-axis indicates to the instance set

3.3 Including the reward/penalty procedure

In this section we include the reward/penalty procedure. At the beginning of the search we set the penalty $p_j$ to 1 for each column j. Additionally, $p_j$ can only take values between $min=0.5$ and $max=1.5$. If some $p_j$ is greater than 1.5 (resp. lower than 0.5) we set this penalty to 1.5 (resp 0.5). Several configuration were tested, but the best results were obtained using the values of $\alpha =0.05$ and $\beta =0.01$

This procedure shows improvements in both, the quality of the solutions and the time of convergence.

The results can be seen in the Table 3. In 51/65 instances we get RPD equal to 0 (i.e., two more than before). We also obtain a great improvement in terms of the standard deviation. From the 51 instances obtaining a RPD equal to 0, in 28 we report $\sigma =0$ and we can observe an important reduction in the rest of them.

Table 3 Results using the ILS process

In Fig. 4 we include a comparison between our complete approach and the technique without the reward/penalty procedure. Note that the most important reductions occur in the last 10 instances, the hardest ones.

Fig. 4

Comparison between our approach using the ILS process and including the reward/penalty procedure. The y-axis shows the accumulative RPD value while the x-axis indicates to the instance set

3.4 Comparing to modern metaheuristics

In this section we include a comparison between modern metaheuristics used in the last few years to deal with the SCP. The metaheuristics used for this comparison are: binary cuckoo search (BCS), binary black hole (BBH), the binary shuffled frog leaping algorithm (BSFLA) (Soto et al. 2017; Crawford et al. 2015), teaching-learning based optimization (TLBO) (Lu and Vasko 2015) and the K-means transition algorithm for the BBH (KMTA-BBH) (García et al. 2019). Note that, unlike our approach, these metaheuristics use sophisticated mechanisms and demands high tuning effort of its parameters for an optimal performance.

Table 4 reports the comparison between the previous techniques using the set problems E, F, G and H of the OR-library. Compared to these modern metaheuristics our approach behaves well, obtaining in 16/20 instances the best results (only being surpassed by KMTA-BBH with 19/20).

Table 4 Comparison between our approach and modern metaheuristics in a subset of the OR-library

In Fig. 5 we include the comparison between our complete approach (GRASP) and some of the previous metaheuristics using the accumulative RPD. From the figure our approach outperforms the strategies BBH and BSFLA, and it performs similar to BCS. Our approach has a good performance in the instances B,C,D,E, however as it can be seen, in the last two group of instances BCS and GRASP have comparable performances.

Fig. 5

Comparison between our approach and some modern metaheuristics

In order to confirm the effectiveness of our approach, we use the ranked based statistical analysis. It consist in assigning ranks to each algorithm based on the performance. The performance of an algorithm $a_1$ is considered better than $a_2$; if $a_1$ obtains an average minimum objective function than $a_2$ in a shortest computational time. A rank 1 is assigned to the best performing algorithm, a rank 2 is assigned to the second best perform algorithm and so on. The average ranks for the algorithms considered are: GRASP$=1.45$, BCS $=1.75$, BBH $=3.05$, BSFLA $=3.75$. According to this ranking, GRASP is the best performing algorithm among these techniques, followed by BCS, then BBH and BSFLA achieving the worst results. To analyze the statistical significance of differences between the evaluated ranks, we make use of the Nemenyi post-hoc test (Nemenyi 1963).

Table 5 Pairwise difference between the average ranks of the algorithms

This test is useful to determinate if the performance of two algorithms significantly differs or not. It considers the performance of two algorithms significantly different if their corresponding average ranks differ by at least a specific threshold critical difference. Considering a significance level of 1% level of significance the critical difference value is 1.05. In Table 5 shows the difference between the average ranks of the algorithms. From this table we infer that our GRASP approach and BCS have comparable performance, and that BBH and BSFLA are outperformed by our approach.

3.5 CPU times

In this final section we report the mean CPU times in seconds spent by our approach, BCS and Meta-RaPS for all the benchmark instances used in this work. The results are shown in Table 6. Our approach has good results compared to the other strategies, obtaining the best solution from Table 3 in less than 1 s in 39 instances. However in the hard instances (G and H) the algorithm requires a good amount of time to obtain good results. Instances G-1, G-2 and G-3 are the ones with the worst results. In 37/65 instances our approach converge faster.

Table 6 Cpu times in seconds for our grasp-based approach, binary cuckoo search and Meta-RaPS

3.6 Testing with new large-scale SCP instances

For today standards, the previous instances might not be large enough to prove the efficiency of our approach. In Umetani (2017) the author uses a SCP-generator to create a new set of larger SCP instances and propose a data mining approach for reducing the search space of local search algorithms. By generating a graph of the problem, the authors can identify promising pairs (resp. quartets) of variables in order to apply a 2-flip (resp. 4-flip) operation between them. Note that this approach is only useful in large instance problems, as the graph-related procedure is highly CPU-time demanding. Some of the benchmarks used in this work are described in Table 7. As it can be seen, these instances are considerably larger than the OR-library ones. To our knowledge, these new instances have not been tested by other metaheuristics. The results reported by our approach can be seen in Table 8, which are compared to the optimum values reported in Umetani (2017). Additionally the CPU-time spent by the authors correspond to 1200 s (resp. 1800 s) for the I class instances (resp. J).

Table 7 Detail of the test instances

Table 8 Results of our approach using larger SCPs instances

Despite not find any optimal solution, our approach behaves well in larger instances where both $\sigma$ and the RPD have low values.

4 Conclusions

In this paper we present a GRASP scheme for solving the SCP. Our approach works in three phases: construction solutions, applying an ILS process and penalizing columns. In the first phase we basically select and instantiate columns using a set of evaluation functions based on a previous research. Unlike other GRASP algorithms, we consider all the columns satisfying certain criteria, thus no additional parameter is involved here. In the second phase we perform an iterative local search procedure to the solution, resetting a part of it and restarting the search from that point. Finally, we penalize columns by analyzing the solution reported by the ILS algorithm. We have tested our approach using a well known set of benchmark instances, obtaining promising results.

Without taking into account the reward/penalty procedure and the time limit, our GRASP algorithm is parameter free. Compared to more sophisticated metaheuristics, we obtain comparable solutions in only a fraction of the time of the other approaches.

As a future work we plan to implement a more sophisticated mechanism for controlling the penalty of the columns in order to improve the results in larger instances and avoid local optima.