Geoscience Reference
In-Depth Information
the corresponding SFrCI constraint is a capacity constraint (in this case,
3
.S
j
/
D
1
.S/). So, the two terms in the left-hand side of (
15.31
) are identical, the two terms
in the right-hand side are also equal, and the inequality becomes:
X
S
rS
r
1
.S/;
r2
which is the basic expression of the capacity constraint.
As is the case for other sets of inequalities, the framed capacity inequalities
(FrCI) where originally developed for two-index flow formulations and later
adapted to the set-partitioning formulation by using Eq. (
15.29
), and reinforced by
modifying the coefficients of the
r
variables as explained in the last section. The
FrCI for formulation LRP2 corresponding to .S;
S
/ is
0
@
X
1
t
X
X
z
jk
C
2
X
i2I
X
X
X
z
jk
C
2
X
i2I
A
z
ij
C
z
ij
j2S
j2S
sD1
j2S
s
k2V nS
k2V nS
s
2
3
.S
j
1
.S
s
/
!
:
t
X
S
/
C
(15.32)
sD1
To illustrate that FrCI (and, therefore, SFrCI) is a broader set of inequalities that
can be stronger than the combination of capacity constraints for the individual sets
S
s
,Fig.
15.3
gives an example of a fractional solution with
Df
S
1
;
;S
4
g
,
where the capacity constraints for each of the S
s
sets are satisfied, but the overall
FrCI constraint is violated. In this figure, customers are numbered from 1 to 7 and
w
i
is given inside each customer. Note that, in this example, we have S
D[
sD1
S
s
,
w
.S/
D
20 and Q
D
7,sothat
1
.S/
D
3. Thus, the capacity constraint for set S is
satisfied, since the total flow in edges with one endpoint in S equals its lower bound,
2
3
D
6. Also, for each set in the partition,
w
.S
s
/<Q,sothat
1
.S
s
/
D
1 and the
S
Fig. 15.3
Example of
unsatisfied FrCI
