Biomedical Engineering Reference
In-Depth Information
is the set of non-negative integral
n
-dimensional vectors,
R
p
+
where
Z
n
+
is the set of
non-negative real
p
-dimensional vectors,
x
=
(x
1
,
...
,
x
n
)
and
y
=
(y
1
,
...
,
y
p
)
are
variables,
c
is an
n
-vector,
d
is a
p
-vector,
A
is an
m
×
n
matrix,
B
is an
m
×
p
matrix,
and
b
is an
m
-vector. The function
z
=
cx
+
dy
is called objective function and the set
R
p
Z
n
+
{
is called feasible region. In many models,
the integer variables are constrained to equal 0 or 1. Thus we obtain 0-1 MIP, where
x
(x
,
y)
|
Ax
+
By
≤
b
,
x
∈
,
y
∈
+
}
B
n
, where
B
n
is the set of
n
-dimensional binary vectors.
Although the general MIP problem is NP-hard, it can be solved efficiently in
many particular cases. Even in the general case, there exist different efficient solution
techniques. Most of them use the LP relaxation of MIP
Z
n
+
∈
is replaced by
x
∈
min
cx
,
R
p
+
R
n
+
z
LP
=
+
dy
|
Ax
+
By
≤
b
,
x
∈
,
y
∈
where the integrality constraints are relaxed. LP is much easier than MIP. It can be
solved in polynomial time. The most commonly used method to solve LP is the simplex
method which, although exponential in the worst case, performs well in practice.
The most important relations between MIP and LP are: (1)
z
LP
≤
z
MIP
, that is,
the optimal objective value of LP is a lower bound on the optimal objective value of
MIP and (2) if
(x
∗
,
y
∗
)
is an optimal solution of LP and
x
∗
∈
then
(x
∗
,
y
∗
)
is an
optimal solution of MIP. The B&B algorithms for MIP are based on these relations.
They partition MIP into subproblems by fixing some of the
x
-variables to integer
values until either, (1) the optimal solution of the LP relaxation of a subproblem
becomes feasible for MIP or (2) the optimal objective value of the LP relaxation of
a subproblem becomes greater than the objective value of the best-known solution
of MIP.
Most optimization problems can be formulated as MIP in several different ways.
Choosing a “good” model is of crucial importance to solving the model. The pruning
conditions (1) and (2) will work earlier for a model with “tighter” LP relaxation.
Z
n
+
18.3.1 Network Flow Formulation
To find the most appropriate MIP model for PTP, we start by restating it as a net-
work optimization problem. Let
A
={
(i
,
j)
∈
L
|
j
−
i
=
1
}
be the set of interactions
between adjacent segments and let
R
=
L
\
A
be the set of remote links. We introduce
a digraph
G(V
,
E)
with vertex set
V
={
(i
,
k)
|
i
=
1,
...
,
m
,
k
=
1,
...
,
n
}
and arc
set
E
=
E
L
∪
E
x
, where
E
L
={
((i
,
k)
,
(j
,
l))
|
(i
,
j)
∈
L
,1
≤
k
≤
l
≤
n
}
,
E
x
={
((i
,
k)
,
(i
+
1,
l))
|
i
=
1,
...
,
m
−
1, 1
≤
k
≤
l
≤
n
}
.
A vertex
(i
,
k)
V
corresponds to segment
i
placed on its
k
th relative position. The
set
E
L
corresponds to the set of links
L
between the segments. The arcs from
E
x
\
∈
E
L
are added to ensure the order of the segments. Depending on the situation, a set of
arcs
E
z
is defined as either
E
L
\
E
x
, corresponding in this case to the links from
R
,or
Search WWH ::
Custom Search