In the branch & cut algorithm, ILOG CPLEX solves a series of LP 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 LP 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.) Such algorithms have been known historically as branch & bound, especially when cuts are not generated.

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. The cutoff value is determined in either of two ways:

• You set the cutoff value in the:

  • Interactive Optimizer by means of the command set mip tolerances lowercutoff (when you are maximizing the objective) or set mip tolerances uppercutoff (when you are minimizing the objective);

  • Concert Technology Library set the parameter CutLo or CutUp.

  • Callable Library set the parameter CPX_PARAM_CUTLO or CPX_PARAM_CUTUP.

The default value of the lower cutoff is -1e+75; the default value of the upper cutoff is 1e+75. You can supply any number that you find appropriate for your problem.

• ILOG CPLEX will use the value of the best integer solution found so far, as modified by tolerance parameters.

  • In the Interactive Optimizer, use the command set mip tolerances objdifference for an absolute objective difference cutoff or set mip tolerances relobjdifference for a relative objective difference cutoff.

  • In the Concert Technology Library set the parameter ObjDif or RelObjDif.

  • In the Callable Library, set the parameter CPX_PARAM_OBJDIF or CPX_PARAM_RELOBJDIF.

Be careful in changing these tolerances: if either of them is nonzero, you may miss the optimal solution by as much as that amount. For example, if the true optimum is 100, and the absolute cutoff is set to 5, and a feasible solution of, say, 103 is found at some point, then the cutoff will discard all nodes with a solution worse than 98, and thus the solution of 100 will be overlooked.

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 ILOG CPLEX traverses in the tree through several parameters, as summarized in Table 5.3 and explained further in later sections. Briefly, ILOG CPLEX must make different kinds of choices:

• within a tree, about which node to branch on,

• at a node, which variable to branch on, and

• at a variable, which direction to branch (up or down or other).

At each node, ILOG CPLEX may delve deeper into the tree or it may backtrack. The value of the backtrack parameter influences this decision. When ILOG CPLEX backtracks, there are usually large numbers of available, unexplored nodes. The node selection parameter influences its selection. Once a node has been selected, the variable selection parameter influences which variable is selected for branching. Priority provides a powerful mechanism through which you supply problem-specific directives about the order of variables during branching. You also supply problem-specific preferences about branching direction, either globally or by specific variable. And special ordered sets (SOS) may also improve branching strategy.