Biomedical Engineering Reference
In-Depth Information
c
4364
Position
c
3264
j
= 4
c
5464
j
= 3
c
4354
c
1132
S
T
c
3243
j
= 2
c
2232
c
1122
j
= 1
i
= 1
i
= 2
i
= 3
i
= 4
i
= 5
i
= 6
Block
Figure 18.4
Example of augmented path. The generalized contact map graph is given in the
bottom. The
x
-arcs of the
S
-
T
path are in solid lines. The activated
z
-arcs are in dashed lines.
The length of the augmented path is equal to the score of the threading
(
1, 2, 2, 3, 4, 4
)
.
x
e
−
x
e
=
0,
v
∈
V
,
(18.3)
e
∈
(v)
−
1
(v)
e
∈
x
e
≥
0,
e
∈
E
x
,
(18.4)
where
(v)
(respectively
−
1
(v)
) denotes the set of the
x
-arcs with tail (respec-
tively head)
v
. Constraint (18.1) (respectively (18.2)) corresponds to unit flow from
S
(respectively to
T
), and constraints (18.3) refer to flow conservation for each vertex.
The well-known properties of the network polytope
X
make it possible to replace the
integrality requirements
x
e
∈{
0.
The set of feasible threadings can also be expressed in the space of
y
-variables as
a set
Y
, defined by the constraints
0, 1
}
by
x
e
≥
n
y
ik
=
1,
i
=
1,
...
,
m
,
(18.5)
k
=
1
k
k
y
il
−
y
i
+
1,
l
≥
0,
i
=
1,
...
,
m
−
1,
k
=
1,
...
,
n
−
1,
(18.6)
l
=
1
l
=
1
y
ik
∈{
0, 1
}
,
i
=
1,
...
,
m
,
k
=
1,
...
,
n
.
(18.7)
The binary variable
y
ik
is 1 if and only if segment
i
is placed on position
k
. Constraints
(18.5) assign each segment to exactly one position and (18.6) ensure the order of
segments (if segment
i
is placed after the
k
th position, then
i
+
1 must also be placed
after the
k
th position).
Starting from the
S
-
T
path defining sets
X
or
Y
, an augmented path defining set
Z
can be constructed by introducing the
z
-variables and adding appropriate connecting
Search WWH ::
Custom Search