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.

19982859 | ||

131052087 |

**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. **Some of this computation took
place on PC's running FreeBSD. FreeBSD's cpu usage timers overflow,
so the cpu times we computed on these machines were often negative
because of these overflows. The real total cpu time used was significantly
more than this value we computed.**
Also, 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.

**Lower Bound Progress**: This plot shows
the computed lower bound as a function of the cpu time used. The cpu
times in this plot are affected by overflows in FreeBSD's cpu usage
timers.

**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. The cpu
times in this plot are affected by overflows in FreeBSD's cpu usage
timers.

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