ISSN:
1436-4646
Keywords:
Traveling salesman
;
facet lifting
;
polyhedral combinatorics
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract Given any family ℱ of valid inequalities for the asymmetric traveling salesman polytopeP(G) defined on the complete digraphG, we show that all members of ℱ are facet defining if the primitive members of ℱ (usually a small subclass) are. Based on this result we then introduce a general procedure for identifying new classes of facet inducing inequalities forP(G) by lifting inequalities that are facet inducing forP(G′), whereG′ is some induced subgraph ofG. Unlike traditional lifting, where the lifted coefficients are calculated one by one and their value depends on the lifting sequence, our lifting procedure replaces nodes ofG′ with cliques ofG and uses closed form expressions for calculating the coefficients of the new arcs, which are sequence-independent. We also introduce a new class of facet inducing inequalities, the class of SD (source-destination) inequalities, which subsumes as special cases most known families of facet defining inequalities.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01581274
Permalink
