Browse Prior Art Database

Branching Rule for Use in the 2-Matching Relaxation of the Traveling Salesman Problem Disclosure Number: IPCOM000035190D
Original Publication Date: 1989-Jun-01
Included in the Prior Art Database: 2005-Jan-28

Publishing Venue


Related People

Stone, HS [+details]


This branching rule in this note generalizes a branch-and-bound process of [*] that is useful for seeking solutions to Symmetric Traveling Salesman Problems. The approach of [*] is useful when matchings are used as the relaxation of the Asymmetric Traveling Salesman Problem. The new branching rule covers a branch-and-bound algorithm that is useful when 2-matchings are used as the relaxation of the Symmetric Traveling Salesman Problem.