Some Results on Node Lifting of TSP Inequalities |
| |
Authors: | Robert Carr |
| |
Institution: | (1) Department of Optimization and Uncertainty Estimation, Sandia National Labs, Mail Stop 1110, P.O. Box 5800, Albuquerque, NM, 87185 |
| |
Abstract: | We can define important classes of TSP inequalities by performing Naddef and Rinaldi's node lifting operation on simple TSP inequalities.We present some new insights into the node lifting operation, namely that 1-node lifting of cut based inequalities always has a geometric interpretation if a certain claw-free condition which is satisfied by most of these TSP inequalities is met. We go on to show that node lifting of the subtour elimination inequalities does not yield any new inequalities. |
| |
Keywords: | traveling salesman problem lifting node lifting polytope inequalities |
本文献已被 SpringerLink 等数据库收录! |
|