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.

923288 | ||

13094345 |

Hardware supported by

System Model | CPU type | # CPUs
available |
Spec CPU95
Int/FP |

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 |

**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