<figure><img src="image_1.png" /></figure>

HAL
open science

# Solving the maximum vertex weight clique problem via binary quadratic programming

Yang Wang, Jin-Kao Hao, Fred Glover, Zhipeng Lü, Qinghua Wu

► To cite this version:

Yang Wang, Jin-Kao Hao, Fred Glover, Zhipeng Lü, Qinghua Wu. Solving the maximum vertex weight clique problem via binary quadratic programming. Journal of Combinatorial Optimization, 2016, 32 (2), pp.531-549. 10.1007/s10878-016-9990-2 . hal-01412535

HAL Id: hal-01412535

https://hal.science/hal-01412535

Submitted on 17 Jun 2021

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Solving the maximum vertex weight clique problem via binary quadratic programming

Yang Wang · Jin-Kao Hao* · Fred Glover · Zhipeng Lü · Qinghua Wu

**Abstract** In recent years, the general binary quadratic programming (BQP) model has been widely applied to solve a number of combinatorial optimization problems. In this paper, we recast the maximum vertex weight clique problem (MVWCP) into this model which is then solved by a Probabilistic Tabu Search algorithm designed for the BQP. Experimental results on 80 challenging DIMACS-W and 40 BHOSLIB-W benchmark instances demonstrate that this general approach is viable for solving the MVWCP problem.

**Keywords:** Maximum Vertex Weight Clique; Binary Quadratic Programming; Probabilistic Tabu Search.

In memory of Professor Wenqi Huang for his pioneer work on nature-inspired optimization methods

Yang Wang
School of Management, Northwestern Polytechnical University, 127 Youyi West Road,
710072 Xi'an, China

E-mail: yangw@nwpu.edu.cn

Jin-Kao Hao (Corresponding author)

1) LERIA, Université d'Angers, 2 Boulevard Lavoisier, 49045 Angers, France

2) Institut Universitaire de France, Paris, France

E-mail: jin-kao.hao@univ-angers.fr

Fred Glover
OptTek Systems, Inc., 2241 17th Street Boulder, CO 80302, USA

E-mail: glover@opttek.com

Zhipeng Lü
School of Computer Science and Technology, Huazhong University of Science and Technology, 430074 Wuhan, China

E-mail: zhipeng.lui@gmail.com

Qinghua Wu
School of Management, Huazhong University of Science and Technology, 430074 Wuhan,
China

E-mail: qinghuawu1005@gmail.com
1

# 1 Introduction

2

3

4

5

6

7

8

9

10

11

12

13

14

15

Given an undirected graph $G = (V, E)$ with vertex set $V$ and edge set $E$, a clique is a set of vertices $C \subseteq V$ such that every pair of distinct vertices of $C$ is connected with an edge in $G$, i.e., the subgraph generated by $C$ is complete. The maximum clique problem (MCP) is to find a clique of maximum cardinality. An important generalization of the MCP, known as the maximum vertex weight clique problem (MVWCP), arises when each vertex $i$ in $G$ is associated with a positive weight $w_i$. The MVWCP aims to find a clique of $G$ with the maximum $\sum_{i \in C} w_i$. It is clear that the MCP is a special case of the MVWCP with $w_i = 1$ for each vertex.

The MCP is computationally difficult given that its associated decision problem is known to be NP-complete [10]. As a generalization of the MCP, the MVWCP has at least as the same computational complexity as the MCP. Like the MCP, the MVWCP has important applications in many domains like computer vision, pattern recognition and robotics [4].

To solve these clique problems, a variety of solution algorithms have been reported in the literature. Examples of exact methods based on the general Branch-and-Bound (B&B) or Branch-and-Cut methods for the MCP (or its equivalent maximum stable set problem) can be found in [8, 22, 23, 25, 28, 32–34, 36]. For the MVWCP, some exact algorithms are tightly related to the corresponding algorithms designed for the MCP [3, 27] while other B&B based methods can be found in [38]. On the other hand, a number of heuristic algorithm have also been proposed to find sub-optimal solutions to the MVWCP, including an augmentation algorithm [26], a distributed computational network algorithm [6], a trust region technique algorithm [7], a phased local search algorithm [31], a multi-neighborhood tabu search algorithm [39], and a break-out local search algorithm [5]. For an updated recent review of algorithms for these clique problems, the reader is referred to [41].

During the past decade, binary quadratic programming (BQP) has emerged as a unified model for numerous combinatorial optimization problems, such as max-cut [20, 37], set partitioning [24], set packing [2], generalized independent set [19] and maximum edge weight clique [1]. A review of the additional applications and the reformulation procedures can be found in [18, 21]. Using the BQP model to solve the targeted problem has the advantage of directly applying an algorithm designed for the BQP rather than resorting to a specialized solution method. Moreover, this approach proves to be competitive for several problems compared to specifically designed algorithms [1, 20, 24, 37].

There exists several studies on the application of the BQP model to solve the classic MCP [21, 29, 30]. However, for the more general MVWCP, no computational study has been reported in the literature using the BQP model. In this paper, we investigate for the first time the application of the BQP model to the MVWCP and solve the resulting BQP problem with the Probabilistic Tabu Search algorithm (BQP-PTS) designed for the BQP [37]. Experimental results on 80 challenging DIMACS-W and 40 BHOSLIB-W instances demonstrate that this general BQP approach with the PTS algorithm performs quite

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45
well in terms of solution quality at the price of more computing time for some benchmark instances.

1

2

The rest of this paper is organized as follows. Section 2 illustrates how to transform the MVWCP into the form of the BQP. Section 3 presents our Probabilistic Tabu Search algorithm to solve the transformed BQP model. Section 4 report the computational results and comparisons with other state-of-the-art algorithms in the literature. The paper concludes with Section 5.

3

4

5

6

7

## 2 Transformation to the BQP model

8

### 2.1 Linear model for the MVWCP

9

Given an undirected graph $G = (V, E)$ with vertex set $V$ and edge set $E$, each vertex associated with a positive weight $w_i$, the binary linear programming model for the MVWCP can be formulated as follows [35]:

$$ 
\begin{array}{ll}
\text{Max} & f(x) = \sum_{i=1}^{n} w_i x_i \\
\text{subject to:} & x_i + x_j \le 1, \forall \{v_i, v_j\} \in \bar{E} \\
& x_i \in \{0, 1\}, i \in \{1, \dots, n\}
\end{array}
\qquad (1) 
$$

where $n = |V|$, $x_i$ is the binary variable associated to vertex $v_i$, $\bar{E}$ denotes the edge set of the complementary graph $\bar{G}$.

10

11

Notice that if $w_i = 1$ ($i \in \{1, \dots, n\}$), Eq. (1) turns into the linear model of the classic maximum clique problem.

12

13

### 2.2 Nonlinear BQP alternative

14

The linear model of the MVWCP can be recast into the form of the BQP by utilizing the quadratic penalty function $g(x) = P x_i x_j$ ($x_i$ is binary, $i \in \{1, \dots, n\}$) to replace the inequality constraint of the MVWCP where $P$ is a negative penalty scalar. Since the inequality constraint $x_i + x_j \le 1$ implies that $x_i$ and $x_j$ cannot receive value 1 at the same time, the infeasibility penalty function $g(x)$ will equal to 0 if the inequality constraint is satisfied; otherwise $g(x)$ will take a large penalty value $2P$. To construct the nonlinear BQP model, each inequality constraint is replaced by the penalty function $g(x)$ which is added to the linear objective of Eq. (1) and the nonlinear BQP model can be formulated as follows:

$$ 
\begin{array}{ll}
\text{Max} & xQx = \sum_{i=1}^{n} w_i x_i + \sum_{i=1}^{n} \sum_{j=1, j \neq i}^{n} w_{ij} x_i x_j \\
& x_i \in \{0, 1\}, i \in \{1, \dots, n\}
\end{array}
\qquad (2) 
$$

where $w_{ij} = P$ if $\{v_i, v_j\} \in \bar{E}$ and 0 otherwise.

15
This formulation is one of many nonlinear reformulations of the MVWCP and has been studied in previous work like [17]. The quadratic function will have the same objective value as the linear form subject to all penalty items equaling to 0, indicating that all constraints are satisfied. According to Eq. (2), any violated constraint, i.e., for each {$v_i, v_j$} $\in \bar{E}$, in a solution will add a penalty value $2P$ to the objective value. Thus, simply setting $|P| > 0.5 \sum_{i=1}^{n} w_i$, where each linear objective function coefficient $w_i > 0$, will enable an infeasible solution to get a large penalty value. Actually it suffices to set a smaller $|P| > 0.5w^m$ ($w^m$ is the maximal value among all $w_i$, $i \in \{1, \dots, n\}$). Under this setting, a good decision for improving an infeasible solution would be to remove vertices associated with violated constraints, making constraints gradually reduced and finally an infeasible solution become feasible. Consider that the quadratic penalty function should be negative under the case of a maximal objective, we select $P = -1000$ for the MVWCP benchmark instances tested in our experiments. With this choice, for any optimal solution $x$ of problem (2), $g(x) = 0$ holds. In other words, the subgraph constructed by the variables with the assignment of 1 in the optimized solution $x$ forms a clique. An illustrative example of this transformation is given in Appendix. Since Eq. (2) corresponds to the well-known BQP model, any algorithm designed for solving the BQP can be readily used to solve the MVWCP. In our case, we apply a probabilistic tabu search algorithm described in the next section.

## 3 Probabilistic tabu search algorithm

Metaheuristics are often used to solve hard optimization problems, such as quasi-human based heuristics [16, 40], variable neighborhood search [15], ant colony algorithm [9], probabilistic tabu search [11, 42], etc. In this paper, we solve the MVWCP directly in the nonlinear BQP form as expressed in Eq. (2) by adapting our previous Probabilistic Tabu Search algorithm (BQP-PTS) designed for the BQP [37]. BQP-PTS is a multistart procedure, consisting of a greedy probabilistic solution construction phase and a sequel tabu search phase to optimize the objective function. These two phases proceed iteratively until a stopping condition is satisfied. Below we summarize the main ingredients of the BQP-PTS algorithm.

### 3.1 Greedy probabilistic construction of initial solutions

We construct a new solution for the general BQP model according to a greedy probabilistic construction heuristic. The construction procedure consists of two phases: one is to adaptively and iteratively select some variables to receive the value 1; the other is to assign the value 0 to the remaining variables. The pseudo-code of this construction procedure is shown in Algorithm 1.

First, the partial solution is set to be empty and all the variables of the problem instance are put into the set of the remaining variables $VS$. At each
<caption>**Algorithm 1** Outline of the greedy probabilistic construction heuristic</caption>

1: Let $px$ denote the partial solution and $VS$ denote variables not in the partial solution, initialize $px = \emptyset$, $VS = \{x_1, x_2, \dots, x_n\}$
2: **repeat**
3: Construct a candidate list $CL \subset VS$ where each variable $x_j$ in $CL$ has a positive objective function increment OFI, calculated as $OFI_j = w_j + \sum_{x_i \in px} w_{ij}$
4: Choose randomly one variable $x_s$ from $CL$ with a probability of $1/|CL|$ and set $x_s = 1$
5: Enlarge the partial solution with $px = px \cup \{x_s\}$
6: Update $VS$ with $VS = VS \setminus \{x_s\}$
7: **until** $CL = \emptyset$
8: Set $x_i = 0$ for $\forall x_i \in VS$

iteration we construct a candidate list $CL$ such that $CL$ is a subset of $VS$ and each variable in $CL$ has a positive objective function increment OFI. Then we choose one variable from $CL$ with a probability of $1/|CL|$ and assign it with the value 1. This variable with its assignment value is added into the partial solution and is removed from $VS$. This process continues until $CL$ becomes empty. The last step is to assign the remaining variables in $VS$ with value 0.

To quickly compute the objective function increment OFI, we maintain a vector $IV$, with each entry $IV_i$ recording the objective function increment when putting a variable $x_i$ with the value 1 into the partial solution. Initially, $IV$ is computed as $w_i$ since the initial partial solution is empty. Once a variable $x_s$ joins into the partial solution, then each such entry $IV_i$ with its corresponding variable belonging to the set of the remaining variables $VS$ is updated as $IV_i = IV_i + 2w_{is}$. Because of this additional vector, the complexity of this construction procedure is bounded by $O(n)^2$.

Although this strategy is much simpler than that used in the original algorithm [37], it was experimentally demonstrated to be effective. Notice that seen from the side of the MVWCP, $CL$ is the set of vertices which form a clique with those in the partial solution. This strategy of constructing an initial solution is consistent with many specific maximum clique algorithms in the literature.

## 3.2 Tabu search

For each initial solution generated by the greedy probabilistic construction, we apply an extended version of the tabu search algorithm described in [37] to further improve its quality. The tabu search algorithm in [37] uses a simple one-flip move (flipping the value of a single variable $x_i$ to its complementary value $1-x_i$) to conduct the neighborhood search. Here we not only exploit the one-flip move but also incorporate a two-flip move (flipping the values of a pair of variables $(x_i, x_j)$ to their corresponding complementary values $(1-x_i, 1-x_j)$) [13]. The above two types of moves constitute the neighborhood structures N1 and N2.

One drawback of an N2 move is the amount of time it consumes. Considerable effort is required to evaluate all the two-flip moves because the neigh-
borhood structure N2 generates $n(n - 1)/2$ solutions at each iteration. To overcome this obstacle, we employ an instance of the Successive Filter candidate list strategy of [14] by restricting our attention to moves in N2 that can be obtained as follows. The first step is to examine all the one-flip moves of the current solution $x$, and if any of these moves is improving we go ahead and select it. But if no one-flip move is improving, we limit attention to one-flip moves that produce an objective function value no worse than $f(x) + 2P$, where $f(x)$ is the objective function value of $x$. (Recall that we are maximizing and the penalty $P$ is negative. This implies that the candidate one-flip moves can violate at most a single additional constraint beyond those violated by $x$, since a single constraint is penalized as $Px_{ij} + Px_{ji}$ and hence incurs a penalty of $2P$.) Finally, only the one-flip moves that pass this filtering criterion are allowed to serve as the source of potential two-flip moves.

Tabu search typically introduces a tabu list to assure that solutions visited within a certain number of iterations, called the tabu tenure, will not be revisited [14]. In the present study, each time a variable $x_i$ is flipped, this variable enters into the tabu list and cannot be flipped for the next TabuTenure iterations. For the neighborhood structure N1, our tabu search algorithm then restricts consideration to variables not forbidden by the tabu list. For the neighborhood structure N2, we consider a move to be non-tabu only if both variables associated with this move are not in the tabu list and only such moves are considered during the search process. According to preliminary experiments, we set TabuTenure($i$) = $7 + rand(5)$ where $rand(5)$ produces a random integer from 1 to 5.

For each iteration in our tabu search procedure, a non-tabu move is chosen according to the following rules: (1) if the best move from N1 leads to a solution better than the best solution obtained in this round of tabu search, we select the best move from N1, thus bypassing consideration of N2; (2) if no such move in N1 exists, we select the best move from the combined pool of N1 and N2. A simple aspiration criterion is applied that permits a move to be selected in spite of being tabu if it leads to a solution better than the current best solution. The tabu search procedure stops when the best solution cannot be improved within a given number $\mu$ of moves and we call this number the improvement cutoff. According to a preliminary experiment on parameter tuning, $\mu$ is set to be 5000 for all the instances except for san instances for which $\mu = 10$. In fact, it was observed that for some san instances, it is more effective to restart the search than to make long tabu iterations.

In order to quickly calculate the gains of performing a move, we maintain a vector $\Delta$ which is initialized as follows:

$$ \Delta_i = \begin{cases} w_i + \sum_{j=1, j \neq i}^{n} 2w_{ij}x_j & (x_i = 0) \\ w_i - \sum_{j=1, j \neq i}^{n} 2w_{ij}x_j & (x_i = 1) \end{cases} \quad (3) $$

Then if a move corresponding to a one-flip move $x_i$ is performed, then we update the set of variables affected by this move using the following scheme [12]:
$$ \Delta_k = \begin{cases} -\Delta_k & (k = i) \\ \Delta_k - 2w_{ik} & (k \neq i, x_k = x_i) \\ \Delta_k + 2w_{ik} & (k \neq i, x_k = 1 - x_i) \end{cases} \quad (4) $$

If a move corresponding to a two-flip move $(x_i, x_j)$ from the neighborhood N2 is performed, then we update the set of variables affected by this move using the following scheme [13]:

1

2

3

$$ \Delta_k = \begin{cases} -\Delta_k - 2w_{ij} & (k = i \text{ or } k = j) \\ \Delta_k - 2w_{ik} + 2w_{jk} & (k \neq i, k \neq j, x_k = x_i, x_k = 1 - x_j) \\ \Delta_k + 2w_{ik} - 2w_{jk} & (k \neq i, k \neq j, x_k = x_j, x_k = 1 - x_i) \end{cases} \quad (5) $$

4

5

6

7

8

9

10

11

Given the fact that the BQP-PTS algorithm is designed for the general BQP model (instead of the MVWCP model studied in the paper), the above presentation of BQP-PTS does not refer to the MVWCP. However, it is possible to give an interpretation of some operators used by BQP-PTS related to the MVWCP. For instance, the one-flip move for the BQP model can be considered as moving a single vertex in or out the current solution (clique). On the other hand, such an interpretation will change depending on the target problem under consideration.

# 4 Experimental results

12

## 4.1 Benchmark instances

13

We used two sets of benchmark instances for our computational assessments. The first set concerns 80 DIMACS-W instances proposed in [31], which were adapted from the well-known DIMACS instances<fnref n="1" /> for benchmark purpose to evaluate maximum clique algorithms. The second set is composed of 40 BHOSLIB-W instances<fnref n="2" />, which were adapted from the BHOSLIB benchmarks with hidden optimum solutions [5]. The weighting method is to allocate weights to vertices according to the following scheme: for each vertex $i$, $w_i$ is set equal to $i \mod 200 + 1$, which enables us to exactly replicate the instances without difficulty.

14

15

16

17

18

19

20

21

22

The DIMACS benchmarks comprise the following families of graphs: Random graphs (Cx.y and DSJCx.y of size x and density 0.y), Steiner triple graphs (MANNx with up to 3321 nodes and 5506380 edges), Brockington graphs with hidden optimal cliques (brockx_1, brockx_2, brockx_3, brockx_4 of size x), Gen random graphs with a unique known optimal solution (genx_p0.9_z of size x), Hamming and Johnson graphs stemming from the coding theory, Keller graphs based on Keller's conjecture on tilings using hypercubes (with up to

23

24

25

26

27

28

29

<footnote n="1">¹ http://cs.hb.g.psu.edu/txn131/clique.html</footnote>

<footnote n="2">² http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm</footnote>
**Algorithm 2** Outline of the tabu search algorithm

1: Input: a given solution $x$ with its solution value $f(x)$

2: Output: the local optimal solution $x^*$ with its solution value $f(x^*)$

3: **TL**: an n-dimensional vector for maintaining the tabu list $\Delta$: an n-dimensional vector for recording the move gain of performing each one-flip move

4: Initialize $\Delta$ according to Eq. (3), $TL_i = 0$ for all $i = 1$ to $n$

5: Set $NonImp = 0, Iter = 0$

6: **while** $NonImp < \mu$ ($\mu$ is called improvement cutoff) **do**

7: Identify the best non-tabu one-flip move or the best one-flip move that is tabu but satisfies the aspiration rule from the neighborhood N1, say this move corresponds to flipping $x_i$

8: **if** $f(x) + \Delta_i > f(x^*)$ **then**

9: $x_i = 1 - x_i, f(x) = f(x) + \Delta_i$

10: Update $\Delta$ according to Eq. (4)

11: Update Tabu List by setting $TL_i = Iter + TabuTenure_i$

12: **else**

13: Identify the best non-tabu move or the best tabu move that satisfies the aspiration rule from the neighborhood N1 and N2

14: **if** this move corresponds to flipping $x_i$ **then**

15: $x_i = 1 - x_i, f(x) = f(x) + \Delta_i$

16: Update $\Delta$ according to Eq. (4)

17: Update Tabu List by setting $TL_i = Iter + TabuTenure_i$

18: **end if**

19: **if** this move corresponds to flipping $x_i$ and $x_j$ **then**

20: $x_i = 1 - x_i, x_j = 1 - x_j, f(x) = f(x) + \Delta_i + \Delta_j + 2w_{ij}$

21: Update $\Delta$ according to Eq. (5)

22: Update Tabu List by setting $TL_i = Iter + TabuTenure_i, TL_j = Iter + TabuTenure_j$

23: **end if**

24: **end if**

25: **if** $f(x) > f(x^*)$ **then**

26: $x^* = x, f(x^*) = f(x), NonImp = 0$

27: **else**

28: $NonImp = NonImp + 1$

29: **end if**

30: $Iter = Iter + 1$

31: **end while**

1 3361 vertices and 4,619,898 edges), P-hat graphs (p_hatx-z of size x), San ran-

2 dom graphs (sanx_y_z of size x and density 0.y) and Sanr random graphs

3 (sanrx-z with size x and density z). The BHOSLIB-W benchmarks have sizes

4 ranging from 450 vertices and 17,794 edges up to 1534 vertices and 127,011

5 edges.

6 4.2 Experimental protocol

7 Our Probabilistic Tabu Search algorithm for the BQP model was programmed

8 in C++ and compiled using GNU GCC on a PC with Pentium 2.83GHz CPU

9 and 2GB RAM. We used the CPU clocks as the stop condition of our algo- rithm. Given the stochastic nature of BQP-PTS, each problem instance was independently solved 100 times.
For the DIMACS-W benchmarks, the time limit for a single run was set as follows: 1 minute for instances of hamming, gen, c-fat, johnson, p hat, sanr, keller except keller6 and mann_a9; 5 minutes for instances of brock, dsjc, san and C families except C2000.5, C2000.9, C4000.5; 60 minutes for C2000.5, C2000.9 and keller6; 600 minutes for C4000.5, mann_a27, mann_a45, mann_a81. For the BHOSLIB benchmarks, the time limit was set as 60 minutes.

1

2

3

4

5

6

7

## 4.3 Experimental results

8

In this section, we verify the effectiveness of our BQP approach with the BQP-PTS algorithm on the 80 DIMACS-W instances and 40 BHOSLIB-W instances. Furthermore, we compare this general BQP approach with three recent and powerful heuristics which are specially dedicated to the MVWCP: the PLS<sub>W</sub> algorithm [31], the multi-neighborhood tabu search algorithm MS/TS [39] and the breakout local search BLS [5].

9

10

11

12

13

14

<table><caption>Table 1: Computational comparisons of the BQP-PTS approach with the PLS, MS/TS and BLS algorithms on the set of DIMACS-W instances</caption><thead><tr><th rowspan="2">Instance</th><th colspan="3">BQP-PTS</th><th colspan="3">PLSW [31]</th><th colspan="3">MS/TS [39]</th><th colspan="3">BLS [5]</th></tr><tr><th>Best</th><th>Succ.</th><th>Time</th><th>Best</th><th>Succ.</th><th>Time</th><th>Best</th><th>Succ.</th><th>Time</th><th>Best</th><th>Succ.</th><th>Time</th></tr></thead><tbody><tr><td>brock200_1</td><td>2821</td><td>100</td><td>0.02</td><td>2821</td><td>100</td><td>0.19</td><td>2821</td><td>100</td><td>&lt; &epsilon;</td><td>2821</td><td>100</td><td>&lt; &epsilon;</td></tr><tr><td>brock200_2</td><td>1428</td><td>100</td><td>0.08</td><td>1428</td><td>100</td><td>0.02</td><td>1428</td><td>100</td><td>&lt; &epsilon;</td><td>1428</td><td>100</td><td>0.03</td></tr><tr><td>brock200_3</td><td>2062</td><td>100</td><td>0.09</td><td>2062</td><td>100</td><td>0.01</td><td>2062</td><td>100</td><td>&lt; &epsilon;</td><td>2062</td><td>100</td><td>0.01</td></tr><tr><td>brock200_4</td><td>2107</td><td>100</td><td>0.22</td><td>2107</td><td>100</td><td>0.70</td><td>2107</td><td>100</td><td>&lt; &epsilon;</td><td>2107</td><td>100</td><td>0.01</td></tr><tr><td>brock400_1</td><td>3422</td><td>100</td><td>0.72</td><td>3422</td><td>32</td><td>437.19</td><td>3422</td><td>32</td><td>0.03</td><td>3422</td><td>100</td><td>0.05</td></tr><tr><td>brock400_2</td><td>3350</td><td>100</td><td>1.00</td><td>3350</td><td>61</td><td>415.95</td><td>3350</td><td>61</td><td>0.03</td><td>3350</td><td>100</td><td>0.08</td></tr><tr><td>brock400_3</td><td>3471</td><td>100</td><td>0.57</td><td>3471</td><td>100</td><td>12.04</td><td>3471</td><td>100</td><td>0.03</td><td>3471</td><td>100</td><td>0.26</td></tr><tr><td>brock400_4</td><td>3626</td><td>100</td><td>4.01</td><td>3626</td><td>100</td><td>0.05</td><td>3626</td><td>100</td><td>4.70</td><td>3626</td><td>100</td><td>7.60</td></tr><tr><td>brock800_1</td><td>3121</td><td>100</td><td>3.95</td><td>3121</td><td>100</td><td>31.46</td><td>3121</td><td>100</td><td>0.05</td><td>3121</td><td>100</td><td>0.13</td></tr><tr><td>brock800_2</td><td>3043</td><td>100</td><td>42.29</td><td>3043</td><td>69</td><td>893.42</td><td>3043</td><td>100</td><td>0.20</td><td>3043</td><td>69</td><td>0.51</td></tr><tr><td>brock800_3</td><td>3076</td><td>100</td><td>8.22</td><td>3076</td><td>100</td><td>3.35</td><td>3076</td><td>100</td><td>0.08</td><td>3076</td><td>100</td><td>0.50</td></tr><tr><td>brock800_4</td><td>2971</td><td>8</td><td>105.53</td><td>2971</td><td>100</td><td>3.77</td><td>2971</td><td>100</td><td>49.70</td><td>2971</td><td>100</td><td>339.07</td></tr><tr><td>C125.9</td><td>2529</td><td>100</td><td>0.02</td><td>2529</td><td>100</td><td>8.08</td><td>2529</td><td>100</td><td>0.02</td><td>2529</td><td>100</td><td>0.01</td></tr><tr><td>C250.9</td><td>5092</td><td>100</td><td>0.05</td><td>5092</td><td>17</td><td>247.69</td><td>5092</td><td>100</td><td>0.06</td><td>5092</td><td>100</td><td>0.06</td></tr><tr><td>C500.9</td><td>6955</td><td>100</td><td>0.21</td><td>6822</td><td>-</td><td>-</td><td>6955</td><td>100</td><td>0.07</td><td>6955</td><td>100</td><td>0.25</td></tr><tr><td>C1000.9</td><td>9254</td><td>100</td><td>37.50</td><td>8965</td><td>5</td><td>344.74</td><td>9254</td><td>100</td><td>8.90</td><td>9254</td><td>100</td><td>12.33</td></tr><tr><td>C2000.5</td><td>2466</td><td>71</td><td>1366.51</td><td>2466</td><td>18</td><td>711.27</td><td>2466</td><td>100</td><td>1.84</td><td>2466</td><td>100</td><td>2.1</td></tr><tr><td>C2000.9</td><td>10999</td><td>72</td><td>2711.97</td><td>10028</td><td>-</td><td>-</td><td>10999</td><td>22</td><td>168.11</td><td>10999</td><td>74</td><td>1152.78</td></tr><tr><td>C4000.5</td><td>2792</td><td>19</td><td>19902.77</td><td>2792</td><td>-</td><td>-</td><td>2792</td><td>100</td><td>80.56</td><td>2792</td><td>100</td><td>179.89</td></tr><tr><td>DSJC500.5</td><td>1725</td><td>100</td><td>3.82</td><td>1725</td><td>100</td><td>0.95</td><td>1725</td><td>100</td><td>0.04</td><td>NA</td><td>NA</td><td>NA</td></tr><tr><td>DSJC1000.5</td><td>2186</td><td>81</td><td>115.42</td><td>2186</td><td>100</td><td>47.76</td><td>2186</td><td>100</td><td>0.20</td><td>NA</td><td>NA</td><td>NA</td></tr><tr><td>keller4</td><td>1153</td><td>100</td><td>0.05</td><td>1153</td><td>100</td><td>0.02</td><td>1153</td><td>100</td><td>0.03</td><td>1153</td><td>100</td><td>0.04</td></tr><tr><td>keller5</td><td>3317</td><td>100</td><td>5.34</td><td>3317</td><td>100</td><td>119.24</td><td>3317</td><td>100</td><td>3.17</td><td>3317</td><td>100</td><td>0.65</td></tr><tr><td>keller6</td><td>8062</td><td>2</td><td>3418.36</td><td>7382</td><td>-</td><td>-</td><td>8062</td><td>5</td><td>606.15</td><td>8062</td><td>44</td><td>1980.16</td></tr><tr><td>MANN_a9</td><td>372</td><td>100</td><td>0.01</td><td>372</td><td>100</td><td>&lt; &epsilon;</td><td>372</td><td>100</td><td>&lt; &epsilon;</td><td>NA</td><td>NA</td><td>NA</td></tr><tr><td>MANN_a27</td><td>12277</td><td>4</td><td>22864.81</td><td>12264</td><td>-</td><td>-</td><td>12281</td><td>1</td><td>88.28</td><td>12281</td><td>16</td><td>396.58</td></tr><tr><td>MANN_a45</td><td>34194</td><td>2</td><td>17524.05</td><td>34129</td><td>-</td><td>-</td><td>34192</td><td>1</td><td>390.58</td><td>34229</td><td>1</td><td>929.41</td></tr><tr><td>MANN_a81</td><td>111137</td><td>1</td><td>6167.28</td><td>110564</td><td>-</td><td>-</td><td>111128</td><td>1</td><td>832.24</td><td>111237</td><td>1</td><td>2942.54</td></tr><tr><td>hamming6-2</td><td>1072</td><td>100</td><td>&lt; &epsilon;</td><td>1072</td><td>100</td><td>&lt; &epsilon;</td><td>1072</td><td>100</td><td>&lt; &epsilon;</td><td>1072</td><td>100</td><td>&lt; &epsilon;</td></tr><tr><td>hamming6-4</td><td>134</td><td>100</td><td>&lt; &epsilon;</td><td>134</td><td>100</td><td>&lt; &epsilon;</td><td>134</td><td>100</td><td>&lt; &epsilon;</td><td>134</td><td>100</td><td>&lt; &epsilon;</td></tr><tr><td>hamming8-2</td><td>10976</td><td>100</td><td>0.80</td><td>10976</td><td>100</td><td>&lt; &epsilon;</td><td>10976</td><td>100</td><td>&lt; &epsilon;</td><td>10976</td><td>100</td><td>0.12</td></tr><tr><td>hamming8-4</td><td>1472</td><td>100</td><td>&lt; &epsilon;</td><td>1472</td><td>100</td><td>&lt; &epsilon;</td><td>1472</td><td>100</td><td>&lt; &epsilon;</td><td>1472</td><td>100</td><td>&lt; &epsilon;</td></tr><tr><td>hamming10-2</td><td>50512</td><td>67</td><td>24.47</td><td>50512</td><td>100</td><td>&lt; &epsilon;</td><td>50512</td><td>100</td><td>0.92</td><td>50512</td><td>100</td><td>6.64</td></tr><tr><td>hamming10-4</td><td>5129</td><td>8</td><td>32.49</td><td>5086</td><td>1</td><td>1433.07</td><td>5129</td><td>100</td><td>2.21</td><td>5129</td><td>100</td><td>26.86</td></tr><tr><td>gen200-p0.9.44</td><td>5043</td><td>100</td><td>0.02</td><td>5043</td><td>100</td><td>4.44</td><td>5043</td><td>100</td><td>&lt; &epsilon;</td><td>5043</td><td>100</td><td>0.01</td></tr><tr><td>gen200-p0.9.55</td><td>5416</td><td>100</td><td>0.43</td><td>5416</td><td>100</td><td>0.05</td><td>5416</td><td>100</td><td>0.33</td><td>5416</td><td>100</td><td>1.75</td></tr><tr><td>gen400-p0.9.55</td><td>6718</td><td>100</td><td>0.28</td><td>6718</td><td>2</td><td>340.11</td><td>6718</td><td>100</td><td>0.15</td><td>6718</td><td>2</td><td>0.18</td></tr><tr><td>gen400-p0.9.65</td><td>6940</td><td>100</td><td>0.11</td><td>6935</td><td>4</td><td>200.79</td><td>6940</td><td>100</td><td>0.04</td><td>6940</td><td>100</td><td>0.05</td></tr><tr><td>gen400-p0.9.75</td><td>8006</td><td>100</td><td>0.67</td><td>8006</td><td>100</td><td>&lt; &epsilon;</td><td>8006</td><td>100</td><td>0.88</td><td>8006</td><td>100</td><td>0.43</td></tr><tr><td>c-fat200-1</td><td>1284</td><td>100</td><td>0.01</td><td>1284</td><td>100</td><td>&lt; &epsilon;</td><td>1284</td><td>100</td><td>0.14</td><td>NA</td><td>NA</td><td>NA</td></tr><tr><td>c-fat200-2</td><td>2411</td><td>100</td><td>0.34</td><td>2411</td><td>100</td><td>&lt; &epsilon;</td><td>2411</td><td>100</td><td>0.06</td><td>NA</td><td>NA</td><td>NA</td></tr><tr><td>c-fat200-5</td><td>5887</td><td>100</td><td>0.20</td><td>5887</td><td>100</td><td>&lt; &epsilon;</td><td>5887</td><td>100</td><td>0.02</td><td>NA</td><td>NA</td><td>NA</td></tr><tr><td>c-fat500-1</td><td>1354</td><td>100</td><td>0.20</td><td>1354</td><td>100</td><td>&lt; &epsilon;</td><td>1354</td><td>100</td><td>0.73</td><td>NA</td><td>NA</td><td>NA</td></tr><tr><td>c-fat500-2</td><td>2628</td><td>100</td><td>3.10</td><td>2628</td><td>100</td><td>0.01</td><td>2628</td><td>100</td><td>0.33</td><td>NA</td><td>NA</td><td>NA</td></tr><tr><td>c-fat500-5</td><td>5841</td><td>100</td><td>1.15</td><td>5841</td><td>100</td><td>&lt; &epsilon;</td><td>5841</td><td>100</td><td>0.14</td><td>NA</td><td>NA</td><td>NA</td></tr><tr><td>c-fat500-10</td><td>11586</td><td>100</td><td>1.29</td><td>11586</td><td>100</td><td>&lt; &epsilon;</td><td>11586</td><td>100</td><td>0.06</td><td>NA</td><td>NA</td><td>NA</td></tr><tr><td>johnson8-2-4</td><td>66</td><td>100</td><td>&lt; &epsilon;</td><td>66</td><td>100</td><td>&lt; &epsilon;</td><td>66</td><td>100</td><td>&lt; &epsilon;</td><td>66</td><td>100</td><td>&lt; &epsilon;</td></tr><tr><td>johnson8-4-4</td><td>511</td><td>100</td><td>&lt; &epsilon;</td><td>511</td><td>100</td><td>&lt; &epsilon;</td><td>511</td><td>100</td><td>&lt; &epsilon;</td><td>511</td><td>100</td><td>&lt; &epsilon;</td></tr></tbody></table>
(Continued...)

<table><thead><tr><th rowspan="2">Instance</th><th colspan="3">BQP-PTS</th><th colspan="3">PLSW [31]</th><th colspan="3">MS/TS [39]</th><th colspan="3">BLS [5]</th></tr><tr><th>Best</th><th>Succ.</th><th>Time</th><th>Best</th><th>Succ.</th><th>Time</th><th>Best</th><th>Succ.</th><th>Time</th><th>Best</th><th>Succ.</th><th>Time</th></tr></thead><tbody><tr><td>johnson16-2-4</td><td>548</td><td>100</td><td>&lt; €</td><td>548</td><td>100</td><td>&lt; €</td><td>548</td><td>100</td><td>0.23</td><td>548</td><td>100</td><td>0.01</td></tr><tr><td>johnson32-2-4</td><td>2033</td><td>40</td><td>26.71</td><td>2033</td><td>100</td><td>44.68</td><td>2033</td><td>100</td><td>0.53</td><td>2033</td><td>100</td><td>0.48</td></tr><tr><td>p.hat300-1</td><td>1057</td><td>100</td><td>0.03</td><td>1057</td><td>100</td><td>0.01</td><td>1057</td><td>100</td><td>0.02</td><td>1057</td><td>100</td><td>0.01</td></tr><tr><td>p.hat300-2</td><td>2487</td><td>100</td><td>0.02</td><td>2487</td><td>100</td><td>19.36</td><td>2487</td><td>100</td><td>&lt; €</td><td>2487</td><td>100</td><td>0.02</td></tr><tr><td>p.hat300-3</td><td>3774</td><td>100</td><td>0.04</td><td>3774</td><td>47</td><td>418.11</td><td>3774</td><td>47</td><td>0.02</td><td>3774</td><td>47</td><td>0.01</td></tr><tr><td>p.hat500-1</td><td>1231</td><td>100</td><td>0.17</td><td>1231</td><td>100</td><td>0.42</td><td>1231</td><td>100</td><td>0.03</td><td>1231</td><td>100</td><td>0.04</td></tr><tr><td>p.hat500-2</td><td>3920</td><td>100</td><td>&lt; €</td><td>3925</td><td>100</td><td>&lt; €</td><td>3920</td><td>100</td><td>&lt; €</td><td>3920</td><td>100</td><td>0.01</td></tr><tr><td>p.hat500-3</td><td>5375</td><td>100</td><td>0.36</td><td>5361</td><td>100</td><td>&lt; €</td><td>5375</td><td>100</td><td>0.10</td><td>5375</td><td>100</td><td>0.05</td></tr><tr><td>p.hat700-1</td><td>1441</td><td>100</td><td>0.30</td><td>1441</td><td>100</td><td>0.20</td><td>1441</td><td>100</td><td>0.03</td><td>1441</td><td>100</td><td>0.01</td></tr><tr><td>p.hat700-2</td><td>5290</td><td>100</td><td>0.03</td><td>5290</td><td>100</td><td>78.51</td><td>5290</td><td>100</td><td>0.02</td><td>5290</td><td>100</td><td>0.02</td></tr><tr><td>p.hat700-3</td><td>7565</td><td>100</td><td>2.07</td><td>7565</td><td>12</td><td>718.40</td><td>7565</td><td>100</td><td>0.38</td><td>7565</td><td>100</td><td>0.13</td></tr><tr><td>p.hat1000-1</td><td>1514</td><td>100</td><td>3.78</td><td>1514</td><td>100</td><td>7.61</td><td>1514</td><td>100</td><td>0.08</td><td>1514</td><td>100</td><td>0.07</td></tr><tr><td>p.hat1000-2</td><td>5777</td><td>100</td><td>0.09</td><td>5777</td><td>87</td><td>940.62</td><td>5777</td><td>87</td><td>0.11</td><td>5777</td><td>87</td><td>0.04</td></tr><tr><td>p.hat1000-3</td><td>8111</td><td>100</td><td>0.65</td><td>7986</td><td>100</td><td>&lt; €</td><td>8111</td><td>100</td><td>1.23</td><td>8111</td><td>100</td><td>0.41</td></tr><tr><td>p.hat1500-1</td><td>1619</td><td>95</td><td>17.25</td><td>1619</td><td>100</td><td>48.91</td><td>1619</td><td>100</td><td>0.06</td><td>1619</td><td>100</td><td>0.14</td></tr><tr><td>p.hat1500-2</td><td>7360</td><td>100</td><td>3.61</td><td>7328</td><td>4</td><td>1056.19</td><td>7360</td><td>100</td><td>0.82</td><td>7360</td><td>100</td><td>0.18</td></tr><tr><td>p.hat1500-3</td><td>10321</td><td>9</td><td>34.14</td><td>10014</td><td>100</td><td>&lt; €</td><td>10321</td><td>96</td><td>188.38</td><td>10321</td><td>100</td><td>1.78</td></tr><tr><td>san200-0.7-1</td><td>3370</td><td>100</td><td>0.06</td><td>3370</td><td>100</td><td>&lt; €</td><td>3370</td><td>100</td><td>0.17</td><td>3370</td><td>100</td><td>30.65</td></tr><tr><td>san200-0.7-2</td><td>2422</td><td>100</td><td>0.41</td><td>2422</td><td>66</td><td>397.38</td><td>2422</td><td>100</td><td>0.02</td><td>2422</td><td>100</td><td>0.01</td></tr><tr><td>san200-0.9-1</td><td>6825</td><td>100</td><td>0.02</td><td>6825</td><td>100</td><td>&lt; €</td><td>6825</td><td>100</td><td>0.13</td><td>6825</td><td>100</td><td>23.68</td></tr><tr><td>san200-0.9-2</td><td>6082</td><td>100</td><td>0.02</td><td>6082</td><td>100</td><td>&lt; €</td><td>6082</td><td>100</td><td>0.21</td><td>6082</td><td>100</td><td>0.19</td></tr><tr><td>san200-0.9-3</td><td>4748</td><td>100</td><td>0.64</td><td>4748</td><td>72</td><td>219.68</td><td>4748</td><td>72</td><td>&lt; €</td><td>4748</td><td>100</td><td>0.02</td></tr><tr><td>san400-0.5-1</td><td>1455</td><td>100</td><td>5.74</td><td>1455</td><td>100</td><td>200.44</td><td>1455</td><td>100</td><td>0.06</td><td>1455</td><td>100</td><td>0.22</td></tr><tr><td>san400-0.7-1</td><td>3941</td><td>100</td><td>2.64</td><td>3941</td><td>100</td><td>0.03</td><td>3941</td><td>100</td><td>13.68</td><td>3641</td><td>98</td><td></td></tr><tr><td>san400-0.7-2</td><td>3110</td><td>100</td><td>6.81</td><td>3110</td><td>100</td><td>0.05</td><td>3110</td><td>100</td><td>43.34</td><td>3110</td><td>33</td><td>166</td></tr><tr><td>san400-0.7-3</td><td>2771</td><td>99</td><td>42.54</td><td>2771</td><td>100</td><td>4.41</td><td>2771</td><td>100</td><td>0.05</td><td>2771</td><td>100</td><td>0.05</td></tr><tr><td>san400-0.9-1</td><td>9776</td><td>100</td><td>0.31</td><td>9776</td><td>100</td><td>&lt; €</td><td>9776</td><td>100</td><td>1.29</td><td>9776</td><td>100</td><td>6.25</td></tr><tr><td>san1000</td><td>1716</td><td>100</td><td>40.93</td><td>1716</td><td>100</td><td>&lt; €</td><td>1716</td><td>100</td><td>13.01</td><td>1716</td><td>100</td><td>4.94</td></tr><tr><td>sanr200-0.7</td><td>2325</td><td>100</td><td>0.08</td><td>2325</td><td>100</td><td>0.62</td><td>2325</td><td>100</td><td>&lt; €</td><td>2325</td><td>100</td><td>0.01</td></tr><tr><td>sanr200-0.9</td><td>5126</td><td>100</td><td>&lt; €</td><td>5126</td><td>5</td><td>182.54</td><td>5126</td><td>100</td><td>&lt; €</td><td>5126</td><td>100</td><td>&lt; €</td></tr><tr><td>sanr400-0.5</td><td>1835</td><td>100</td><td>1.41</td><td>1835</td><td>100</td><td>0.67</td><td>1835</td><td>100</td><td>0.02</td><td>1835</td><td>100</td><td>0.04</td></tr><tr><td>sanr400-0.7</td><td>2992</td><td>100</td><td>0.47</td><td>2992</td><td>100</td><td>141.50</td><td>2992</td><td>100</td><td>&lt; €</td><td>2992</td><td>100</td><td>0.03</td></tr></tbody></table>

Table 1 presents the experimental results for the DIMACS-W benchmarks, where the columns under headings of BQP-PTS, PLS<sub>W</sub>, MN/TS and BLS list respectively the best solution values *Best* obtained by each algorithm, number of times to reach *Best* over 100 runs *Succ.*, and the average CPU time *Time* (in seconds) to reach *Best*. Notice that an entry with *< €* signifies the average CPU time was less than 0.01 second and *NA* signifies the results are unavailable. The solution values inferior to the best known ones are marked in bold.

From Table 1, we observe that BQP-PTS obtains 76 best solutions for the evaluated 80 instances, better than 67 of PLS<sub>W</sub> and competitive with 77 of MN/TS and 78 of BLS. For the 2 failed cases, BQP-PTS achieves the second best solutions. In addition, BQP-PTS has a success rate of 100% to reach the best solutions for 64 instances, 12 more than PLS<sub>W</sub> but 4 and 5 less than MN/TS and BLS, respectively. Finally, BQP-PTS reaches the best known results within a reasonable time (less than 30 minutes) for most instances, except for 7 instances of C and MANN families. The long computing time for these instances could be attributed to their difficulty (in fact, the reference MVWCP heuristics also need longer time to attain their best solutions for these instances than for other instances). In particular, PLS<sub>W</sub> can only attain its indicated best values for some of these C and MANN instances (as well as some other instances) under a long and relaxed time condition (indicated by '-' in Table 1). Moreover, unlike the dedicated MVWCP algorithms which incorporate problem specific implementation to ensure their search efficiency, BQP-PTS, as a general solver, does not benefit from such advantages.

Table 2 shows the results of the BQP-PTS approach compared to those of the MN/TS and BLS algorithms for the BHOSLIB-W benchmarks (the PLS<sub>W</sub> algorithm does not report results for the BHOSLIB-W benchmarks).
<table><caption>**Table 2** Computational comparisons of the BQP-PTS approach with the MS/TS and BLS algorithms on the set of BHOSLIB-W instances</caption><thead><tr><th rowspan="2">Instances</th><th colspan="4">BQP-PTS</th><th colspan="4">MN/TS</th><th colspan="4">BLS</th></tr><tr><th>Best</th><th>Succ.</th><th>Avg</th><th>Time</th><th>Best</th><th>Succ.</th><th>Avg</th><th>Time</th><th>Best</th><th>Succ.</th><th>Avg</th><th>Time</th></tr></thead><tbody><tr><td>frb30-15-1</td><td>2990</td><td>100</td><td>2990</td><td>4.90</td><td>2990</td><td>100</td><td>2990</td><td>0.35</td><td>2990</td><td>100</td><td>2990</td><td>1.12</td></tr><tr><td>frb30-15-2</td><td>3006</td><td>100</td><td>3006</td><td>1.58</td><td>3006</td><td>100</td><td>3006</td><td>3.45</td><td>3006</td><td>100</td><td>3006</td><td>8.15</td></tr><tr><td>frb30-15-3</td><td>2995</td><td>100</td><td>2995</td><td>5.80</td><td>2995</td><td>100</td><td>2995</td><td>4.72</td><td>2995</td><td>100</td><td>2995</td><td>11.67</td></tr><tr><td>frb30-15-4</td><td>3032</td><td>100</td><td>3032</td><td>1.04</td><td>3032</td><td>100</td><td>3032</td><td>0.12</td><td>3032</td><td>100</td><td>3032</td><td>0.33</td></tr><tr><td>frb30-15-5</td><td>3011</td><td>100</td><td>3011</td><td>2.13</td><td>3011</td><td>100</td><td>3011</td><td>3.01</td><td>3011</td><td>100</td><td>3011</td><td>3.64</td></tr><tr><td>frb35-17-1</td><td>3650</td><td>100</td><td>3650</td><td>6.59</td><td>3650</td><td>100</td><td>3650</td><td>25.80</td><td>3650</td><td>100</td><td>3650</td><td>68.45</td></tr><tr><td>frb35-17-2</td><td>3738</td><td>100</td><td>3738</td><td>183.17</td><td>3738</td><td>96</td><td>3736.84</td><td>72.09</td><td>3738</td><td>100</td><td>3738</td><td>197.42</td></tr><tr><td>frb35-17-3</td><td>3716</td><td>100</td><td>3716</td><td>15.54</td><td>3716</td><td>100</td><td>3716</td><td>7.72</td><td>3716</td><td>100</td><td>3716</td><td>11.58</td></tr><tr><td>frb35-17-4</td><td>3683</td><td>100</td><td>3683</td><td>5.60</td><td>3683</td><td>77</td><td>3678.31</td><td>94.03</td><td>3683</td><td>100</td><td>3683</td><td>232.36</td></tr><tr><td>frb35-17-5</td><td>3686</td><td>100</td><td>3686</td><td>3.73</td><td>3686</td><td>100</td><td>3686</td><td>8.09</td><td>3686</td><td>100</td><td>3686</td><td>20.00</td></tr><tr><td>frb40-19-1</td><td>4063</td><td>100</td><td>4063</td><td>87.72</td><td>4063</td><td>83</td><td>4062.15</td><td>85.57</td><td>4063</td><td>96</td><td>4062.8</td><td>291.14</td></tr><tr><td>frb40-19-2</td><td>4112</td><td>100</td><td>4112</td><td>76.39</td><td>4112</td><td>87</td><td>4111.16</td><td>134.58</td><td>4112</td><td>100</td><td>4112</td><td>439.81</td></tr><tr><td>frb40-19-3</td><td>4115</td><td>100</td><td>4115</td><td>171.07</td><td>4115</td><td>19</td><td>4108.3</td><td>215.98</td><td>4115</td><td>46</td><td>4111.72</td><td>778.75</td></tr><tr><td>frb40-19-4</td><td>4136</td><td>100</td><td>4136</td><td>758.82</td><td>4136</td><td>89</td><td>4135.56</td><td>96.65</td><td>4136</td><td>98</td><td>4135.92</td><td>333.89</td></tr><tr><td>frb40-19-5</td><td>4118</td><td>100</td><td>4118</td><td>96.63</td><td>4118</td><td>90</td><td>4117.6</td><td>178.89</td><td>4118</td><td>88</td><td>4117.52</td><td>343.82</td></tr><tr><td>frb45-21-1</td><td>4760</td><td>100</td><td>4760</td><td>896.25</td><td>4760</td><td>44</td><td>4748.66</td><td>126.26</td><td>4760</td><td>58</td><td>4754.3</td><td>982.32</td></tr><tr><td>frb45-21-2</td><td>4784</td><td>100</td><td>4784</td><td>92.94</td><td>4784</td><td>47</td><td>4775.86</td><td>228.03</td><td>4784</td><td>100</td><td>4784</td><td>307.06</td></tr><tr><td>frb45-21-3</td><td>4765</td><td>100</td><td>4765</td><td>150.64</td><td>4765</td><td>26</td><td>4756.9</td><td>125.35</td><td>4765</td><td>88</td><td>4764.76</td><td>641.03</td></tr><tr><td>frb45-21-4</td><td>4799</td><td>100</td><td>4799</td><td>453.15</td><td>4799</td><td>43</td><td>4772.41</td><td>174.73</td><td>4799</td><td>96</td><td>4797.24</td><td>576.80</td></tr><tr><td>frb45-21-5</td><td>4779</td><td>100</td><td>4779</td><td>34.17</td><td>4779</td><td>82</td><td>4777.38</td><td>193.82</td><td>4779</td><td>100</td><td>4779</td><td>206.60</td></tr><tr><td>frb50-23-1</td><td>5494</td><td>20</td><td>5487.90</td><td>1911.49</td><td>5494</td><td>6</td><td>5484.74</td><td>186.62</td><td>5494</td><td>11</td><td>5486.41</td><td>1221.72</td></tr><tr><td>frb50-23-2</td><td>5462</td><td>15</td><td>5452.65</td><td>2338.40</td><td>5462</td><td>3</td><td>5434.14</td><td>149.66</td><td>5462</td><td>5</td><td>5440.22</td><td>2837.74</td></tr><tr><td>frb50-23-3</td><td>5486</td><td>100</td><td>5486</td><td>418.35</td><td>5486</td><td>53</td><td>5480.29</td><td>158.71</td><td>5486</td><td>98</td><td>5485.98</td><td>537.96</td></tr><tr><td>frb50-23-4</td><td>5454</td><td>28</td><td>5453.3</td><td>1957.22</td><td>5454</td><td>9</td><td>5451.69</td><td>176.41</td><td>5454</td><td>14</td><td>5453.14</td><td>1190.43</td></tr><tr><td>frb50-23-5</td><td>5498</td><td>100</td><td>5498</td><td>751.84</td><td>5498</td><td>89</td><td>5495.7</td><td>110.85</td><td>5498</td><td>100</td><td>5498</td><td>388.18</td></tr><tr><td>frb53-24-1</td><td>5670</td><td>43</td><td>5660.35</td><td>981.33</td><td>5670</td><td>5</td><td>5637.94</td><td>233.22</td><td>5670</td><td>13</td><td>5652.18</td><td>1056.82</td></tr><tr><td>frb53-24-2</td><td>5707</td><td>25</td><td>5694.3</td><td>1265.70</td><td>5707</td><td>6</td><td>5676.56</td><td>145.22</td><td>5707</td><td>3</td><td>5685.32</td><td>147.65</td></tr><tr><td>frb53-24-3</td><td>5640</td><td>90</td><td>5639.35</td><td>1486.24</td><td>5640</td><td>15</td><td>5610.79</td><td>215.79</td><td>5640</td><td>48</td><td>5629.38</td><td>984.53</td></tr><tr><td>frb53-24-4</td><td>5714</td><td>25</td><td>5700.75</td><td>1753.36</td><td>5714</td><td>7</td><td>5645.61</td><td>449.39</td><td>5714</td><td>13</td><td>5676.16</td><td>1604.50</td></tr><tr><td>frb53-24-5</td><td>5659</td><td>6</td><td>5653.05</td><td>2802.83</td><td>5659</td><td>5</td><td>5628.77</td><td>294.00</td><td>5659</td><td>4</td><td>5642.5</td><td>278.91</td></tr><tr><td>frb56-25-1</td><td>5916</td><td>19</td><td>5877.3</td><td>1035.00</td><td>5916</td><td>3</td><td>5836.85</td><td>308.90</td><td>5916</td><td>5</td><td>5860.82</td><td>1764.87</td></tr><tr><td>frb56-25-2</td><td>5886</td><td>3</td><td>5861.3</td><td>1428.18</td><td>5872</td><td>1</td><td>5807.7</td><td>73.25</td><td>5886</td><td>1</td><td>5838.96</td><td>1013.85</td></tr><tr><td>frb56-25-3</td><td>5859</td><td>1</td><td>5831.6</td><td>449.24</td><td>5859</td><td>1</td><td>5799.38</td><td>181.93</td><td>5859</td><td>1</td><td>5811</td><td>101.48</td></tr><tr><td>frb56-25-4</td><td>5892</td><td>5</td><td>5869.3</td><td>1756.22</td><td>5892</td><td>3</td><td>5839.16</td><td>104.58</td><td>5892</td><td>12</td><td>5860.86</td><td>1256.90</td></tr><tr><td>frb56-25-5</td><td>5853</td><td>1</td><td>5811.5</td><td>3549.57</td><td>5839</td><td>1</td><td>5768.39</td><td>322.70</td><td>5853</td><td>1</td><td>5787.04</td><td>4386.60</td></tr><tr><td>frb59-26-1</td><td>6591</td><td>67</td><td>6585.05</td><td>2228.21</td><td>6591</td><td>3</td><td>6547.53</td><td>166.20</td><td>6591</td><td>17</td><td>6571.6</td><td>1435.99</td></tr><tr><td>frb59-26-2</td><td>6645</td><td>40</td><td>6614.45</td><td>1820.56</td><td>6645</td><td>3</td><td>6567.07</td><td>212.49</td><td>6645</td><td>13</td><td>6602.34</td><td>1834.93</td></tr><tr><td>frb59-26-3</td><td>6608</td><td>1</td><td>6567.55</td><td>2561.16</td><td>6608</td><td>1</td><td>6514.18</td><td>232.77</td><td>6608</td><td>1</td><td>6542.74</td><td>507.93</td></tr><tr><td>frb59-26-4</td><td>6592</td><td>5</td><td>6533.5</td><td>3322.64</td><td>6592</td><td>1</td><td>6498.37</td><td>318.39</td><td>6592</td><td>6</td><td>6526.5</td><td>952.34</td></tr><tr><td>frb59-26-5</td><td>6584</td><td>9</td><td>6554.55</td><td>747.80</td><td>6584</td><td>1</td><td>6522.57</td><td>161.47</td><td>6584</td><td>5</td><td>6546.94</td><td>1512.09</td></tr></tbody></table>

Table 2 lists the best solution values *Best*, number of times hitting *Best* over 100 runs *Succ.*, the average solution values and the average CPU time *Time* (in seconds) to reach *Best* for each algorithm. From Table 2, we observe that BQP-PTS is able to attain the best known results for all the 40 instances as BLS does while MN/TS misses two best values (frb56-25-2 and frb56-25-5). In addition, BQP-PTS has a success rate of 100% to reach the best known results for 22 instances, better than MN/TS for 8 instances and BLS for 14 instances.

1

2

3

4

5

6

7
Moreover, BQP-PTS obtains better average solution values than MN/TS and BLS for 32 and 26 instances, while requiring slightly more computing time, particularly compared to MN/TS.

Finally, we also evaluated our BQP-PTS approach for the (unweighted) maximum clique instances. Without bothering to show tabulated results, we observed that BQP-PTS was able to attain the best known results for 77 of 80 DIMACS instances except for C2000.9 (79 vs 80), MANNa_45 (344 vs 345), MANNa_81 (1098 vs 1100) and for all the 40 BHOSLIB instances. Such a performance can be considered as quite good even compared to the best performing MCP algorithms presented in the recent review [41]. However, our BQP-PTS algorithm requires more computing time than specific MCP algorithms, in particular when it is applied to solve some very difficult instances.

## 5 Conclusion

We recast the maximum vertex weight clique problem (MVWCP) into the binary quadratic programming (BQP) model, which was solved by a Probabilistic Tabu Search algorithm. Experiments on two sets of challenging DIMACS-W and BHOSLIB-W benchmarks indicate that this general BQP approach is viable for solving the MVWCP problem. In particular, without incorporation of domain specific knowledge, this approach was able to attain the best known results for 76 out of 80 DIMACS-W instances and for all the 40 BHOSLIB-W instances within reasonable computing times. For the conventional maximum clique problem, the BQP approach achieved similar performances by attaining the best known results for 77 out of 80 DIMACS instances and for all the 40 BHOSLIB instances. However, our BQP approach is more time consuming than specific algorithms especially for some very difficult instances and some parameters need to be tuned to achieving its best performance. These computational outcomes demonstrate that the general BQP model constitutes an interesting alternative to solve these clique problems without calling for specific heuristics.

For future consideration, it would be interesting to explore using the Probabilistic Tabu Search design not only within the restart part of our method, but also periodically within the improving part of our method which currently consists of a relatively simple form of tabu search. Another interesting research line is to investigate automatic parameter tuning techniques to obtain a general and parameter free BQP solver.

## Acknowledgment

We are grateful to the reviewers and the editors for their comments which help us to improve the paper. This work was supported by National Natural Science Foundation of China (Grant No. 71501157, 71371154) and Northwestern Polytechnical University (Grant No. 3102015RW007).
References

1. Alidaee B, Glover F, Kochenberger GA, Wang H (2007) Solving the maximum edge weight clique problem via unconstrained quadratic programming. European Journal of Operational Research 181:592-597

2. Alidaee B, Kochenberger GA, Lewis K, Lewis M, Wang H (2008) A new approach for modeling and solving set packing problem. European Journal of Operational Research 186(2):504-512

3. Babel L (1994) A fast algorithm for the maximum weight clique problem. Computing 52(1):31-38

4. Ballard D, Brown C (1983) Computer Vision. Prentice-Hall, Englewood Cliffs.

5. Benlic U, Hao JK (2013) Breakout local search for maximum clique problems. Computers & Operations Research 40(1):192-206

6. Bomze IM, Pelillo M, Stix V (2000) Approximating the maximum weight clique using replicator dynamics. IEEE Transactions on Neural Networks 11:1228-1241

7. Busygin S (2006) A new trust region technique for the maximum weight clique problem. Discrete Applied Mathematics 154:2080-2096

8. Carraghan R, Pardalos PM (1990) An exact algorithm for the maximum clique problem. Operations Research Letters 9(6):375-382

9. Dorigo M (1997) Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transaction on Evolutionary Computation 1(1):53-66

10. Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-Completeness. Freeman San Francisco, CA, USA

11. Glover F (1989) Tabu Search - Part I. ORSA Journal on Computing 1(3):190-206

12. Glover F, Hao JK (2010) Efficient evaluation for solving 0-1 unconstrained quadratic optimization problems. International Journal of Metaheuristics 1(1): 3-10

13. Glover F, Hao JK (2010) Fast 2-flip Move Evaluations for Binary Unconstrained Quadratic Optimization Problems. International Journal of Metaheuristics 1(2):100-107

14. Glover F, Laguna M (1997) Tabu Search. Kluwer Academic Publishers

15. Hansen P, Mladenović N (2001) Variable neighborhood search: Principles and applications. European Journal of Operational Research 130(3):449-467

16. He K, Huang W (2010) A quasi-human algorithm for solving the three-dimensional rectangular packing problem. SCIENCE CHINA Information Sciences 53(12): 2389-2398

17. Horst R, Pardalos PM, Thoai N.V. (1995) Introduction to Global Optimization, Non-convex optimization and its applications, vol. 3, Kluwer Academic Publishers

18. Kochenberger GA, Glover F, Alidaee B, Rego C (2004) A unified modeling and solution framework for combinatorial optimization problems. OR Spectrum 26:237-250

19. Kochenberger G, Alidaee B, Glover F, Wang HB (2007) An effective modeling and solution approach for the generalized independent set problem. Optimization Letters 1:111-117

20. Kochenberger G, Hao JK, Lü Z, Wang H, Glover F (2013) Solving large scale max cut problems via tabu search. Journal of Heuristics 19(4):565-571

21. Kochenberger G, Hao JK, Glover F, Lewis M, Lü Z, Wang H, Wang Y (2014) The Unconstrained binary quadratic programming problem: a survey. Accepted to Journal of Combinatorial Optimization 28(1):58-81

22. Konc, J., Janězič, D. (2007). An improved branch and bound algorithm for the maximum clique problem. MATCH - Communications in Mathematical and in Computer Chemistry, 58, 569-590

23. Li C, Quan Z (2010) An efficient branch-and-bound algorithm based on MAXSAT for the maximum clique problem. In proceedings of the 24th AAAI conference on artificial intelligence, 128-133

24. Lewis M, Kochenberger G, Alidaee B (2008) A new modeling and solution approach for the set-partitioning problem. Computers & Operations Research 2008:807-813

25. Macreesh C, Prosser P (2013) Multi-threading a state-of-the-art maximum clique algorithm. Algorithms, 6(4):618-635

26. Manninno C, Stefanutti E (1999) An augmentation algorithm for the maximum weighted stable set problem. Computational Optimization and Applications 14:367-381

27. Östergård PRJ (2001) A new algorithm for the maximum weight clique problem. Nordic Journal of Computing 8(4):424-436
1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

28. Östergård PRJ (2002) A fast algorithm for the maximum clique problem. Discrete Applied Mathematics 120(1): 197-207

29. Pajouh FM, Balasumdaram B, Prokopyev O (2013) On characterization of maximal independent sets via quadratic optimization. Journal of Heuristics 19(4):629-644

30. Pardalos PM, Rodgers GP (1992) A branch and bound algorithm for the maximum clique problem. Computers & Operations Research 19(5):363-375

31. Pullan W (2008) Approximating the maximum vertex/edge weighted clique using local search. Journal of Heuristics 14:117-134

32. Rebennack S, Oswald M, Theis D, Seitz H, Reinelt G, Pardalos PM (2011) A branch and cut solver for the maximum stable set problem. Journal of Combinatorial Optimization 21(4):434-457

33. Rebennack S, Reinelt G, Pardalos PM (2012) A tutorial on branch and cut algorithms for the maximum stable set problem. International Transactions in Operational Research 19(1-2):161-199

34. Segundo, P.S., Rodríguez-Losada, D., Jiménez, A. (2011). An exact bitparallel algorithm for the maximum clique problem. Computers & Operations Research, 38(2), 571-581.

35. Sengor NS, Cakir Y, Guzelis C, Pekergin F, Morgul O (1999) An analysis of maximum clique formulations and saturated linear dynamical network. ARI 51:268-276

36. Tomita E, Kameda T (2007) An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments. Journal of Global Optimization 37(1):95-111

37. Wang Y, Lü Z, Glover F, Hao JK (2013) Probabilistic GRASP-Tabu Search Algorithms for the UBQP problem. Computers & Operations Research 40(12):3100-3107

38. Warren JS, Hicks IV (2006) Combinatorial branch-and-bound for the maximum weight independent set problem. Technical Report, Texas A&M University.

39. Wu Q, Hao JK, Glover F (2012) Multi-neighborhood tabu search for the maximum weight clique problem. Annals of Operations Research 196(1): 611-634

40. Wu Y, Huang W, Lau S, Wong CK, Young GH (2002) An effective quasi-human based heuristic for solving the rectangle packing problem. European Journal of Operational Research 141(2): 341-358

41. Wu Q, Hao JK (2015) A review on algorithms for maximum clique problems. European Journal of Operational Research 242:693-709

42. Xu JF, Chiu SY, Glover F (1996) Probabilistic tabu search for telecommunications network design. Combinational Optimization: Theory and Practice 1(1):69-94

35

## Appendix

36

37

To illustrate the transformation from the MVWCP to the BQP, we consider the following graph:

<figure><img src="image_3.png" /><figcaption>Fig. 1 A graph sample</figcaption></figure>

<figure><img src="image_4.png" /></figure>

38

Its linear formulation according to Eq. (1) is:
$$
\begin{array}{ll}
\text{Max} & f(x) = 2x_1 + 3x_2 + 4x_3 + 5x_4 + 2x_5 + 3x_6 \\
\text{s.t.} & x_1 + x_3 \le 1; \qquad x_1 + x_4 \le 1; \\
& x_1 + x_6 \le 1; \qquad x_2 + x_4 \le 1; \\
& x_2 + x_6 \le 1; \qquad x_3 + x_5 \le 1; \\
& x_3 + x_6 \le 1; \qquad x_5 + x_6 \le 1.
\end{array}
\qquad (6)
$$

Choosing the scalar penalty $P = -15$, we obtain the following BQP model: 1

$$
\begin{equation}
\begin{aligned}
\text{Max} \quad & f(x) = 2x_1 + 3x_2 + 4x_3 + 5x_4 + 2x_5 + 3x_6 - 30x_1x_3 - 30x_1x_4 \\
& \quad -30x_1x_6 - 30x_2x_4 - 30x_2x_6 - 30x_3x_5 - 30x_3x_6 - 30x_5x_6
\end{aligned}
\tag{7}
\end{equation}
$$

which can be re-written as: 2

$$
(x_1 \ x_2 \ x_3 \ x_4 \ x_5 \ x_6) \times \begin{pmatrix} 2 & 0 & -15 & -15 & 0 & -15 \\ 0 & 3 & 0 & -15 & 0 & -15 \\ -15 & 0 & 4 & 0 & -15 & -15 \\ -15 & -15 & 0 & 5 & 0 & 0 \\ 0 & 0 & -15 & 0 & 2 & -15 \\ -15 & -15 & -15 & 0 & -15 & 3 \end{pmatrix} \times \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \end{pmatrix} \quad (8)
$$

Solving this BQP problem yields $x_3 = x_4 = 1$ (all other variables equal zero) and the optimal objective function value is 9. 3
4