Parallel Optimization in Custom Branch-and-Bound
Answered
Hi everyone,
I am implementing a custom branch-and-bound (BnB) algorithm where, at each node, I need to solve $n$ optimization models. These are nonlinear mixed-integer models, and they are structurally identical—the only difference is in the input data. After solving all $n$ models, I decide whether to prune or branch based on a certain condition.
If branching is required, I add a constraint (the same) to all $n$ models and continue with the BnB process. Since $n$ can be relatively large and the problems are independent of each other, I am using the multiprocessing package in Python to solve the models in parallel, following the approach suggested here:
How do I use multiprocessing in Python with Gurobi?
The Problem
The issue with this approach is that at each BnB node, I have to rebuild all $n$ models from scratch before solving them. This significantly increases computational time, especially as the tree grows.
My Question
Instead of recreating the models at each node, is there a way to:
- Copy the existing models (so I don’t have to rebuild them),
- Add the new constraints, and
- Reoptimize in parallel using multiprocessing?
I’d appreciate any advice on how to efficiently handle model copies while keeping multiprocessing capabilities.
Thanks in advance!
Jaime
-
-
Gurobi Staff
Hi Jaime,
Instead of using Pool.map, you could look at a slightly lower-level approach where you start N processes and keep them running continuously (maintaining their own Gurobi environment object). Your would need to maintain your own communication between main and child processes (e.g. inform the child which constraints to add; inform the main which solution was calculated).
Another idea could be using the multi-scenario functionality: depending on what "structurally identical" means, this might remove the need for multiprocessing, although it would likely increase runtime a bit.
Kind regards,
Ronald0 -
Please sign in to leave a comment.
Comments
1 comment