On DP-constraints for the Traveling Salesman polytope.

Abstract

The DP-constraints are a recently defined class of valid inequalities for the Symmetric Traveling Salesman Polytope (STSP) which includes the family of comb constraints. Moreover, there exists a polynomial-time exact separation algorithm for the DP-constraints for points whose support graph is planar. However, while the comb constraints are known to be facet-inducing, the same is not true in general of the DP-constraints. This thesis addresses the question of which DP-constraints are facet-inducing; some sufficient conditions are given for identifying DP-constraints which are not facet-inducing, and a family of facet-inducing DP-constraints, the twisted comb constraints, is described and shown to be distinct from other known families of facet-inducing inequalities. We also present a new formulation of the DP-constraints in terms of tripartitions of the node set, which allows easier recognition of equivalent DP-constraints.