Performance Features of the Mixed Integer Optimizer

The ILOG CPLEX Mixed Integer Optimizer contains a wealth of features intended to aid in the solution of challenging MIP models. While default strategies are provided that solve the majority of models without user involvement, there exist difficult models that benefit from attention to performance tuning. This section discusses the ILOG CPLEX parameters that are the most likely to offer help on such models.

Because many of these parameter settings directly affect the branch & cut algorithm, we first give a description of how that algorithm is implemented within ILOG CPLEX.

Branch & Cut

In the branch & cut algorithm, ILOG CPLEX solves a series of continuous subproblems. To manage those subproblems efficiently, ILOG CPLEX builds a tree in which each subproblem is a node. The root of the tree is the continuous relaxation of the original MIP problem.

If the solution to the relaxation has one or more fractional variables, ILOG CPLEX will try to find cuts. Cuts are constraints that cut away areas of the feasible region of the relaxation that contain fractional solutions. ILOG CPLEX can generate several types of cuts. (Cuts tells you more about that topic.)

If the solution to the relaxation still has one or more fractional-valued integer variables after ILOG CPLEX tries to add cuts, then ILOG CPLEX branches on a fractional variable to generate two new subproblems, each with more restrictive bounds on the branching variable. For example, with binary variables, one node will fix the variable at 0 (zero), the other, at 1 (one).

The subproblems may result in an all-integer solution, in an infeasible solution, or another fractional solution. If the solution is fractional, ILOG CPLEX repeats the process.

ILOG CPLEX cuts off nodes when the value of the objective function associated with the subproblem at that node is worse than the cutoff value.

You set the cutoff value by means of the CutUp parameter (for a minimization problem) or the CutLo parameter (for a maximization problem), to indicate to ILOG CPLEX that integer feasible solutions worse than this cutoff value should be discarded. The default value of the lower cutoff is -1e+75 ; the default value of the upper cutoff is 1e+75. The defaults, in effect, mean that no cutoff is to be supplied. You can supply any number that you find appropriate for your problem. It is never required that you supply a cutoff, and in fact for most applications is it not done.

ILOG CPLEX will use the value of the best integer solution found so far, as modified by the tolerance parameters ObjDif or RelObjDif (absolute and relative objective function difference, respectively), as the cutoff. Again, it is not typical that users set these parameters, but they are available if you find them useful. Use care in changing these tolerances: if either of them is nonzero, you may miss the optimal solution by as much as that amount. For example, in a model where the true minimum is 100 and the absolute cutoff is set to 5, if a feasible solution of say, 103 is found at some point, the cutoff will discard all nodes with a solution worse than 98, and thus the solution of 100 would be overlooked.

Periodically during the branch & cut algorithm, ILOG CPLEX may apply a heuristic process that attempts to compute an integer solution from available information, such as the solution to the relaxation at the current node. This activity does not replace the branching steps, but sometimes is able to inexpensively locate a new feasible solution sooner than by branching, and a solution found in this way is treated in the same way as any other feasible solution. At intervals in the tree, new cuts beyond those computed at the root node may also be added to the problem.

Once ILOG CPLEX finds an integer solution, it does the following:

it makes that integer solution the incumbent solution and that node the incumbent node;
it makes the value of the objective function at that node (modified by the objective difference parameter) the new cutoff value;
it prunes from the tree all subproblems for which the value of the objective function is no better than the incumbent.

You control the path that CPLEX traverses in the tree through several parameters, as summarized in Table 8.3.

Table 8.3 Parameters for Controlling Branch & Cut Strategy
Interactive Optimizer Command	Concert Technology IloCplex Method	Callable Library Routine
`set mip strategy backtrack`	setParam(BtTol, n)	`CPXsetdblparam(env, CPX_PARAM_BTTOL, n)`
`set` `mip strategy nodeselect`	setParam(NodeSel, i)	`CPXsetintparam(env, CPX_PARAM_NODESEL, i)`
`set` `mip strategy variableselect`	setParam(VarSel, i)	`CPXsetintparam(env,` `CPX_PARAM_VARSEL, i)`
`set` `mip strategy bbinterval`	setParam(BBInterval, i)	`CPXsetintparam(env,` `CPX_PARAM_BBINTERVAL, i)`
`set` `mip strategy branch`	setParam(BrDir, i)	`CPXsetintparam(env,` `CPX_PARAM_BRDIR, i)`

During the branch & cut algorithm, ILOG CPLEX may choose to continue from the present node and dive deeper into the tree, or it may backtrack (that is, begin a new dive from elsewhere in the tree). The value of the backtrack parameter, BtTol, influences this decision, in terms of the relative degradation of the objective function caused by the branches taken so far in this dive. Setting BtTol to a value near 0.0 increases the likelihood that a backtrack will occur, while the default value near 1.0 makes it more likely that the present dive will continue to a resolution (fathoming either via a cutoff or an infeasible combination of branches or the discovery of a new incumbent integer feasible solution). See the ILOG CPLEX Reference Manual, Appendix A, for more details on how this parameter affects the computation that determines the decision to backtrack.

When ILOG CPLEX backtracks, there usually remain large numbers of unexplored nodes from which to begin a new dive. The node selection parameter, NodeSel, determines this choice.

Table 8.4 NodeSel Parameter Values for Node Search Type
NodeSelValue	Symbolic Value	Node Search Type
`1`(Default)	CPX_NODESEL_BESTBOUND	Best Bound search, which means that the node with the best objective function will be selected, generally near the top of the tree.
`2`	CPX_NODESEL_BESTEST	Best Estimate search, whereby ILOG CPLEX will estimate a given node's progress toward integer feasibility relative to its degradation of the objective function. This setting can be useful in cases where there is difficulty in finding feasible solutions or in cases where a proof of optimality is not crucial.
`2`	CPX_NODESEL_BESTEST_ALT	A variation on the Best Estimate search.
`0`	CPX_NODESEL_DFS	Depth First search will be conducted. In many cases this amounts to a brute force strategy for solving the combinatorial problem, gaining a small amount of tactical efficiency due to a variety of reasons, and it is rare that it offers any advantage over other settings.

In instances where Best Estimate node selection (NodeSel = 2 or 3) is in effect, the BBInterval parameter determines the frequency at which backtracking is done by Best Bound anyway. The default value of 7 works well, but you can set it to 0 to assure that Best Estimate is used every time backtracking occurs.

Once a node has been selected, the variable selection parameter, VarSel, influences which variable is chosen for branching at that node.

Table 8.5 VarSel Parameter Values for Branching Variable Choice
VarSel Value	Symbolic Value	Branching Variable Choice
`-1`	`CPX_VARSEL_MININFEAS`	Branch strictly at the nearest integer value which is closest to the fractional variable.
`1`	`CPX_VARSEL_MAXINFEAS`	Branch strictly at the nearest integer value which is furthest from the fractional variable.
`0`(Default)	`CPX_VARSEL_DEFAULT`	ILOG CPLEX makes the determination of each branch direction.
`2`	`CPX_VARSEL_PSEUDO`	Use pseudo costs, which derives an estimate about the effect of each proposed branch from duality information.
`3`	`CPX_VARSEL_STRONG`	Use Strong Branching, which invests considerable effort in analyzing potential branches in the hope of drastically reducing the number of nodes that will be explored.
`4`	`CPX_VARSEL_PSEUDOREDUCED`	Use pseudo reduced costs, which is a computationally less-intensive version of pseudo costs.

Once a variable has been selected for branching, the BrDir parameter influences the direction, up or down, of the branch on that variable to be explored first.

Table 8.6 BrDir Parameter Values for Branching Direction Choice
BrDirValue	Symbolic Value	Branching Direction Choice
`0`(Default)	CPX_BRANCH_GLOBAL	ILOG CPLEX makes the determination of each branch direction.
`-1`	CPX_BRANCH_DOWN	Branch downward.
`1`	CPX_BRANCH_UP	Branch upward.

Note that "Priority Orders" , complement the behavior of these parameters, as a mechanism by which you supply problem-specific directives about the order in which to branch on variables. In a Priority Order you can also provide preferred branching directions for specific variables.