The following section, Performance Features of the Mixed Integer Optimizer, goes into great detail about the algorithmic features, controlled by parameter settings, that are available in ILOG CPLEX to achieve performance tuning on difficult MIP models. However, there is an important parameter, MIPEmphasis
, that is oriented less toward the user understanding the algorithm being used to solve the model, and more toward the user telling the algorithm something about the underlying aim of the optimization being run. That parameter is discussed here.
Optimizing a MIP model involves:
For most models, a balance between these two sometimes-competing aims works well, and this is another way of stating the philosophy behind the default MIPEmphasis
setting: "balance optimality and integer feasibility".
At this default MIPEmphasis
setting of 0
(MIPEmphasisBalanced
or CPX_MIPEMPHASIS_BALANCED
), ILOG CPLEX uses tactics intended to quickly find a proven optimal solution, for models of a broad range of difficulty. That is, considerable analysis of the model is performed before branching ever begins, in the expectation that the investment will result in a faster total run time, yet not every possible analysis is performed. And then branching is performed in a manner that seeks to find good quality feasible solutions, without sacrificing too much time that could be spent proving the optimality of any solution that has already been found.
In many situations, the user will desire a greater emphasis on feasibility and less emphasis on analysis and proof of optimality. For instance, a restrictive time limit (set by the user using the TiLim
parameter) may be in force due to a real-time application deployment, where a model is of sufficient difficulty that a proof of optimality is unlikely, and the user wants to have simply as good a solution as is practicable when the time limit is reached. The MIPEmphasis
setting of 1
(MIPEmphasisFeasibility
or CPX_MIPEMPHASIS_FEASIBILITY
) directs ILOG CPLEX to adopt this emphasis. Less computational effort is applied at the outset toward the analyses that aid in the eventual proof of optimality, and more effort is spent in immediately beginning computations that search for early (and then improved) feasible solutions. It is likely on most models that an eventual proof of optimality would take longer by setting MIPEmphasis
to 1
, but since the user has given ILOG CPLEX the additional information that this proof is of less importance than usual, the user's needs will actually be met more effectively.
Another choice for MIPEmphasis
is 2
(MIPEmphasisOptimality
or CPX_MIPEMPHASIS_OPTIMALITY
), which results in a greater emphasis on optimality than on feasibility. The search for feasible solutions is not ignored completely, but the balance is shifted toward moving the Best Bound (described in the following paragraph) more rapidly, at the likely expense of feasible solutions being found less rapidly, and improved feasible solutions less frequently, than under the default emphasis. This setting also provides a general (though not precise) compatibility mode to prior versions of ILOG CPLEX.
The fourth choice for MIPEmphasis
, 3
(MIPEmphasisBestBound
or CPX_MIPEMPHASIS_BESTBOUND
), works exclusively at moving the Best Bound. The Best Bound represents the objective function value at which an integer feasible solution could still potentially exist. As possibilities are eliminated, this Best Bound value will move in the opposite direction to that of any improving series of integer feasible solutions. The process of moving the Best Bound will eventually result in the optimal feasible solution being discovered, at which point the optimization is complete, and feasible solutions may be discovered along the way anyway, due to branches that happen to locate feasible solutions that do not match the Best Bound. A great deal of analysis may be performed on the model, beyond what is done under the default emphasis. Therefore it is recommended to use this setting only on models that are difficult for the default emphasis, and for which you do not care about interim feasible solutions that may or may not be optimal.
To make clear a point that has been alluded to in the above: every choice of MIPEmphasis
results in the branch & cut algorithm proceeding in a manner that eventually will find and prove an optimal solution, or will prove that no integer feasible solution exists. The choice of emphasis only guides ILOG CPLEX to produce feasible solutions in a way that is in keeping with the user's particular purposes, but the accuracy and completeness of the algorithm is not sacrificed in the process.
The MIPEmphasis
parameter may be set in conjunction with any other ILOG CPLEX parameters (discussed at length in the next section). For example if you wish to set an upward branching strategy via the BrDir
parameter, this will be honored under any setting of MIPEmphasis
. Of course, certain combinations of MIPEmphasis
with other parameters may be counter-productive, such as turning off all Cuts under emphasis 3
, but the user has the option if that is what is desired.