Geoscience Reference
In-Depth Information
to prove that a certain family of valid inequalities can cut fractional solutions of
LKUFLP. The results of Cánovas et al. (
2001
) also characterize the extreme points
of the polyhedra associated with the FLP formulation in Leung and Magnanti (
1989
)
and of other related problems.
3.5.2
Valid Inequalities and Facets
Next we present several families of valid inequalities of P
mn
. Further details and
results can be found in Cho et al. (
1983a
) and Cánovas et al. (
2002
).
Cornuéjols et al. (
1977
) presented the first polyhedral study of the KUFLP. They
proposed, without proof, the following family of valid inequalities of P
mn
X
b
ij
x
ij
C
X
i2I
C
N
y
i
2k
d
k=t
e
;
(3.67)
i2I
C
where k and t are integers such that k
D
tp
C
1 for some integer p;B is a cyclic
matrix of type .k;t/ and I
B
I; J
B
J are subsets of cardinality k: Later,
Cornuéjols and Thizy (
1982
) proved that (
3.67
) is a facet.
Several well-known families of facets for the KUFLP with binary coefficients are
discussed below:
Theorem 3.4 (Cho et al.
1983b
)
Consider
I
S
I
and
J
S
J
. Then, the
inequality
X
X
s
ij
x
ij
C
X
i2I
S
N
y
i
Ǜ.G
S
/;
i2I
S
j2J
S
where
s
ij
D
0
or 1, is facet-defining for
P
mn
(and different from a clique facet) if
and only if
S
is a
j
I
S
jj
J
S
j
, maximal mn-adjacency matrix.
A characterization of maximal
mn
-adjacency matrices can be found in Cho et al.
(
1983b
). A special case of maximal
mn
-adjacency matrix gives rise to a concrete
family of facet-defining inequalities of P
mn
:
Theorem 3.5 (Cornuéjols and Thizy
1982
)
Consider
`
and
t
such that
2
t<
`
m
and subsets
P
I
,
D
J
, such that
j
D
jD
`
t
,
j
P
jD
`
.Let
A
`t
be the
matrix whose columns are all vectors 0-1 with
t
ones and
`
t
zeros. Then,
N
y
i
`
t
C
t
1
X
X
ij
x
ij
C
X
i2I
a
`t
i2I
j2J
is a facet-defining inequality of
P
mn
.
