Biology Reference
In-Depth Information
Step 2 - Solving the relaxed master problem
The master problem is essentially the problem projected onto the y-space (i.e.,
that of the binary variables). To expedite the solution of this projection, the dual
representation of the master is used. This dual representation is in terms of the
supporting Lagrange functions of the projected problem. It is assumed that the
optimal solution of the primal problem as well as its Lagrange multipliers can be
used for the determination of the support function. Also, the support functions are
gradually built up over each successive iteration. The relaxed master problem to
be solved is hence:
min
y,µ
B
µ
B
(Problem 6)
L
(
x
k
,y,λ
k
,µ
k
)
,k
=1
,K
s.t.
µ
B
≥
L
(
x
l
,y,λ
l
,µ
l
)
,l
=1
,L
0
≥
L
(
x
k
,y,λ
k
,µ
k
)=
f
(
x
k
,y
)+
λ
k
h
(
x
k
,y
)+
µ
k
g
(
x
k
,y
)
L
(
x
l
,y,λ
l
,µ
l
)=
λ
l
h
(
x
l
,y
)+
µ
l
g
(
x
l
,y
)
In accordance to the general format of the problem, f(x, y) is the objective
function, h(x, y) are the active constraints, and g(x, y) are the inactive constraints.
'x' represents the solutions of the continuous variables (i.e.,
z
jk
) from the primal
problem and 'y' represents the binary variables (i.e.,
w
ij
) to be determined in the
relaxed master. '
λ
' represents the Lagrange multipliers for the active constraints
and '
µ
' represents the Lagrange multipliers for the inactive constraints. The super-
script 'k' represents values from the feasible primal problems and the superscript
'l' (and the over-bar) represents values from the infeasible primal problems. The
master problem is to be solved as a MIP (mixed integer programming) problem.
The solution loop then returns to step 1 and the process is repeated. For each
excursion into step 1, the primal could be either feasible or infeasible. With each
successive iteration, a new support function is added to the list of constraints for
the master problem. Thus in a sense, the support functions for the master problem
build up with each iteration, forming a progressively tighter envelope and gradu-
ally pushing up the lower bound solution until it converges with the upper bound
solution.
Since fixing x to the solution of the corresponding primal problem may not
necessarily produce valid support functions, the master solution obtained at each
iteration is checked against the current lower bound solution so that the latter is
updated only if the master solution is higher than the current lower bound solution.
Search WWH ::
Custom Search