Journal of Computational and Applied Mathematics 234 (2010) 240–252

Contents lists available at ScienceDirect

Journal of Computational and Applied
Mathematics
journal homepage: www.elsevier.com/locate/cam

Maximum cut in fuzzy nature: Models and algorithms
Rui-Sheng Wang a,b,∗ , Li-Min Wang caDepartment of Mathematics, Renmin University of China, Beijing 100872, Chinab

Department of Electronics, Information and Communication Engineering, Osaka Sangyo University, Osaka 574-8530, Japanc

China University of Mining and Technology, Beijing 100083, China

articleinfo

Article history:
Received 10 October 2007
Received in revised form 5 October 2009
Keywords:
Max-Cut
Fuzzy coefficients
Mathematical models
Fuzzy simulation
Genetic algorithm

abstract
The maximum cut (Max-Cut) problem has extensive applications in various real-world
fields, such as network design and statistical physics. In this paper, a more practical version,
the Max-Cut problem with fuzzy coefficients, is discussed. Specifically, based on credibility
theory, the Max-Cut problem with fuzzy coefficients is formulated as an expected value
model, a chance-constrained programming model and a dependent-chance programming
model respectively according to different decision criteria. When these fuzzy coefficientsare represented by special fuzzy variables like triangular fuzzy numbers and trapezoidal
fuzzy numbers, the crisp equivalents of the fuzzy Max-Cut problem can be obtained.
Finally, a genetic algorithm combined with fuzzy simulation techniques is designed for thegeneral fuzzy Max-Cut problem under these models and numerical experiment confirms
the effectiveness of the designed genetic algorithm.
© 2009 Elsevier B.V. All rights reserved.

1. Introduction
The Max-Cut problem is a well-known combinatorial optimization problem which aims to find a division of a vertex set
into two parts maximizing the sum of weights over all the edges across the two vertex subsets in a given edge-weighted
graph. For an unweighted graph, the weights over the edges are equal to 1. Such a division is called a maximum cut. The
worst-case complexity of the Max-Cut problem has been studied in a few papers, some of them dealing with weighted
graphs and some with unweighted graphs. Determining the maximum cut of a graph is an NP-hard problem, though it issolvable in polynomial time for some special classes of graphs [1]. Besides its theoretical importance, the Max-Cut problem
has many applications in various fields such as network design, statistical physics and VLSI design, circuit layout design [2],and data clustering [3]. For a comprehensive survey of the Max-Cut problem, the reader is referred to the paper of Poljak
and Tuza [4].
The Max-Cut problem is one of the first problems proved to be NP-hard, meaning that there are no strongly efficient exact
algorithms [5]. So many authors turn their attention to find approximate algorithms and heuristic algorithms. For example,
Delorme and Poljak [6] and Poljak and Rendl [7] designed eigenvalue relaxation algorithms for the problem. Goemans andWilliamson [8] developed a randomized algorithm based on semi-definite programming with the performance guaranteeof 0.878. In contrast to these approximate algorithms with performance guarantee, several efficient heuristic algorithms
have also been developed [9,10]. The striking characteristics of these heuristic algorithms are their efficiency in terms of
implementing time and possibility of finding global optimal solutions.
When applied in various real-world fields, the weight of the cut in the Max-Cut problem has real and concrete
implications. For example, for network design, the weight may represent the cost of some infrastructure. Owing to the effects∗ Corresponding author at: Department of Electronics, Information and Communication Engineering, Osaka Sangyo University, Osaka 574-8530, Japan.
Tel.: +81 072 875 3001; fax: +81 072 870 8189.
E-mail address: wrs@ruc.edu.cn (R.-S. Wang).
0377-0427/$ – see front matter © 2009 Elsevier B.V. All rights reserved.
doi:10.1016/j.cam.2009.12.022

R.-S. Wang, L.-M. Wang / Journal of Computational and Applied Mathematics 234 (2010) 240–252

241

of many factors in the real life, these parameters are not so deterministic. The imprecision may come from multiple sources
such as linguistic definition of importance, inexact values of measurements, integration of opinions of multiple experts, andpersonal bias in evaluating a quantity [11–13]. At this time, we need to deal with decision-making problems in uncertain
environments and design models suitable for a more practical situation. The concept of fuzzy set theory developed in [14,15]
and well studied by many other researchers is suited to formulate vague or subjective nature quantities. Based on this theory,
many optimization problems including various fuzzy programming models [16,17], fuzzy shortest path problems [18] andfuzzy max-flow problems [19] have been studied in imprecise environments. Recently, Liu [20,21] developed a credibility
theory where the expected value criterion, the optimistic value criterion and the credibility criterion are used as fuzzyranking methods. Based on this uncertain theory, several optimization models in stochastic and fuzzy environments havebeen studied [22–24].
In this paper, the Max-Cut problem is investigated in an uncertain environment based on Liu’s credibility theory.
Specifically, the Max-Cut problem with fuzzy coefficients is formulated as an expected value model, a chance-constrained
programming model and a dependent-chance programming model respectively according to different decision criteria. Then
their crisp equivalents are also discussed when the fuzzy costs are characterized by special fuzzy variables such as triangularfuzzy numbers and trapezoidal fuzzy numbers. Finally, since the Max-Cut problem is NP-hard even in a deterministic
environment, this paper will examine the design of efficient heuristic algorithms. A hybrid genetic algorithm combinedwith fuzzy simulation techniques is designed for the general fuzzy Max-Cut problem under these three models.
The paper is organized as follows: Some preliminaries on credibility theory are described in Section 2, then Section 3
introduces the Max-Cut problem with fuzzy coefficients. Three types of optimization models for the Max-Cut problem withfuzzy coefficients are developed in Section 4, where their crisp equivalents under special fuzzy variables are also discussed. In
Section 5, a genetic algorithm combined with fuzzy simulation techniques is designed for solving the general fuzzy Max-Cut
problem. Finally, numerical experiments are done to test the effectiveness of the designed algorithm in Section 6. Section 7
concludes the paper.
2. Preliminaries for credibility theory
Fuzzy set theory, developed in [14] and well studied by many other researchers, is well suited for formulating vague
or subjective quantities. Like the role of random variables in probability theory to describe many stochastic phenomena, afuzzy variable is a type of mathematical tools to describe fuzzy or vague uncertainty. Based on fuzzy set theory, possibility
theory was first developed in [15], and later extended by many researchers including Dubois and Prade [25].
Let X denote a nonempty set and P (X) denote the power set of X. Pos is a possibility measure on P (X). Then (X,P (X), Pos) represents a possibility space. Let ξ be a fuzzy variable with membership function µ : R → [0, 1], and let x, x0
be real numbers. According to possibility theory [25], the possibility of a fuzzy event ξ ≥ x0 is defined asPos{ξ ≥ x0 } = sup µ(x)x≥x0

and the necessity of this event is defined as
Nec{ξ ≥ x0 } = 1 − Pos{ξ < x0 } = 1 − sup µ(x).
x<x0

Liu and Liu [22] introduced a credibility measure which is an average of possibility measure and necessity measure:Cr{ξ ≥ x0 } =1
2(Pos{ξ ≥ x0 } + Nec{ξ ≥ x0 }).

Credibility measure Cr is a monotone regularized non-additive measure and vanishes at an empty set. For each fuzzy event
A its possibility to occur is Pos{A}, while its necessity to occur is defined by Nec{A} = 1 − Pos{Ac }. It is obvious that a fuzzy
event may fail even if its possibility is 1, and hold even if its necessity is 0. Credibility measure, as the mean of possibility
and necessity measures, can characterize fuzzy phenomena appropriately. Credibility theory was founded for studying the
behavior of fuzzy phenomena [26] and has been widely used to describe fuzzy phenomena in many real problems [20,21,
27,28].
Let ξ be a fuzzy variable defined on the credibility space (X, P (X), Cr). Then its membership function is derived fromthe credibility measure Cr byµ(x) = (2Cr{ξ = x}) ∧ 1,

x ∈ R.

It is clear that a fuzzy variable has a unique membership function [26]. The membership function represents the degree of
possibility that the fuzzy variable ξ takes some prescribed value. For example, the membership degree µ(x) = 0 if x is an
impossible point, and µ(x) = 1 if x is the most possible point that ξ takes. With the credibility measure, the expected valueof a fuzzy variable ξ is defined as follows:
Definition 2.1 (Liu and Liu [21]). Let ξ be a fuzzy variable defined on the credibility space (X, P (X), Cr). The expected valueof ξ is defined as

242

R.-S. Wang, L.-M. Wang / Journal of Computational and Applied Mathematics 234 (2010) 240–252

Z +∞

Z 0
Cr{ξ ≤ r }drCr{ξ ≥ r }dr −E [ξ ] =−∞0provided that at least one of the two integrals is finite.
As indicated by the following proposition, the expected value operator is linear.
Proposition 2.1 (Liu [20]). Let ξ and η be independent fuzzy variables defined on the credibility space (X, P (X), Cr). Then for
any real numbers a and b, the following equality
E [aξ + bη] = aE [ξ ] + bE [η]holds.
Definition 2.2 (Liu [20]). Let ξ be a fuzzy variable defined on the credibility space (X, P (X), Cr), and α ∈ (0, 1]. Thenξsup (α) = sup{r |Cr{ξ ≥ r } ≥ α}is called the α -optimistic value of ξ .
3. The Max-Cut problem with fuzzy coefficients
Let G = (V , E ) be an undirected edge-weighted graph with nonnegative weights ξ : E → R+ . A cut C of G is any nontrivial
subset of V and the weight of a cut is the sum of weights of edges crossing C and C̄ , where C̄ = V − C . A max-cut is thendefined as a cut of G with maximum weight. The goal of the Max-Cut problem is just to find such a cut. Assume that thevertices in V are labeled as {v1 , v2 , . . . , vn } and the edges in E are labeled as eij = (vi , vj ), where n = |V |, i, j = 1, 2, . . . , n.
ξij is the weight associated with the edge eij . We define a binary variable xi for each vertex vi to denote whether it is in a cut
C or not:


xi =

1

−1

if vi ∈ C
if vi ∈ V − C .

Then any cut of the graph G can be denoted by an n-dimensional binary vector (x1 , x2 , . . . , xn )T over {1, −1}. Similarly, any
n-dimensional binary vector (x1 , x2 , . . . , xn )T over {1, −1} corresponds to a cut of G. So the weight of a cut (x1 , x2 , . . . , xn )T
can be denoted asn

W (x, ξ ) =n

1 XX
2 i=1 j=1

ξij (1 − xi xj ).

Obviously, if and only if vi and vj respectively belong to two parts of the vertex set V (xi xj = −1), the weight of the edge (ifany) linking them is considered. Let C be the set of all cuts of G. Then a cut x∗ is called a maximum cut if and only if
W (x∗ , ξ ) ≥ W (x, ξ )for any x ∈ C . As mentioned in the Introduction, the Max-Cut problem has wide practical applications. When applied in thereal world, the weights of a graph have real and concrete implications. They are often not so deterministic since decision
makers are often faced with some uncertain situations due to the vagueness or subjective nature of these parameters.
In other words, usually precise weight parameters can be hardly obtained. For these cases, the weights on edges can beformulated as fuzzy variables which are more proper to describe the quantities in the real world. An important problem infuzzy set theory is how to rank two fuzzy variables. Many methods for ranking fuzzy numbers have been proposed [29,21].
Among them a credibility theory including the credibility criterion, the optimistic value criterion and the expected value
criterion has recently been developed as a fuzzy ranking method [21], which is also the basis of our fuzzy Max-Cut models.
For this paper, assume that ξij are all fuzzy variables. In real-world decision systems, different decision makers may havedifferent preferences. According to these ranking methods of fuzzy variables, we can have several more practical versionsof the Max-Cut problem. Some decision makers want to find a cut maximizing the expected value of the total weight, thenthe concept of expected maximum cuts can be adopted.
Definition 3.1. A cut x∗ is called an expected Max-Cut (EMC) if and only if
E [W (x∗ , ξij )] ≥ E [W (x, ξij )]for any x ∈ C . At this time, E [W (x∗ , ξij )] is called the expected weight of x∗ .
Some others may prefer to find a critical value of the maximum weight, leading to the following criterion:
Definition 3.2. A cut x∗ is called an α -optimistic Max-Cut (α -OMC) if and only ifsup{W̄ |Cr{W (x∗ , ξij ) ≥ W̄ } ≥ α} ≥ sup{W̄ |Cr{W (x, ξij ) ≥ W̄ } ≥ α}for any x ∈ C , where α is a predetermined confidence level. At this time, sup{W̄ |Cr{W (x∗ , ξij ) ≥ W̄ } ≥ α} is called theα -optimistic weight of x∗ .

R.-S. Wang, L.-M. Wang / Journal of Computational and Applied Mathematics 234 (2010) 240–252

243

There is also such a case, where decision makers prefer to provide a predetermined infimum W̄ and hope to find a cut
such that the credibility that its weight is not lower than W̄ will be as maximized as possible. For this case, the following
way can be adopted:
Definition 3.3. A cut x∗ is called a most Max-Cut (MMC) if and only if
Cr{W (x∗ , ξij ) ≥ W̄ } ≥ Cr{W (x, ξij ) ≥ W̄ }for any x ∈ C , where W̄ is a predetermined infimum. At this time, Cr{W (x∗ , ξij ) ≥ W̄ } is called the most credibility of x∗ at
W̄ .
These practical versions of the max-cut problem, on the one hand, incorporates crisp max-cut problems (with precise
weights) as a special case. On the other hand, it generalizes the max-cut problem and its applicability.
4. Models for Max-Cut in fuzzy nature
In this section, we will develop three models for the fuzzy Max-Cut problem according to the three decision criteria
introduced in Section 3. They are respectively the expected value model, the chance-constrained programming model andthe dependent-chance programming model.
Like the important role of the expected value model in stochastic programming, the expected valued model of fuzzy
programming, first developed in [20], is a straightforward and easily understandable method for modeling fuzzy/vague
phenomena in mathematical programming. Its goal is to optimize the expected objective subject to some constraints. Here,
if decision makers prefer finding a cut with the maximum expected weight, we can construct the following expected value
model for the fuzzy Max-Cut problem:

"

n

#

n

1 XX

ξij (1 − xi xj )

max

E

s.t .

x2i = 1,xi ∈ Z ,i = 1, 2, . . . , n2 i=1 j=1

(1)where the constraint x2i = 1, xi ∈ Z implies xi ∈ {−1, 1}, meaning x ∈ C . This model indicates that among all the possible
cuts of G, the one with the maximum expected weight is preferred. We call this model as the Expected Max-Cut (EMC)
problem.
In contrast to the expected value model, chance-constrained programming developed by in [30] has been a powerfulstrategy for modeling stochastic phenomena in decision systems. Liu and Iwamura [23] presented chance-constrained
programming to model the fuzzy case in an uncertain environment. The main idea underlying it is to optimize the criticalvalue of the fuzzy objective with certain confidence level subject to some constraints, which is well suited for finding an
α -optimistic Max-Cut mentioned in Section 3:
max
s.t .

W̄ (
Cr

n

)

n

1 XX
2 i=1 j=1

ξij (1 − xi xj ) ≥ W̄≥α(2)x2i = 1,xi ∈ Z ,i = 1, 2, . . . , n

where α is a confidence level provided by decision makers. This model is referred as the α -Optimistic Max-Cut (α -OMC)
problem.
As mentioned in Section 3, some decision makers prefer providing a predetermined infimum and hope to maximize thecredibility that the weight of the cut wanted is not lower than this infimum. For this case, we can use dependent-chance
programming developed in [24] for the third criteria in decision-making. The main idea underlying it is to select a solutionthat can meet a fuzzy event with maximum credibility. Therefore, to find a most Max-Cut of G, we can construct the following
dependent-chance programming model for the fuzzy Max-Cut problem:

(

n

)

n

1 XX

ξij (1 − xi xj ) ≥ W̄

max

Cr

s.t .

x2i = 1,xi ∈ Z ,i = 1, 2, . . . , n2 i=1 j=1

(3)

244

R.-S. Wang, L.-M. Wang / Journal of Computational and Applied Mathematics 234 (2010) 240–252

where W̄ is a predetermined infimum provided by decision makers. This model is referred as the Most Max-Cut (MMC)
problem.
With the three models discussed above, the next important thing we should do is to find the best solutions for them. Since
there are no simple analytic expressions for the objective functions or constraints in these models, we need to estimate theexpected value, the critical value or the credibility measure in them, which is not a straightforward and easy work. From
the following part of this section, we can see that there are actually several simple cases when the fuzzy variables in thesemodels are special.
Firstly, from the linearity of the expected value of a fuzzy variable, we can directly have the following theorem:
Theorem 4.1. Let ξij , i, j = 1, 2, . . . , n be independent fuzzy variables defined on the possibility space (X, P (X), Pos). Then the
EMC model (1) is equivalent to the following crisp optimization model:
n

max
s.t .

n

1 XX
2 i=1 j=1

E [ξij ](1 − xi xj )(4)x2i = 1,xi ∈ Z ,i = 1, 2, . . . , n.

Although the credibility of a fuzzy variable is not linear and thus the left two models do not have the corresponding crisp
equivalents, they indeed have crisp equivalents when the fuzzy variables are special fuzzy numbers such as triangular fuzzy
numbers and trapezoidal fuzzy numbers which are widely used in modeling fuzziness. A trapezoidal fuzzy variable is often
denoted by r̃ = (r1 , r2 , r3 , r4 ) whose membership function has the following expression: x − r1

 r2 − r11µr̃ (x) = x − r4
 r3 − r40

if r1 ≤ x ≤ r2 ,if r2 ≤ x ≤ r3 ,(5)

if r3 ≤ x ≤ r4 ,otherwise.

From its membership function expression, we can see that a trapezoidal fuzzy variable is fully determined by the quadruple(r1 , r2 , r3 , r4 ). When r2 = r3 , the trapezoidal fuzzy variable becomes a triangular fuzzy number. From Zadeh’s extension
principle, it is easy to check that a nonnegative linear combination of two trapezoidal fuzzy variables is still a trapezoidal
fuzzy number. In addition, from the special membership function and the definition of the credibility Cr, it is easy to computethe credibility of the fuzzy event {r̃ ≥ x0 } based on a trapezoidal fuzzy number r̃ = (r1 , r2 , r3 , r4 ) as follows:Cr(r̃ ≥ x0 ) =


1



2r1 − r2 − x0





 2(r2 − r1 )
1


2


r 3 − x0





2
(
 r4 − r3 )0

if x0 ≤ r1 ,if r1 ≤ x0 ≤ r2 ,if r2 ≤ x0 ≤ r3 ,(6)

if r3 ≤ x0 ≤ r4 ,if x0 ≥ r4 .

Lemma 4.1. Let ξ = (r1 , r2 , r3 , r4 ) be a trapezoidal fuzzy variable defined on the credibility space (X, P (X), Cr), and let α bea given confidence level. Then (a) when α ≤ 1/2, Cr{ξ ≥ W̄ } ≥ α if and only if (1 − 2α)r1 + 2α r2 ≥ W̄ ; (b) when α > 1/2,
Cr{ξ ≥ W̄ } ≥ α if and only if (2 − 2α)r3 + (2α − 1)r4 ≥ W̄ .
Theorem 4.2. Let ξij = (ξij1 , ξij2 , ξij3 , ξij4 ) be independent trapezoidal fuzzy numbers defined on the credibility space(X, P (X), Cr). Then the crisp equivalent of the α -OMC model (2) is given by
max
s.t .

f ( x)
x2i = 1,xi ∈ Z ,i = 1, 2, . . . , n(7)where f (x) is such a real function



X
n X
n 
1

1
2

−
α
ξ
+
αξ

ij
ij (1 − xi xj )2
i=1 j=1
 
f (x) = X
n X
n 

1
3


(
1
−
α)ξ
+
α
−
ξij4 (1 − xi xj )ij
i=1 j=12

if α ≤
if α >

1
2
1
2

(8)

.

R.-S. Wang, L.-M. Wang / Journal of Computational and Applied Mathematics 234 (2010) 240–252

245

Proof. On the one hand, 1 − xi xj ≥ 0 and ξij are independent, so according to the properties of trapezoidal fuzzy variables,
Pn Pn
1
i=1
j=1 ξij (1 − xi xj ) is also a trapezoidal fuzzy number and can be denoted by a quadruple2

Tξ (1 − xi xj )
 2 i =1 j =1



n X
n


X

T  12
r1 (x)
ξij (1 − xi xj )

 2 i =1 j =1
r2 (x)
 .
=r (x)
n X
n


X
3
3
1
ξij (1 − xi xj )

r4 (x)
 2 i =1 j =1

 n n

1 X X 4ξij (1 − xi xj )
n X
n
1 X

1
ij

(9)

2 i =1 j =1

On the other hand, from Lemma 4.1, the constraint in α -OMC model (2)

(
Cr

n

)

n

1 XX
2 i=1 j=1

ξij (1 − xi xj ) ≥ W̄≥αis equivalent to (1 − 2α)r1 (x) + 2α r2 (x) ≥ W̄ when α ≤12and (2 − 2α)r3 (x) + (2α − 1)r4 (x) ≥ W̄ when α >1.
2

In other words, this constraint is equivalent to f (x) ≥ W̄ , where f (x) is defined by (8). Since maximizing W̄ is actuallymaximizing f (x), the α -OMC model (2) can be transformed into a crisp equivalent (7) when ξij are independent trapezoidal
fuzzy variables. űNote that at this time, the α -OMC model becomes a general nonlinear optimization model without fuzzy variables.
Theorem 4.3. Let ξij = (ξij1 , ξij2 , ξij3 , ξij4 ) be independent trapezoidal fuzzy numbers defined on the credibility space (X, P (X),
Cr). Then the crisp equivalent of the MMC model (3) is given byf (x)x2i = 1,xi ∈ Z ,i = 1, 2, . . . , n

max
s.t .

(10)

where f (x) is such a real functionf ( x) =1 2r1 (x) − r2 (x) − W̄
 2(r2 (x) − r1 (x))


1


2



r3 (x) − W̄





2
(
r
 4 (x) − r3 (x))
0

if W̄ ≤ r1 (x),if r1 (x) ≤ W̄ ≤ r2 (x),if r2 (x) ≤ W̄ ≤ r3 (x),(11)

if r3 (x) ≤ W̄ ≤ r4 (x),if W̄ ≥ r4 (x).

Proof. Since 1 − xi xj ≥ 0 and ξij are independent, according to the properties of trapezoidal fuzzy variables, 21
i =1Pn
j=1 ξij (1 − xi xj ) is also a trapezoidal fuzzy number and can be denoted by the quadruple (r1 (x), r2 (x), r3 (x), r4 (x)) definedby (9). From formula (6), the objective function in the MMC model (3)

Pn

(
Cr

n

)

n

1 XX
2 i=1 j=1

ξij (1 − xi xj ) ≥ W̄is equivalent to the real function f (x) defined by (11). Therefore, the MMC model can be transformed into a crisp equivalent(10). űAgain this is also a crisp nonlinear optimization model.
5. A hybrid genetic algorithm
As mentioned in the Introduction, since the crisp Max-Cut problem is NP-hard, there are no efficient exact algorithms
for solving its large-scale instances. The fuzzy Max-Cut problem will be more difficult to solve since it is an extension to246

R.-S. Wang, L.-M. Wang / Journal of Computational and Applied Mathematics 234 (2010) 240–252

the Max-Cut problem. So we do not try to design exact algorithms such as branch-and-bound algorithms and semi-definite
programming algorithms. We examine the design of heuristic algorithms for efficiently solving the models EMC, α -OMC,
MMC. Genetic algorithm (GA) is a widely used global optimization method with a random search mechanism [31] and has
been successfully used in various fields. Another reason for using GA is that the coding of GA for the fuzzy Max-Cut problem
is simple and can be achieved by binary vectors. Binary vectors form a moderate search space and thus make GA able to findglobal optimal solutions.
5.1. Construction of the solution space
We use a binary vector to express an individual code which represents a cut of the graph G (a feasible solution to EMC,

α -OMC and MMC). The length of individuals (feasible solutions) in the solution space is the size of the vertex set in G. Afterlabeling the vertices by v1 , v2 , . . . , vn , the value −1 or 1 on the ith position of an individual characterizes the membershipof the ith vertex. Thus, all binary vectors over {−1, 1} with length of n constitute the whole solution space:
S = {(x1 , x2 , . . . , xn )T |xi ∈ {−1, 1}, i = 1, 2, . . . , n}.
5.2. Designation of the fitness function
For each individual (chromosome) in a population of GA, we need to assign a fitness value. According to the optimization
models EMC, α -OMC and MMC, the fitness of an individual is dependent on the objective values of these models with thisindividual as a feasible solution. Hence, the following fitness functions are designed respectively for EMC, α -OMC and MMC:"
U1 (x) = En2 i =1 j =1((U2 (x) = sup W̄ |Cr(U3 (x) = Cr

#

n

1 XX

n

ξij (1 − xi xj ) ,
n

)

n

1 XX
2 i=1 j=1

ξij (1 − xi xj ) ≥ W̄

2 i=1 j=1

)
≥α ,

(13)

)

n

1 XX

(12)

ξij (1 − xi xj ) ≥ W̄ .

(14)

Obviously, the fitness of an individual is positively proportional to the objective value of the corresponding model. The goalof GA is to find an individual with highest fitness.
Note that the expected value E and the credibility measure Cr have no simple analytic expressions for general fuzzy
variables. So we have to resort to other means in order to compute the fitness of an individual. Fuzzy simulation techniquefor computing E and Cr presented in [20] is an approximate way and has been widely used to compute the objective
values of expected value models, chance-constraint programming models and dependent-chance programming models.
The motivation for these fuzzy simulation techniques is that, according to the definition of the credibility, for any numberr ≥ 0, Cr{f (x, ξ ) ≥ r } can be approximated by
Lmax (x, r ) =

1



2

max {vk |f (x, uk ) ≥ r } + min {1 − vk |f (x, uk ) < r }

1≤k≤N



1≤k≤N

(15)

and for any number r < 0, Cr{f (x, ξ ) ≤ r } can be approximated by
Lmin (x, r ) =

1
2





max {vk |f (x, uk ) ≤ r } + min {1 − vk |f (x, uk ) > r } ,

1≤k≤N

1≤k≤N

(16)

where N is a very large positive number, vk = µξ (uk ) ∧ 1, and uk , k = 1, 2, . . . , N are randomly generated from the levelset of ξ . Here we definenf (x, ξ ) =n

1 XX
2 i =1 j =1

ξij (1 − xi xj ).

Fuzzy simulation for expected value
The following algorithm is for computing U1 (x) by fuzzy simulation:
Step 1. Set E = 0;
Step 2. Randomly generate vector uk from the ε -level sets of fuzzy vectors ξ , k = 1, 2, . . . , N, where ε is a sufficiently small
number;
Step 3. Let a = min1≤k≤N f (x, uk ) and b = max1≤k≤N f (x, uk );Step 4. Randomly generate a random number r from [a, b];

R.-S. Wang, L.-M. Wang / Journal of Computational and Applied Mathematics 234 (2010) 240–252

247

Step 5. If r ≥ 0, then E ← E + Cr{f (x, ξ ) ≥ r }; If r < 0, then E ← E − Cr{f (x, ξ ) ≤ r };Step 6. Repeat the fourth to fifth steps for N times.
Step 7. U1 (x) = a ∨ 0 + b ∧ 0 + E (b − a)/N.
In this algorithm, N is a large positive integer; Generally, a larger N corresponds to a better approximation to expectedvalues. The principle in this algorithm is based on the expected value definition of fuzzy variables. Note that computing Cr
in this algorithm also needs the fuzzy simulation for credibility (in the following).
Fuzzy simulation for α -optimistic value
The following algorithm is for computing U2 (x) by fuzzy simulation:
Step 1. Randomly generate uij,k from the ε -level set of ξij , and, where k = 1, 2, . . . , N and ε is a sufficiently small positive
number.
Step 2. Set vk = minij µξij (uij,k ) for k = 1, 2, . . . , N .
Step 3. Compute Lmax (x, W ) by using vk , uij,k according to the definition (15);
Step 4. Find a maximum value W̄ such that L(x, W̄ ) ≥ α holds.
Step 5. U2 (x) = W̄ .
Fuzzy simulation for credibility
The following algorithm is for computing U3 (x) by fuzzy simulation:
Step 1. Randomly generate uij,k from the ε -level set of ξij , and, where k = 1, 2, . . . , N and ε is a sufficiently small positive
number;
Step 2. Set vk = minij µξij (uij,k ) for k = 1, 2, . . . , N;
Step 3. Compute Lmax (x, W̄ ) by using vk , uij,k according to the definition (15);
Step 4. U3 (x) = Lmax (x, W̄ ).
5.3. Genetic operators
There are several kinds of selection operators for GA, such as tournament selection, rank selection and roulette wheel
selection. Among them roulette wheel selection is very popular in GA algorithm. However, in order to avoid the crowding
phenomenon and to yield a more diverse population, we adopt both tournament selection and roulette wheel selection
in different parts of our algorithm. A combination of single-point crossover and uniform crossover is adopted. In addition,according to the principle that the fittest survives, we use roulette wheel selection operator to select individuals to crossoverand generate offspring. Similarly, we adopt the combination of single-point mutation and swap mutation.
5.4. Flow steps of hybrid genetic algorithm
The details of our implementation of GA for the fuzzy Max-Cut problem are described as follows:
Step 0. Give proper parameter settings, e.g. population size popsize, crossover rate pc , mutation rate pm and the maximum
number of population generation GN.
Step 1. Randomly generate popsize individuals as an initial population P0 , k = 0.
Step 2. Evaluate Pk , i.e. compute the fitness of every individual in Pk using the functions (12), (13) or (14) and retain theindividual with the highest fitness.
Step 3. If k < GN, stop, return the individual with the highest fitness in the history, otherwise create a new generation Pk+1
using the following method:(1) Select (1 − pc )popsize members of Pk and add them to Pk+1 using tournament selection operator.
(2) Probabilistically select Pc · popsize/2 pairs of individuals from Pk using roulette wheel selection operator. For each pair
(x1 , x2 ), produce two offspring by randomly applying single-point crossover operator and uniform crossover operator. Add
all offspring to Pk+1 .
(3) Select pm percentage of the individuals in Pk+1 with uniform probability. For each, invert the value at a randomly
selected position, or swap the values at two randomly selected positions.
Step 4. k = k + 1, go to Step 2.
6. Numerical experiments
In this section, we consider several numerical examples to illustrate the proposed fuzzy Max-Cut models and verify theeffectiveness of the designed hybrid genetic algorithm. The algorithm is coded in Microsoft Visual C++ 6.0 and implemented
on PC.
6.1. A simulated example
In the example shown in Fig. 1, there are totally 8 vertices and 13 edges. The weight on each edge is given in Table 1.
Some of these weights are trapezoidal fuzzy variables with the membership function (5) and denoted by the quadruple

248

R.-S. Wang, L.-M. Wang / Journal of Computational and Applied Mathematics 234 (2010) 240–252

Table 1
The weights on the edges of the graph, where Tri. denotes triangular fuzzy variables, Trp. denotes trapezoidal fuzzy variables and Nor. denotes normal
fuzzy variables.
No.

Edges (i, j)

TypeWeights ξij

1
2
3
4
5
6
7
8
9
10
11
12
13

(1, 2)(1, 3)(1, 4)(2, 3)(2, 5)(3, 6)(3, 7)(4, 6)(4, 7)(5, 6)(5, 8)(6, 8)(7, 8)

Tri.
Tri.
Nor.
Trp
Nor.
Tri.
Trp.
Nor.
Trp.
Nor.
Nor.
Trp.
Tri.

(1, 2, 3)(0.5, 1, 1.8)
(5, 1)(0.2, 0.8, 1.2, 2)(4, 1)(6, 7, 8)(9, 10, 11, 12)(12, 1)(12, 13, 14, 15)(16, 1)(3, 1)(2, 3, 4, 5)(7, 8, 9.5)

1

2

5

3

6

4

7

8

Fig. 1. A graph with 8 vertices and 13 edges.

(r1 , r2 , r3 , r4 ) of crisp numbers with r1 < r2 < r3 < r4 . Some of them are triangular fuzzy variables which are special
trapezoidal fuzzy variables with r2 = r3 and thus denoted by a triplet (r1 , r2 , r3 ) of crisp numbers with r1 < r2 < r3 . Whileother weights are normal fuzzy variables with the following membership functionµ(x) = exp(−(x − r̄ )2 /σ )and denoted by (r̄ , σ ).
In the GA implementation for solving the EMC, α -OMC and MMC models on this example, popsize is set as 30 and GN is
set as 50. In addition, crossover rate pc = 0.5 and mutation rate pm = 0.2. In fact, GA is very robust with respect to theseparameters. To solve the expected model of the fuzzy Max-Cut problem EMC, we use GA algorithm with the fitness function(12). The iteration process of GA on EMC is illustrated in Fig. 2(a). We obtain an expected Max-Cut C = {v3 , v4 , v5 , v8 } withexpected weight 82.35. Assume that the predetermined credibility level α given by decision makers is 0.8. The iteration
process of GA on the chance-constraint programming model (α -OMC) is shown in Fig. 2(b). At this time, the fitness function(13) is used. We obtain an α -optimistic Max-Cut C = {v3 , v4 , v5 , v8 } with an α -optimistic weight 78.78. Fig. 3(a) illustrates
the effect of the predetermined credibility level α on α -optimistic Max-Cut weights. As expected, with the increase of α ,the constraint of α -OMC becomes stronger and the weight W satisfying the constraint decreases. Finally, if a predetermined
infimum W̄ given by decision makers is 80, we use GA with the fitness function (14) to solve the corresponding dependentchance programming model (MMC, See Fig. 2(c)) and obtain a most Max-Cut C = {v3 , v4 , v5 , v8 } with a most credibility
0.755. Fig. 3(b) shows the effect of the predetermined infimum W̄ on the most credibility. Again, as expected, with theincrease of W̄ , the requirement of decision makers becomes stricter, so the credibility that the best solution can satisfy therequirement decreases. From Fig. 2 we can see that the designed hybrid genetic algorithm is able to converge to a goodsolution with high fitness (a solution with optimal or near optimal objective value) in only a few iterations, demonstrating
its effectiveness.
6.2. A practical example
Cluster analysis aims to partition a set of data points into groups of closely related observations. The points in a particulargroup or cluster should be more similar to each other than to points in other clusters. Graph cut-based clustering methods
have been widely used, including Max-Cut, Min-Cut, Min-Max-Cut and normalized cut [32,3,33]. When the objectivefunction of clustering is to minimize the within-cluster sums of dissimilarities or distances [34], the clustering problem
can be formulated as a Max-Cut problem by creating a graph with vertices representing data points, edges with weights
denoting the dissimilarity or distance between a pair of data points. An online software for max-cut clustering can be foundat http://riot.ieor.berkeley.edu/riot/Applications/Clustering/.

R.-S. Wang, L.-M. Wang / Journal of Computational and Applied Mathematics 234 (2010) 240–252

a

b

0.8

75
70
65

0

10

20
30
Iteration step

40

75

70

65

50

0.7

Best most credibility

80

60

c
80

Best α – optimistic weight

Best expected weight

85

249

0

10

20
30
Iteration step

40

0.6
0.5
0.4
0.3
0.2

50

0

10

20

30

40

50

Iteration step

Fig. 2. (a) The iteration process of GA on the expected value model (EMC). (b)The iteration process of GA on the chance-constraint programming model(α -OMC). (c) The iteration process of GA on the dependent-chance programming model (MMC).

b

95

1
0.9

90
The most credibility

The weight of α – optimistic Max–Cut

a

85
80
75

0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1

70

0.2

0

0.4

0.6

0.8

0
76

1

78

80

82

α

84

86

88

90

W

Fig. 3. (a) The plot of the weight of the α -optimistic Max-Cut with respect to α . (b) The plot of the most credibility with respect to the predetermined
infimum W .

Memebship degree

Extremely
similarSharing somesimilarity but with
dissimilarity

Similar

Extremely
dissimilar

Dissimilar

1

0.5

0

1

1.5

2

2.5

3

3.5

4

4.5

5

Dissimilarity score
Fig. 4. Membership functions of linguistic distance measures.

We give an example where max-cut-based clustering needs to handle imprecise weights (dissimilarities) between data
points. With the rapid progress in the internet technology, online marketing is becoming a promising way for selling diverse
kinds of commodities. In order to make marketing more effective such as advertising and promotion, it is often demanded
to collect the characteristics of consumers and classify them into different types according to their consumption records.
Assume there is a consumer population who visit an online market often and the marketing manager wants to cluster the
consumers into two groups. The similarity between consumers, which is critical for the classification, needs to be determinedaccording to multiple factors such as age, fashion preference, and past shopping records. A simple real number is hardto describe the similarity between consumers comprehensively. The expert scoring method is usually used [13], which
integrates the scores or suggestions (sometime, they are linguistic such as ‘very similar’, ‘similar’, and ‘not similar at all’) ofindividual experts into a fuzzy number represented by a membership function. Here five linguistic similarity (dissimilarity)degrees are used, with their membership functions shown in Fig. 4.

250

R.-S. Wang, L.-M. Wang / Journal of Computational and Applied Mathematics 234 (2010) 240–252

Fig. 5. The clustering result by solving the expected Max-Cut problem.

A graph with 40 consumers as vertices is generated. To test if the fuzzy max-cut-based clustering is able to classify
the consumers correctly, we design the graph in such way: the relationships within the first 20 consumers and the last
20 consumers are randomly set as ‘extremely similar’ or ’similar’ with 80 edges preserved, and the relationships between
these two groups are randomly set as ’extremely dissimilar’ or ’dissimilar’ with 80 edges preserved. The goal is to test if the
fuzzy max-cut-based clustering can cluster these consumers into two groups correctly. We applied our GA algorithm (withpopsize = 150 and GN = 500) to solve the expected max-cut model (EMC) and cluster these consumers into two groups.
The result is illustrated in Fig. 5, where the cut is denoted by different vertex shapes. We can see that most of consumers
with high dissimilarities are clustered into different groups. Only three vertices are misclassified: vertex 1, vertex 31 andvertex 36. The misclassification of vertex 36 is because vertex 36 is a leaf node and has only a single connection. Thus putting
it into the other group will increase the weight of maximum cut. The results given by the α -OMC and MMC models dependon the preferences of decision makers such as predetermined confidence level α and predetermined infimum W̄ , which are
not shown here.
6.3. Benchmark examples
In order to further examine the effectiveness of GA algorithm and test our models on larger instances, we adapt somebenchmark examples for the classical Max-Cut problem for our use [35]. Specifically, topology structure in this graph ispreserved, and each edge is assigned with a normal fuzzy weight with r = 1 and σ being a random number in [0, 0.5].
If ignoring σ , GA is actually solving the classical Max-Cut problem. When considering fuzzy weights, GA is used to solve
the fuzzy Max-Cut problem through the EMC, α -OMC and MMC models. For these larger instances, the parameters in GA
algorithm are set as those in the last subsection. The results are listed in Tables 2 and 3. Since GA may return differential
solutions upon different initial settings, the results shown here are the averaged solutions over ten execution times. As weknow, the Max-Cut problem is NP-hard. Exact algorithms for even such instances of medium size take unacceptable time.
From Tables 2 and 3, we can see when GA is used to solve the classical Max-Cut problem, it can obtain solutions quite nearto the optima. The average running time for each instance is about 30 seconds. When solving the EMC, α -OMC and MMC
models, the main part of running time is spent on fuzzy simulation for calculating expected values, α -optimistic values andcredibilities, so GA takes more than one hour for each instance. With the optimal solutions as reference, we can see that theobtained solutions for EMC are also nearly optimal. The solutions of α -OMC indicate that when optimal solutions are hard to
obtain, the solutions with α confidence level to optima, which are obviously smaller than optimal solutions, are preferred.
The solutions of MMC indicate that for a preferred maximum cut infimum, what their confidence levels are in comparison
with optima.
7. Conclusion and discussion
In this paper, we investigate the Max-Cut problem with fuzzy weights. The fuzzy Max-Cut problem was formulated
into an expected valued model, a chance-constraint programming model and a dependent-chance programming modelaccording to different decision criteria/fuzzy ranking methods. Their crisp equivalents under some special conditions are also
discussed based on credibility theory. In addition, a genetic algorithm combined fuzzy simulation techniques is designed
for solving the fuzzy Max-Cut problem under the presented models. Numerical experiments illustrate the algorithm andconfirm its effectiveness. As we know, fuzziness is not the only kind of uncertain phenomena in the real world. Randomness

R.-S. Wang, L.-M. Wang / Journal of Computational and Applied Mathematics 234 (2010) 240–252

251

Table 2
The results of GA for the classical max-cut problem and the fuzzy max-cut problem on 60-node instances, where α = 0.85 for α -OMC and W̄ = 515 for
MMC.
Example name

Optimum

GA solution

EMC

α -OMCMMC

G05_60.0
G05_60.1
G05_60.2
G05_60.3
G05_60.4
G05_60.5
G05_60.6
G05_60.7
G05_60.8
G05_60.9

536
532
529
538
527
533
531
535
530
533

534.8
529.5
526.3
535.0
525.5
529.6
528.3
532.5
526.3
531.6

533.6
532.1
528.2
535.5
526.2
528.9
530.3
533.3
527.8
531.3

519.6
517.9
514.4
520.1
513.3
517.7
516.0
520.1
516.2
517.8

1.000
0.801
0.802
1.000
0.600
0.899
0.901
1.000
0.898
0.921

Table 3
The results of GA for the classical max-cut problem and the fuzzy max-cut problem on 100-node instances, where α = 0.85 for α -OMC and W̄ = 1410 for
MMC.
Example name

Optimum

GA solution

EMC

α -OMC

MMC

G05_100.0
G05_100.1
G05_100.2
G05_100.3
G05_100.4
G05_100.5
G05_100.6
G05_100.7
G05_100.8
G05_100.9

1430
1425
1432
1424
1440
1436
1434
1431
1432
1430

1423.21420.21422.71416.01427.21424.61426.21422.01420.61417.81421.21421.51424.91412.81432.31433.01430.91425.21417.41420.51396.01397.51398.31389.81408.51412.81408.41402.01398.11396.2

0.811
0.804
0.863
0.600
1.000
0.987
0.870
0.801
0.802
0.737

and mixed uncertainness of randomness and fuzziness are also common in real decision systems. We may investigate the
Max-Cut problem under these kinds of uncertain environments in the future research work. In addition, although we adopt
the credibility measure to characterize fuzzy phenomena, the framework and algorithm provided in this paper also suit wellfor the models using possibility or necessity measures.
There are some limitations in the current study. Although the algorithm discussed in this work is efficient for instance ofsmall and medium size, its running time will become very intense for very large-scale problems due to the fuzzy simulation
part for evaluating objective functions. This is the price for the ability of the algorithms and models to handle any type offuzzy variables. Other ranking methods of fuzzy variables may be explored in the future research [11]. In addition, somelocal search techniques can be incorporated into GA to further improve its efficiency. Finally, in this study, we only consider
fuzzy Max-Cut problems in a moderate dimension. To handle the large-scale instances of Max-Cut problems in fuzzy nature,
it will be better to build on the new progresses on heuristic algorithms for the Max-Cut problem such as the discrete filled
function algorithm in [36].
Acknowledgements
The author is grateful to the anonymous reviewers for their valuable comments and suggestions. This work is supportedby the National Natural Science Foundation of China (NSFC) under Grant No.10701080.
References[1] F. Hadlock, Finding a maximum cut of a planar graph in polynomial time, SIAM J. Comput. 4 (1975) 221–225.
[2] F. Barahona, M. Grotschel, M. Junger, G. Reinelt, An application of combinatorial optimization to statistical physics and circuit layout design, Oper.
Res. 36 (1988) 493–513.
[3] J. Poland, T. Zeugmann, Clustering pairwise distances with missing data: Maximum cuts versus normalized cuts, Lecture Notes in Comput. Sci. 4265
(2006) 197–208.
[4] S. Poljak, Zs. Tuza, Maximum cuts and largest bipartite subgraphs, in: W. Cook, L. Lováz, P. Seymour (Eds.), Combinatorial Optimization, American
Mathematical Society, Providence, 1995, 20, R, l.
[5] R.M. Karp, Reducibility among combinatorial problems, in: R. Miller, J. Thatcher (Eds.), Complexity of Computer Computations, Plenum Press, New
York, 1972, pp. 85–103.
[6] C. Delorme, S. Poljak, Laplacian eigenvalues and the maximum cut problem, Math. Program. 62 (1993) 557–574.
[7] S. Poljak, F. Rendl, Solving the Max-cut problem using eigenvalue, Discrete Appl. Math. 62 (1995) 249–278.
[8] M.X. Goemans, D.P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,
J. ACM 42 (1995) 1115–1145.
[9] A. Duarte, F. Fernández, A. Sánchez, A. Sanz, A hierarchical social metaheuristic for the max-cut problem, Lecture Notes in Comput. Sci. 3004 (2004)
84–94.
[10] G. Xia, Z. Tang, Y. Li, R. Wang, Hopfield neural network with hysteresis for maximum cut problem, Neural Inf. Process. Lett. Rev. 4 (2) (2004) 19–26.
[11] S.T. Liu, C. Kao, Network flow problems with fuzzy arc lengths, IEEE Trans. Syst. Man Cybernet. — Part B: Cybernetics 34 (1) (2004) 765–769.

252

R.-S. Wang, L.-M. Wang / Journal of Computational and Applied Mathematics 234 (2010) 240–252[12] M. Ghateea, S.M. Hashemia, B. Hashemib, M. Dehghanb, The solution and duality of imprecise network problems, Comput. Math. Appl. 55 (2008)
2767–2790.
[13] J. Zeng, M. An, N.J. Smith, Application of a fuzzy based decision making methodology to construction project risk assessment, Int. J. Proj. Manag. 25(6) (2007) 589–600.
[14] L.A. Zadeh, Fuzzy sets. Inform. Control 8 (1965) 338–353.
[15] L.A. Zadeh, Fuzzy sets as a basis for a theory of possibility, Fuzzy Sets and Systems 1 (1) (1978) 3–28.
[16] J.J. Buckley, Solving possibilistic linear programming problems, Fuzzy Sets and Systems 31 (1989) 329–341.
[17] H.F. Wang, M.L. Wang, A fuzzy multi-objective linear programming, Fuzzy Sets and Systems 86 (1997) 61–72.
[18] S. Okada, Fuzzy shortest path problems incorporating interactivity among paths, Fuzzy Sets and Systems 142 (2004) 335–357.
[19] P. Diamond, A fuzzy max-flow min-cut theorem, Fuzzy Sets and Systems 119 (2001) 139–148.
[20] B. Liu, Theory and Practice of Uncertain Programing, Physica-Verlag, New York, 2002.
[21] B. Liu, Uncertainty Theory, 2nd ed., Springer-Verlag, Berlin, 2007.
[22] B. Liu, Y.K. Liu, Expected value of fuzzy variable and fuzzy expected value models, IEEE Trans. Fuzzy Syst. 10 (2002) 445–450.
[23] B. Liu, K. Iwamura, Chance constrained programming with fuzzy parameters, Fuzzy Sets and Systems 94 (1998) 227–237.
[24] B. Liu, Dependent-chance programming with fuzzy decisions, IEEE Trans. Fuzzy Syst. 7 (3) (1999) 354–360.
[25] D. Dubois, H. Prade, Possibility Theory: An Approach to Computerized Processing of Uncertainty, Plenum, New York, 1988.
[26] B. Liu, A survey of credibility theory, Fuzzy Optim. Decis. Mak. 5 (2006) 387–408.
[27] B. Das, et al., A two warehouse supply-chain model under possibility/necessity/ credibility measures, Math. Comput. Modelling 46 (2007) 398–409.
[28] A.K. Maity, et al., A production-recycling-inventory system with imprecise holding costs, Applied Mathematical Modelling 32 (2008) 2241–2253.
[29] G. Bortolan, R. Degani, A review of some methods for ranking fuzzy subsets, Fuzzy Sets and Systems 15 (1985) 1–19.
[30] A. Charnes, W.W. Cooper, Chance-constrained programming, Manage. Sci. 6 (1) (1959) 73–79.
[31] D.E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, 1989.
[32] C. Ding, X. He, H. Zha, M. Gu, H.D. Simon, A min–max cut algorithm for graph partitioning and data clustering, in: IEEE International Conference on
Data Mining, 2001, pp. 107–114.
[33] E.L. Johnson, A. Mehrotra, G.L. Nemhauser, Min-cut clustering, Math. Program. 62 (1993) 133–151.
[34] M. Brusco, S. Stahl, Branch-and-Bound Applications in Combinatorial Data Analysis, Spinger, 2005.
[35] A. Wiegele, Biq Mac Library, http://biqmac.uni-klu.ac.at/biqmaclib.html 2007.
[36] A.F. Ling, C.X. Xu, F.M. Xu, A discrete filled function algorithm embedded with continuous approximation for solving max-cut problems, European J.
Oper. Res. 197 (2009) 519–531.