Improved branch and bound in constraint logic programming

Constraint logic programming has been applied to cost minimization problems such as job-shop scheduling with some success, using the (depth-first) branch and bound method. Recent work has shown that problem-specific heuristics can improve the performance of CLP systems on combinatorial optimisation problems. In this paper we take an orthogonal approach, by developing a generic parallel branch and bound strategy which improves existing CLP strategies in several ways: by avoiding the sometimes prohibitive overheads common to existing implementations; by speeding up convergence to optimal solutions; and by speeding up the proof of optimality for suboptimal solutions. The latter two improvements exploit parallelism in novel ways, which can be smoothly integrated with Or-parallelism. We evaluate these ideas on a set of job-shop scheduling problems, in some cases achieving order of magnitude speedups.