Terminating MIP optimization

Describes termination conditions of the MIP optimizer.

CPLEX terminates MIP optimization under a variety of circumstances. First, CPLEX declares integer optimality and terminates when it finds an integer solution and all parts of the search space have been processed. Optimality in this case is relative to whatever tolerances and optimality criteria you have set. For example, CPLEX considers any user-supplied cutoff value (such as CutLo or CutUp) as well as the objective difference parameter (ObjDif) when it treats nodes during branch & cut. Thus these settings indirectly affect termination.

An important termination criterion that the user can set explicitly is the MIP gap tolerance. In fact, there are two such tolerances: a relative MIP gap tolerance that is commonly used, and an absolute MIP gap tolerance that is appropriate in cases where the expected optimal objective function is quite small in magnitude. The default value of the relative MIP gap tolerance is 1e-4; the default value of the absolute MIP gap tolerance is 1e-6. These default values indicate to CPLEX to stop when an integer feasible solution has been proved to be within 0.01% of optimality. On a difficult model with input data obtained with only approximate accuracy, where a proved optimum is thought to be unlikely within a reasonable amount of computation time, a user might choose a larger relative MIP gap to allow early termination; for example, a relative MIP gap of 0.05 (corresponding to 5%). Conversely, in a model where the objective function amounts to billions of dollars and the data are accurate to a degree that further processing is worthwhile, a tighter relative MIP Gap (even 0.0) may be advantageous to avoid any chance of missing the best possible solution.

CPLEX also terminates optimization when it reaches any limit that you have set. You can set limits on time, number of nodes, size of tree memory, and number of integer solutions. Table 1 summarizes those parameters and their purpose.

Table 1. Parameters to limit MIP optimization
To set a limit on	Use this parameter	Concert Technology	Callable Library	Interactive Optimizer
elapsed time	optimizer time limit in seconds	`TiLim`	`CPX_PARAM_TILIM`	`timelimit`
elapsed deterministic time	deterministic time limit	`DetTiLim`	`CPX_PARAM_DETTILIM`	`dettimelimit`
number of nodes	MIP node limit	`NodeLim`	`CPX_PARAM_NODELIM`	`mip limits nodes`
size of tree	tree memory limit	`TreLim`	`CPX_PARAM_TRELIM`	`mip limits treememory`
number of integer solutions	MIP integer solution-file switch and prefix	`IntSolLim`	`CPX_PARAM_INTSOLLIM`	`mip limits solutions`
relative MIP gap tolerance	relative MIP gap tolerance	`EpGap`	`CPX_PARAM_EPGAP`	`mip tolerances mipgap`
absolute MIP gap tolerance	absolute MIP gap tolerance	`EpAGap`	`CPX_PARAM_EPAGAP`	`mip tolerances absmipgap`

CPLEX also terminates when an error occurs, such as when CPLEX runs out of memory or when a subproblem cannot be solved. If an error is due to failure to solve a subproblem, an additional line appears in the node log file to indicate the reason for that failure. For suggestions about overcoming such errors, see Troubleshooting MIP performance problems.