Author(s)
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.
Accepted Papers