Article ID: | iaor2006618 |
Country: | Portugal |
Volume: | 25 |
Issue: | 1 |
Start Page Number: | 63 |
End Page Number: | 83 |
Publication Date: | Jun 2005 |
Journal: | Investigao Operacional |
Authors: | Soares Joo, Ramires Ana |
In this article we describe how to compute a lower bound for the asymmetric traveling salesman problem that dominates the bound that comes from the assignment relaxation, through the solving of a sequence of assignment problems. The algorithm that we propose is a first-order method based on the exponential penalty function. Directions of movement are derived from a disjunctive relaxation that we proposed as being one of two possible classes, one based on cycles, the other based on cliques.