A Novel Clustering Approach: Global Optimum Search with Enhanced Positioning - Clustering Challenges in Biological Network - page 314

For our clustering problem, with fixed starting values for w ij , the primal prob-
lem becomes:
min z jk i =1 s k =1 a ik − i =1 c j =1 s k =1 a ik w ij z jk (Problem 7.1)
s.t. z jk i =1 w ij − i =1 a ik w ij =0 , ∀ j ∀ k

z jk ≤ z jk ,

z jk ≤ ∀ j, ∀ k

The primal problem is a Linear Programming (LP) problem. All the other
constraints drop out since they do not involve z jk , which are the variables to be
solved in the primal problem. Besides z jk , the Lagrange multipliers λ jk for each
of the constraints above is obtained. The objective function is the upper bound
solution. These are substituted into the master problem, which becomes:

min y,µ B µ B (Problem 7.2)

µ B ≥ i =1 s k =1 a ik − i =1 c j =1 s k =1 a ik w ij z jk + ...
c j =1 s k =1 λ m ∗

s.t.

jk ( z jk i =1 w ij − i =1 a ik w ij ) ,m =1 ,M
c j =1 w ij =1 ,

∀ i

≤ i =1 w ij ≤ 1 n − c +1 , ∀ j

w ij =0 − 1 , ∀ i, ∀ j

The master problem solves for w ij and µ B , and results in a lower bound solu-
tion (i.e., the objective function). The master problem is a Mixed Integer Linear
Programming (MILP) problem. The w ij solutions are cycled back into the primal
problem and the process is repeated until the solution converges. Thus, there is
no longer a need for the variables y ijk , which substantially reduces the number of
variables to be solved. Also, after every solution of the master problem, where a
solution set for w ij is generated, an integer cut is added for subsequent iterations
to prevent redundantly considering that particular solution set again. The cut is
expressed as:

n n

w ij − w ij ≤ n − 1 (16.4)

i∈ [ n|w ij =1] i∈ [ n|w ij =0]

Note that the initial condition w ij for the primal problem can be generated
either by solving the above problem as a relaxed MINLP problem or by randomly
generating starting w ij values. For the former, the w ij solution is then rounded up
and used as the initial condition for the GOS algorithm. It is found that well over
95% of the w ij solution from the MINLP problem adopt [0,1] solutions anyway.