Deza M.M., Laurent M. Geometry of Cuts and Metrics

406

Chapter

26.

Operations on Valid Inequalities

and

Facets

Corollary

26.3.7.

Given v E JltE

n

,

Vo

E

JIt

and a cut vector

8(A),

the following

assertions are equivalent.

(i) The inequality v

T

x

:S

Vo is valid or facet inducing for

CUT~,

respectively.

(ii) The inequality

(v

6

(A))T x

:S

vo-v

T

8(A)

is valid or facet inducing for

CUT~,

respectively. I

Corollary

26.3.8.

Suppose that

CUT

n =

{x

E JltE

n

I

v[

x

:S

0 for i =

1,

...

,

m}

.

Then,

CUT~

=

{x

E JltE

n

I

(v~(A))T

x:S

-v[8(A)

for i = 1,

...

,m,

and A

~

V

n

}.

I

There

is clearly

an

analogue

of

switching for the correlation polytope

COR~,

as

this

polytope is in linear bijection

with

the

cut

polytope

CUT~+l.

We

indicate

explicitly in

the

how switching applies

to

the

correlation polytope.

Remark

26.3.9.

Analogue

of

switching

for

the

correlation

polytope.

Given a subset A

of

V

n

,

consider

the

mapping:

(26.3.10)

This

mapping

acts as follows:

o

~-1

0

T6(A)

0

~

0

CORn

-----t

CUT

n

+

1

-----t

CUT

n

+

1

-----t

CORn.

Here,

8(A)

is considered as a

cut

vector in K

n

+

1

,

r6(A)

is

the

corresponding

switching

mapping

of

the

space

JltE

n

+l

,

and

~

is

the covariance mapping. There-

fore,

the

mapping

t?6(A)

preserves the polytope

COR~,

i.e.,

i?6(A)(COR~)

=

COR~.

One can easily verify

that

is defined by

for i

E

Vn

and

I

{1-

Pii

p

..

=

"

Pii

{

I -

Pii

-

Pjj

+

Pij

I

Pii

-

Pij

P--

=

'J

Pjj

-

Pij

ifi

E A,

if

i

It

A,

ifi,j

E A,

if i

It

A, j E A,

if i E A, j

It

A,

ifi,j

It

A

26.3

The

Switching

Operation

407

for i

=1=

j E V

n

.

Note, therefore,

that

switching

has

a much simpler form when

applied

in

the

context of

the

cut

polyhedra

rather

than

in

the

context

of

the

correlation

polyhedra. I

Both

the

switching

and

the

permutation

operations

map

faces

of

CUT~

to

faces of

CUT~;

in

more technical

terms,

they

are

both

symmetries

of

CUT~,

i.e.,

orthogonal

linear

transformations

of

~En

that

map

CUT~

to itself.

In

Section 26.3.3,

we

will see

that

the

group

of

symmetries

of

CUT~

(n

=1=

4)

is

generated

by these two operations.

Clearly, if

the

complete description of

CUT

n

we

start

with

in

Corollary 26.3.8

is

nonredundant,

then

all of

the

inequalities describing

CUT~

are facet defining.

But

many

of these inequalities may

appear

repeatedly. However, as observed by

Grotschel [1994]'

there

is a (theoretically) easy way to

compute

the

number

of

facets

of

CUT~

from

the

number

of facets of

CUT

n

and

vice versa, as

indicated

in

Lemma

26.3.11 below.

Let

us call, for a given face F of

CUT~,

the

set of all

the

faces

of

CUT~

that

can

be

obtained

from F by applying

the

permutation

and

switching

operations

the

orbit !1D(F) of

F.

We similarly define

the

orbit

!1(F)

of

a face F

of

CUTn

where,

instead

of general switching,

we

only allow switching by

roots

of

F.

Recall

that

R(F)

denotes

the

set of

roots

of

the

face

F.

Lemma

26.3.11.

Let v

T

x

:s;

0

be

a valid inequality for

CUT

n

,

it

defines a face

F

of

CUT

n and a face

FD

of

CUT~.

Then,

Proof.

Let

us define a

I!1D(FD)1

x

12

Vn

-

1

matrix

B = (bHs) by

setting

bHs = 1

if

the

cut

vector 8(8) is a

root

of

the

face H of !1D(FD)

and

bHs = 0 else.

Then,

counting

row-

and

columnwise,

we

obtain

I

Hence,

I!1D(FD)1

can

be deduced once

we

know

1!1(F)1

and

the

number

of

roots

of FD.

Of

course,

it

is

neither

trivial

to

compute

the

cardinality of

an

orbit

nor

to

determine

the

number

of

roots

of a face.

We

shall as often as possible

explicitly describe

the

roots

of

the

valid inequalities

treated

in

this

part.

(See, for

instance,

Section 30.4 where

we

present

the

parachute

inequality whose

number

of

roots

is

the

Fibonacci sequence.) We now

state

an

upper

bound

on

the

number

of

roots, given

in

Deza

and

Deza [1994a].

408

Chapter

26.

Operations

on

Valid Inequalities

and

Facets

Proposition

26.3.12.

For any facet F

of

the cut polytope

CUT~

we

have

with equality

if

and only

if

F is defined

by

a triangle inequality.

Proof. Let F be a facet of

CUT~

induced

by,

say,

the

inequality v

T

x

:s

0:.

Ap-

plying switching,

we

can

assume

that

0:

=

O.

Suppose

Vij

is a nonzero

component

ofv.

If

S is any subset

of

Vn

\

{i,j}

then

v

T

6(SU{i})

+v

T

6(SU{j})

-v

T

8(S)

-v

T

6(SU{i,j})

= 2vij.

This

implies

that

at

most

three

ofthese

four

cut

vectors are

roots

of

F.

Therefore,

F

has

no more

than

~2n-l

=

3·

2

n

-

3

roots. Suppose now

that

F

has

exactly

3·2

n

-

3

roots.

We

show

that

F is defined by a triangle inequality.

It

is

not

difficult

to check

that

v

has

at

least

three

nonzero coordinates, say, Vij, vhk,

Vst

oF

O.

We

have:

(a) v

T

6(A

U {i}) + v

T

6(A

U {j}) - v

T

6(A) - v

T

6(A

U {i,j}) = 2Vij,

(b) v

T

8(BU{h})

+v

T

6(BU{k})

-v

T

6(B)

-v

T

6(BU{h,k})

=2Vhk,

(c)

vT6(CU{s})+vT6(CU{t})-vT6(C)-vT6(CU{s,t})=2vst

where A

~

Vn

\

{i,j},

B

~

Vn

\ {h, k},

and

C

~

Vn

\ {s, t}. Since F contains

3/4

of

the

total

number

of cuts, exactly three

terms

of

the

left

hand

side of each

of

the

equations

(a),(b),(c) are equal to

o.

We

can

suppose

that

Vij

and

Vhk

have

the

same

sign. Suppose first

that

l{i,j,h,k,s,t}1

= 6.

We

have

that

v

T

6({i}) =

o (for, if

not,

considering

the

equation

(a)

with

A =

(/)

and

the

equation

(b)

with

B = {i} yields v

T

6({i}) =

2Vij

and

-v

T

8({i})

=

2Vhk,

contradicting

the

fact

that

Vij

and

Vhk

have

the

same sign).

In

the

same way, v

T

6(

{i, s}) =

0,

v

T

6({i,t})

=

0,

v

T

6({i,s,t})

=

o.

Hence,

equation

(c)

with

C =

{i}

yields

Vst

=

0,

a contradiction. Similar

arguments

lead to a contradiction if I { i,

j,

h,

k, s,

t}

I =

5

or

4.

Hence, v has exactly three nonzero coordinates Vij,

Vik,

and

Vjk.

Using (a)

for A =

(/)

and

(b) (replacing h by i) for B = {j},

we

deduce

that

v

T

6( {j}) =

0,

i.e.,

Vij

=

-Vjk.

In

the

same way, v

T

8(

{k})

=

0,

i.e.,

Vik

=

-Vjk.

Therefore,

v

T

x

:s

0 is a multiple of

the

triangle inequality

Xjk

-

Xik

-

Xij

:S

O.

I

Counting

the

number

of elements in

the

orbit

fl(F) of a face F of

CUTn

can

be done

in

the

following way (see Deza, Grishukhin

and

Laurent

[1991]

and

Deza

and

Laurent

[1992c]). Let

flp(F)

:=

{a(F)

I a E

Sym(n)}

denote

the

set

of faces

that

are

permutation

equivalent

to

F

and

set

Aut(F)

:=

{a

E

Sym(n)

I

a(F)

= F};

the

members

of

Aut(F)

are called

the

automorphisms of

F.

Then,

it is easy

to

check

that

n!

Iflp(F)1 = IAut(F)1

26.3.3

The

Symmetry

Group

of

the

Cut

Polytope

409

Let

k

denote

the

number

of

distinct

switchings (by roots) of F

that

are

pair-

wise

not

permutation

equivalent

and

let

Fo

:=

F,

F

I

,

...

,F

k

-

l

denote

these

k

switchings.

Then,

n!

IQ(F)I = L

IAut(F)I'

O$i$k-l

'

Hence,

determining

the

number

of elements

in

the

orbit

Q(F)

of

F

amounts

to

counting

the

number

of

automorphisms

of

any

switching

of

F.

This

has

been

done

in

Deza

and

Laurent

[1992c] for several classes

of

facets

and,

in

particular,

for all

the

facets

of

the

cut

cone

CUT

n for n

:::;

7.

As

an

application, one

can

count

the

exact

number

of

facets of

CUTn

and

CUT~

for n

:::;

7;

see Section 30.6.

Although

we have

introduced

orbits

here only as a

tool

for

enumerating

faces

we would like

to

remark

that

this

concept deserves

more

attention.

For instance,

if we prove

that

some inequality defines a facet we

automatically

obtain

that

all

the

faces

in

its

orbit

are,

in

fact, facets.

The

corresponding defining inequalities

are

obtained

from

the

original one by switching

and

permuting.

Proving

that

an

inequality

defines a facet is (often) laborious work

that

heavily uses

apparent

structures

and

symmetries

of a given inequality

and

it

is of

great

importance

to

choose,

among

all possible inequalities defining

the

facets

of

the

orbit,

one

that

has

an

"exploitable"

shape

or some "nice

and

easily

understandable

form".

Of

course,

this

is a

matter

of

taste,

but

nevertheless, as

we

have seen

in

our

own

work

it

is helpful

to

find a convenient representative inequality of

an

orbit,

not

only for

proof

technical

purposes

but

also for

further

generalizations

and

the

investigation

of

other

issues.

26.3.3

The

Symmetry

Group

of

the

Cut

Polytope

We describe here

the

symmetry

group

of

the

cut

polytope

CUT~.

The

results

are

taken

from Deza,

Grishukhin

and

Laurent

[1991].

A

mapping

f :

JE.E

n

---t

JE.E

n

is called a

symmetry

of

CUT~

if

it

is

an

isometry

satisfying:

f(CUT~)

=

CUT~;

an

isometry of

JE.E

n

being

a linear

mapping

preserving

the

Euclidean

distance.

Let

Is(CUT~)

denote

the

set

of

symmetries

of

CUT~.

Let

denote

the

group

generated

by all

permutation

and

switching

mappings.

The

commutation

rules

in

G

n

are:

(In

fact, G

n

is

nothing

but

the

quotient

of

the

symmetry

group

of

the

n-

dimensional

hypercube

by a

subgroup

of order 2.) Therefore,

IGnl

= 2

n

-

1

n!.

As we have seen earlier,

G

n

~

Is(CUT~).

Let

H(n)

denote

the

graph

whose nodes are

the

cut

vectors 8(A) for A

~

V

n

,

with

two

cut

vectors 8(A), 8(B)

being

adjacent

if

(II

8(A)

-8(B)

112?

=

n-1,

i.e.,

410

Chapter

26. Operations on Valid Inequalities

and

Facets

if

(II

8(A6.B)

112)2

= n

-lor,

equivalently, if IA6.BI = 1, n

-1.

Obviously, every

symmetry

of

CUT~

induces

an

automorphism

of

the

graph

H(n).

Therefore,

Is(CUT~)

<;

Aut(H(n)).

The

graph

H(n)

is

known as

the

folded

n-cube

graph.

Its

automorphism

group

is

G

n

for n >

4,

(Sym(4) x Sym(4))Sym(2) for n =

4,

and

Sym(4) for n = 3 (see

Brouwer,

Cohen

and

Neumaier

[1989]

or Deza, Grishukhin

and

Laurent [1991]).

We have

the

following result (only (ii) needs a proof):

Theorem

26.3.13.

(i) For n

i=

4,

Is(CUT~)

= G

n

,

with order 2

n

-

I

n!.

(ii) For n = 4,

Is(CUT~)

~

(Sym(4) x Sym(4))Sym(2), with order 2(4!)2.

Hence,

Is(CUT~)

~

Aut(H(n))

for

n

~

3. I

In

other

words, for n

i=

4,

switchings

and

permutations

are

the

only sym-

metries

of

CUT~.

For n = 4, there are are some additional symmetries. Note

that

H(

4)

is

the

complete

bipartite

graph

K

4

,4

with

bipartition

of

its node set

(X

I

,X

2

),

where

Xl

:=

{8(i)

Ii

=

1,2,3,4}

and

X

2

:=

{8(0),8({1,i})

Ii

=

2,3,4}.

Every

automorphism

of

H(4) acts in

the

following way:

Permute

the

el-

ements

within

Xl,

permute

the

elements within X

2

,

and

exchange elements from

Xl

to

X2.

In

fact, one

can

show

that

every such

operation

yields a

symmetry

of

CUT~.

In

the

same way, one may ask

what

are

the

symmetries

of

the

correlation

polytope

COR~.

In

fact,

the

only symmetries

of

COR~

are

permutations,

i.e.,

Is(COR~)

~

Sym(n)

for all

n.

Indeed, even

though

the

mapping

i?8(A)(=

er8(A)e-l)

(the analogue of switching)

preserves

the

polytope

COR~,

it is not a

symmetry

of

it

because

the

mapping

i?o(A) is

not

an

isometry.

It

is

shown in Laurent

[1996c]

that

the

semimetric

polytope

MET~

has

the

same group

of

symmetries as

CUT~.

The

description

of

the

symmetry

groups

of

other

cut

polyhedra (such as

the

equicut polytope,

the

multicut

polytope)

can

be

found in Deza, Grishukhin

and

Laurent [1991].

26.4

The

Collapsing

Operation

We describe

in

this

section

the

collapsing operation, which

permits

to

construct

valid inequalities for CUT;;' (or CUTm) from valid inequalities for

CUT~

(or

CUTn),

where m <

n.

The

collapsing

operation

was introduced

in

De Simone,

Deza

and

Laurent

[1994]

and

Deza

and

Laurent [1992b].

Let

'if

=

(Ir,

... ,Ip) be a

partition

of

Vn

=

{l,

...

,n}

into p

parts,

i.e.,

Ir,

...

,Ip

are nonempty disjoint subsets such

that

Ir

U

..

. UIp = V

n

•

For v E ffi.En,

we

define its 'if-collapse

v"

E

ffi.Ep

by

(V,,)hk:=

L

Vij

for

hk

E Ep.

iEh,jEh

26.4

The

Collapsing

Operation

411

When

the

partition

7r consists only

of

singletons except one

pair

{i,

j}

(where

i I-

j),

i.e.,

when

7r = {{i,j},

{k}

for 1

:S

k

:S

n,

i I- k I- j I- i},

then

v" E

jRE

n

-

1

and

we say

that

v" is

obtained

from v by collapsing the two nodes

i,j

into a single

node.

If

G is

an

edge weighted

graph

on

Vn

with

edgeweight vector v,

then

the

7r-collapse

of

G is

the

graph

G"

on

Vp

whose edgeweight vector is v".

In

other

words, we

obtain

G"

from G by

contracting

all nodes from a

common

partition

class

into

a single

node

and

adding

the

edgeweights correspondingly.

If

S is a

subset

of

Vp

=

{I,

2,

...

,p},

define

the

subset

S"

:=

UhES

h

of

V

n

.

The

relation

v;

8(S)

= v

T

8(S")

for S

<:;;

{I,

...

,p}

can

be

easily checked, implying

immediately

the

following

lemma.

Lemma

26.4.1.

Given v E REn,

Vo

E R and a partition 7r = (h, ... , Ip)

of

Vn

into p parts, the following statements hold.

(i)

If

the inequality v

T

x

:S

Vo

is valid for

CUT~,

then the inequality

v;

x

:S

Vo

is valid

for

CUT~

.

(ii)

The roots

of

the inequality

v;x

:S

Vo

are the cut vectors

8(S)

such that

S

<:;;

{I,

...

,p}

and

8(S")

is a root

of

the inequality v

T

x

:S

Vo·

I

We

present

in

the

when

the

collapsing

and

the

switching

operations

commute.

Lemma

26.4.2.

Let

7r = (h, ...

,Ip)

be

a partition

of

{I,

...

,n},

S

be

a subset

of

V

p

, and v E

REn.

Then,

I

Observe

that

the

collapsing

operation

preserves validity,

but

it

may

not

al-

ways preserve facets. Also,

it

may

be

that

the

collapse

of

a nonfacet

inducing

valid inequality is facet inducing. For example, for n

::::

3,

the

(triangle) inequal-

ity

X23

-

X12

- Xl3

:S

0 is facet inducing for

CUT

n

but

the

inequality -

2X12

:S

0,

obtained

by collapsing

the

two nodes 2,3

into

a single

node

2, is valid

but

not

facet inducing. For n

::::

5,

the

inequality

(X23

-

X12

-

X13)

+

(X45

-

X14

-

X15)

:S

0

is valid

but

not

facet inducing, while

the

inequality

X23

-

X12

-

X13

:S

0,

obtained

by

collapsing

the

two nodes 1,5 into a single

node

1, is facet inducing for

CUT

n

.

Nevertheless, collapsing

may

be

a useful tool for

the

construction

of

facets;

Theorems

26.4.3

and

26.4.4

below

state

results

of

the

form: "Take a valid in-

equality,

assume

that

some collapsings

of

it

are

facet inducing

and

... ,

then

the

inequality

is facet inducing".

The

is shown in De Simone, Deza

and

Laurent

[1994].

412

Chapter

26.

Operations on Valid Inequalities

and

Facets

Theorem

26.4.3.

Let v E

Jm.E

n

and

iI,

i2,

ia

be

distinct nodes in

{I,

2,

...

1

n}.

Assume

that the Jollowing conditions hold.

(i) The inequality v

T

x

::;

0 is valid Jor

CUT

n

•

(ii) v

T

6(

{id)

=

O.

(iii) The two inequalities obtained from v

T

x

::;

0

by

collapsing the nodes {iI, i2},

and the nodes {iI, i3}, respectively,

are

facet inducing for

CUT

n-l.

(iv)

For

some distinct

1',8

{I,

...

,

n}

\

{ill

i2, i3}, V

rs

f

O.

Then, the inequality v

T

x

::;

0 is facet inducing for

CUT

n

.

Proof. For ease

of

notation,

we

may assume

that

il

=

1,

i2

=

2,

i3

=

3.

Denote

by v

l

,2

and

vl,a

the

vector obtained from v by collapsing

the

nodes

{I,

2}

and

the

nodes

{I,

3}, respectively. Take a valid inequality

aTx

::;

0 for CUTn such

that

{x

E CUTn I v

T

x

O}

~

{x

E CUTn I

aT

x =

OJ.

In

order to prove

that

v

T

x

::;

0 is facet defining,

we

show

that

v =

aa

for some

scalar

a >

O.

Denote analogously by a

l

,2

and

a

I

,3

the vector obtained from a by

collapsing

the

nodes {1,2}

and

{I,

3}, respectively.

It

is easy to see

that

for i 2,3. Since

(VI,i)T

x

::;

0 is facet inducing by assumption (iii), there exists

a scalar

ai

> 0 such

that

Vi,;

=

a;al,i

for i = 2,3.

We

deduce

that

al

a2

a

from assumption (iv). Hence,

we

already have

that

V

rs

=

aa

rs

for 3

::;

l'

< S

::;

n,

or

l'

= 2

and

4

::;

s

::;

n and, also,

(a)

VIi

+ V2i =

a(ali

+ a2;) for i

:::::

3,

(b)

VIi

+ V3i =

a(ali

+ a3;) for i =

2,i

:::::

4.

Hence,

VIi

=

ali

for i

:::::

4.

It

remains

to

check

that

Vl2

aal2,

Vl3

aal3

and

V23 = aa23 in order

to

deduce

that

V =

aa.

By assumption (ii),

we

have

v

T

6({I})

= 0, implying

that

V12

+ V13 = -

2::

VIi

49::;n

2::

aali

a(a12 + aI3)'

4::;i::;n

This relation, together

with

(a), (b) for i = 3, yields

that

V23 aa23 and, then,

Vl3

=

aal3,

Vl2

= aa12· I

The

following result was proved in Deza, Grotschel and Laurent

[1992]

in

the

more general context

of

multicuts.

Theorem

26.4.4.

Let V E

Jm.E

n

,

Vo

E

lR,

andi),

i21 i

3

,

i4

be

distinct elements in

{I,

...

,

n}.

Assume that the Jollowing conditions hold.

(i)

The inequality v

T

x

::;

Vo

is

valid for

CUT~.

26.5

The

Lifting

Operation

413

(ii)

Vo

-:f.

0, or there exist distinct

r,s

E

{l,

...

,n}

\

{il,i2,

i4} such that

V

rs

-:f.

O.

(iii) The three inequalities obtained from the inequality v

T

x

:::;

'110

by

collapsing

the nodes

{il,id,

the nodes

{il,i3},

and the nodes

{il,i4},

respectively,

are

facet inducing for

CUT~_l'

Then, the inequality v

T

x

:::;

Vo

is facet inducing for

CUT~

.

Proof.

Let

us assume

that

il

1,

i2

2,

i3

3,

i4

4.

Let

aT

x

:::;

(10 be a

valid inequality for

CUT~

such

that

{x

E

CUT~

I v

T

x

vol

r;;;;

{x

E

CUT~

I

aT

x =

ao}.

We show

the

existence

of

a scalar a > 0 such

that

v =

aa,

Vo

= aao.

For

i =

2,3,4,

denote

byvl,i

(resp. al,i)

the

vector

obtained

from v (resp. from a)

by collapsing

the

nodes

{I,

i}. Clearly, every

root

of

the

inequality (vl,i)T x

:::;

Va

is a

root

of

the

inequality

(al,i)T

x:::; (LO. Hence,

there

exists a scalar

ai

> 0

such

that

vl,i = aial,;

and

'110

aiaO,

for i

2,3,4.

By

assumption

(ii),

we

deduce

that

001

002 003

a. We already have

that

V

rs

=

('tlL

rs

for 3

:::;

l'

< s

:::;

n,

or

l'

= 2

and

4

:::;

s

:::;

n,

or

{r,

s}

{2, 3}. Also, Vli+V2i = a(ali+a2i) for i

:::::

3, from

which

we

deduce

that

Vli

aati

for 3

:::;

i

:::;

n. Finally,

Vii

+

V4i

=

a(ali

+ a4i)

for i

2,3,5,

...

,n,

implying

that

'1112

= aal2. Therefore, v =

aa

holds

and,

thus,

the

inequality

:::;

'110

is facet inducing. I

26.5

The

Lifting

Operation

The

collapsing

operation,

which is described

in

the

preceding section,

permits

to

construct

certain

valid inequalities

of

CUT

n

_

1

from a given valid inequality

of

CUT

n

.

Conversely, by lifting,

we

mean

any

general procedure for

constructing

a valid inequality

of

CUTn+l

(preferably, facet inducing) from a given valid

inequality

(or facet) for

CUT

n'

The

simplest case

of

lifting is

that

of

O-lifting. Namely, for v E , define

its

O-lifting

Vi

E ]]REn+l by

v:j

=

Vij

v:,n+l = 0

for

ij

E

En,

for 1

:::;

i

:::;

n.

In

the

same

way,

we

say

that

the

inequality

(Vi?

x

:::;

Vo

is

obtained

by O-lifting

the

inequality v

T

x

:::;

Vo.

It

is

immediate

to

see

that

O-lifting preserves vd,liditYi

a nice feature

of

O-lifting

is

that

it also preserves facets.

Theorem

26.5.1.

Given

Vo

E

lR,

v E

]]REn

and its O-lifting

'11'

E

]]REn+l,

the

following assertions

are

equivalent.

(i) The inequality v

T

x:::;

Vo

is facet inducing

for

CUT~.

(ii) The inequality

(v'?

x

:::;

'110

is facet inducing for

CUT~+

1 •

414

Chapter

26.

Operations

on

Valid Inequalities

and

Facets

The

proof

of

Theorem

26.5.1 is based on

the

following

Lemma

26.5.2.

Both

results

were given

in

Deza [1973a] (see also Deza

and

Laurent

[1992aJ

for

the

full

proofs). Given a subset

F

of

En,

set F

:=

En

\

F.

If

X E JREn, let

denote

the

projection

of

x

on

the

subspace

liF

indexed

by

F

and,

if

X is a subset

of

liEn, set

XF:=

{XF I x E

X},

XF

{x

E X I

XF

= o}.

Lemma

26.5.2.

Let

v

T

x

~

0

be

a valid inequality for

CUT

n and let

R(

v)

denote

its

set

of

roots.

Let

F

be

a subset

of

(i)

If

rank(R(v)F)

= IFI and rank(R(v)F) iFl 1, then the inequality

v

T

x

~

0 is facet inducing.

(ii)

If

the inequality v

T

x

~

0 is facet inducing and

'll'F

=f

0 (resp. v

F

= 0), then

rank(R(v)F) =

IFI

(resp. rank(R(v)F)

IFI

1).

Proof. (i)

By

the

assumption,

we

can

find a set A

~

R(v)

of

IFI vectors whose

projections on

F are linearly independent

and

a set B

~

R(v)

of

iFl-llinearly

independent

vectors whose projections on F are zero.

It

is

immediate

to

see

that

the

set A U B is linearly independent.

This

implies

that

v

T

x

~

0 is facet

inducing.

(ii) Since

v

T

x

~

0 is facet inducing, we

can

find a set A

R(

v)

of

G)

-1

linearly

independent

roots. Let M denote

the

«;)

- 1) x

G)

matrix

whose rows

are

the

vectors

of

A. Hence, all

the

columns

of

M

but

one

are

linearlyindependent.

We

distinguish two cases:

(a) either, all

the

columns

of

M

that

are indexed

by

F are linearly independent

and,

then,

rank(AF) = IFI,

(b) or, rank(AF)

=

IFI-l,

implying

that

rank(R(v)F) IFI

1.

Suppose first

that

we are

in

the

case (b).

Let

Tl

~

A

be

a subset

of

IFI

- 1

vectors whose projections on

F

are

linearly independent, set

T2

:=

AI"

and

Ta

:=

A \

(Tl

U T2)' Hence,

IT2

U

T:;I

=

iFl.

For x E

T3,

its projection

XF

on

F

can

be

written

as a linear combination

of

the

projections on F

of

the

vectors in

T

I

,

say

Set

XF

= L

A~al'"

/lET,

x'

:=x-

L

A~a

aET,

and

T~

{x' I x E T3}'

It

is easy

to

check

that

the

set

T2

U

T~

is linearly

independent. Note

that,

for any x E

T2

U

T~,

Xl"

= 0

and

v

T

x

0;

this

implies

that

v

F

=

O.

Suppose now

that

we

are

in

the

case (a).

Then,

rank(R(v)F)

iFl

- 1

and,

by

the

above reasoning,

Vl"

= 0, which implies

that

'll'F

=f

o.

I

26.5

The

Lifting

Operation

415

Proof

of

Theorem 26.5.1.

We

can

assume,

without

loss

of

generality,

that

Vo

=

0;

else, switch

the

inequality by a

root

and

apply

the

result

for

the

switched in-

equality.

Suppose first

that

the

inequality (v')Tx

:::;

0

is

facet inducing for

CUTn+l.

Con-

sider

the

set

F

:=

{(i, n +

1)

I 1:::; i

:::;

n}

and

let F

:=

En

denote

its com-

plement

in

the

set

En+l.

By

construction,

v~

=

o.

Hence,

we

deduce from

Lemma

26.5.2 (ii)

that

rank(R(v')F)

=

WI-1

=

G)

-1.

Therefore,

the

inequal-

ity

v

T

x

:::;

0

is

facet inducing for

CUT

n

.

Suppose now

that

the

inequality vTx

:::;

0

is

facet inducing for

CUT

n

• Since

v

=f:.

0,

we

can

suppose

without

loss

of

generality

that

v

F

=f:.

0,

where F

:=

{12, 13,

...

,

In}

and

F

:=

En

\ F.

By

Lemma

26.5.2 (ii), rank(R(v)F) = IFI.

Therefore,

we

can

find n - 1

roots

6(Tk)

(1

:::;

k

:::;

n -

1)

of

v

T

x

:::;

0 whose pro-

jections

on

F are linearly independent. Since v

T

x

:::;

0

is

facet inducing,

we

can

also find

G)

- 1 linearly

independent

roots

6(Sj)

(1

:::;

j

:::;

G)

-

1)

of

v

T

x

:::;

o.

Without

loss

of

generality,

we

can

suppose

that

the

element 1 does

not

belong

to

any

of

the

sets

Tk

and

Sj. So,

we

have a set

c:=

{6(Sj)

11:::; j:::;

(;)

-1

}U{6(TkU{n+1})

11:::;

k:::;

n-1}U{6({n+1})}

of

(n~l)

- 1

cut

vectors (in

Kn+l),

which are

roots

of

the

inequality (v')T x

:::;

o.

We show

that

the

set

C

is

linearly independent. For this,

we

verify

that

the

correlation vectors (pointed

at

position

1)

associated

with

the

cut

vectors

in

C are linearly independent. Let us consider

the

square

matrix

M

of

order

(n~l)

_

1,

whose rows are: first,

the

G)

- 1 vectors

7r(Sj);

then,

the

n - 1

vectors

7r(Tk

U

{n

+ I})

and,

finally,

the

vector

7r(

{n +

I}).

The

columns

of

M

are

indexed by

the

set

I U J U

K,

where I

:=

{(i,j)

I 2

:::;

i

:::;

j

:::;

n},

J:=

{(i,n

+

1)

12:::; i

:::;

n},

and

K:=

{(n +

1,n

+

I)}.

The

matrix

Mis

ofthe

form:

I J K

M~

(~

~

'n

(where e

denotes

the

all-ones vector).

The

matrix

X has full row

rank,

since

the

vectors 7r(Sj) are linearly independent.

The

matrix

Y has full

rank,

since its rows

are

the

vectors

7r(TkU{

n+

l})J

= 6(Tk)F, which are linearly independent. Hence,

the

matrix

M

has

full row

rank,

which implies

that

the

inequality (v')T x

:::;

0

is

facet inducing. I

Lifting is a very general methodology for

constructing

facets of polyhedra,

which

can

be described as follows. Suppose

we

are given a vector v E ffiEn for

which

the

inequality v

T

x

:::;

0

is

valid for

CUT

n

.

Then,

lifting

the

inequality

v

T

x

:::;

0 means finding a vector

v'

E lR.En+l

(obtained

by adding n new coordi-

nates

to

v,

after

possibly altering some

of

its coordinates) such

that

the

inequality

(v')T x:::; 0 is valid for

CUTn+l.

Of

course, a desirable objective

is

to

produce

in

Deza M.M., Laurent M. Geometry of Cuts and Metrics

Подождите немного. Документ загружается.