Emphasizing feasibility and optimality

Describes the context of the MIP emphasis parameter.

The following topic, Tuning performance features of the mixed integer optimizer, goes into great detail about the algorithmic features, controlled by parameter settings, that are available in CPLEX to achieve performance tuning on difficult MIP models. However, there is an important parameter, MIPEmphasis or CPX_PARAM_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:

1. finding a succession of improving integer feasible solutions (that is, solutions satisfying the linear and quadratic constraints and the integrality conditions); while

2. also working toward a proof that no better feasible solution exists and is undiscovered.

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: it balances optimality and integer feasibility.

At this default MIPEmphasis setting of 0 (that is, MIPEmphasisBalanced in Concert Technology or CPX_MIPEMPHASIS_BALANCED in the Callable Library), CPLEX uses tactics intended to find a proven optimal solution quickly, for models of a broad range of difficulty. 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 may want a greater emphasis on feasibility and less emphasis on analysis and proof of optimality. For example, a restrictive time limit (set by the user with 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 in Concert Technology or CPX_MIPEMPHASIS_FEASIBILITY in the Callable Library) directs 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 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 in Concert Technology or, in the Callable Library, CPX_MIPEMPHASIS_OPTIMALITY). This setting 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 with the default emphasis.

The fourth choice for MIPEmphasis, 3 (MIPEmphasisBestBound in Concert Technology or, in the Callable Library, 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 with 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.

The final choice for MIPEmphasis is 4 (CPX_MIPEMPHASIS_HIDDENFEAS). It applies considerable additional effort toward finding high quality feasible solutions that are difficult to locate, and for this reason the eventual proof of optimality may take longer than with default settings. This choice is intended for use on difficult models where a proof of optimality is unlikely, and where emphasis 1 (one) does not deliver solutions of an appropriately high quality.

To make clear a point that has been alluded to so far: every choice of MIPEmphasis results in the search 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 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 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 by any setting of MIPEmphasis. Of course, certain combinations of MIPEmphasis with other parameters may be counter-productive, such as turning off all cuts with emphasis 3, but the user has the option if that is what is wanted.