Tolerances in Branch-and-Bound Algorithms

from my staff member Boris Goldengorin. So, the ideas are not my own,
but the formulation and the accents are. The talk will have a rather
informal, lecture like, character.

Branch-and-bound is a powerful method for solving hard problems. It
is easy to program but without special care the exponentiality will
normally not allow to solve very big problem instances. Good upper
and lower bounds and methods to make induced decisions are the key
to success. Another important point is the branching decision and the
way the branching tree is developed. We focus on these latter points,
using the Symmetric (that is, undirected) Hamiltonian Path Problem
(SHPP) and the Symmetric Travelling Salesman Problem (STSP) as example.

I will present the notion of upper and lower tolerance and argue that
it is a good idea to base the branching decisions on the values of the
tolerances. The tolerance notion even allows to derive better lower
bounds. Tolerances can be used to develop the branch-and-bound tree in
such a way that we can be sure that the first feasible solution is an
optimal solution.

In the second, shorter part, of the talk i will consider the issue of
how to compute tolerances for the problems considered. The lower
tolerances can be computed by a well-known generalization of the
range-minimum problem to trees. It might not be known how to construct
the required data structure in parallel, and i want to present this
problem for possible joint research.