Boyd, Sylvia,Cockburn, Sally.2009-03-232009-03-2320012001Source: Masters Abstracts International, Volume: 40-05, page: 1296.9780612660298http://hdl.handle.net/10393/9349http://dx.doi.org/10.20381/ruor-16270The 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.84 p.Engineering, System Science.Thesis