WG211/M14Scholz

Parallel Branch and Bound, functionally!

Branch and bound algorithms play an important role in many combinatorial search and optimisation problems. Parallel implementations of these algorithms typically involve rather sophisticated orchestrations of concurrency constructs. In this talk we propose a purely functional implementation for branch and bound algorithms that is based on a single map-like construct with a controlled form of non-deterministic state modifications. Besides presenting the central language construct and the way it can be utilised for implementing branch and bound algorithms, we also present some initial performance measurements of a prototypical implementation in the context of SaC.