On Mitten's Axioms for Branch-and-Bound
A.H.G. Rinnooy · 1976
The axiomatic characterization of branch-and-bound methods proposed by L. G. Mitten contains a number of inaccuracies. We develop a closely related, revised system of axioms that allows the deduction of a number of attractive properties. LET f BE a real function defined on a set S of feasible solutions and let f* = sUp.Es{f(x)} I S* = { x* l f(x*) = f*} One possible way to find at least one x* C S* is provided by methods of branch-and-bound. Several axiomatic characterizations of such methods have been proposed in the literature (see reference 3 for a survey). Prominent among them is the often quoted and very general approach due to L. G. Mitten [1] in which, for instance, the cardinality I S I of S is allowed to be transfinite. Apart from a system of axioms characterizing a branching rule, an upper bounding rule, and a lower bounding rule, reference 1 contains a number of desirable properties of branch-and-bound methods, claimed to be deducible from the axioms. Unfortunately, the latter claim is not true. The purpose of this note is to correct this logical deficiency by presenting a revised axiom system that is close in spirit to Mitten's original formulation, but that allows a proper demonstration of all results mentioned in reference 1.