1 Introduction

Let G=(V,E) be an undirected graph with vertex set V={1,…,n} and edge set E⊂V×V. A clique C of G is a subset of V such that every two vertices are pairwise adjacent, i.e., ∀u,v∈C,{u,v}∈E. A clique is maximal if it is not contained in any other clique, a clique is maximum if its cardinality is the largest among all the cliques of the graph. The maximum clique problem (MCP) asks for a maximum clique. MCP is one of the first problems shown to be NP-complete in Karp’s seminal paper on computational complexity (Karp 1972).

An important generalization of MCP is the maximum weight clique problem (MWCP). Given G=(V,E), let w:V→Z + be a weighting function that assigns to each vertex i∈V a positive value. For a clique C of G, define its weight as W(C)=∑ i∈C w i . The MWCP is to determine a clique C ∗ of maximum weight, i.e., ∀C∈Ω,W(C ∗)≥W(C) where Ω is the set of all possible cliques of the graph. Applications of the MWCP arise in a number of domains like computer vision, pattern recognition and robotics (Ballard and Brown 1982).

The MCP, also called the unweighted maximum clique problem, can be considered as a special case of the MWCP where the weight of each vertex is set equal to 1 (i.e., w:V→{1}). It is clear that a maximum clique of the MCP does not necessarily lead to a maximum weight clique of the MWCP, and the MWCP has at least the same computational complexity as the MCP.

To solve the MWCP, a number of exact algorithms have been reported in the literature (see e.g., Babel 1994; Östergård 2001) which can be applied to instances of small sizes. For larger problems, various heuristic methods have been proposed to find approximative solutions. For instance, in Pullan (2008), an efficient local search algorithm is presented which is based on ideas developed for the unweighted case (Pullan and Hoos 2006). Along with the proposed algorithm, a set of MWCP benchmark instances using the DIMACS graphs are also introduced (we use these instances in our experiments). In Mannino and Stefanutti (1999), an augmentation algorithm is described which is based on edge projections for the equivalent maximum weight stable set problem. Other representative studies include a deterministic iterated greedy construction algorithm using a nonlinear programming formulation (Busygin 2006), and a distributed computational network algorithm (Bomze et al. 2000).

In this paper, we present a multi-neighborhood tabu search approach (denoted by MN/TS) for the maximum weight clique problem. In order to effectively explore the search space, the proposed algorithm combines three neighborhoods induced by three types of moves. The particularity of the combined neighborhood relies on the union of the underlying neighborhoods instead of the conventional sequential exploration of basic neighborhoods (Sects. 2.3 and 2.4). At each iteration of the algorithm, our tabu search approach explores the union of these three neighborhoods and selects the overall best admissible neighboring solution. The algorithm integrates a dedicated tabu mechanism (Sect. 2.5) and a randomized restart strategy (Sect. 2.6).

The performance of the proposed MN/TS algorithm is assessed on a large set of benchmarks from the well-known DIMACS and BHOSLIB libraries and the set packing problem (Sect. 4). Extensive experimental tests disclose that the proposed approach finds new best solutions for 26 DIMACS instances of the maximum weight clique problem, while matching the best known solution on all but one of the others. For the unweighted maximum clique problem, MN/TS is able to attain the best known solutions for the 120 tested instances except for only two cases, rivaling the performance of the best algorithms for the MCP problem without specializing our method to exploit the unweighted class. For an additional set of 16 instances derived from the set packing problem, MN/TS is able to attain the current best-known results while discovering 2 improved results, again without being designed to exploit the set packing structure (in contrast to the methods that have produced the previous best results). An analysis is also provided to show the relevance of the union exploration of the underlying neighborhoods (Sect. 5).

2 Multi-neighborhood tabu search for the MWCP

In this section, we present our multi-neighborhood tabu search (MN/TS) approach for the general MWCP. MN/TS integrates several features which are responsible for its effectiveness, including three complementary neighborhoods defined by three basic move operators. These neighborhoods are explored in a combined manner employing a rule that selects the most favorable neighboring solution that is admissible subject to the tabu conditions. The method is driven by a dedicated tabu list strategy employing a restart mechanism for diversification.

2.1 Search space and evaluation function

For a given MWCP instance G=(V,E,w), our MN/TS algorithm explores a search space Ω composed of all possible cliques of G, i.e., Ω={C:C⊂V such that ∀i,j∈C, i≠j, {i,j}∈E}. For any solution C∈Ω, its quality is evaluated by its weight W(C)=∑ i∈C w i . Given two solutions C and C′, C′ is better than C if and only if W(C′)>W(C). Our objective function (to be maximized) is thus given by: W:Ω→Z +.

2.2 Randomized procedure for initial solutions

Our algorithm starts from an initial clique C∈Ω and then uses the tabu search procedure (Sects. 2.3–2.5) to improve C by maximizing its weights. The initial solution C is constructed as follows. We first select randomly a seeding vertex i from the graph and set the current clique C to the set consisting of this single vertex. We then randomly pick another vertex v∉C subject to the stipulation that v is connected to all the vertices of C (i.e., v is taken from the set {v:v∈V\C,{v,i}∈E,∀i∈C}). This process is repeated until no such vertex v exists. This procedure is also used to initialize each restart during a run of the MN/TS algorithm (see Sect. 2.6). This procedure has the advantage of being simple and fast, leading to diversified initial solutions for each round of the tabu search procedure.

2.3 Basic move operators and neighborhoods

In local search, a neighborhood is typically defined by a move operator mv, which transforms a given solution C to generate a neighboring solution C′, denoted by C′=C⊕mv. Let M(C) be the set of all possible moves which can be applied to C, then the neighborhood N of C is defined by: N(C)={C′:C′=C⊕mv,mv∈M(C)}.

Our MN/TS algorithm explores jointly three neighborhoods which are defined by three basic move operators (denoted by ADD, SWAP and DROP). These move operators are based on the definition of two vertex subsets: PA and OM relative to a given clique C.

PA is composed of the vertices that are excluded from the clique C and connected to all the vertices of C: PA={v:v∈V\C,{v,i}∈E,∀i∈C}.

OM contains the vertices that are excluded from the clique C and connected to all but one vertex of C: OM={v:v∈V\C,|A(v)∩C|=|C|−1} where A(v)={j:j∈V,{j,v}∈E} is the set of vertices adjacent to v.

The relationship between a clique C and the associated subsets PA and OM is illustrated in Fig. 1.

Fig. 1
figure 1

A clique and its two associated subsets: C={1,2,3,4}, PA={5} and OM={6,7}

Full size image

The two subsets PA and OM just described form the basis for defining the ADD and SWAP move operators while the DROP move operator is defined independently of these subsets, as follows.

  • ADD(i): This move operator (which applies when PA is not empty) consists in adding a vertex i from the set PA to the current clique C. The neighborhood defined by this move operator is given by N 1={C′:C⊕ADD(i),i∈PA}.

    After a ADD(i) move, the change in the clique weight (i.e., the move gain denoted by Δ i ) is given by the following expression:

    $$ \varDelta_{i} = w_{i}$$
    (1)

    where w i is the weight associated to vertex i. Since the move gain is always positive for a ADD move, such a move always leads to an improved neighboring solution. The size of this neighborhood is clearly bounded by O(n).

  • SWAP(i,j): This move operator (which applies when OM is not empty) consists in exchanging a vertex i from the set OM with the only vertex j of C which is not connected to i in C. The neighborhood defined by this move operator is given by N 2={C′:C⊕SWAP(i,j), i∈OM,j∈C,{i,j}∉E}.

    For a given SWAP(i,j) move, the move gain Δ ij can be conveniently computed by:

    $$ \varDelta_{ij} = w_{i} - w_{j}$$
    (2)

    Since Δ ij can be either positive or negative, a SWAP move can improve or deteriorate the quality of the current solution. The size of this neighborhood is bounded by O(n).

  • DROP(i): This move operator removes a vertex i from the current clique C. The neighborhood induced by the DROP move can be formally defined by N 3={C′:C\{i},i∈C}.

    The move gain Δ i of dropping vertex i can be calculated by:

    $$ \varDelta_{i} = -w_{i}$$
    (3)

    We can see that a DROP move always leads to a decrease to the objective function.

2.4 Combined neighborhood and neighbor selection strategy

In the case of the unweighted maximum clique problem, ADD moves are always preferable to other moves (in a local sense) since they invariably increase the clique weight. However, for the weighted case (MWCP), a SWAP move may lead to a solution better than any solution that can be obtained by a ADD move. Figure 2 shows an illustrative example where the current clique C contains three vertices. From Fig. 2, we can see that swapping vertices 6 and 1 (Δ 6,1=w 6−w 1=4) leads to the solution C 1={3,4,6}, which is better than the solution C 2={1,2,3,4} obtained by adding vertex 2 (Δ 2=3) to C.

Fig. 2
figure 2

From clique C={1,3,4}, the SWAP move between vertices 6 and 1 (SWAP(6,1)) leads to a solution C 1={3,4,6}, which is better than the solution C 2={1,2,3,4} obtained by the ADD move (ADD(2))

Full size image

Moreover, when no ADD move is possible (PA=∅), a DROP move may lead to a solution which is better than any solution that can be obtained by a SWAP move (see Fig. 3 for an illustrative example). To summarize, for the MWCP, there is no absolute dominance of one move operator (and its neighborhood) over another move operator. The best move operator to be applied depends on the current search context and should be determined according to the context.

Fig. 3
figure 3

From clique C={3,4,6}, the DROP move of dropping vertex 4 leads to a neighbor solution ({3,6}) better than any other neighbor solution obtained by the SWAP moves

Full size image

These observations lead us to create a combined neighborhood \(\mathcal {N}\) which corresponds to the union of the three neighborhoods N 1, N 2 and N 3, denoted by \(\mathcal{N} = N_{1}\cup N_{2} \cup N_{3}\). Using this union neighborhood, our tabu search algorithm selects at each iteration the most favorable move (i.e., with the largest Δ value) among all the ADD, SWAP and DROP moves to generate the next solution. Ties are broken at random.

2.5 Tabu list and tabu tenure management

Tabu search (Glover and Laguna 1997) characteristically introduces a tabu list to forbid recently visited solutions from being revisited. In our MN/TS algorithm, we adopt the following general prohibition rule: a vertex that leaves the current clique C (by a SWAP or DROP move) is forbidden to move back to C for the next tt iterations (tabu tenure). A vertex that joins the clique C (by an ADD or SWAP move) is free to be removed from C without restriction.

With this prohibition rule, no tabu list is needed for the ADD moves. This choice can be intuitively explained by the fact that due to the objective of maximizing the clique weight, an added vertex has little chance to be removed anyway. (As noted in Glover and Laguna (1997), a tabu tenure to prevent elements from being dropped should typically be smaller than one to prevent elements from being added. We have simply elected to make the smaller tenure 0.)

For the SWAP move, when a vertex i∈OM is swapped with the only node j∈C not connected to i, j is prohibited to be moved back to C for the next T swap iterations while no tabu status is assigned to i. T swap is tuned dynamically according to the cardinality of OM:

$$ T_{\mathit{swap}} = \mathit{random}\bigl(|\mathit{OM}|\bigr) + T_{1}$$
(4)

where T 1 is set equal to 7 and random(|OM|) takes a random integer in the range [1,…,|OM|].

For the DROP move, each time a vertex i is removed from C, moving i back to C is declared tabu for the next T 1 iterations where T 1=7.

Our tabu restrictions (like most of those employed by tabu search) apply to attributes of solutions that are affected by the moves—in this case, the vertices affected by the moves. We call a move tabu if one of its attributes is tabu (hence in this case the vertex that would be added to C), and employ the common aspiration criterion that permits a move to be accepted in spite of being tabu if it produces a solution better than any found so far. A move that is not tabu or that satisfies the aspiration criterion is called admissible.

2.6 Multistart strategy and stop criteria

Our tabu search algorithm examines at each iteration the three neighborhoods and selects an admissible move that produces the most favorable neighboring solution. The inclusion of all three neighborhoods allows the algorithm to make a more thorough examination of the solutions around each solution. On the other hand, the tabu restrictions provide a form of local diversification by forcing the search to leave the regions already examined. To establish a more global form of diversification, and thereby reinforce the capacity of the algorithm to visit unexplored areas in the search space, we employ a multistart strategy to restart the search from new starting points. A restart is triggered each time the current search is judged to be trapped in a deep local optimum, a condition that is deemed to occur upon exceeding a maximum allowable number of consecutive iterations without improving the clique weight. We call this number the depth of the search (denoted by L).

Basically, our multistart tabu search algorithm iterates the following two steps until the stop criterion is satisfied:

  1. 1.

    Generate a new start point C (see Sect. 2.2).

  2. 2.

    Apply the tabu search procedure to improve the solution C until the fixed depth L is reached.

The algorithm stops when it attains a predetermined maximum number of iterations (Iter max ). The complete MN/TS algorithm is described as Algorithm 1. Each outside while loop triggers a restart of the tabu search procedure which is realized in the inner while loop. The variables C and C′ designate respectively the current solution and one of its neighboring solution. C local_best is the best solution found during one inner while loop while C ∗ is the overall best solution found by the algorithm.

Algorithm 1
figure 4

The multi-neighborhood tabu search approach for MWCP

Full size image

3 Discussion

The move operators ADD, SWAP and DROP (and particularly ADD and SWAP) have been widely used in previous studies for both the MMCP and MCP. However, previous studies have applied these operators independently and sequentially rather than making reference to their union as done here.

For instance, the PLS approach for the weighted MCP (Pullan 2008) alternates between a greedy expansion phase during which suitable vertices are added to the current clique followed by a plateau phase where vertices of the current clique are swapped with some vertices out of the clique. This strategy implicitly causes PLS to give a higher priority to ADD moves even if a SWAP move may lead to a solution better than any ADD move (see Fig. 2 for an example). Such a sequential application of ADD and SWAP moves can miss favorable neighboring solutions. In short, the union neighborhood explored by MN/TS ensures a more aggressive and intensified examination of the search space, increasing the chance to find solutions of better quality. In Sect. 5, we give computational evidence of this assertion. Another difference between our method and PLS is that MN/TS picks the two vertices for a SWAP(i,j), according to the move gain, while PLS selects a vertex i with the largest weight w i in OM to exchange with the only vertex not connected to i in C.

Finally, for the unweighted MCP, most local search methods (such as Battiti and Protasi 2001; Friden et al. 1989; Gendreau et al. 1993; Grosso et al. 2004; Katayama et al. 2005; Pullan and Hoos 2006) use these moves in manner similar to the way they are employed in PLS. These algorithms differ from each other chiefly in: (1) the strategies for exploring the neighborhoods, (2) the scheme of vertex selection and (3) the prohibition mechanism applied to the performed moves.

4 Experimental results

This section is dedicated to an intensive evaluation of the proposed algorithm.Footnote 1 For this purpose, we present computational results on a large panel of benchmark instances and show comparisons with state of the art algorithms when such comparisons are possible.

4.1 Benchmark instances and experimental settings

DIMACS and BHOSLIB unweighted benchmarks

These test sets consist of popular benchmarks frequently used to assess unweighted clique algorithms. The DIMACS benchmark set was established for the Second DIMACS Implementation Challenge (Johnson and Trick 1996). This set comprises 80 instances from a variety of real applications. The set also includes graphs generated randomly and graphs whose maximum clique has been hidden by incorporating low-degree vertices. These problem instances range in size from 50 vertices and 1000 edges to 3300 vertices and 5000000 edges.

The set of 40 BHOSLIB (Benchmark with Hidden Optimum Solutions) instances arose from the SAT’04 Competition. The BHOSLIB instances were translated from hard random SAT instances and have been known to be hard both theoretically and practically for maximum clique algorithms. The BHOSLIB benchmarks have been widely used in the recent literature to test new MCP heuristics. The full BHOSLIB set of instances is available from http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm.

BHOSLIB-W and DIMACS-W weighted benchmarks

These test instances consist of benchmarks used to assess algorithms for the maximum weight clique problem. The weighted DIMACS-W benchmarks were obtained from the DIMACS benchmark instances by allocating weights to vertices. There are different ways to define the weighting function. We adopt the method described in Pullan (2008): for each vertex i, w i is set equal to (i mod 200)+1. Similarly, we apply the same weighting function to the (unweighted) BHOSLIB benchmark instances to obtain the weighted instances (denoted by BHOSLIB-W benchmarks).

Structured benchmarks from set packing

These are a set of 16 instances derived from the set packing problem (Kwon 2005) with sizes ranging from 1000 to 2000.

Experimental settings

Our MN/TS algorithm is programmed in C and compiled using GNU GCC on a PC with 2.83 GHz CPU and 8 G RAM. Like (Pullan 2008) and given the stochastic nature of the MN/TS algorithm, each instance is solved 100 times independently by MN/TS with different random seeds. The maximum allowed iterations Iter max (see Algorithm 1) per run and per instance is set equal to 108. For the search depth L (see Sect. 2.6), we use L=4000 for the instances of the weighted case (MWCP). For the unweighted case (MCP), we use L=104 except for the brock and san families (DIMACS) for which L is equal to 100.

4.2 Experimental results for the maximum weight clique problem

In Tables 1 and 2, we show respectively the computational results of our algorithm on the set of 80 DIMACS-W instances and on the set of 40 BHOSLIB-W benchmarks. Columns 2–3 give the features of each tested instance: the number of vertices (Node) and the largest known clique size for the graph. In columns 4–9, we give the same computational statistics as in (Pullan 2008) (our main reference algorithm): the maximum weight obtained by MN/TS over the 100 independent trials (W best ), the cardinality of the obtained maximum weighted clique (|C|), the average weight over the 100 trials (W avg ), the number of successful trials in which MN/TS reached W best (Success), the average time (AvgTime) and the average iterations (Iteration) over these successful trials.

Table 1 Results obtained by MN/TS on the 80 DIMACS-W benchmarks. The weight w i of each vertex i is set equal to (i mod 200)+1 according to Pullan (2008). Statistics are based on 100 executions of MN/TS on each benchmark instance
Full size table
Table 2 Results obtained by MN/TS on the 40 BHOSLIB-W benchmarks. The weight w i of each vertex i is set equal to (i mod 200)+1 according to Pullan (2008). Statistics are based on 100 executions of MN/TS on each benchmark instance
Full size table

For problems in the MWCP class, studies in the literature are often based on DIMACS-W instances (different weighting functions may be used). We are unaware of studies reporting computational results on the BHOSLIB-W benchmarks. For this reason, our comparisons reported in the next section are based on DIMACS-W benchmarks (as well as a set of instances from the set packing problem) while our results on the BHOSLIB-W benchmarks can serve as a basis for performance assessment of other MWCP algorithms.

4.3 Comparative results for the weighted maximum clique problem

In order to show the relative effectiveness of our MN/TS for the MWCP, we first compare MN/TS with two state of the art algorithms from the literature (Pullan 2008; Mannino and Stefanutti 1999). The main comparison criterion is the quality of the solutions found. Due to the differences among the programming languages, data structures, compiler options and computers, computing times are provided only for indicative purposes. Since the reference algorithms report results only for DIMCAS-W benchmarks, our first comparisons are based on this set of instances.

Table 3 summarizes the comparative results between our MN/TS and the well-known PLS algorithm (Pullan 2008). For both algorithms, the number of the trials devoted to solving each instance was 100. In Table 3, we indicate the largest weights obtained by the two algorithms for each graph over the 100 independent trials (W best ), the number of successful trials where an algorithm reached W best (Success), the average time (CPU) over these successful trials. Finally, column 8 indicates the difference in the largest weights obtained by MN/TS and PLS.

Table 3 Comparative results between MN/TS and PLS (Pullan 2008) on the set of 80 DIMACS-W benchmarks. The weight of each vertex i is set equal to (i mod 200)+1. Statistics are based on 100 trials of each algorithm. An entry with “–” for PLS means that PLS was terminated because of excessive CPU time. An entry with “<ϵ” signifies that the average CPU time required by PLS was less than 0.01 seconds. MN/TS finds improved solutions for 13 instances (in bold)
Full size table

Table 3 discloses that, over the 80 instances tested, the quality of solutions obtained by our MN/TS algorithm matches or exceeds that of solutions obtained by the PLS algorithm except in one case (p_hat500-2) where our method obtained a slightly worse solution. By contrast, the MN/TS method obtained strictly superior solutions on 13 out of the 80 instances (C500.9, C1000.9, C2000.9, keller6, MANN_a27, MANN_a45, MANN_a81, hamming10-4, gen400_p0.9_65, p_hat500-3, p_hat1000-3, p_hat1500-2, p_hat1500-3). For all of the remaining 66 instances on which the two algorithms attain the same largest weight (W best ), MN/TS has a success rate of 100 %, while PLS has a 100 % success rate on 52 of these instances.

According to Pullan (2008), the experiments of PLS were performed on a computer that, when executing the DIMACS MC Machine Benchmark program (ftp://dimacs.rutgers.edu in directory /pub/dsj/clique), required respectively 0.31, 1.93 and 7.35 CPU seconds for the graphs r300.5, r400.5 and r500.5. Running this benchmark program on our computer leads to respectively 0.46, 2.79 and 10.44 CPU seconds for these three graphs. In other words, the computer used by PLS is slightly faster than the computer we used for our experiments. Table 3 shows that our MN/TS algorithm required in most cases less computing time to obtain solutions of the same or better quality.

To augment the above comparison, Table 4 contrasts the results of our MN/TS with those of the AugSearch algorithm reported in (Mannino and Stefanutti 1999). The authors of the AugSearch algorithm used a subset of 36 DIMACS graphs with weighting function in which the weight w i of vertex i is set equal to (i mod 10)+1. We have run our algorithm 100 times to solve each of these instances and report the computational statistics in Table 4. As demonstrated, our MN/TS algorithm attains easily all the best objective values W best reported in (Mannino and Stefanutti 1999) with a short computing time ranging from less than 1 second to 13 minutes. (The computing times of AugSearch are based on an IBM-RISC SYSTEM 6000 POWER station 375.) In addition, MN/TS obtains solutions better than those found by AugSearch in 11 cases out of the 36 instances.

Table 4 Comparative results between MN/TS and AugSearch on 36 DIMACS weighted instances. The weight of each vertex i is set equal to (i mod 10)+1 according to Mannino and Stefanutti (1999). Notice that the results reported in Mannino and Stefanutti (1999) for two instances (MANN_a81 and keller6) are wrong since their respective W best values are superior to their respective upper bounds (11000 and 590). MN/TS finds improved solutions for 11 instances (in bold)
Full size table

4.4 Computational results on structured instances from set packing

In this section, we report the outcomes of testing the MN/TS algorithm on the set of 16 structured instances derived from the set packing problem (Delorme et al. 2004; Alidaee et al. 2008), which have sizes ranging from 1000 to 2000. In Alidaee et al. (2008), the set packing problem is solved via a unconstrained quadratic formulation while in Delorme et al. (2004), a dedicated GRASP heuristic was used. For the approach to convert a set packing problem into a maximum weight independent set problem, interested readers are referred to Kwon (2005). (A maximum weight independent set in a graph corresponds to a maximum weight clique in the complement of the graph.)

The results of this experiment are summarized in Table 5. Columns 1–3 give the problem identification (Alidaee et al. 2008). Column 4 gives the previous best known results reported in Alidaee et al. (2008) and Delorme et al. (2004), and columns 5–9 show the computational statistics of the MN/TS algorithm. Table 5 shows that MN/TS attains the previous best known results for all these 16 tested instances. Moreover, our algorithm discovers new best results for two instances (ID15 and ID16). This performance is surprising given that our MN/TS algorithm is not specifically designed for the set packing problem.

Table 5 Computational results on the 16 weighted maximum clique instances from the set packing problem. The best known results (BKR) are published in Alidaee et al. (2008) and Delorme et al. (2004). MN/TS finds improved solutions for 2 instances (in bold)
Full size table

4.5 Experimental results for the unweighted maximum clique problem

The results on the weighted instances have shown the efficacy of the MN/TS algorithm for the maximum weight clique problem. In this section, we additionally test the MN/TS algorithm on the unweighted maximum clique problem, using the DIMACS and BHOSLIB benchmark instances. For this experiment, the search depth L is set equal to 104 except for the brock and san graphs (DIMACS) for which L is set equal to 100.

Table 6 shows the performance of MN/TS on the 80 DIMACS benchmarks. The different columns have the same interpretation as before. W best (column 4) identifies the largest clique found by MN/TS. For 78 of the 80 instances, MN/TS finds the previous best known results in less than seven minutes. This performance matches the current best MCP algorithms like (Cai et al. 2011; Pullan and Hoos 2006; Wu and Hao 2012) and dominates other methods.

Table 6 The computational results obtained by MN/TS on the 80 unweighted DIMACS benchmarks. For 78 of the 80 instances, MN/TS finds the previous best known results in less than 10 minutes
Full size table

The outcomes of applying MN/TS to the BHOSLIB benchmark instances are displayed in Table 7, reinforcing these findings. In particular, for all of these 40 instances, MN/TS successfully obtains the known optimal solutions. In addition, for 23 instances, MN/TS finds optimal solutions with a success rate of 100 %.

Table 7 The computational results obtained by MN/TS on the 40 unweighted BHOSLIB benchmark instances. For all the instances, MN/TS attains the known optimal solutions in less than 7 minutes
Full size table

In sum, Tables 1 to 7 together demonstrate that our MN/TS algorithm is not only very effective for the maximum weight clique problem, but also very competitive for the conventional unweighted case for which it was not specially designed.

5 Influence of neighborhood combination

One of the most important features of a local search algorithm is certainly the definition of its neighborhood. When several neighborhoods are available, the issue of effective ways for using these neighborhoods becomes relevant (Di Gaspero and Schaerf 2006; Lü et al. 2011). As previously noted, the three neighborhoods N 1, N 2 and N 3 induced respectively by the ADD, SWAP and DROP moves are natural components to embody in an overall choice strategy. In our case, at each iteration of our tabu search approach, we have elected to employ the combined neighborhood N 1∪N 2∪N 3, from which we select the admissible move (non-tabu or globally improving) yielding the largest move gain.

For traditional approaches which have been previously applied to the unweighted maximum clique problem, the basic moves consist of the addition or removal of a single vertex from the current clique. (Swap moves thus trivially decompose into two separate moves (Battiti and Mascia 2010).) Within this setting of traditional methods for the MCP, the ADD moves are applied whenever possible as they are the only moves that augment the current clique. DROP moves are considered only when no ADD or SWAP move exists. In this section, we perform tests to apply this traditional way of combining neighborhoods to the MWCP: When admissible ADD moves are present, we select the one yielding the largest move gain (i.e., drawing the move from N 1). Otherwise, if admissible SWAP moves are present, we similarly select one of these moves with the largest gain (drawing the move from neighborhood N 2). If none of these two types of moves is available, a DROP move is applied to remove from C the vertex with the minimum weight (N3). In this approach, the neighborhoods are explored sequentially, as denoted by N 1→N 2→N 3.

We apply our MN/TS algorithm to 10 MWCP instances from the DIMACS-W and BHOSLIB-W benchmarks to compare our N 1∪N 2∪N 3 neighborhood combination with the N 1→N 2→N 3 combination. Each version of the algorithm was run 100 times on each instance with Iter max =108. Table 8 shows that on all these 10 instances, MN/TS with N 1∪N 2∪N 3 matches or outperforms MN/TS with N 1→N 2→N 3. For three instances (C2000.9, Keller6 and frb59-26-4), MN/TS with N 1∪N 2∪N 3 achieves a better weight (W best ) than MN/TS with N 1→N 2→N 3. One also observes that MN/TS with N 1∪N 2∪N 3 requires significantly fewer iterations to reach the same W best .

Table 8 The comparative results between two neighborhood combinations
Full size table

To augment these observations, we show in Fig. 4 the running profiles of our algorithms with N 1∪N 2∪N 3 and N 1→N 2→N 3 on the instances C1000.9 and brock800_1. A running profile is defined by the function i↦f ∗(i) where i is the number of iterations and f ∗(i) is the best value of the objective function (averaged over 100 runs) known at iteration i. Such a profile gives a natural way to observe the evolution of the best values of the objective function during a search.

Fig. 4
figure 5

Running profile of the two algorithms base on N 1∪N 2∪N 3 and N 1→N 2→N 3 on C1000.9 and brock800_1

Full size image

Figure 4 shows that MN/TS with N 1∪N 2∪N 3 strongly dominates MN/TS with N 1→N 2→N 3 on these two test instances by obtaining a faster and better convergence to the best result.

6 Conclusion

A natural concern in local search is to identify how to exploit several different neighborhoods so as to increase the ability of the algorithm to explore the search space more effectively. In this work, we have presented a tabu search algorithm for the maximum weight clique problem based on a combined neighborhood induced by three types of moves. The algorithm explores all these moves at each iteration and selects the best admissible (non-tabu or globally improving) solution that yields the largest weight gain. The tabu mechanism creates an effective local diversification and a multistart strategy is employed to create a global diversification.

Our proposed algorithm is evaluated on a large number of WMCP benchmarks from the BHOSLIB-W and DIMACS-W test sets (containing 40 instances and 80 instances, respectively) and is also applied to 16 instances derived from the set partitioning problem. Compared with leading reference algorithms from the literature, our MN/TS algorithm finds new best solutions in 26 cases (24 DIMACS-W instances and 2 set packing instances). Moreover, our MN/TS approach exhibits an excellent performance when applied to the classical maximum clique problem, obtaining the best-known solutions for all the BHOSLIB instances and for 78 out of the 80 DIMACS instances. All these results are achieved with a computing time ranging from less than one second to 15 minutes on a standard laptop.

We also provided an analysis to show the relevance of the union combination of the underlying neighborhoods by comparing it to the sequential exploration of these neighborhoods. The outcomes suggest that the union combination of neighborhoods plays a key role in contributing to the effectiveness of the proposed algorithm.