Three Implementations of Branch-and-Bound in CLP''

Nortel technology, London Road, Harlow,
Essex, CM17 9NA, England
steven@nortel.co.uk

Abstract
Constraint logic programming systems are becoming increasingly popular for solving real-life combinatorial optimization problems. An important component of such systems is therefore an optimization function, and one or more implementations of the branch-and-bound method are typically provided. However, there seems to be no available methodology for choosing an implementation, and making the wrong choice can cause disastrous performance problems. This paper examines the robustness of three known implementations by testing their performance under extreme conditions. One implementation performs badly when constraint propagation is poor and also interacts poorly with parallelization in three distinct ways. Another performs badly on certain cost functions. The third is not always the fastest but it emerges as more robust than the other two. We therefore recommend that only the third or something like it be provided, thus relieving the programmer of a difficult but critical decision.