10. The Domino Inequalities for the Symmetric Traveling Salesman Problem
Denis Naddef · Society for Industrial and Applied Mathematics eBooks · 2004
This chapter is the first of a series of two papers that deal with the domino parity inequalities introduced by Adam Letchford [4] in an article in which he shows that such inequalities can be separated in polynomial time, provided that the support graph of the fractional point to be separated is planar. These inequalities contain the combs as a special case. In this chapter we give necessary conditions for such inequalities to be facet-inducing. This will bring a big deal of structure to these inequalities. In a second [6] paper some facet-inducing results are given for the symmetric traveling salesman polytope.