Concurrent Optimizer
Concurrent optimization is a simple approach for exploiting multiple processors. It starts multiple, independent solves on a model, using different strategies for each. Optimization terminates when the first one completes. By pursuing multiple different strategies simultaneously, the concurrent optimizer can often obtain a solution faster than it would if it had to choose a single strategy.
Concurrent optimization is our default choice for solving LP models, and a user-selectable option for solving MIP models. The concurrent optimizer can be controlled in a few different ways. These will be discussed in this section. To avoid confusion when reporting results from multiple simultaneous solves, we've chosen to produce simplified logs and callbacks when performing concurrent optimization. These will also be discussed in this section.
Controlling Concurrent Optimization
If you wish to use the concurrent optimizer to solve your model, the steps you need to take depend on the model type. As mentioned earlier, the concurrent optimizer is the default choice for LP models. This choice is controlled by the Method parameter. For MIP models, you can select the concurrent optimizer by modifying the ConcurrentMIP parameter.
When controlling the concurrent optimizer using these parameters, the strategies used for the different independent solves are chosen automatically. While we reserve the right to change our choices in the future, for LP models we currently devote the first concurrent thread to dual simplex, the second through fourth to a single parallel barrier solve, and the fifth to primal simplex. Additional threads are devoted to the one parallel barrier solve. Thus, for example, a concurrent LP solve using four threads would devote one thread to dual simplex and three to parallel barrier. For MIP, we divide available threads evenly among the independent solves, and we choose different values for the MIPFocus and Seed parameters for each.
If you want more control over concurrent optimization (e.g., to choose
the exact strategies used for each independent solve), you can do so
by creating two or more concurrent environments. These can be
created via API routines (in
C,
C++,
Java,
.NET, or
Python), or they
can be created from .prm files using the
ConcurrentSettings
parameter if you are using our command-line interface. Once these
have been created, subsequent optimization calls will start one
independent solve for each concurrent environment you created. To
control the strategies used for each solve, you simply set the
parameters in each environment to the values you would like them to
take in the corresponding solve. For example, if you create two
concurrent environments and set the MIPFocus parameter to 1 in
the first and 2 in the second, subsequent MIP optimize calls will
perform two solves in parallel, one with MIPFocus=1 and the
other with MIPFocus=2.
Your first indication that the concurrent optimizer is being used is output in the Gurobi log that looks like this...
Concurrent LP optimizer: dual simplex and barrier Showing barrier log only......or like this...
Concurrent MIP optimizer: 2 concurrent instances (2 threads per instance)These log lines indicate how many independent solves will be launched. For the LP case, the lines also indicate which methods will be used for each.
Since it would be quite confusing to see results from multiple solves interleaved in a single log, we've chosen to use a simplified log format for concurrent optimization. For concurrent LP, we only present the log for a single solve. For concurrent MIP, the log is similar to our standard MIP log, except that it only provides periodic summary information (see the MIP logging section if you are unfamiliar with our standard MIP log). Each concurrent MIP log line shows the objective for the best feasible solution found by any of the independent solves to that point, the best objective bound proved by any of the independent solves, and the relative gap between these two values:
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 - - - 24.00000 13.00000 45.8% 0s
0 0 - - - 16.50000 13.21154 19.9% 0s
0 0 - - - 16.50000 13.25000 19.7% 0s
0 0 - - - 16.50000 13.37500 18.9% 0s
0 0 - - - 16.50000 13.37500 18.9% 0s
0 0 - - - 16.50000 13.37500 18.9% 0s
0 6 - - - 15.50000 13.37500 13.7% 0s
310 149 - - - 15.00000 13.66923 8.87% 0s
3873 1634 - - - 15.00000 14.00000 6.67% 5s
9652 4298 - - - 15.00000 14.12500 5.83% 10s
16535 6991 - - - 15.00000 14.18056 5.46% 15s
23610 9427 - - - 15.00000 14.22333 5.18% 20s
...
We also include node counts from one of the independent solves, as
well as elapsed times, to give some indication of forward progress.
Concurrent optimization essentially sets up a race between multiple threads to solve your model, with the winning thread returning the solution that it found. In cases where multiple threads solve the model in roughly the same amount of time, small variations in runtime from one run to the next could mean that the winning thread is not the same each time. If your model has multiple optimal solutions (which is quite common in LP and MIP), then it is possible that running a concurrent solver multiple times on the same model could produce different optimal solutions. This is known as non-deterministic behavior.
By default, the Gurobi concurrent solvers all produce non-deterministic behavior. You can obtain deterministic behavior for the concurrent LP solver by setting the Method parameter to value 4. This setting typically increases runtimes slightly, but if your application is dependent on deterministic behavior, deterministic concurrent LP is often your best option. There is no similar setting for the concurrent MIP solver.
Rather than providing callbacks from multiple independent solves simultaneously, we've again chosen to simplify behavior for the concurrent optimizer. In particular, we only supply callbacks from a single solve. A few consequences of this choice:
- Information retrieved by your callback (solutions, objective bounds, etc.) will come from a single model.
- User cutting planes are only applied to a single model.
- You aren't allowed to use lazy constraints with concurrent MIP, since they would only be applied to one model.
