Transcript The Domino Inequalities: New Facets for the Symmetric Traveling

The Domino Inequalities: New
Facets for the Symmetric
Traveling Salesman Polytope
Denis Naddef
Emmanuel Wild
Some STSP facets
Consider a set of Handles H1 … Hh
Integers … h
Consider a set of Teeth T1 … Tt
Numbers … t
Plain Closed Set Form Facets
 x((H )) x((T))r(H,T)
h
t
i
i1
i
i
i1
i
EXAMPLES
Comb inequalities
Clique tree inequalities
Path inequalities
COMB INEQUALITIES
x((H )) x((Ti))3t1
t
i1
H
T1
T2
Ti
Tt-1
Tt
Closed Set Form with
negative Correcting Term
 x((H )) x((T)) c x r(H,T)
h
t
i
i1
i
i
i1
i
e e
eE*
Correcting term?
The correcting term transforms some valid
closed set form inequalities into facet
inducing inequalities. Some edges may not
belong to any tight tour of the valid inequality,
the correcting term corrects this
It may not be uniquely detremined since it is
in general the result of a sequential
procedure
Example: the ladder inequalities
Ladder Inequalities
Two handles H1 and H2 , H1 H2 = 
T1, T2 , …Tt, t=2k, k odd,
Ti Tj = i≠j
T1 H1 ≠  T1 H2 = 
T2 H1 =  T2 H2 ≠ 
Ti H1 ≠ , Ti H2 ≠  , i≥3
1 = 2 =1,
i =1 if Ti\(H1 H2)≠  i =2 else
 x((H )) x((T))2x(E*)t22
2
t
i
i1
t
i
i
i
i1
i1
H1
1
T1
..........
2
1
E*
H2
T3
..........
Tt
1
T2
Closed Set Form with positive
Correcting Term
This correcting term aims at making
valid a closed set form inequality
which would not be valid without it
The Domino Configurations
A handle H
A nested set of teeth T1 … Tt, t odd
Ti = Ai Bi≠V, Ai Bi =  for every non minimal
tooth Ti
A tooth is odd if it is minimal or strictly
contains an even number of teeth
There are at least three odd maximal teeth
Each Ai
Bi contains at least two odd
teeth
The Domino Inequality
Let (Ai : Bi)={e
a Ai  b Bi} and
E* (Ai :Bi )\(H)
i
x((H)) x((Ti))2x(E*)3t1
t
i1
H
a0
Ai
ai
bi
Bi
bi
ai
a0
Domino Parity Inequality
Adam Letchford has defined a class of
inequalities known as the Domino Parity
Inequalities. He describes a polynomial time
algorithm to separate them provided the
support graph of the fractional solution to be
separated is planar. We conjecture that the
domino inequalities contain all the facet
inducing such inequalities.
Validity
LHS1/2(x((Ti))x((Ai))x((Bi))3t
t
t
t
i1
i1
i1
Since t is odd, and LHS even one
can raise to 3t+1. Exactly the same
proof as for the comb inequalities
Not valid without the correcting
term: 20 instead of 22
H
Definitions
Ti = Ai Bi, we call it a domino, Ai and Bi are its
half-dominoes
A fundamental even tooth is such that one
half domino contains 2 minimal teeth and the
other 3.
A fundamental odd tooth is such that each
half domino contains either 2 or 3 minimal
teeth, called (2,2)-teeth and (3,3)-teeth
Building a domino inequality
from the simple 3-tooth comb:
Add two minimal teeth inside a same half
domino Ai or Bi or outside all maximal teeth
H
Add an even fundamental tooth inside a half
domino Ai or Bi
or outside any maximal tooth
H
Replace a minimal tooth by a (2,2) or
(3,3)-tooth (odd)
1-node lifting
H
0-NODE LIFTING
Consists in replacing any of the
previously shown nodes by a
clique.
Theorem
Let D* be a domino configuration obtained
by one of the previous operations from a
facet inducing domino configuration D, then
it is also facet inducing. That is, all the
previous operations preserve the facet
inducing property.
Theorem
The domino inequality are facet inducing for the
Symmetric Traveling Salesman Polytope.
Proof: The simple 3-tooth comb is facet
inducing for STSP(6), the rest follows from
the previous theorem.