Computational Efficiency of Approximate Branch-and-Bound Algorithms

To improve the computational efficiency of a branch-and-bound algorithm at the sacrifice of obtaining an optimal solution, the lower bound test is sometimes strengthened beyond its limit, i.e., a partial problem P_i is terminated if g(P_i) ≥ z − ϵ(z) (instead of g(P_i) ≥ z), where g(P_i) is a lower bound of P_i, z is the current incumbent value and ϵ(z) (≥0) specifies the allowance within which the value of an obtained solution can deviate from the optimal.

This paper first shows that the efficiency (as measured by the number of decomposed partial problems) does not generally improve by introducing ϵ or by increasing ϵ, and then isolates subclasses of branch-and-bound algorithms for which a monotone increase in efficiency with respect to ϵ is guaranteed.