Deza M.M., Laurent M. Geometry of Cuts and Metrics
Подождите немного. Документ загружается.
Part
V
Facets
of
the
Cut
Cone
and
Polytope
Introduction
In
this
last
part,
we
survey the results which are known
about
the facial
structure
of
the
cut
cone
and
of
the
cut
polytope. Actually, all the facets of the
cut
polytope
can
be
derived from those of the
cut
cone, via the switching operation (see
Section
26.3). Therefore,
we
will almost exclusively concentrate
our
attention
to
the
facets of the
cut
cone.
On
the other hand, (almost) any result
about
the
facial
structure
of the cut polyhedra has a direct counterpart for the correlation
polyhedra, as
both
sets of polyhedra are in one-to-one linear correspondence (see
Section
26.1).
As was explained in
Part
I, the members of the
cut
cone
CUT
n are
the
semimetrics on
Vn
=
{I,
...
, n}
that
can
be
isometrically embedded into some
f1-space. Hence, the facets of CUTn correspond
to
the linear inequalities char-
acterizing f1-spaces.
On
the other hand, the
cut
polytope plays
an
important
role in combinatorial optimization, as
it
permits
to
model
the
max-cut problem:
max(c
T
8(8) I 8
~
V
n
)
(where c E
JW.En)
by
max
~x
s.t. x E
CUT~.
(Recall Sections 4.1
and
5.1 where connections
and
applications are mentioned.)
We
will see
in
Section 31.2
that
the
facets of
the
cut
polytope have
moreover
the
following interesting application: They yield valid inequalities for
the
pairwise angles among a set of n
unit
vectors.
The
complete description of all
the
facets of
the
cut cone
CUT
n (or of
the
cut
polytope
CUT~)
is probably hopeless. Indeed, as the max-cut problem is
NP-hard,
it
follows from a result of
Karp
and Papadimitriou
[1982]
that
there is
no polynomially concise way of describing a list of inequalities sufficient to define
CUT~
jf
NP
=1=
co-NP.
Still a limited knowledge of some classes of facets remains interesting, from
many
points of view. For instance, when a separation routine is available, these
classes of facets may be used in cutting plane algorithms for solving practical
instances
ofthe
max-cut problem. (The reader may consult the survey by Jiinger,
ReineIt
and
Thienel [1995] for more information on solving optimization problems
using
cutting
plane procedures.) Also, some subclasses of facets are sometimes
already sufficient for handling some special classes of
f
1-
metrics (for a list of
several such cases, see Remark
6.3.5), or
for
the complete description of
the
cut
polyhedra for restricted classes of graphs (see Section 27.3).
398
Introduction
The
complete description
of
all the facets
of
the
cut
polyhedra CUTn
and
CUT~
is known for n
:5
8;
we
list
the
facets
of
the
cut
polyhedra on n
:5
7 nodes
in
Section 30.6. For instance, CUT7 has 38780 facets, while
CUT~
has 116764
facets. For n = 8,
the
number
of
facets is enormous: more
than
217 millions,
subdivided into
147
orbits!
Part
V is organized as follows.
We
present in
Chapter
26
some tools
and
operations for constructing facets
and
in
Chapters 27-30
the
known classes of
valid inequalities
and
facets for the cut cone and polytope.
We
then
group
in
Chapter
31 several geometric properties of the cut polytope and related objects.
Most
of
Part
V deals with
the
facial structure of
the
cut
polyhedra. However,
we
also visit
en
route some adjacent topics where cut and semimetric polyhedra
are directly relevant; namely, cycle polyhedra of general binary matroids
in
Sec-
tion
27.4, a positive semidefinite approximation of
the
cut
polytope
in
Section
28.4.1,
and
completion problems
for
positive semidefinite matrices
and
Euclidean
distance matrices
in
Sections 31.3
and
31.4.
Many
of
the inequalities
that
we
investigate are
of
the
form:
L
bibjXij
- L
Xij:5
0,
l:'Si<j:'Sn
ijEE(G)
where b1,'" ,b
n
are integers
and
G is a subgraph (possibly edge weighted) of
Kn.
When
L1<i<n
bi
= 1
and
G is
the
empty graph,
we
find
the
hypermetric
inequalities.
When
L1<i<n
bi
is
odd
and
G is
an
antiweb (resp. a suspended
tree),
we
have
the
clique-':web
inequalities (resp.
the
suspended-tree inequalities),
considered in
Chapter
29
and
Section 30.1. However, three classes of facets are
presented
in
Sections 30.2-30.4, which do not fit into
this
scheme.
Hypermetric inequalities constitute perhaps
the
most interesting known class
of valid inequalities for
the
cut
cone. They have already been considered in
Part
I
in connection with the study of f1-metrics;
we
saw in Remark 6.3.5 several classes
of
metrics for which the hypermetric inequalities already suffice for character-
izing l'l-embeddability.
They
have also been extensively studied
in
Part
II, in
connection with Delaunay polytopes in lattices.
We
focus in
Chapter
28 on
the
study
of
hypermetric inequalities as facets
of
the
cut polyhedra. Note
that
all
the facets
of
the
cut
cone on n
:5
6 points are, in fact, hypermetric.
Triangle inequalities, which are a very special case of hyper metric inequalities,
are
treated
in
detail
in
Chapter
27.
In
Chapter
29,
we
consider
the
clique-web
inequalities, which are a generalization of hypermetric inequalities.
Other
classes
of
facets not covered by this vast class are given
in
Chapter
30.
We
describe in
Chapter
31
several properties of geometric type for
the
cut
polytope
CUT~
and related objects.
We
study in Sections 31.6-31.8 questions
dealing with adjacency properties
and
small dimensional faces of the
cut
polytope
and
of
the
semimetric polytope, or with the
'shape'
of
CUT~
in terms of distances
of its facets to the barycentrum, or with
its
simplex facets.
We
describe
in
Section 31.2
an
interesting application of the linear description of the
cut
cone
CUT"
for
finding valid inequalities for
the
pairwise angles among any set
of
n
Introduction
399
vectors
in
Jm
n
.
Section 31.1 indicates how cuts
can
be
used for disproving a
long standing conjecture by Borsuk. Finally, Sections 31.3
and
31.4 consider
the
completion problems for partial positive semidefinite matrices
and
partial
Euclidean distance matrices.
It
turns
out
that
several
of
the
polyhedra studied in
this book, including
the
cut
polytope, the semimetric polytope
and
the
negative
type
cone, play an
important
role in these two problems.
The
symbol 6(8), which was called
"a
cut semimetric" so far
in
the
book,
will be most often called "a
cut vector'
in
Part
V.
This reflects
the
fact
that
we
are not any more concerned here with the
study
of
semimetrics
but
rather
with
the
cut
polyhedra CUTn and
CUT~
as geometrical objects.
We
remind
that
the
symbol 6Kn
(8)
denotes
the
cut in Kn determined by
8,
that
is, the set
of
edges
in
Kn having exactly one endnode
in
8.
Hence,
the
incidence vector of the edge
set
6K"
(8)
is
the
cut
vector 6(8).
We
may sometimes use interchangeably
the
notation
6(8)
and
6K"
(8)
and, e.g., speak of the "cut 6(8)".
We
will occasionally consider some other cones and polytopes, generated
by
restricted
cut
families, such as equicuts, even cuts, etc.
The
notions
of
even
T-cut,
k-uniform
cut
and
odd
cut
semimetrics have already been introduced in
Section
25.1, where
we
have studied the lattices they span. For convenience,
we
recall
the
definitions here. Let 8
be
a subset of V
n
•
Then, 6(8) is called
an
even cut vector (or even
cut
semimetric)
if
181
and
IVn
\
81
are
both
even;
6(8) is called
an
equicut vector (resp. an inequicut vector)
if
181
= liJ,
ril
(resp.
181
=1=
l
iJ
,
ri
1).
Given
an
integer k
::;
n,
6(8) is a k-uniform cut vector if
181
k, n
k.
We
let
ECUT
n
(resp.
ICUT
n
,
UCUT~)
denote the cone in
IRE"
generated by all even
cut
(resp. inequicut, k-uniform cut) vectors;
EQCUT~
denotes
the
polytope in
IRE"
defined as the convex hull
of
all equicut vectors
in
Kn. These polyhedra are called
in
the obvious manner, i.e.,
EQCUT~
is the
equicut polytope,
ECUT
n
is the even cut cone,
ICUT
n
is the inequicut cone,
and
UCUT~
is
the
k-uniform cut cone. Note
that
EQCUT~
coincides
with
the
face
of
CUT~
defined by
the
inequality:
(a)
2.:=
Xij::;
l::J
r::l·
l~i<j~n
2 2
When
n is odd, n =
2p
+
1,
then
EQCUT~p+l
is
a facet
of
CUT~p+l
(as
the
inequality (a) is a switching
of
the pure hypermetric inequality, which is facet
defining by Corollary
28.2.5 (i)). When n is even, n 2p, then
EQCUT~p
is a
face of dimension
en
-p of
CUT~p'
We
also consider
the
multicut polytope
MC~,
which is defined as
the
convex
hull of all
multicut
vectors 6(8
1
,
...
,8
p
)
(for any partition of
Vn
into
an
arbitrary
number
of
parts). (Note
that
the
cone generated by all multicut vectors coincides
with
the
cut
cone
CUT
n
, as
6(8J,
...
,8
p
)
=
~
L:f=l
6(8i) for any
partition
of
Vn
into 8
1
U
...
U 8
p
.)
We
will only give very occasional information on the above polyhedra. For
more details concerning the equicut polytope, see Conforti, Rao
and
Sassano
[1990a, 1990b], Deza, Fukuda
and
Laurent
[1993],
De Souza
[1993],
De Souza
400
Introduction
and
Laurent
[1995]; see Deza, Grotschel
and
Laurent
[1991, 1992],
Chopra
and
Rao
[1995]
and
further
references
therein
for
the
multicut
polytope;
the
inequicut,
even
cut
and
k-uniform
cut
cones are considered, respectively,
in
Deza,
Fukuda
and
Laurent
[1993],
and
Deza
and
Laurent
[1993b, 1992e].
We will use
the
definitions
about
polyhedra
(faces, facets, valid inequalities,
etc.) from Section 2.2.
We
also use
the
following
additional
definitions for roots,
pure
inequalities
and
edgeweight vectors. Given
an
inequality v
T
x
::;
Va which
is valid for
the
cut
polytope
CUT~,
where V E
REn
and
Va E
R,
a
cut
vector
8(S)
is
called a root of
the
inequality v
T
x::; Va if
it
satisfies it
at
equality, i.e., if
v
T
8(S)
=
Va.
Similarly,
the
cut
vectors
that
belong to a face F of
CUTn
or
of
CUT~
are called its roots. We let
R(F)
denote
the
set of
roots
of
the
face F.
Given V E
REn
and
Va E
R,
the
inequality v
T
x
::;
Va is said
to
be
pure if
Vij
E
{O,
1,
-I}
for all
ij
E En. For
any
cut
vector 8(S),
we
use
the
notation:·
v(8(S))
:=
v
T
8(S) =
:E
Vij·
ijEO(S)
Given V E
REn,
we
can
define
an
associated weighted
graph
G
v
with
node set
{I,
...
,n},
whose edges are
the
pairs
ij
for which
Vij
i=
0;
to
the
edge
ij
we
assign
the
weight
Vij.
The
graph
G
v
is called
the
support graph of v. Conversely,
if G
=
(V,
E)
is
an
edge weighted graph,
that
is a
graph
G together
with
some
weights
Vij
(ij
E
E)
on
its edges,
then
we
define its edgeweight vector as
the
vector V E
REn
whose components are
the
weights
Vij
for
the
edges
ij
E E
and
setting
Vij
:=
0 if
ij
is
not
an
edge of G.
Let
v
T
x
::;
0
be
a valid inequality for
the
cut
cone
CUT
n
. As
CUTn
is a
full-dimensional cone
in
the
space
R(~),
the
inequality v
T
x
::;
0 defines a facet
of
CUTn
if it
has
G)
- 1 linearly
independent
roots, i.e., if
there
exist
G)
- 1
linearly
independent
cut
vectors 8(S) such
that
v
T
8(S) =
o.
Hence, one way to
show
that
v
T
x
::;
0
is
facet defining for
CUTn
is by exhibiting such a set of
cut
vectors.
This
direct
method
can
be
applied, for instance, for
the
small
values
of
n where linear independence
can
be
tested by
hand
or by computer.
Equivalently, one
may
show
that
the
inequality v
T
x
::;
0
is
facet inducing for
CUTn
in
the
following way. Let a E
REn
be a vector such
that
or, equivalently, such
that
a(8(S)) = 0 whenever
v(8(S))
= 0 for S
~
V
n
.
If
for
every
such
vector a there exists a scalar a such
that
a =
av,
then
the
inequality
v
T
x
::;
0 is facet inducing for
CUT
n
. (Note
that
we
may
restrict
ourselves to
showing this
property
for all a E
REn
for which
the
inequality
aT
x ::; 0
is
valid
for
CUTn.)
We will see
in
Section 26.5 some lifting techniques
permitting
to
construct
facets
in
an
iterative manner.
M.M. Deza, M. Laurent, Geometry of Cuts and Metrics, Algorithms and Combinatorics 15,
DOI 10.1007/978-3-642-04295-9_26, © Springer-Verlag Berlin Heidelberg 2010
Chapter
26.
Operations
on
Valid
Inequalities
and
Facets
In
this
chapter
we
present several operations
on
valid inequalities
and
facets
of
the
cut
polytope. One
of
the
basic
properties
of
the
cut
polytope
CUT~
is
that
all
its
facets
can
be
deduced from
the
facets of
the
cut
cone
CUTn
using
the
so-called switching
operation
(cf.
Section 26.3.2).
In
fact, switchings
and
permutations
constitute
the
whole group of
symmetries
of
the
cut
polytope
(cf.
Section 26.3.3). A general technique for constructing new facets of
CUTn+l
from
given facets of
CUTn
is
by applying
the
so-called lifting operation;
we
describe
conditions of
application
of
this
technique
in
Section 26.5
and
the
converse oper-
ation: collapsing,
in
Section 26.4.
Another
technique for
constructing
facets (by
looking
at
projections) is mentioned
in
Section 26.6.
26.1
Cut
and
Correlation
Vectors
As was already explained
in
Section 5.2,
cut
vectors are
in
one-to-one linear
correspondence
with
correlation vectors, via
the
correlation mapping.
This
fact
will
be
very
often
used here, so
we
recall
the
details.
Let
Vn
=
{I,
...
, n}, V
n
+
1
=
Vn
U
{n+
I},
and
let
En,
En+l
denote
the
set
of
unordered
pairs
of elements of V
n
,
Vn+l,
respectively.
The
covariance mapping
is
defined as follows. For x =
(Xij
)l:Si<j:Sn+l E jRE
n
+
1
and
p =
(Pij
h:Si:Sj:Sn
E
jRVnUE
n
,
let p = e(x)
be
defined by
Pii
= Xi,n+1
for 1
::;
i
::;
n,
Pij
= h
X
i,n+1
+
Xj,n+1
-
Xij)
for 1
::;
i < j
::;
n.
Given a
subset
S
s;::
V
n
,
the
vector 7r(S)
:=
e(8(S)) is called
the
correlation vector
of
S pointed at position n +
1;
so, 7r(S)ij = 1 if i, j E
Sand
7r(S)ij = 0 otherwise
for 1
::;
i
::;
j
::;
n.
In
the
above definition,
we
have distinguished
the
position
n +
1;
we
also
denote
the
covariance
mapping
e by
en+l
if
we
want
to
stress
this
fact.
Of
course,
any
other
position i E V
n
+
1
could
be
distinguished as well
with
the
covariance
mapping
ei
being
analogously defined.
The
covariance
mapping
e is clearly linear
and
bijective. Therefore, given
subsets
Sl,
...
,Sk
s;::
V
n
,
the
set
of
cut
vectors {8(Sd,
...
,8(Sk)} is linearly in-
dependent
if
and
only if
the
corresponding set {7r(Sl),
...
,7r(Sk)}
of
correlation
402
Chapter
26.
Operations on Valid Inequalities and Facets
vectors is linearly independent. Often, when
we
have to check the linear inde-
pendence
of
a set
of
cut vectors,
we
will work with the associated correlation
vectors whose manipulation is generally easier.
Recall
that
the
correlation cone COR,. and the correlation polytope
COR~
are defined, respectively, as
the
conic hull and
the
convex
hull
of
the set
of
correlation vectors
1I"(S)
for
S
~
V
n
•
Hence,
As
a consequence, any result on the facial structure
of
the
cut
polytope can
be
translated into a result on the facial structure
of
the correlation polytope
and
vice versa.
We
recall the following result, which was already formulated in
Proposition 5.2.7.
Proposition
26.1.1.
Let c E
lR.
E
,,+l and a E
lR.V"UE"
be
related
by
aii
=
LIS;jS;n+I,#i
Cij
aij
=
-2Cij
for 1
:s;
i
:s;
n,
for 1
:s;
i < j
:s;
n.
Then, the inequality:
L
CijXij
:s;
a
lS;i<jS;nH
defines a valid inequality (resp. a facet)
of
the cut polytope
CUT~H
if
and only
if
the inequality:
L
aiiXi
+ L
O-ijXij:S;
a
lS;iS;n
lS;i<jS;n
defines a valid inequality (resp. a facet)
of
the correlation polytope
CO~.
I
We have chosen to present most
of
our results
in
the
context
of
cuts.
The
corresponding results for
the
correlation polyhedra can
be
easily deduced using
Proposition 26.1.1.
The
two forms taken by several classes
of
inequalities (trian-
gle, hypermetric, negative type inequalities)
in
both
the "cut" and "correlation"
contexts have been shown
in
Figure 5.2.6. One reason for our choice
of
present-
ing inequalities for cut polyhedra
rather
than
for correlation polyhedra
is
that
they have often a much simpler form. For instance,
we
find it easier to handle
the
triangle inequality:
XI2
+
X13
+ XZ3
:s;
2
rather
than
the
corresponding inequality:
Pll
+
P22
+
P33
PI2
-
PI3
P23:S;
1.
There
are, however, some exceptions
to
this rule. There exist indeed some results
whose formulation
is
easier in the context
of
correlation polyhedra
than
in
the
context
of
cuts;
we
will see one such result in Section 26.6.
26.2
The
Permutation
Operation
403
26.2
The
Permutation
Operation
Since
we
are working with
the
complete graph K
n
, all the faces of CUTn or of
CUT~
are clearly preserved under any
permutation
of
the nodes. Let Sym(n)
denote
the
group
of
permutations of the set {1,2,
...
,n},
called the symmetric
group
of
{I,
...
,
n}.
Given a permutation u E Sym(n) and a vector v E
~En,
define the vector
u(v)
E
~E"
by
U(V)ij
:=
Vq(i)q(j)
for
ij
E En.
The
following result
is
trivial.
Lemma
26.2.1.
Given v E
~E",
Vo
E
~
and U E Sym(n), the following
statements
are
equivalent.
(i) The inequality v
T
x:::;
Vo
is valid (resp. facet inducing) for
CUT~.
(ii)
The inequality
u(v)T
x:::;
Vo
is valid (resp. facet inducing) for
CUT~.
I
We
have a similar statement about
the
cut cone
CUT
n when applying Lemma
26.2.1 to homogeneous inequalities, i.e., to inequalities
of
the form v'I'x
:::;
O.
Let
F be
the
face
of
CUT~
induced
by
the
valid inequality v
T
x
:::;
vo,
then
u(F)
:=
{u(x)
I x E
F}
is
the
face
of
CUT~
induced by
the
inequality u( v)T X :::;
Va.
We say
that
F and
u(F)
are permutation equivalent.
The
two faces F and
u(F)
have obviously
the
same dimension.
26.3
The
Switching
Operation
The
cut polytope has
the
remarkable property
that
if,
for some vertex, all
the
facets containing this vertex are known,
then
all
the
facets
of
the
whole poly-
tope can
be
easily derived, using the so-called switching operation. This
is
a
consequence
of
the
simple fact
that
the
symmetric difference
of
two cuts
is
again
a cut.
This
property applies more generally to
the
set families
that
are closed
under taking
the
symmetric difference.
We
first present the switching operation
in
the
general setting of set families, which will enable us to apply it to several
instances of polyhedra, and then specialize it to cut polyhedra.
We
describe in
Section 26.3.3
the
full symmetry group of
the
cut
polytope.
26.3.1
Switching:
A
General
Definition
Let A be a family
of
subsets of a given finite set
E,
let B
~
E,
and set
AB:=
{A.0.B I A E
A}.
Let
P(A)
(resp. P(AB)) denote the polytope
in
~E,
which
is
defined as the
convex hull
ofthe
incidence vectors
of
the
members
of
A (resp. of AB). A linear
404
Chapter
26.
Operations
on
Valid Inequalities
and
Facets
description
of
the
polytope
P(AB)
can
be easily deduced if one knows a linear
description
of
the
polytope
P(A);
see Corollaries 26.3.4
and
26.3.5.
For a vector
v E
m.
E
,
let
vB
E
m.
E
be defined by
(26.3.1)
B
{-ve
Ve
:=
Ve
ife
E
B,
if
e E E \
B.
Consider
the
mapping
rB
:
m.
E
-----+
m.
E
defined by
rB(x)
:=
x
B
+ X
B
for x E
m.
E
,
i.e.,
(26.3.2)
if
e E
B,
if
e E E \
B.
The
mapping
r B is
an
affine bijection
of
the
space
m.
E
,
called switching mapping.
The
following
can
be easily checked:
Lemma
26.3.3.
Let
A,
B,
AI,
...
,Ak
be
subsets
of
E and let v E
m.
E
.
Then,
(i)
rB(x
A
)
= X
A6B
.
(ii)
vB(A)
=
v(A6B)
-
v(B).
(iii) {X
A1
,
...
, X
Ak
} is affinely independent
if
and only
if
{X
A16B
,
...
,XA
k
6B}
is affinely independent. I
Corollary
26.3.4.
P(AB)
=
rB(P(A)).
I
Corollary
26.3.5.
Given v E
m.
E
,
Va
E
m.
and B
~
E,
the following assertions
are equivalent.
(i)
The inequality v
T
x
:S
Va
is valid
or
facet inducing
for
the polytope
P(A),
respectively.
(ii) The inequality
(vBf
x
:S
va-v(B)
is valid
or
facet inducing
for
the polytope
P(AB),
respectively. I
We say
that
the
inequality:
is
obtained
by switching the inequality v
T
x
:S
Va
by the
set
B.
Hence,
the
list
of
inequalities defining
P(A
B
)
is
obtained
from
the
list
of
inequalities defining
P(A)
by switching each
of
them
by
the
set
B.
If
Va
= 0
and
if
the
set B defines a root
of
the
inequality v
T
x
:S
va, i.e.,
if
v(B)
=
0,
then
the
switched inequality reads:
(vB)T
x
:S
o.
In
other
words,
the
"switching by roots"
operation
preserves homogeneous inequalities.
Let
F denote
the
face
of
P(A)
induced by
the
valid inequality v
T
x
:S
va,
then
26.3
The
Switching
Operation
405
is
the
face
of
P(AB)
induced by
the
switched inequality (vB)Tx
::;
Vo
-
v(B).
By
Lemma
26.3.3,
both
faces
F,
rB(F) have
the
same dimension
and
the
roots
of
rB(F) (i.e.,
the
members
C E
AB
for which
XC
E rB(F)) are exactly
the
vectors X
A6B
, for X
A
E
F.
Hence, the switching
mapping
establishes a
1-1
correspondence between
the
face lattices
of
the
polytopes
peA)
and
P(AB).
Let
us now suppose
that
the
family A is closed under taking
the
symmetric
difference, i.e.,
that
Af'::.B E A for all
A.,
B E
Ai
hence,
I')
E
A.
Then,
the
class
of
valid inequalities for
peA)
is closed under switching. Moreover, the full list
of
facets
of
peA)
can
be
derived from
the
list
of
facets containing any given
point
X
A
(where
A.
E A).
In
particular,
the
full facial
structure
of
the
polytope
peA)
can
be
deduced from
that
of
the
cone
C(A),
which
is
defined as
the
cone
generated
by the vectors X
A
for A E A.
The
next
proposition summarizes these
facts.
Proposition
26.3.6.
Let A
be
a collection
of
subsets
of
E that is closed under
the
symmetric
difference. Suppose that
C
(A)
=
{x
E
:IRE
I
vT
x
::;
0 for
iI,
...
,
m}
.
Then,
peA)
=
{x
E
:IRE
I
(vff
x::;
-vi(B)
for i = 1,
...
,
m,
and
BE
A}.
I
A typical example
of
a set family
that
is closed
under
taking
the
symmetric
difference
is
the
set
of
cuts
in
a graph,
or
the
set
of
cycles
in
a graph.
In
fact,
the
set families
that
are
closed
under
taking
the
symmetric difference
are
precisely
the
cycle spaces
of
binary matroids.
The
switching
operation
was defined
in
this
general framework by
Barahona
and
Grotschel [1986]. We will
return
to
cycle
spaces
of
binary
matroids
in
Section 27.4.
The
switching
operation
has been discovered independently by several
other
authors.
In
particular,
by McRae
and
Davidson
[1972]
and
Pitowsky [1989, 1991]
in
the
context
of
the
correlation polytope
CO~,
by Deza [1973a]
in
the
context
of
the
cut
cone
CUT
n
,
by
Barahona
and
Mahjoub
[1986J
in
the
context
of
the
cut
polytope
of
an
arbitrary
graph.
26.3.2
Switching:
Cut
Polytope
versus
Cut
Cone
All
the
features
of
the
switching operation described above apply
to
the
special
case
of
the
cut
polytope
CUT~
and
of
the
cut
cone
CUT
n
,
as
the
set
of
cuts
is closed
under
taking
the
symmetric difference; Corollary 26.3.5
and
Proposi-
tion
26.3.6
can
be reformulated as follows
1
.
'Given
v E
:IRE"
and
a
cut
vector 6(A)
in
K",
the
vector vc(A) is defined as
in
(26.3.1)
by
v:}A)
=
-Vij
if
fi(A)i;
= 1
and
v~1A)
Vi;
if
6(Alij
O.
In
other
words,
vc(A)
stands
for
v
6K
,,(A),