Loading...
Please wait, while we are loading the content...
Similar Documents
The Symmetric Traveling Salesman Polytope Revisited (1998)
| Content Provider | CiteSeerX |
|---|---|
| Author | Naddef, Denis Pochet, Yves |
| Abstract | We propose in this paper a tour of the symmetric traveling salesman polytope, focusing on inequalities that can be defined on sets. The most known inequalities are all of this type. Many papers have appeared which give more and more complex valid inequalities for this polytope, but no intuitive idea on why these inequalities are valid has ever been given. In order to help in understanding these inequalities, we develop an intuition into the validity of such inequalities by giving a unifying way of defining them through a sequential lifting procedure. This procedure is based on lifting the slack variables associated with subtour elimination inequalities defined on sets of nodes (called teeth). We apply this procedure to some known classes of valid inequalities for the TSP, respectively Comb, Brushes, Star and Path, Bipartition inequalities, where the lifting coefficients are sequence independent. We also give an example where a facet defining inequality is derived from the... |
| File Format | |
| Language | English |
| Publisher Date | 1998-01-01 |
| Publisher Institution | Math. Oper. Res |
| Access Restriction | Open |
| Subject Keyword | Symmetric Traveling Salesman Polytope Intuitive Idea Valid Inequality Lifting Coefficient Complex Valid Inequality Unifying Way Salesman Polytope Sequential Lifting Procedure Slack Variable Known Inequality Many Paper Bipartition Inequality Subtour Elimination Inequality |
| Content Type | Text |
| Resource Type | Technical Report |
