Keywords

1 Introduction

The Minimum Vertex Cover Problem (MVCP) is one of the standard combinatorial optimization problems that has been extensively researched. The decision version of the MVCP is one of Karp’s 21 NP-complete problems [9]. It is defined for a graph G(V, E) having a set of vertices V and a set of edges E. A vertex set \(C \subset V\) is called a vertex cover if for every edge \(\{u, v\} \in E\) at least one of the vertices u or v is an element of C. The objective of the MVCP is to find a vertex cover C that has minimum cardinality. In this paper, we focus on solving the Minimum Weighted Vertex Cover Problem (MWVCP) which is a variation of the MVCP in which for each node \(u \in V\) there is a corresponding weight \(w_u\). The objective in the MWVCP is to find the vertex cover having the minimum total weight. Formally, the objective is to find a set \(C \subset V\) which minimizes:

$$\begin{aligned} \sum _{u \in V} w_u x_u \end{aligned}$$
(1)

In (1), variables of type \(x_u\) are equal to 1 if \(u \in C\) and zero otherwise. The variables \(x_u\) need to satisfy the following constraints:

$$\begin{aligned} x_u + x_v \ge 1 \qquad \quad (\{ u, v\} \in E) \end{aligned}$$
(2)

The MWVCP well represents a large number of real-world problems related to wireless communication, circuit design, and network flow [11, 15] which resulted in an extensive amount of research dedicated to finding optimal and near optimal solutions. It should be noted that the vast majority of research solves the MWVCP with positive coefficients. It has been shown that it can be solved as fast as the unweighted vertex cover in \(O(1.2738^p+ p N_V)\), with exponential memory use [3, 4] (here \(N_V\) is the size of the vertex set and p the size of the prospective cover, if it exists). Due to the NP-Hardness of the MWVCP a wide range of methods have been developed for finding near optimal solutions ranging from greedy algorithms to different types of metaheuristics.

In [12], an ant colony optimization (ACO) is presented. The performance of the ACO method has been further improved using a pheromone correction strategy as presented in [7]. The problem has also been solved using genetic algorithms combined with a greedy heuristic [13], a population-based iterated greedy (PBIG) algorithm [1] and a reactive tabu search hybridized with simulated annealing [14]. One of the most successful approaches is the multi-start iterated tabu search (MS-ITS) algorithm [16]. The most successful methods incorporate some types of local searches [10]. In this paper a dynamic scoring strategy is incorporated to improve the local search performance, which produces a computationally very effective method being capable to solve problem instances having hundreds of thousands of nodes and edges. Another method designed to solve problem instances on massive graphs can be found in [2], in which first an initial vertex cover is generated that is later improved using an advanced local search.

Due to the fact that the use of local searches has proven very efficient in case of the MWVCP, in this paper the potential effectiveness of the Greedy Randomized Adaptive Search Procedure (GRASP) [5] is explored. To be more precise, our objective is to see the effectiveness of combining a simple to implement greedy algorithm and local search. Two local searches are presented based on a downhill procedure using swap operations which remove one or two vertices from the solutions and add necessary vertices. The basic idea of the swap operations is very similar to the ones used in [10, 14]. The performance of the proposed GRASP algorithm is further improved by extending it to the novel Fixed Set Search metaheuristic [8], which has previously been successfully applied to the Traveling Salesman Problem (TSP). The FSS uses a simple approach to add a learning mechanism to GRASP based on elements frequently appearing in high quality solutions. The performed computational experiments show that the FSS is highly competitive with the state-of-the-art methods in the quality of found solutions. Further, we show that the FSS produces a significant improvement when compared to the GRASP algorithm on which it is based.

The paper is organized as follows. In Sect. 2, we give a brief description of the randomized greedy algorithm for the MWVCP. In the following section details of the local searches are presented. In Sect. 4, an outline of the GRASP metaheuristic is given. In the next section, we give details of the FSS and how it is applied to the MWVCP. In Sect. 6, we discuss the performed computational experiments. The paper is finalized with concluding remarks.

2 Greedy Algorithm

In this section, the standard greedy constructive algorithm for the MWVCP is presented. The basic idea of the method is to start from a partial solution \(S = \emptyset \) and at each step expand it with the vertex that has the most desirable properties based on a heuristic function h. To be more precise, it is preferable to expand the solution with a vertex u that covers the largest number of non-covered edges and has the minimal weight \(w_u\). Formally, the heuristic function for a partial solution S and a node n has the following form.

$$\begin{aligned} Cov(n, S)= & {} \{ \{ n, v\} \mid (\{n,v\} \in E) \wedge (v \notin S)\}\end{aligned}$$
(3)
$$\begin{aligned} h(n,S)= & {} \frac{|Cov(n,S)|}{w_n} \end{aligned}$$
(4)

In (3), Cov(n, S) is the set of edges in E that contain node n but are not already covered by S. An edge is covered if at least on of its vertices is in S. The heuristic function, defined in (4), is proportional to the number of elements of Cov(S, n), and reversely proportional to the weight \(w_n\) of the vertex n.

Since, our goal is to use the presented greedy algorithm as a part of the GRASP metaheuristic it is necessary to include randomization. In the proposed algorithm we use the standard approach of a restricted candidate list (RCL) as follows. Let us define R as the set of N elements from \(v \in V \setminus S\) that have the largest value of h(v, S). Now, we can expand the partial solution with a random element of set R. The pseudocode for the proposed randomized greedy constructive algorithm (RGC) can be seen in Algorithm 1. In it, the partial solution S is initially set to an empty set. At each iteration S is expanded with a random element from the RCL. This is repeated until all the edges E are covered. The proposed RGC has computational complexity of |S||V|, where S is the generated solution.

figure a

3 Local Searches

In this section, two local searches based on a correction procedure are presented. The basic idea of the proposed local searches is based on the concept of swapping elements of a solution S with elements of \(V \setminus S\) that produce a vertex cover but decrease the objective function. This approach has proven to be very successful on the closely related dominating set problem.

3.1 Element Swap

Assume that we aim to improve a solution S. Since S is a vertex cover of G, for each edge \(\{u, v \}\) at least one of u or v is an element of S. Let us define Un(v, S), for a solution S and vertex \(v \in S\), as the set of vertices that correspond to edges that are uniquely covered by vertex vS as

$$\begin{aligned} Un(v,S) = \{ u \mid u \notin S \wedge \{u, v\} \in E \} \end{aligned}$$
(5)

It is evident that if we swap a vertex v with all the elements Un(v, S) a new vertex cover will be created. For simplicity of notation let us define the swap operation for a vertex v as

$$\begin{aligned} Swap(v,S) = (S \cup Un(v,S)) \setminus \{v\} \end{aligned}$$
(6)

Now, a swap operation for a vertex v can be evaluated as

$$\begin{aligned} EvSwap(v,S) = w_v - \sum _{i \in Un(v,S)}{w_i} \end{aligned}$$
(7)

In Eq. (7), EvSwap(v) gives the change in the solution weight when \(v \in S\) is swapped. More precisely, it is equal to the weight \(w_v\) of vertex v that is removed from the solution minus the total sum of weights of vertices that are added to the solution. Now, we can define Imp(S) as the set of all vertices of S for which a swap operation produces an improvement

$$\begin{aligned} Imp(S) = \{v \mid v \in S \wedge EvSwap(v,S) > 0\} \end{aligned}$$
(8)

3.2 Pair Swap

The basic idea of the swap operation can be extended to pairs of vertices. In case of a local search based on swap pairs it generally is the case that the computational cost will increase |S| times, where S is the solution being improved. Although this cannot be changed asymptotically, it can be greatly decreased in practical applications. It is important to note that in case of the MWVCP swap operations of this type are more effective than for other problems since the elements that are used for substitution are uniquely defined. In designing the local search based on swap pairs, we focus on two objectives. Firstly, to have a very small overlap with a local search based on element swaps and secondly to increase computational efficacy.

In our application, we assume that in a pair swap operation involving \(\{u, v\}\) both elements will be removed and none of them will be re-added. In case this constraint is not used the same effect can be achieved using an element swap. In case such a constraint exists, if \(\{ u, v\} \in E\) such a pair can never be swapped since the edge \(\{ u,v \}\) will not be covered. Additional positive effects of a pair swap \(\{ u, v\}\) can only occur if u and v have overlapping neighborhoods, or in other words in case there is a node w that is adjacent to both u and v. Using this idea, let us formally define the set of improving swap pairs for a solution S. Based on the previous discussion the set of all vertex pairs that should be tested for a graph G can be defined as follows:

$$\begin{aligned} C_p = \{ \{u, v\} \mid (u,v \in V) \wedge (N(v) \cap N(u) \ne \emptyset ) \} \setminus E \end{aligned}$$
(9)

In (9), the notation N(v) is used for the open neighborhood of v, i.e., all nodes adjacent to v not including itself. Using this set of candidate swap pairs for graph G, we can define the set of improving swap pairs in a similar way as a set of improving elements using the following set of equations.

$$\begin{aligned} Un(u, v, S)= & {} Un(u,S) \cup Un(v,S)\end{aligned}$$
(10)
$$\begin{aligned} Swap(u,v, S)= & {} (S \cup Un(u, v, S)) \setminus \{ u, v\}\end{aligned}$$
(11)
$$\begin{aligned} EvSwap(u,v,S)= & {} w_u + w_v - \sum _{i \in Un(u,v,S)}w_i \end{aligned}$$
(12)
$$\begin{aligned} ImpPair(S)= & {} \{\{ u, v\} \mid (\{ u,v \}\in C_p \cap S^2) \\ \nonumber&\wedge (EvSwap(u,v,S) > 0)\} \end{aligned}$$
(13)

In (10), Un(u, v, S) corresponds to the set of nodes that correspond to the set of edges that are uniquely covered by one of the vertices u or v. Note, that this set excludes vertices u and v. In (11), the effect of the swapping elements u and v from a solution S is given. To be more precise, the vertices u and v are removed from the solution S, and all the nodes corresponding to uniquely covered edges are added. EvSwap(u, v, S), given in (12), is equal to the change on the weight of the solution if the vertex pair \(\{u, v\}\) is swapped. Finally, in the next equation ImpPair(S) is the set of all swap pairs that improve the quality of the solution from the set of the restricted list of candidate pairs. The restricted set of candidate pairs is equal to the intersection of the unordered product of set S with itself \(S^2\) and the set of all candidate pairs for graph G.

3.3 Local Search

In this subsection, we present the local search based on the presented improvement using element swaps and pair swaps. It should be noted that these two types of improvement explore different neighborhoods of a solution S. Because of this, as in the case of the variable neighborhood search [6], it is advantageous to use both of them interchangeably. The pseudocode for the local search based on swap operations can be seen in Algorithm 2.

figure b

In Algorithm 2, a solution S is interchangeably improved based on swap elements and swap pairs. Firstly, all the possible improvements are performed using swap elements since this operation is computationally less expensive. This is done by repeatedly performing swap element improvements until no further improvement of this type is possible. Next, we test if an improvement can be achieved using swap pairs. If this is true, the improvement is performed. As there is a possibility, that after applying a swap pair improvement new element swaps can produce improvement, the main loop is repeated until no such improvement exists. It should be noted that for both types of improvements there are several different ways to select the swap that will be performed; in the proposed implementation we simply select a random one.

4 GRASP

To enhance the performance of the proposed greedy algorithm and local search, we extend them to the GRASP metaheuristic as illustrated in Algorithm 3. In the main loop of Algorithm 3, a new solution S to the MWVCP is generated using the RGC algorithm. The local search is applied to the solution S and tested if it is the new best solution. This procedure is repeated until some stopping criterion is satisfied, usually a time limit or a maximal allowed number of solutions has been generated.

figure c

5 Fixed Set Search

The fixed set search (FSS) is a novel metaheuristic that adds a learning mechanism to the GRASP. Literally it uses elite solutions, consistent solution elements or alike to direct the search. It has previously been successfully applied to the TSP [8]. The FSS has several important positive traits. Firstly, there is a wide range of problems on which it can possibly be applied (this paper tries to put evidence on it) since the only requirement is that the solution of the problem is represented in a form of a set. The learning mechanism is simple to implement and many existing GRASP algorithms can easily be extended to this form. In this section the general concepts used in the FSS are presented as well as details of its application to the MWVCP. A more detailed explanation of the concepts used in the FSS can be found in [8].

The main inspiration for the FSS is the fact that generally many high quality solutions for a combinatorial optimization problem contain some common elements. The idea is to use such elements to steer the search of the solution space. To be more precise, we wish to force such elements in a newly generated solution and dedicate computational effort to finding optimal or near optimal solutions in the corresponding subset of the solution space. The selected set of common elements will be called the fixed set. In the FSS, we are trying to find the additional elements to complete the partial solution, corresponding to the fixed set, or in other words to “fill in the gaps.” In practice, we are intensifying the search around such fixed sets. This can be achieved through the following steps. Firstly, a method for generating fixed sets needs to be implemented. Next, the randomized greedy algorithm used in the corresponding GRASP needs to be adapted in a way to be able to use a preselected set of elements. Lastly, the learning mechanism which gains experience from previously generated solutions needs to be specified.

5.1 Fixed Set

Let us first define a method that will make it possible to generate random fixed sets. As previously stated the FSS can be applied to a problem for which a solution can be represented in a form of a set S having elements in some set W, or in other words \(S \subset W\). In case of the MWVCP this concerns a solution \(S \subset V\). In the following the notation \(\mathcal {P}\) will be used for the set of all the generated solutions (population). Next, let us define \(\mathcal {P}_n \subset \mathcal {P}\) as the set of n solutions having the best value of the objective function inside \(\mathcal {P}\).

One of the requirements of the FSS is that the method used to generate a fixed set F has the ability to control its size |F|. Further, such fixed sets need to be able to produce high quality feasible solutions. This can be achieved using a base solution \(B \in \mathcal {P}_m\). If the fixed set satisfies \(F \subset B\), it can be used to generate the base solution. In practice this means it can generate a feasible solution at least of the same quality as B, and F can contain arbitrary elements of B. It is preferable for F to contain elements that frequently occur in some group of high quality solutions. To achieve this, let us define \(\mathcal {S}_{kn}\) as the set of k randomly selected solutions out of the n best ones \(P_n\).

Using these building blocks it is possible to define a function \(Fix(B, \mathcal {S}_{kn}, Size)\) for generating a fixed set \(F \subset B\) that consists of Size elements of the base solution \(B = \{ v_1, ... v_l\}\) that most frequently occur in \(\mathcal {S}_{kn} = \{S_1, .., S_k\}\). Let use define the function \(C(v_x, S)\), for an element \(v_x \in V\) and a solution \(S \subset V\), which is equal to 1 if \(v_x \in S\) and 0 otherwise. We can define a function that counts the number of occurrences of element \(v_x\) in the elements of the set \(\mathcal {S}_{kn}\) using the function \(C(v_x, S)\) as follows.

$$\begin{aligned} O(v_x, \mathcal {S}_{kn}) = \sum _{S \in \mathcal {S}_{kn}}C(v_x,S) \end{aligned}$$
(14)

Now, we can define \(Fix(B,\mathcal {S}_{kn}, Size)\) as the set of Size elements \(v_x \in B\) that have the largest value of \(O(v_x, \mathcal {S}_{kn})\).

5.2 Learning Mechanism

The learning mechanism in the FSS is implemented through the use of fixed sets. To achieve this it is necessary to adapt the RGC algorithm used in the corresponding GRASP to a setting where some elements are preselected (the newly generated solution must contain them). Let us use the notation RGF(F) for the solution generated using such an algorithm with a preselected (fixed) set of elements F. In case of the MWVCP, the RGC algorithm is trivially adapted to a RGF(F) by setting the initial partial solution S to F instead of an empty set.

In the FSS, as in the case of the GRASP, solutions are repeatedly generated and a local search is applied to each of them. The first step is generating an initial population of solutions \(\mathcal {P}\) by performing N iterations of the corresponding GRASP algorithm. The initial population is used to generate a random fixed set F having some size Size, using the method from the previous section. The fixed set F is used to generate a new solution \(S= RGF(F)\) and the local search is applied to it. The population of solutions is expanded using the newly generated locally optimal solutions. This procedure is repeated until no new best solutions are found for a long period by some criteria, or in other words until stagnation has occurred. In case of stagnation the size of the fixed set is increased. In case the maximal allowed size of the fixed set is reached, the size of the fixed set is reset to the minimal allowed value. This procedure is repeated until some stopping criterion is reached. An important part of the algorithm is defining the array of allowed fixed set sizes, which is related to the part of the solution that is fixed. In our implementation this array is defined as follows:

$$\begin{aligned} Sizes[i] = (1 - \frac{1}{2^i}) \end{aligned}$$
(15)

The size of the used fixed sets is proportional to the used base solution B. More precisely, at the i-th level it is equal to \(|B|\cdot Size[i]\).

figure d

The pseudocode for FSS can be seen in Algorithm 4. In it, the first step is initializing the sizes of fixed sets using (15). The current size of the fixed set Size is set to the smallest value. The next part of the initialization stage is generating the initial population of N solutions by performing N iterations of the basic GRASP algorithm. Each iteration of the main loop consists of the following steps. A random set of solutions \(\mathcal {S}_{kn}\) is generated by selecting k elements from \(\mathcal {P}_n\) and a random base solution B is selected from the set \(\mathcal {P}_m\). Next, the function \(Fix(B, \mathcal {S}_{kn}, Size|B|)\) is used to generate a fixed set F. A new solution \(S= RGF(F)\) is generated using the randomized greedy algorithm with preselected elements and the local search is applied to it. Next, we check if S is the new best solution and add it to the set of generated solutions \(\mathcal {P}\). In case stagnation has occurred, the value of Size is set to the next value in Sizes. Let us note, that the next size is the next larger element of array Sizes. In case Size is already the largest size, we select the smallest element in Sizes. This procedure is repeated until some termination criterion is satisfied.

In our implementation of the proposed algorithm for the MWVCP, the criterion for stagnation was that no new best solution has been found in the last, say, Stag iterations. As previously stated the adaptation of the randomized constructive greedy algorithm to the RGF(F) consists of simply setting the initial partial solution to the fixed set instead of an empty set. The set of candidate swap pairs \(C_p\) is calculated in the initialization stage. At this time the set of all neighboring vertices for valid candidate pairs \(\{ u,v \}\) are also calculated with the intention of speeding the calculation of ImpPair(S).

6 Results

In this section we give details of the performed computational experiments. Their objective is to evaluate the performance of the proposed GRASP and FSS in combination with the element- (GRASP-E and FSS-E) and pair- (GRASP-P and FSS-P) based local searches. Note that the pair-based local search is only used in combination with the element-based one. This has been done in comparison with the ACO algorithm from [12] and its improvement version (ACO-SEE) [7]. Further, a comparison is with the population-based iterated greedy (PBIG) algorithm [1], the multi-start iterated tabu search (MS-ITS) algorithm [16] and the Diversion Local Search based on Weighted Configuration Checking (DLSWC) [10] which are the best performing methods. Note that the reactive tabu search hybrid produces about the same quality of results than DLSWC, but in [14] results are only presented for a small subset of instances.

Table 1. Comparison of the methods for medium-size problem instances of Type 1.
Full size table
Table 2. Comparison of the methods for medium-size problem instances of Type 2.
Full size table
Table 3. Comparison of best found solutions over 10 independent runs for large problem instances by different methods.
Full size table
Table 4. Comparison of average quality of found solutions over 10 independent runs for large problem instances by different methods.
Full size table

The comparison is done on the set of test instances introduced in [12], that have been also used to evaluate the other mentioned methods. The test instances are divided into three groups: small, medium and large. In case of the small and medium test instances, random graphs having 10–300 nodes and 10–5000 edges are used for evaluation. For each pair \((N_V,N_E)\) with \(N_V\) and \(N_E\) being the number of vertices and edges, respectively, there are ten different graph instances. The test instances are divided into Type 1 where there is no correlation between the weight of a vertex and number on incident edges, and Type 2 where some weak correlation exists; details can be found in [12]. In case of large test instances the graphs have between 500 and 1000 vertices and between 500 and 20 000 edges, and there is only one instance for each pair \((N_V, N_E)\).

The used parameters for FSS are the following, \(k=10\) random solutions are selected from the best \(n=100\) ones for the set of solutions \(\mathcal {S}_{kn}\). The base solution is selected from the \(m=100\) best solutions. The size of the initial population is 100. The stagnation criterion is that no new best solution is found in the last \(Stag=100\) iterations for the current fixed set size. The used size of the RCL in the randomized greedy algorithm is 10. The stopping criterion for all the proposed methods is that 5000 solutions are generated or a time limit of 10 minutes has been reached. The FSS and GRASP have been implemented in C# using Microsoft Visual Studio 2017. The calculations have been done on a machine with Intel(R) Core(TM) i7-2630 QM CPU 2.00 Ghz, 4 GB of DDR3-1333 RAM, running on Microsoft Windows 7 Home Premium 64-bit.

In Tables 1 and 2 the results for the medium-size problem instances are given for graphs of Type 1 and Type 2, respectively. For each pair \((N_V, N_E)\), the average weight of all the vertex covers of this type are evaluated. With the intention of having a clearer presentation, the average value of the objective function is only given for DLSWC, while for the other methods only the difference to this value is presented. The values for the methods used for comparison are taken from the corresponding papers. Note that we did not include the results for small problem instances since all the methods except the two ACO methods manage to find all the optimal solutions. From the results in these tables it can be seen that the two ACO algorithms have a substantially worse performance than the other methods. Further, the FSS-P had the overall best performance of all the methods except DLSWC, having on average only 0.8 and 0.1 higher value of the objective function. It should be noted that although FSS overall has a worse performance than DLSWC in case of two pairs \((N_V, N_E)\) it managed to find higher quality average solutions. The experiments performed on large test instances can be seen in Tables 3 and 4 where the values of the best found and average weight over 10 runs of each algorithm are given, respectively. In case of problems instances of this size a similar behavior can be seen as for medium-size instances.

From the computational results it is evident that the methods FSS-P and GRASP-P in which the local search includes pair swaps manages to find significantly better solutions than the element-based ones. The use of pair swaps in the local search produces a more significant improvement than the addition of the learning mechanism used in the FSS. It should be noted that GRASP-P has a better performance than FSS-E for medium-size instances, while FSS-E manages to have a slightly better performance for large instances with FSS-P being consistently better in both cases. The improvement that is achieved by FSS is more significant in case of the weaker local search based on element swaps. However, it is most important to note that the improvement achieved by FSS compared to the corresponding GRASP is very consistent, and it only has worse average quality of found solutions for 1 or 3 of the \((N_V, N_E)\) pairs, when the used local search was based on elements or pairs, respectively.

The convergence speed of the FSS-P is competitive to other methods, in case of medium-size instances it needs an average time of 0.76 and 0.43 s to find the best solution for Type 1 and Type 2 graphs, respectively. This is a very similar result to MS-ITS which needed between 0.51 and 0.45 s to solve instances of Type 1 and Type 2, and better than PBIG which needs 2.49 and 4.23 s. DLSWC has a substantially better performances; on average it needs only 0.03 and 0.4 s. The FSS-P scales well, and for large graphs needs an average of 5.05 s to find the best solution for an instance which is similar to 5.20 of DLWSC, but it should be noted that the quality of solutions is of lower quality. The scaling of PBIG and MS-ITS is significantly worse and the methods on average need 126.94 and 74.80 s to solve large problem instances, respectively. It is interesting to point out that although the asymptotic computational cost of the local search based on pairs is greater than the one based on elements, the time for finding the best solutions for GRASP-P and FSS-P is generally 2–5 times lower than for GRASP-E and FSS-E. The FSS, on average, needs around half the time of GRASP with the same type of local search to find the best solution. The pair swap local search proves to be very efficient; for graphs having up to 100 nodes GRASP-P generally needs less than 20 iterations to find the best known solutions.

7 Conclusion

In this paper we have presented an efficient easy to implement method for finding near optimal solutions for the MWVCP. This has been done by developing two local searches based on a correction procedures which switches one or two vertices from a solution with new ones which produces a new vertex cover having a lower weight. These local searches have been used as a part of a GRASP algorithm. The performance of the developed GRASP has been improved by extending it to the novel Fixed Set Search metaheuristic. The conducted computational experiments have shown that the proposed FSS is highly competitive with the state-of-the-art methods. The results also indicate that the learning mechanism in the FSS manages to significantly enhance its performance when compared to the GRASP on which it is based. Importantly, the positive effect is most significant on large-scale problem instances on which the effectiveness of GRASP algorithms is generally decreased. For future research we aim to extend the application of the FSS to other types of problems.