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.
| Identifer | oai:union.ndltd.org:uottawa.ca/oai:ruor.uottawa.ca:10393/9349 |
| Date | January 2001 |
| Creators | Cockburn, Sally. |
| Contributors | Boyd, Sylvia, |
| Publisher | University of Ottawa (Canada) |
| Source Sets | Université d’Ottawa |
| Detected Language | English |
| Type | Thesis |
| Format | 84 p. |
Page generated in 0.0101 seconds