Browse Prior Art Database

Eliminating Redundant Constraints in Branch-and-Bound Solutions to the Traveling Salesman Problem

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

Publishing Venue

IBM

Related People

Stone, HS: AUTHOR

Abstract

This note describes a simple and effective method for eliminating redundant constraints that are generated while searching for optimal tours that solve the traveling salesman problem. In a typical branch-and-bound search, some arcs are constrained to be outside of the solution and some are constrained to be in the solution. Suppose that arc (i,j) is constrained to be outside of the solution (*). Subsequently, if arc (i,k) is constrained to be in the solution, the constraint on arc (i,j) is redundant. If (i,k) is part of the solution, then (i,j) cannot be in the solution, so that it is not necessary to store the constraint for arc (i,j).

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

Eliminating Redundant Constraints in Branch-and-Bound Solutions to the Traveling Salesman Problem

       This note describes a simple and effective method for
eliminating redundant constraints that are generated while searching
for optimal tours that solve the traveling salesman problem.  In a
typical branch-and-bound search, some arcs are constrained to be
outside of the solution and some are constrained to be in the
solution.  Suppose that arc (i,j) is constrained to be outside of the
solution (*). Subsequently, if arc (i,k) is constrained to be in the
solution, the constraint on arc (i,j) is redundant.  If (i,k) is part
of the solution, then (i,j) cannot be in the solution, so that it is
not necessary to store the constraint for arc (i,j).

      This idea relies on the context in which solutions are
generated, saved and retrieved.  In branch-and-bound algorithms the
central high- level strategy is the following:
    1. Recover the next problem to solve.
    2. Install the constraints of the problem that has been
recovered.

      3. Generate and solve k new subproblems.  To generate a
subproblem, add one or more new constraints to the recovered problem.
 After each subproblem is solved, enqueue the new subproblem and its
constraints unless global bounds indicate that the subproblem does
not have an optimal solution among its solutions.  Then restore the
constraints to a state that per     mits the constraints for the next
subproblem to be added.

      4. Repeat the steps above starting from Step 1 until Step 1
recovers a problem that forces a termination of the branch-and-bound
algorithm.

      When this procedure is followed, constraints are generated in
any particular order, intermixing forced arcs (arcs that must be in a
solution) with broken arcs (arcs that cannot be in a solution).  A
broken- arc constraint becomes redundant when a subsequent forced-arc
constraint eliminates the forced-arc constraint.  It is worthwhile to
remove the redundant broken arcs in such cases, provided that the
cost of finding a redundant constraint is not too high.  The method
described below provides the required capability at low cost.
    The method consists of the following operations:
    1. When recovering constraints for a subproblem, reorder storage
as necessary to place the forced arcs in storage before the broken
arcs.

      2. After the constraints have been recovered and stor...