  We present a general method for obtaining strong bounds for discrete
optimization problems that is based on a concept of branching duality. It can
be applied when no useful integer programming model is available, and we
illustrate this with the minimum bandwidth problem. The method strengthens a
known bound for a given problem by formulating a dual problem whose feasible
solutions are partial branching trees. It solves the dual problem with a
"worst-bound" local search heuristic that explores neighboring partial trees.
After proving some optimality properties of the heuristic, we show that it
substantially improves known combinatorial bounds for the minimum bandwidth
problem with a modest amount of computation. It also obtains significantly
tighter bounds than depth-first and breadth-first branching, demonstrating that
the dual perspective can lead to better branching strategies when the object is
to find valid bounds.
