Browse Prior Art Database

Branching Rule for Use in the 2-Matching Relaxation of the Traveling Salesman Problem

IP.com Disclosure Number: IPCOM000035190D
Original Publication Date: 1989-Jun-01
Included in the Prior Art Database: 2005-Jan-28

Publishing Venue

IBM

Related People

Authors:
Stone, HS [+details]

Abstract

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.