Geoscience Reference
In-Depth Information
Theorem 3.10 (Cánovas et al.
2002
)
Consider three numbers,
k
5
,
1
a<
k
3
and
b
D
k
3
a
and let
S
be the
k
k
adjacency matrix given by
0
@
1
A
I
aa
0
ab
0
a1
0
a1
1
a1
0
ba
I
bb
1
b1
0
b1
1
b1
1
1a
0
1b
100
0
1a
1
1b
010
0
1a
0
1b
111
S
D
:
Then,
X
X
s
ij
x
ij
C
X
i2I
S
N
y
i
C
a
N
y
k2
C
b
N
y
k1
2k
3
i2I
S
j2J
S
nfk2;k1g
is a facet-defining inequality of
P
kk
.
Theorem 3.11 (Cánovas et al.
2002
)
Let
B
be the cyclic
.2k
C
1;2/
matrix,
k
1
,
and let
S
be the
.2k
C
2/
.4k
C
2/
adjacency matrix given by
S
D
B
.2kC1/.2kC1/
I
.2kC1/.2kC1/
0
1.2kC1/
:
1
1.2kC1/
Then,
X
X
2kC1
X
s
ij
x
ij
C
2
N
y
i
C
.k
C
1/
N
y
2kC2
6k
C
3
i2I
S
j2J
S
iD1
is a facet-defining inequality of
P
.2kC2/.4kC2/
.
Other types of inequalities have been suggested. For instance, Myung and Tcha
(
1996
) develop a family of inequalities that may cutoff feasible solutions but not
optimal ones. In particular, they propose a method for generating inequalities for a
constrained KUFLP which considers its feasible domain and the objective function
value, as well. For the sake of brevity, details are omitted here.
3.5.3
Lifting Procedures
The procedures that transform a valid inequality (facet) of a polyhedron P
m
n
into a valid inequality (facet) of an higher polyhedron P
mn
;m
m
or n
n
;
are called lifting procedures. Such results invite the study of small polyhedra. The
following result indicates how to lift all the facets in the previous section.
