When is distributed optimization useful?

Why Distributed Optimization?

Distributed Optimization can be used for:

• Distributed Concurrent: You can use multiple machines to solve an LP or MIP model. Each machine uses a different strategy to solve the same problem, hoping that one strategy will be particularly effective and finish much earlier than the others.
• Distributed MIP: This allows you to divide the work of solving a single MIP model among multiple machines. A manager machine passes problem data to worker machines to coordinate the overall solution process.
• Distributed Parameter Tuning: If you are using a Gurobi Compute Server, you can harness the power of multiple machines to perform distributed parallel tuning to speed up the search for effective parameter settings.

Distributed Concurrent

With Distributed Concurrent, the approach is to solve the same problem on multiple machines simultaneously but with different settings.

This approach is particularly helpful if there is huge performance variability. By default, Gurobi will use a different random seed for each run -- which often produces enough variability. You can also specify other parameter settings if you have additional knowledge.

Since the concurrent solves are independent, the communication overhead is negligible. Thus, using a distributed concurrent approach will never hurt performance. Therefore, if you have extra machines, there is always a good chance that you will get some benefit from using Distributed Concurrent. The additional benefit may tail off with adding more and more machines, as the main effect for speed-up (performance variability) is usually exploited well enough with a few machines.

Distributed MIP

With Distributed MIP, the approach is to split the work of solving one big MIP among multiple machines.

In general, parallelism for MIP is beneficial only in a few situations -- even on a single machine. Based on our experience, our general sense is that the speedups are not significantly better beyond 8 (or maybe 16) threads. In fact, sometimes too many threads can even be detrimental due to the overhead incurred by synchronization. This sense also agrees with Amdahl's law regarding the theoretical speedup when using multiple processors.

Benefits are even harder to achieve when splitting the work between multiple machines because the communication overhead is more significant due to latency. Often, it is not beneficial to use lots of workers. Whenever possible, it is better to perform the optimization on one big machine instead of many small ones. 

However, the distributed MIP approach can work well for models that produce very large but relatively shallow trees. With these models, the number of open (unexplored) nodes with good dual bounds becomes very large during the optimization.

On the other hand, if the MIP tree search is a "dive", parallelism won't help much because only one thread can process a single dive, while each of the other threads needs to process their own dives. Suppose the MIP is essentially solved by just following a single dive to the end until an optimal or very good solution is found at a leaf node. In that case, processing additional dives using additional threads will not help.

How does distributed MIP work?

When solving a model with the distributed MIP approach, Gurobi begins with a "ramp-up" phase.
In this phase, each distributed worker solves the problem concurrently.

At some point, Gurobi selects the "best" branch-and-bound tree these workers have produced.

This search tree is used as the starting point for the distributed phase. From that point, the different machines each explore different parts of the tree and synchronize their progress.

Distributed Tuning

Gurobi includes a parameter tuning tool that automatically searches for parameter settings that improve optimization performance on a single or set of models. This tuning tool has proven to be quite effective. One downside of the tuning tool is the time it can take. Automated tuning performs many solves on your model, each using different parameter settings and random seeds. In our experience, you should account for the time to test at least 100 parameter settings, each with 3 random seeds.

The distributed tuning tool uses multiple independent machines to perform tuning, thus allowing you to explore more candidate parameter settings in the same amount of time.

Limitations

• Distributed Optimization is not fully supported for MIQCP.
• Callbacks are limited in Concurrent Optimizers. For specifics, please see Concurrent Optimizer.
• Distributed Optimization works best if all of the workers have very similar performance. For example, if one machine in your worker pool were much slower than the others in a distributed tuning run, any parameter sets tested on the slower machine would appear less effective than if run on a faster machine. Similar considerations apply to Distributed MIP and Distributed Concurrent. We strongly recommend that you use machines with very similar performance.

Licensing

• You need a license that has distributed enabled on the manager machine to use Distributed MIP or Distributed Concurrent. For Distributed Tuning, you don't need a special license.
• On Gurobi Instant Cloud, Distributed Optimization is always allowed and can be enabled in the pool settings.
• The distributed workers do not require any license.

Further information

• Distributed Algorithms overview
• Gurobi Remote Services > Distributed Algorithms
• Distributed Algorithm Considerations
• Concurrent Optimizer