Browse Prior Art Database

Technique for Finding Initial Arcs in 2-Matchings

IP.com Disclosure Number: IPCOM000101295D
Original Publication Date: 1990-Jul-01
Included in the Prior Art Database: 2005-Mar-16
Document File: 4 page(s) / 169K

Publishing Venue

IBM

Related People

Stone, HS: AUTHOR

Abstract

The technique described here is an initialization procedure that quickly produces roughly 70% of the arcs required for a weighted 2-matching algorithm. A weighted 2-matching algorithm can be used as a core algorithm for branch-and-bound searches used to solve Symmetric Traveling Salesman Problems. The objective is to place as many arcs as possible during initialization, in order to reduce the total execution time of the 2-matching algorithm.

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

Technique for Finding Initial Arcs in 2-Matchings

       The technique described here is an initialization
procedure that quickly produces roughly 70% of the arcs required for
a weighted 2-matching algorithm.  A weighted 2-matching algorithm can
be used as a core algorithm for branch-and-bound searches used to
solve Symmetric Traveling Salesman Problems.  The objective is to
place as many arcs as possible during initialization, in order to
reduce the total execution time of the 2-matching algorithm.

      Recall that a 2-matching on a bipartite graph is a set of edges
such that each source node has exactly two outgoing edges and each
sink node has exactly two incoming edges. Stone (1) describes an
efficient algorithm for finding a maximum cardinality 2-matching of
minimum weight.

      The prior art is reflected by Carpaneto and Toth (2) in their
algorithm for a 1-matching.  The idea of their initialization is to
set the dual variables for source nodes and sink nodes, and while
doing this, place arcs that are easy to place.  The initialization of
source node duals ui and sink node duals vj with respect to a cost
matrix ci,j is the following:
ui : = 0
vj : = min ci,j
 i
This initialization uses the essential property:
slack(i,j) = c i,j - (vj - ui) / 0                (1)
which is satisfied for all arcs in the algorithm throughout the
algorithm.  The slack of an arc in a 1-matching is 0, and is 0 or
negative for an arc in a 2-matching.

      As each sink node is scanned for a minimum, an arc is added for
that sink node if source node f.i can be connected to sink node j
without violating the matching constraints. For 1-matchings, arc
(i,j) is added if source node i is not the source of another arc.
For 2-matchings, the generalization permits the arc to be added if
source node i is the source of less than 2 arcs before adding the new
arc. Arcs must be added only if Eq. (1) is satisfied with equality.

      Carpaneto and Toth (1987) enhanced this initialization by
following the sink node scan with a source node scan. They use the
following scheme:
ui : = - min ci,j - vj                            (2)
 j
Note that the quantity on the right side of Eq. (2) is negative, and
therefore ui is set to a quantity that does not exceed 0.  Also, note
that after updating  ui as indicated by Eq. (2), Eq. (1) is satisfied
with equality at the sink node j for which Eq. (2) is minimum.
Because of this equality an arc (i,j) can be added when ui is
updated, provided that both source i and sink j are not saturated.
For 1-matchings, source i cannot be the source of an arc and sink j
cannot be the sink of an arc.  For 2-matchings, the source and sink
nodes each must have fewer than 2 arcs.

      Carpaneto and Toth (2) have one additional enhancement that
yields a few more arcs but it does not alter the values of the dual
variables.  The technique described here is independent of that
e...