| Article ID: | iaor1990660 |
| Country: | Netherlands |
| Volume: | 9 |
| Issue: | 1 |
| Start Page Number: | 1 |
| End Page Number: | 7 |
| Publication Date: | Jan 1990 |
| Journal: | Operations Research Letters |
| Authors: | Malik Kavindra, Fisher Marshall L. |
A dual ascent algorithm is described for the 1-tree relaxation of the symmetric traveling salesman problem. The ascent directions correspond to increasing (decreasing) the dual variables for the nodes of a set that is out of kilter high (low) for all 1-trees that are optimal at the current dual solution. This algorithm is shown to obtain near optimal bounds in about one-quarter of the time required by the subgradient method on a sample of well-known test cases.