Parallel Branch and Bound Priority Queue

Specific Domains Optimization (Mathematical)
, ,
1

I’ve implemented code for a simple branch and bound procedure for maximizing a function in Julia (actually I’ve tweaked the code in NeuralPriorityOptimizer.jl).

Currently the code runs on a single thread, but I’d like to use parallelization/multithreading to get some speedup.

It basically computes an upper bound of my function over some domain and stores the result in a priority queue.
During the branch and bound algorithm, it always takes the subdomain with the largest upper bound and refines it to get a better approximation.
The rough structure is shown below:

q = PriorityQueue(Base.Order.Reverse)
enqueue!(q, init_domain, relax_ub(init_domain))

while some_condition
    dom, relax_val = peek(q)
    dequeue!(q)
    
    ...
    dom1, dom2 = split(dom)
    enqueue!(q, dom1, relax_ub(dom1))
    enqueue!(q, dom2, relax_ub(dom2))
end

What would be the best way to parallelize this code?

I imagine the easiest solution would be a parallel priority queue, but I haven’t found a Julia solution thus far.

2

Two simple options:

  1. Use an ordinary priority queue, and pair it with a lock. Threads grab the lock when they want to modify the queue.
  2. Have a single main thread “driving” the optimization, and have it push work onto a channel (i.e. a work queue) and workers push results onto another channel. The other threads just sit around waiting for work (e.g. points to evaluate, or regions to search).

Both of these approaches will suffer from scaling difficulties when you get to huge numbers of threads, because at some point you will be limited by contention over the single lock/channel. One way around this is to use work-stealing, e.g. via ConcurrentCollections.jl. But I would try the simple approach first and see if you run into problems … it may not be an issue depending on the scale of your problem.

If you want to scale to distributed-memory systems, you will have to eventually go beyond threads. A low-level option is to implement work stealing in something like MPI.jl, but a higher-level option might be Dagger.jl.