# A VNS Metaheuristic with Stochastic Steps for Max 3-Cut and Max 3-Section

Authors: Ai-fan Ling
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

A heuristic algorithm based on VNS is proposed to solve the Max 3-cut and Max 3-section problems. By establishing a neighborhood structure of the Max 3-cut problem, we propose a local search algorithm and a variable neighborhood global search algorithm with two stochastic search steps to obtain the global solution. We give some numerical results and comparisons with the well-known 0.836-approximate algorithm. Numerical results show that the proposed heuristic algorithm can obtain efficiently the high-quality solutions and has the better numerical performance than the 0.836-approximate algorithm for the NP-Hard Max 3-cut and Max 3-section problems.


---

## Body

## 1. Introduction

Given a graphG(V;E), with nodes set Vand edges set E, the Max 3-cut problem is to find a partition S0⊂V, S1⊂V and S2⊂V, of the set V, such that S0⋃‍S1⋃‍S2=V, Si⋂‍Sj=∅(i≠j) and the sum of the weights on the edges connecting the different parts is maximized. Similar to the Max cut problem, the Max 3-cut problem has long been known to be NP complete [1], even for any un-weighted graphs [2], and has also applications in circuit layout design, statistical physics, and so on [3]. However, due to the complexity of this problem, its research progresses is much lower than that of the Max cut problem. Based on the semidefinite programming relaxation proposed by Goemans and Williamson [4], Frieze and Jerrum [5] obtained a 0.800217-approximation algorithm for the Max 3-Cut problem. Recently, Goemans and Williamson [6] and Zhang and Huang [7] improved Frieze and Jerrum’s 0.800217-approximation ratio to 0.836 using a complex semidefinite programming relaxation of the Max 3-cut problem.For the purpose of our analysis, we first introduce some notations. We denote the complex conjugate ofy=a+ib by y¯=a-ib, where i=-1 is the pure image number and the real part and image part of a complex number by Re(·) and Im(·), respectively. For an n dimensional complex vector y∈ℂn written as bold letter and n dimensional complex matrix Y∈ℂn×n, we write y* and Y* to denote their conjugate and transpose. That is, y*=y¯T and Y*=Y¯T. The set of n dimensional real symmetric (semidefinite positive) matrices and the set of n dimensional complex Hermitian (semidefinite positive) matrices are denoted by 𝒮n(𝒮n+) and ℋn(ℋn+), respectively. We sometimes use A≽0 to show A∈𝒮n+(or A∈ℋn+). For any two complex vector u,  v∈ℂn, we write 〈u,v〉=u·v=u*v as their inner product. For any two complex matrices A, B∈ℋn, we write 〈A,B〉=A·B as their inner product; that is, 〈A,B〉=A·B=Tr(B*A)=∑i,j‍b¯ijaij, where A=(aij) and B=(bij). ∥·∥ means the module of a complex number or the 2-norm of a complex vector or the F-norm of a complex matrix.Let the third root of unity be denoted byω0=1, ω=ω1=ei(2π/3), ω2=ei(4π/3). Introduce a complex variable yi∈{1,ω,ω2}, i=1,…,n, then it is not hard to know that
(1.1)23-13yi⋅yj-13yj⋅yi=23(1-Re(yi⋅yj)).
Denote Sk={i:yi=ωk,k=0,1,2} and y=(y1,…,yn)T. Then the Max 3-cut problem can be expressed as
(1.2)M3C:max⁡⁡f(y)=23∑i<j‍wij(1-Re(yi⋅yj))s.t.fy∈{1,ω,ω2}n,
here y∈{1,ω,ω2}n means that yi∈{1,ω,ω2}, i=1,…,n, W=(wij) is the weight-valued matrix of a given graph.By relaxing the complex variableyi into an n dimensional complex vector yi, we get a complex semidefinite programming (CSDP) relaxation of (M3C) as follows:
(1.3)CSDP:max⁡23∑i<j‍wij(1-Re(yi⋅yj))s.t.‖yi‖=1,i=1,2,…,n,s.t.Aijk⋅Y≥-1,i,j=1,2,…,n,k=0,1,2s.t.Y≽0,
where Yij=yi·yj, Aijk=ωkeiejT+ω-kejeiT and ei denotes the vector with zeros everywhere except for an unit in the ith component. It is easily to verify that constraints Aijk·Y≥-1 can be expressed as
(1.4)Re(ωkYij)≥-12,k=0,1,2.
To get an approximate solution of M3C, Goemans and Williamson [6] do not directly solve the CSDP, but solve an equivalent real SDP with following form (Although some softwares, such as SeDuMi [8] and the earlier version of SDPT3-4.0 [9], can deal with SDPs with complex data, this does not reduce the dimensions of problems):
(1.5)RSDP:max⁡⁡12[QOOQ]⋅Xs.t.[eieiTOOeieiT]⋅X=2,i=1,2,…,n,s.t.X[Re(Aijk)-Im⁡(Aijk)Im⁡(Aijk)Re(Aijk)]⋅X≥-2,1≤i<j≤n,k=0,1,2s.t.X[Aij0OO-Aij0]⋅X=0,1≤i<j≤n,s.t.X[OAij0Aij0O]⋅X=0,1≤i<j≤n,s.t.X[OeieiTeieiTO]⋅X=0,i=1,2,…,n,s.t.XX∈S+2n,
where Q=(1/3)diag(We)-W is the Laplace matrix of given graph, O is an n-dimensional full zeros matrix.In RSDP, the first, third, and forth classes of equality constraints ensure thatXii=1, i=1,2,…,n and with the form
(1.6)X=[R-SSR].
The final two classes of equality constraints ensure that Sii=0(i=1,…,n) and S is a skew-symmetric matrix.IfX is an optimal solution of RSDP, then the complex matrix Y^=R+iS is an optimal solution of CSDP. Then one can randomly generate a complex vector ξ, such that ξ~N(0,Y^), and set
(1.7)yi^={1,ifArg(ξi)∈[0,2π3),ω,ifArg(ξi)∈[2π3,4π3),ω2,ifArg(ξi)∈[4π3,2π),
where Arg(·)∈[0,2π] means the complex angle principal value of a complex number. Goemans and Williamson [6] had verified that, see also Zhang and Huang [7],
(1.8)f(y^)≥0.836⋅(Q⋅Y^).The algorithm proposed by Goemans and Williamson [6] can obtain a very good approximate ratio, and RSDP can be solved by interior point algorithm, but the 0.836-approximate algorithm will be not practical in numerical study for the Max 3-cut problem. From RSDP, one can see that for a graph with n nodes, RSDP has 2n+5n(n-1)/2 constraints and 3n(n-1)/2 slack variables via the inequality constraints. That is to say, RSDP has a 2n dimensional unknown symmetrical semidefinite positive matrix variable and a 3n(n-1)/2 dimensional unknown vector variable, and 2n+5n(n-1)/2 constraints, and has also many matrices without an explicit block diagonal structure although they are sparse. For instance, when n=100, RSDP becomes a very-high-dimensional semidefinite programming problem with 14850 slack variables and 24950 constraints. Further, as we known, it is only a class of universal and medium-scale instances for Max 3-cut problems with 50 to 100 nodes. Hence, it will be very time consuming to solve such a RSDP relaxation of M3C using the current existing any SDP softwares. This leads that 0.836-approximate algorithm is not suitable for computational study of the Max 3-cut problem. This limitation for solving M3C based on CSDP (or RSDP) relaxation motivates us to find a new efficient and fast algorithm for the practical purpose for the Max 3-cut problem.In the current paper, we first establish a definition ofK-neighborhood structure of the Max 3-cut problem and design a local search algorithm to find the local minimizer. And then, we propose a variable neighborhood search (VNS) metaheuristic with stochastic steps which is originally considered by Mladenović and Hansen [10], by which we can find efficiently a high-quality global approximate solution of the Max 3-cut problem. Further, combining a greed algorithm, we extend the proposed algorithm to the Max 3-section problem. To the best of our knowledge, it is first time to consider the computational study of the Max 3-cut problem. In order to test the performance of the proposed algorithm, we compare the numerical results with Goemans and Williamson’s 0.836-approximate algorithm.This paper is organized as follows. In Section2, we give some definitions and lemmas. In Section 3, we present the VNS metaheuristic for solving the Max 3-cut problem. The VNS is extended to the Max 3-section problem in Section 4. In Section 5, we give some numerical results and comparisons.


## 2. Preliminaries

In this section, we will establish some definitions and give some facts for our sequel purpose. For the third roots of unity,1, ω, ω2, we can get the following fact:
(2.1)‖1-ω‖2=‖ω-ω2‖2=‖1-ω2‖2=3.
Denote 𝕊={1,ω,ω2}n. Then based on (2.1), for any y∈𝕊, we may definite a K-neighborhood of y as follows.Definition 2.1.
For anyy∈𝕊 and any positive integer number K(1≤K≤n), one defines the K-neighborhood, denoted by NK(y), of y as the set
(2.2)NK(y)={z∈S:‖z-y‖2=∑i=1n‖zi-yi‖2≤3K}.
In particular, if K=1, we write the 1-neighborhood N1(y) of y as N(y).The boundary of theK-neighborhood NK(y) is defined by ∂NK(y)={z∈𝕊:∥y-z∥2=3K}. Clearly, N(y)=∂N(y). If z∈∂NK(y), we call z a K-neighbor of y. From Definition 2.1, the difference of between points y and its K-neighbor z is that they have only K different components. By computing straightforwardly, we get the number of elements of ∂NK(y), that is |∂NK(y)|=2KCnK. Particularly, |∂N(y)|=2n when K=1.Example 2.2.
Lety=(ω,ω,ω2)T∈{1,ω,ω2}3. Then (1,ω,ω2)T∈N(y), (1,ω2,ω2)T∈∂N2(y)⊂N2(y), and (1,ω2,ω)T∈∂N3(y)⊂N3(y).Definition 2.3.
For anyu∈{0,1,2}, define two maps from {1,ω,ω2} to itself as follows: τi(ωu)=ωu+i∈{1,ω,ω2},i=1,2.Clearly, for anyu∈{0,1,2}, τi(ωu)≠ωu, i=1,2 and τ1(ωu)≠τ2(ωu). Applying Definition 2.3, for any z∈N(y) there exists an unique component, zk say, of z, such that zk≠yk and either zk=τ1(yk) or zk=τ2(yk), and other components of z and y are the same. For simplicity, for any z∈N(y) with zk≠yk and zi=yi(i=1,…,n,i≠k), we denote by z=τ1k(y) or z=τ2k(y) corresponding to zk=τ1(yk) or zk=τ2(yk). By Definitions 2.1 and 2.3, for any y∈𝕊, we can structure its 1-neighborhood points using maps defined by Definition 2.3; that is, we have the following result.Lemma 2.4.
Letτi(·)(i=1,2) be defined by Definition 2.3. Then, for any y∈𝕊 and any fixed positive integer number k(1≤k≤n), one has
(2.3)τik(y)∈N(y),i=1,2,
that is, τ1k(y) and τ2k(y) are two 1-neighborhood points of y.Definition 2.5.
A pointy^∈𝕊 is called a K-local maximizer of the function f over 𝕊, if f(y^)≥f(y), for all y∈NK(y^). Furthermore, if f(y^)≥f(y) for all y∈𝕊, then y^ is called a global maximizer of f over 𝕊. A 1-local maximizer of the function f is also called a local maximizer of the function f over 𝕊.


## 3. VNS for Max 3-Cut

### 3.1.  Local Search Algorithm

Lety0=(y10,…,yn0)T∈𝕊 be a feasible solution of problem M3C. If y0 is not a local maximizer of f, then for all y∈N(y0), we may find a y~∈N(y0), such that f(y~)=max{f(y):y∈N(y0)}. It is clear that f(y~)≥f(y0). If y~ is not still a local maximizer of f, then replacing y0 with y~ and repeating the process until a point y^ satisfying f(y^)=max{f(y):y∈N(y^)} is found, which indicates that y^ is a local maximizer of f.For any positive integer numberk(1≤k≤n), let yk=(y1k,…,ynk)T=τik(y0)∈N(y0)(i=1,2); that is,
(3.1)yik=yi0,i=1,2,…,k-1,k+1,…,n;ykk≠yk0.
Denote
(3.2)δ(k)=f(y0)-f(yk).
Then, we have the following result whose proof is clear.Lemma 3.1.
Consider(3.3)δ(k)={23∑i=1k-1wikRe[yi0⋅(ykk-yk0)]+23∑j=k+1nwkjRe[(ykk-yk0)⋅yj0],k>1;23∑j=k+1nwkjRe[(ykk-yk0)⋅yj0],k=1.Based on Lemma3.1, if we know the value of f(y0), then we can obtain the value function f(yk) at next iterative point yk by calculating δ(k) by (3.3), instead of calculating directly the values f(yk), which reduces sharply the computational cost. By Definition 2.1, there exist two points satisfying (3.1) for fixed k; that is, when yk∈N(y0) and (3.1) is satisfied, then either ykk=τ1(yk0) or ykk=τ2(yk0). For our convenience, we denote δ(k) by δ1(k) when ykk=τ1(yk0) and by δ2(k) when ykk=τ2(yk0). In what follows, we describe the local search algorithm for the Max 3-cut problem denoted by LSM3C; by this algorithm, we can get a local maximizer of functionf(y) over 𝕊.ForLSM3C, one has the following.(1)
Input any initial feasible solutiony0 of problem (M3C).(2)
Fork from 1 to n, set zk1=τ1k(y0), calculate δ1(k), and set again zk2=τ2k(y0), calculate δ2(k).(3)
Findδi*(k*) by the following way:
(3.4)δi*(k*)=min⁡{δ1(1),δ2(1),…,δ1(k),δ2(k),…,δ1(n),δ2(n)}.(4)
Ifδi*(k*)≥0, then set y^=y0, return y^, and stop. Otherwise, go to next.(5)
Sety0=τi*k*(y0); go to Step 2.


### 3.2.Variable Neighborhood Stochastic Search

Lety^ be a local maximizer obtained by LSM3C and Kmax(1<Kmax≤n) a fixed positive integer number. we now describe the variable neighborhood search (VNS) with stochastic steps, by which we can find an approximate global maximizer of problem (M3C). The proposed VNS algorithm actually has three phases: First, for any given positive integer number K<Kmax, a K-neighborhood point, y say, is randomly selected; that is, y∈NK(y^). Next, a solution, y^^ say, is obtained by applying algorithm LSM3C to y. Finally, the current solution jumps from y^ to y^^ if it improves the former one. Otherwise, the order K of the neighborhood is increased by one when K<Kmax and the above steps are repeated until some stopping condition is met. The VNS that is also called k-max [11] can be illustrated as follows.ForVNS-k, one has the following.(1)
Arbitrary choose a pointy0∈𝕊, implement LSM3C starting from y0∈𝕊 and denote the obtained local maximizer byy^.Set K=1.(2)
Randomly take a pointy∈∂NI(K)(y^) and implement again LSM3C from y, and denote the obtained new local maximizer by y^^.(3)
Iff(y^^)>f(y^), then set y^=y^^ and K=1; go to Step 2.(4)
IfK<Kmax(≤n), set K=K+1; go to Step 2. Otherwise, return y^ as an approximate global solution of problem M3C and stop.The subscriptI(K) in Step 2 is a function of K and is also a positive integer number not greater than n. I(K) reflects the main skill of converting the current neighborhood of local maximizer y^ into another neighborhood of y^. For a given Kmax, let m=⌊n/Kmax⌋ and K0=n-mKmax, where ⌊a⌋ means the integral part of a. We divide the n neighborhoods of y^, N(y^),N2(y^),…,NK(y^),…,Nn(y^) into Kmax neighborhood blocks NI(1)(y^),…,NI(Kmax)(y^), such that, for K=1,2,…,Kmax-K0,
(3.5)N(K-1)m+1(y^)⊆NI(K)(y^)⊆NKm+1(y^),
and, for K=Kmax-K0+1,…,Kmax-K0+j,…,Kmax,
(3.6)N(K-1)(m+1)+1(y^)⊆NI(K)(y^)⊆NK(m+1)(y^).
In order to obtain the Kmax neighborhood blocks of y^, NI(K)(y^), K=1,…,Kmax, we divide the set {1,2,…,n} into Kmax disjoint subsets, where each subset of the first Kmax-K0 subsets has m integers and each subset of the last K0 subsets has m+1 integers. For any integer K(≤Kmax), let
(3.7)I(K)=(K-1)⋅m+[c⋅m]+1,K=1,2,…,Kmax⁡-K0,
or
(3.8)I(K)=(Kmax⁡-K0)m+[(m+1)⋅c]+1+(m+1)(K-(Kmax⁡-K0)-1)=[(m+1)⋅c]+1+(m+1)(K-1)-(Kmax⁡-K0),K=Kmax⁡-K0+1,…,Kmax⁡-K0+j,…,Kmax⁡.
Then we can randomly choose a point y in ∂NI(K)(y^), where c∈(0,1) is a random number from uniformly distribution 𝒰(0,1), such that NI(K)(y^) satisfies (3.5) or (3.6).VNS-k stops when the maximum K neighborhood is reached. Additionally, we also consider another termination criterion of VNS based on the maximum CPU-time and denoted by VNS-t. VNS-t can obtain a better solution than VNS-k since VNS-t actually runs several times VNS-k in the maximum allowing time tmax, but it generally has to spend more computational time. The VNS-t can be stated as follows.ForVNS-t, one has the following.(1)
SettCPU=0, running VNS-k for an arbitrary initial point y0∈𝕊, and let a local optimal solution y^ be obtained.(2)
IfK=Kmax(≤n), go to Step 3.(3)
IftCPU<tmax, then set K=1; go to Step 2 in VNS-k. Otherwise, return y^ as an approximate global solution of problem M3C and stop.We mention that it differs from the classical variable neighborhood search metaheuristic that is originally proposed by Mladenović and Hansen [10]. In order to obtain a global optimal solution or a high-quality approximate solution of problem M3C, we use two stochastic steps in VNS. First, for a fixed K, a K-neighbor of y^ is chosen randomly. Second, by the definition of I(K), when we change the neighborhood of y^ from NI(K-1) to NI(K), NI(K) may take any a neighborhood among N(K-1)m+j, j=1,2,…,m of y^, which is decided by random number c. In VNS, positive integer Kmax decides the maximum search neighborhood block of y^, which also decides directly the CPU-time of VNS. Based on the second stochastic step, we may choose a relative small Kmax comparing with n. This can decrease our computational time.


## 3.1.  Local Search Algorithm

Lety0=(y10,…,yn0)T∈𝕊 be a feasible solution of problem M3C. If y0 is not a local maximizer of f, then for all y∈N(y0), we may find a y~∈N(y0), such that f(y~)=max{f(y):y∈N(y0)}. It is clear that f(y~)≥f(y0). If y~ is not still a local maximizer of f, then replacing y0 with y~ and repeating the process until a point y^ satisfying f(y^)=max{f(y):y∈N(y^)} is found, which indicates that y^ is a local maximizer of f.For any positive integer numberk(1≤k≤n), let yk=(y1k,…,ynk)T=τik(y0)∈N(y0)(i=1,2); that is,
(3.1)yik=yi0,i=1,2,…,k-1,k+1,…,n;ykk≠yk0.
Denote
(3.2)δ(k)=f(y0)-f(yk).
Then, we have the following result whose proof is clear.Lemma 3.1.
Consider(3.3)δ(k)={23∑i=1k-1wikRe[yi0⋅(ykk-yk0)]+23∑j=k+1nwkjRe[(ykk-yk0)⋅yj0],k>1;23∑j=k+1nwkjRe[(ykk-yk0)⋅yj0],k=1.Based on Lemma3.1, if we know the value of f(y0), then we can obtain the value function f(yk) at next iterative point yk by calculating δ(k) by (3.3), instead of calculating directly the values f(yk), which reduces sharply the computational cost. By Definition 2.1, there exist two points satisfying (3.1) for fixed k; that is, when yk∈N(y0) and (3.1) is satisfied, then either ykk=τ1(yk0) or ykk=τ2(yk0). For our convenience, we denote δ(k) by δ1(k) when ykk=τ1(yk0) and by δ2(k) when ykk=τ2(yk0). In what follows, we describe the local search algorithm for the Max 3-cut problem denoted by LSM3C; by this algorithm, we can get a local maximizer of functionf(y) over 𝕊.ForLSM3C, one has the following.(1)
Input any initial feasible solutiony0 of problem (M3C).(2)
Fork from 1 to n, set zk1=τ1k(y0), calculate δ1(k), and set again zk2=τ2k(y0), calculate δ2(k).(3)
Findδi*(k*) by the following way:
(3.4)δi*(k*)=min⁡{δ1(1),δ2(1),…,δ1(k),δ2(k),…,δ1(n),δ2(n)}.(4)
Ifδi*(k*)≥0, then set y^=y0, return y^, and stop. Otherwise, go to next.(5)
Sety0=τi*k*(y0); go to Step 2.


## 3.2.Variable Neighborhood Stochastic Search

Lety^ be a local maximizer obtained by LSM3C and Kmax(1<Kmax≤n) a fixed positive integer number. we now describe the variable neighborhood search (VNS) with stochastic steps, by which we can find an approximate global maximizer of problem (M3C). The proposed VNS algorithm actually has three phases: First, for any given positive integer number K<Kmax, a K-neighborhood point, y say, is randomly selected; that is, y∈NK(y^). Next, a solution, y^^ say, is obtained by applying algorithm LSM3C to y. Finally, the current solution jumps from y^ to y^^ if it improves the former one. Otherwise, the order K of the neighborhood is increased by one when K<Kmax and the above steps are repeated until some stopping condition is met. The VNS that is also called k-max [11] can be illustrated as follows.ForVNS-k, one has the following.(1)
Arbitrary choose a pointy0∈𝕊, implement LSM3C starting from y0∈𝕊 and denote the obtained local maximizer byy^.Set K=1.(2)
Randomly take a pointy∈∂NI(K)(y^) and implement again LSM3C from y, and denote the obtained new local maximizer by y^^.(3)
Iff(y^^)>f(y^), then set y^=y^^ and K=1; go to Step 2.(4)
IfK<Kmax(≤n), set K=K+1; go to Step 2. Otherwise, return y^ as an approximate global solution of problem M3C and stop.The subscriptI(K) in Step 2 is a function of K and is also a positive integer number not greater than n. I(K) reflects the main skill of converting the current neighborhood of local maximizer y^ into another neighborhood of y^. For a given Kmax, let m=⌊n/Kmax⌋ and K0=n-mKmax, where ⌊a⌋ means the integral part of a. We divide the n neighborhoods of y^, N(y^),N2(y^),…,NK(y^),…,Nn(y^) into Kmax neighborhood blocks NI(1)(y^),…,NI(Kmax)(y^), such that, for K=1,2,…,Kmax-K0,
(3.5)N(K-1)m+1(y^)⊆NI(K)(y^)⊆NKm+1(y^),
and, for K=Kmax-K0+1,…,Kmax-K0+j,…,Kmax,
(3.6)N(K-1)(m+1)+1(y^)⊆NI(K)(y^)⊆NK(m+1)(y^).
In order to obtain the Kmax neighborhood blocks of y^, NI(K)(y^), K=1,…,Kmax, we divide the set {1,2,…,n} into Kmax disjoint subsets, where each subset of the first Kmax-K0 subsets has m integers and each subset of the last K0 subsets has m+1 integers. For any integer K(≤Kmax), let
(3.7)I(K)=(K-1)⋅m+[c⋅m]+1,K=1,2,…,Kmax⁡-K0,
or
(3.8)I(K)=(Kmax⁡-K0)m+[(m+1)⋅c]+1+(m+1)(K-(Kmax⁡-K0)-1)=[(m+1)⋅c]+1+(m+1)(K-1)-(Kmax⁡-K0),K=Kmax⁡-K0+1,…,Kmax⁡-K0+j,…,Kmax⁡.
Then we can randomly choose a point y in ∂NI(K)(y^), where c∈(0,1) is a random number from uniformly distribution 𝒰(0,1), such that NI(K)(y^) satisfies (3.5) or (3.6).VNS-k stops when the maximum K neighborhood is reached. Additionally, we also consider another termination criterion of VNS based on the maximum CPU-time and denoted by VNS-t. VNS-t can obtain a better solution than VNS-k since VNS-t actually runs several times VNS-k in the maximum allowing time tmax, but it generally has to spend more computational time. The VNS-t can be stated as follows.ForVNS-t, one has the following.(1)
SettCPU=0, running VNS-k for an arbitrary initial point y0∈𝕊, and let a local optimal solution y^ be obtained.(2)
IfK=Kmax(≤n), go to Step 3.(3)
IftCPU<tmax, then set K=1; go to Step 2 in VNS-k. Otherwise, return y^ as an approximate global solution of problem M3C and stop.We mention that it differs from the classical variable neighborhood search metaheuristic that is originally proposed by Mladenović and Hansen [10]. In order to obtain a global optimal solution or a high-quality approximate solution of problem M3C, we use two stochastic steps in VNS. First, for a fixed K, a K-neighbor of y^ is chosen randomly. Second, by the definition of I(K), when we change the neighborhood of y^ from NI(K-1) to NI(K), NI(K) may take any a neighborhood among N(K-1)m+j, j=1,2,…,m of y^, which is decided by random number c. In VNS, positive integer Kmax decides the maximum search neighborhood block of y^, which also decides directly the CPU-time of VNS. Based on the second stochastic step, we may choose a relative small Kmax comparing with n. This can decrease our computational time.


## 4.  A Greedy Algorithm for Max 3-Section

When the number of nodesn is a multiple of three and the condition |S0|=|S1|=|S2|=n/3 is required, the Max 3-cut problem becomes the Max 3-section problem. Notice that 1+ω+ω2=0, then the Max 3-section problem can be formulated as the following programming problem M3S:
(4.1)M3S:max⁡23∑i<j‍wij(1-Re(yi⋅yj))s.t.23∑i=1n‍yi=0,s.t.2323y∈S,
and its CSDP relaxation is
(4.2)CSDP1:max⁡23∑i<j‍wij(1-Re(yi⋅yj))s.t.2323eeT⋅Y=0,s.t.2323‖yi‖=1,i=1,2,…,n,s.t.2323Aijk⋅Y≥-1,i,j=1,2,…,n,k=0,1,2s.t.2323Y≽0,
where e is the column vector of all ones. Andersson [12] extended Frieze and Jerrum’s random rounding method to M3S and obtained a (2/3)+O(1/n3)-approximate algorithm, which is the current best approximate ratio for M3S; also see the recent research of Gaur et al. [13]. The author of the current paper considers a special the Max 3-Section problem and obtains a 0.6733-approximate algorithm; see Ling (2009) [14].Clearly, the feasible region of problem M3S is a subset of𝕊, and the optimal value of problem M3S is not greater than that of problem M3C. Assume that we have get a global optimal solution or a high-quality approximate solution y^ of problem M3C. It is clear that y^ may not satisfy the condition ∑i=1n‍y^i=0. But we may adjust y^ to get a new feasible solution ys using a greedy algorithm, such that ys satisfies ∑i=1n‍yis=0. This is the motivation that we propose the greedy algorithm for the Max 3-section problem.For the sake of our analysis, without loss of generality, we assume that the local maximizery^ satisfies |S0|=max{|S0|,|S1|,|S2|}. This means that S0={i:y^i=1} is the subset of V with maximum cardinal number. If |Sk|=max{|S0|,|S1|,|S2|}(k≠0,k=1,2), then we may set yiN=w¯ky^i, i=1,…,n. The resulted new solution yN=(y1N,…,yiN) will not change the objective value since f(y^)=f(w¯ky^)(k≠0,k=1,2); moreover, the new partition {S0N,S1N,S2N} based on yN satisfies |S0N|=max{|S0N|,|S1N|,|S2N|}. By our assumption, the partition S={S0,S1,S2} still exist four possible cases.Case 1.
|
S
0
|
≥
|
S
1
|
≥
n
/
3
≥
|
S
2
|.Case 2.
|
S
0
|
≥
n
/
3
≥
|
S
1
|
≥
|
S
2
|.Case 3.
|
S
0
|
≥
|
S
2
|
≥
n
/
3
≥
|
S
1
|.Case 4.
|
S
0
|
≥
n
/
3
≥
|
S
2
|
≥
|
S
1
|.
The sizes adjusting greedy algorithm of Cases3 and 4 are similar to Cases 1 and 2. Hence, we mainly consider Cases 1 and 2 for adjusting the partition of V from S={S0,S1,S2} to S~={S~0,S~1,S~2} such that |S~k|=n/3, k=0,1,2. Denote
(4.3)δ0(i)=∑j∈S1∪S2‍wij,i∈S0,δ01(i)=∑j∈S1‍wij,i∈S0,δ10(i)=∑j∈S0‍wij,i∈S1,δ02(i)=∑j∈S2‍wij,i∈S0,δ20(i)=∑j∈S0‍wij,i∈S2,δ12(i)=∑j∈S2‍wij,i∈S1,δ21(i)=∑j∈S1‍wij,i∈S2.
Then, it follows from simple computation that
(4.4)δ0(i)=δ01(i)+δ02(i),foreachi∈S0,∑i∈Sk‍δkl(i)=∑i∈Sl‍δlk(i),k,l=0,1,2,k≠l,f(y^)=∑i∈S0‍δ0(i)+∑i∈S1‍δ12(i)=∑i∈S0‍δ01(i)+∑i∈S0‍δ02(i)+∑i∈S1‍δ12(i)=d01+d02+d12,
where d01=∑i∈S0‍δ01(i), d02=∑i∈S0‍δ02(i), d12=∑i∈S1‍δ12(i).
In what follows, we describe the size adjusting greedy algorithms (SAGAs) for Cases1 and 2, and denote the greedy algorithms for the two cases by SAGA1 and SAGA2, respectively.
ForSAGA1, one has the following.(1)
Calculate(4.5)m02=∑i∈S0‍δ02(i)|S0|,m12=∑i∈S1‍δ12(i)|S1|.(2)
Ifm02≥m12, let S1={j1,j2,…,j|S1|}, where δ12(jl)≥δ12(jl+1), l=1,2,…,|S1|. Set S~1={j1,j2,…,jn/3}, S~2=S2⋃‍(S1∖S~1) and renew to calculate
(4.6)δ02′(i)=∑j∈S^2‍wij,
for each i∈S0. Let S0={i1,i2,…,i|S0|}, where δ02′(ik)≥δ02′(ik+1). Set S~0={i1,i2,…,in/3} and S~2=S~2⋃‍(S0∖S~0).(3)
Ifm02<m12, let S0={i1,i2,…,i|S0|}, where δ02(ik)≥δ02(ik+1), k=1,2,…,|S0|, set S~0={i1,i2,…,in/3}, S^2=S2⋃‍(S0∖S~0), and then renew to calculate
(4.7)δ12′(i)=∑j∈S^2‍wij,
for each i∈S1. Set S~1={j1,j2,…,jn/3} and S~2=S^2⋃‍(S1∖S~1), where δ12′(jk)≥δ12′(jk+1) here.(4)
Return the current partitionS~={S~0,S~1,S~2}; stop.
ForSAGA2, one has the following.(1)
Calculated01=∑i∈S0‍δ01(i), d02=∑i∈S0‍δ02(i), and
(4.8)m01=d01|S0|,m02=d02|S0|.(2)
Ifm01≤m02, let
(4.9)S0={i1,i2,…,i|S0|},
where δ01(ik)≥δ01(ik+1), k=1,2,…,|S0|. Set
(4.10)S^0={i1,i2,…,i|S0|-q1},S~1=S1⋃‍(S0∖S^0),
where q1=(n/3)-|S1|. Renew to calculate
(4.11)δ02′(i)=∑j∈S2‍wij,i∈S^0.
and let
(4.12)S^0={i1′,i2′,…,i|S^0|′},
where δ02′(ik′)≥δ02′(ik+1′), k=1,2,…,|S^0|. Set
(4.13)S~0={i1′,i2′,…,in/3′},S~2=S2⋃‍(S^0∖S~0).(3)
Ifm01>m02, let
(4.14)S0={i1,i2,…,i|S0|},
where δ02(ik)≥δ02(ik+1), k=1,2,…,|S0|. Set
(4.15)S^0={i1,i2,…,i|S0|-q2},S~2=S2⋃‍(S0∖S^0),
where q2=(n/3)-|S2|. Renew to calculate
(4.16)δ01′(i)=∑j∈S1‍wij,i∈S^0.
and let
(4.17)S^0={i1′,i2′,…,i|S^0|′},
where δ01′(ik′)≥δ01′(ik+1′), k=1,2,…,|S^0|. Set
(4.18)S~0={i1′,i2′,…,in/3′},S~1=S1⋃‍(S^0∖S~0).(4)
Return the current partitionS~={S~0,S~1,S~2}; stop.


## 5. Numerical Results

This section describes the obtained experimental results for some instances of Max 3-cut and Max 3-Section problems using the proposed VNS metaheuristic. We also show a quantitative comparison with 0.836-approximate algorithm. The computational experiments are performed in an Intel Pentium 4 processor at 2.0 GHz, with 512 MB of RAM, and all algorithms are coded in Matlab. Because RSDP relaxation of M3C includes many slack variables, many constraints, and matrices variables without a block diagonal structures, in our numerical comparisons, we choose SDPT3-4.0 [9], one of the best and well-known solvers of semidefinite programming, to solve RSDP relaxation of M3C.All our test problems are generated randomly by the following way. Letp∈(0,1) be a constant and r∈(0,1) a random number. If r≤p, then there is an edge between nodes i and j with weight wij, that is, a random integer between 1 and 10. Otherwise, wij=0; that is, there is no edge between nodes i and j. Because of the limits of memory of SDPT3, when n>200, RSDP becomes a huge semidefinite programming problem with not less than 59700 slack variables and 99900 constraints and is out of memory of SDPT3. Hence, in the numerical experiments, we consider 30 instances with p=0.1,0.3,0.6, and n varying from 20 to 200.Firstly, we check the influence ofKmax on the quality of solution obtained by VNS-k. For a given graph, we take Kmax=3,5,10,15,30; Table 1 presents the results, where Wnp in the first column of this table and the following tables means that a graph is randomly generated with nodes n and density p; for instance, W30.6 presents a graph generated randomly with n=30 and p=0.6. We find from Table 1 that the influence of Kmax to objective value denoted by Obj in Table 1 is slight when Kmax>5, but the CPU time increases sharply as Kmax increases. This result is actually not surprising. Indeed, because I(K)>K, we choose randomly a point y in ∂NI(K)(y^), instead of ∂NK(y^). This avoids to choose too large Kmax which leads to more CPU-time cost. Hence, in sequel numerical comparisons, we fix Kmax=5 for all test problems.Table 1
The objective value obtained by VNS for M3C with differentKmax.
W
np
K
max
=
3
K
max
=
5
K
max
=
10
K
max
=
15
K
max
=
30
Obj
t
Obj
t
Obj
t
Obj
t
Obj
t
W60.1
960
1.38
965
2.14
967
4.63
967
6.29
969
12.50
W100.3
6001
7.55
6010
12.66
6013
23.37
6013
29.28
6015
69.52
W120.1
3323
13.76
3335
34.07
3337
38.78
3339
50.48
3343
101.85Secondly, we compare VNS (VNS-k, VNS-t) metaheuristic with 0.836-approximate algorithm for all test problems. To avoid the effect of initial points, for each test problem, after RSDP is solved, we run the round procedure of 0.836-approximate algorithm and VNS metaheuristic ten times, respectively.Table2 gives the result of numerical comparisons. In the numerical presentations of Table 2, Objrsdp is the optimal value of problem RSDP; that is, it is an upper bound of M3C. ObjGM is the largest value obtained by 0.836-approximate algorithm in the ten tests. Objvns stands for the largest value obtained by VNS for M3C in the ten tests, respectively. m and s.v. are the number of constraints and slack variables (s.v.), respectively. tGM and tvns-k are the average time (second) associated with the two algorithms in the ten tests. For the maximum CPU time of VNS-t, we take tmax=2tvns-k, but the real CPU time of VNS-t will be greater than tmax. Additionally, for measuring the performance of solutions, we take
(5.1)ρ=Objvns-ObjrsdpObjrsdp=ObjvnsObjrsdp-1
for M3C and
(5.2)ρ=Objvns+saga-ObjrsdpObjrsdp=Objvns+sagaObjrsdp-1
for M3S. Clearly, ρ can reflect how close to the solution obtained by VNS from the optimal solution of RSDP. One can see from Table 2 that (1) the VNS metaheuristic not only can obtain a better solution than 0.836-approximate algorithm for all test problems, but also that the elapsed CPU-time of VNS metaheuristic is much less than that of 0.836-approximate algorithm for all test problems, (2) the performance of solution can be improved by VNS-t for most of test problems when the termination criterion of VNS is based on the maximum CPU-time, but VNS-t spends more computational time than VNS-k. The improved performance can be reflected by ∇ρ=ρt-ρk in the final column of Table 2. Average speaking, VNS-t improves 0.91 percentage point.Table 2
The numerical comparisons of 0.836-approximate algorithm with VNS metaheuristic.
W
np
m
Obj
rsdp
0.836-algorithm
VNS
s.v.
Obj
GM
t
GM
Obj
vns-
k
t
vns-
k
ρ
k
%
Obj
vns-
t
ρ
t
%
∇
ρ
%
W20.1
990
121
117
22.93
119
0.28
−1.65
119
−1.65
0
W20.3
570
232
225
25.58
228
0.29
−1.72
228
−1.72
0
W20.6
492
464
14.27
479
0.40
−2.65
479
−2.24
0.41
W30.1
2235
147
139
161.56
144
0.81
−2.04
144
−2.04
0
W30.3
1305
566
521
140.12
550
0.97
−2.83
550
−2.30
0.53
W30.6
1181
1101
94.93
1151
0.92
−2.54
1151
−2.03
0.51
W45.1
5040
675
594
202.48
605
0.92
−10.38
612
−9.33
1.05
W45.3
2970
1300
1147
211.72
1192
1.02
−8.31
1300
−7.15
1.16
W45.6
2441
2272
217.57
2313
1.02
−5.25
2350
−3.73
1.52
W60.1
8970
1069
918
256.35
965
2.14
−9.73
981
−8.23
1.50
W60.3
5310
2494
2228
256.57
2301
3.13
−7.74
2332
−6.50
1.24
W60.6
4403
4054
266.68
4213
2.48
−4.32
4307
−2.18
2.14
W80.1
15960
1567
1357
537.58
1415
5.82
−9.71
1438
−8.23
1.48
W80.3
9480
4094
3666
546.23
3801
7.35
−7.16
3912
−4.45
2.71
W80.6
7746
7328
495.34
7423
6.31
−4.17
7481
−3.42
0.75
W100.1
24950
2526
2149
893.52
2262
12.73
−10.46
2302
−8.87
1.60
W100.3
14850
6418
5814
882.73
6010
12.66
−6.36
6113
−4.75
1.61
W100.6
11956
11212
865.28
11391
11.99
−4.73
11422
−4.47
0.26
W120.1
33990
3746
3222
1476.54
3335
34.07
−10.98
3392
−9.45
1.53
W120.3
21420
9173
8266
1498.18
8575
35.41
−6.52
8623
−6.00
0.52
W120.6
16748
15596
1567.43
16056
43.80
−4.14
16114
−3.79
0.35
W150.1
56175
5821
5020
2618.11
5208
69.20
−10.54
5257
−9.69
0.85
W150.3
33525
14432
13209
3021.87
13543
70.60
−6.15
13607
−5.72
0.43
W150.6
26310
25076
3172.22
25405
74.46
−3.44
25517
−3.01
0.43
W180.05
80910
4303
3578
9043.25
3726
133.10
−13.41
3812
−11.41
1.20
W180.1
48330
7236
6328
10225.54
6481
130.07
−10.44
6547
−9.52
0.92
W180.3
20147
18436
9887.36
19031
132.14
−5.54
19213
−4.64
0.90
W180.6
37292
35386
10004.11
35949
102.77
−3.61
36124
−3.13
0.48
W200.05
99900
5174
4306
25872.33
4484
71.90
−13.40
4509
−12.85
0.55
W200.1
59700
9271
8092
29003.28
8799
149.50
−5.10
8853
−4.51
0.59
W200.5
38831
36481
28774.17
37477
200.16
−3.49
37552
−3.29
0.20Finally, we consider the solution of M3S by combining VNS-k and greedy sizes-adjusted algorithm SAGA stated in Section4. Let y^ be an approximate solution of M3C obtained by VNS; we can obtain an approximate solution of M3S from SAGA. The numerical results are reported by Table 3 in which Objvns+saga stands for the largest value obtained by VNS-k plus SAGA for M3S. Although our sizes-adjusted algorithm may decrease the objective value obtained by VNS, the changes of objective values are very slight from Table 3. Particular, objective values of some problems do not decrease, instead increase, such as W150.3. We do not compare the obtained results with Andersson’s 2/3-approximate algorithm. Because we find that all approximate solutions of M3S obtained by VNS plus SAGA still are better than that of 0.836-approximate algorithm with the exception of only W30.1 and W30.3.Table 3
The numerical results of combining VNS-k metaheuristic with SAGA for M3S.
W
np
Obj
rsdp
Obj
GM
Obj
vns+saga
ρ
k (%)
W30.1
147
139
138
−6.12
W30.3
566
521
518
−8.49
W30.6
1181
1101
1151
−2.55
W45.1
675
594
605
−10.38
W45.3
1300
1147
1191
−8.39
W45.6
2441
2272
2313
−5.25
W60.1
1069
918
952
−10.95
W60.3
2494
2228
2301
−7.74
W60.6
4403
4054
4213
−4.32
W120.1
3746
3222
3290
−12.18
W120.3
9173
8266
8449
−7.90
W120.6
16748
15596
16056
−4.14
W150.1
5821
5020
5203
−10.62
W150.3
14432
13209
13551
−6.11
W150.6
26310
25076
25096
−4.62
W180.05
4303
3578
3726
−13.41
W180.1
7236
6328
6396
−11.61
W180.3
20147
18436
18823
−6.58
W180.6
37292
35386
35947
−3.61


## 6. Conclusions

A variable neighborhood stochastic metaheuristic was proposed to solve the Max 3-cut and Max 3-section problems in this paper. Our algorithms can solve Max 3-cut and Max 3-section problems with different sizes and densities. Although 0.836-approximate algorithm has the very good theoretic results, in numerical aspects, our comparisons indicate that the proposed VNS metaheuristic is superior to the well-known 0.836-approximate algorithm and can efficiently obtain very high-quality solutions of the Max 3-cut and Max 3-section problems.We mention that the proposed algorithm in fact can deal with higher dimensionalG-set graphs problems created by Pro. Rinaldi using a graph generator, rudy. But, we cannot give numerical comparisons with 0.836-approximate algorithm since RSDP relaxations of these problems are out of memory of the current all SDP software. In additionally, if we increase Kmax or tmax in numerical implementing, then the quality of solution of M3C will further be improved by VNS.



---

*Source: 475018-2012-08-23.xml*