Geoscience Reference
In-Depth Information
By exploiting the set packing structure of KUFLP, the odd holes in the intersec-
tion graph of KUFLP allow to define two new families of valid inequalities.
Theorem 3.6 (Cornuéjols and Thizy
1982
)
The inequality
3
3
3
X
X
X
x
ii
C
x
.iC1/ mod 3;i
C
N
y
i
4
iD1
iD1
iD1
is facet-defining for
P
33
.
Theorem 3.7 (Cornuéjols and Thizy
1982
)
The inequality
X
5
X
5
X
5
x
13
C
x
41
C
x
ii
C
x
.iC1/ mod 5;i
C
N
y
i
7
iD1
iD1
iD1
is facet-defining for
P
55
.
Families of facet defining inequalities for KUFLP with general integer coeffi-
cients are also known.
Theorem 3.8 (Cánovas et al.
2000
)
Let
S
be an
r
c
adjacency matrix satisfy-
ing
(i)
8
i
1
;i
2
2
I
S
9
j
2
J
S
such that
s
i
1
j
s
i
2
j
D
1
and
(ii)
8
.i;j/
2
I
S
J
S
with
s
ij
D
1
9
`
2
I
S
,
`
¤
i
, such that
s
`j
D
1
and
s
ih
s
`h
D
0
8
h
¤
j
.
Then,
0
@
X
j2J
S
1
A
N
y
i
X
i2I
S
X
X
s
ij
x
ij
C
X
i2I
S
X
s
ij
j
I
S
jC
1
s
ij
1
i2I
S
j2J
S
j2J
S
is a facet-defining inequality of
P
rc
.
Theorem 3.9 (Cánovas et al.
2002
)
Let
S
be the
k
k
adjacency matrix,
k
3
,
given by
S
D
0
1
1.k1/
1
.k1/1
I
.k1/.k1/
Then,
X
X
X
k
s
ij
x
ij
C
.k
2/
N
y
1
C
N
y
i
2k
2
iD2
i2I
S
j2J
S
is a facet-defining inequality of
P
kk
.
