Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

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

IP.com Disclosure Number: IPCOM000099363D
Original Publication Date: 1990-Jan-01
Included in the Prior Art Database: 2005-Mar-14
Document File: 3 page(s) / 119K

Publishing Venue

IBM

Related People

Stone, HS: AUTHOR

Abstract

This branching rule described in this article generalizes a branch-and- bound process of (*) that is useful for seeking solutions to Symmetric Traveling Salesman Problems. The Bellmore-Malone approach 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.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 50% of the total text.

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

       This branching rule described in this article generalizes
a branch-and- bound process of (*) that is useful for seeking
solutions to Symmetric Traveling Salesman Problems.  The
Bellmore-Malone approach 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.

      The new rule takes advantage of the fact that edges of a
2-matching that is also a tour must all be bidirectional, because a
2-matching tour has 2N edges for an N-city problem, and therefore the
minimal tour occurs twice in the 2-matching; once in each direction.
If a 2-matching contains some arc (i,j) that is not bidirectional,
and that arc is broken or included in one of the subproblems
generated by branch and bound, then the branch-and-bound process
should also, respectively, break or include arc (j,i) to the extent
that this is possible in the context of the 2-matching algorithm in
use.  There are also other constraints that can be added for which
the Bellmore-Malone approach does have equivalent constraints. THE
BRANCHING RULE

      The branching rule must break cycles within 2-matchings in a
way that:

      1. the cycles are broken to create k subproblems whose
solutions are disjoint,

      2. if the optimal tour is among the solutions of the original
problem, then it is among the solutions of one of the subproblems,

      3. each subproblem is maximally constrained under the
conditions that generate the subproblem partitioning.

      Bellmore-Malone propose that a cycle (i1, i2, ..., ik, i1) be
broken into k subproblems as follows:
    1. Break (i1, i2) in the first subproblem.
    2. Force (i1, i2) and break (i2, i3) in the next subproblem.

      3. Force (i1, i2) and (i2, i3), and break (i3, i4) in the next
subproblem.

      4. Each subsequent subproblem forces the arc broken by the last
subproblem, and breaks the next arc on the cycle.
    5. The last subproblem forces arcs.
    6. Force (i1, i2) through (ik-1, ik) and breaks arc (ik, i1).

      It is well known that this partitioning of the problem space
satisfies the required properties stated above.

      For a 2-matching, we use the same rules above given by Bellmore
and Malone but add as well the following rules:

      1. If an arc (i,j) is broken, then break the reverse arc (j,i).

      This arc need not be in the two matching.  It can be guaranteed
    to be broken by setting its cost to infinity.
    2. If an arc (i,j) is forced (and must therefore be part of the
present solution), then force the arc (j,i), if that arc is part of
the present solution.  If (j,i) is not part of the present solution,
then the 2-matching algorithm should m...