RL11849 Computation Status

For some notes about what this means, see the notes at the end of this page.  Many individual items also have links to the appropriate entry in the notes.

Solved on September 28, 1999, 3:17 AM CST

Hardware supported by Compaq
Available CPU summary
System Model CPU type # CPUs
Spec CPU95
Compaq XP1000 500 MHz Alpha 21264 5 26.9/52.2
Compaq DS20 500 MHz Alpha 21264 6 27.7/58.7
Compaq ES40 500 MHz Alpha 21264 32 27.3/57.7
Digital AS4100 5/400 400 MHz Alpha 21164 12 12.1/17.2


RL11849 Lower Bound Progress

rl11849 progress summary

RL11849 Branch and Bound Tree

rl11849 branching tree

RL11849 Number of Active Nodes

rl11849 active node summary

Notes about this page:

This page summarizes our computation which solved RL11849, a TSP instance from TSPLIB. The computation attempts to close the gap between the upper bound (best known solution) and a lower bound on all solutions by raising the lower bound until it matches the upper bound.  In the process it may also discover improvements to the current best solution.

Status:  This status information is prepared by collecting data about the run. 

Lower Bound:  The lower bound is the focus of the primary computational effort.  It is computed by a branch and bound process, using a linear programming relaxation, and then tightening the relaxation with cutting planes to obtain the bound.  When no more progress is being made on the bound on a problem, we branch, dividing the problem into two subproblems.  Thus, the lower bound is the minimum lower bound of all of the current subproblems.  The current subproblems are also referred to as the active nodes.

Optimal Solution:  The upper bound on the solution value is just the length of the best tour known, shown here. Because the edge lengths are all integers, the lower bound shows that this tour is indeed the optimal solution.

CPU Time Used:  The cpu time used in the branch and bound computation.  CPU times on various machine types are just added together, so this does not reflect the CPU time on any one type of CPU.  This time does not include the time spent working on the upper and lower bounds of the root node, prior to beginning branch and bound.

Available CPU summary:  This table provides a list of the CPUs we had available for this computation.  The CPUs that were used on the problem are some subset of these CPUs, because machines crash, the machine is needed temporarily for some other work, or some other reason.

We would like to thank Compaq for the research relationships which have enabled us to acquire the computers powering this computation.  The invigorating performance of the new 21264-based computers has brought new life into our TSP computations.

We would also like to thank Zoran Budimlic, Alan Cox, Peter Druschel, Rob Fowler, and Willy Zwaenepoel for letting us run on their computers.

Lower Bound Progress: This plot shows the computed lower bound as a function of the cpu time used.

Active Node:  An active node is another way of referring to a subproblem which has not been
further split, and whose lower bound is less than the current upper bound.  Every active node needs to be worked on, and any active node could be worked on next.  The computation assigns the active nodes with the smallest lower bounds to the available CPUs.  The computation on an active node will either result in its lower bound being increased to the current upper bound, or the problem will be split into two new subproblems (and hence two new active nodes).  From another viewpoint, the active nodes are the leaves of the current branch and bound tree.

Number of Active Nodes: This plot shows the number of active nodes as a function of the cpu time used.

Branch and Bound Tree:  This is a picture of the current branch and bound tree.  The active nodes are shown in red and magenta, while the processed nodes are shown in green.  The vertical position of a node is determined by its lower bound.

Last updated:  June  1, 2001.
Contact:  david@research.att.com