In addition to a robust branch & cut algorithm, ILOG CPLEX also offers a dynamic search algorithm. The dynamic search algorithm consists of the same building blocks as branch & cut: LP relaxation, branching, cuts, and heuristics. The following sections of the manual describe performance and tuning in relation to branch & cut. The parameters mentioned in this context have a similar effect in the dynamic search algorithm as in conventional branch & cut. In fact, the generic description in relation to branch & cut suffices for both branch & cut and dynamic search. ILOG CPLEX offers the MIP search parameter ( MIPSearch , CPX_PARAM_MIPSEARCH ) for you to control whether it pursues dynamic search or conventional branch & cut in solving your problem. At its default setting, this parameter specifies that ILOG CPLEX should choose which algorithm to apply on the basis of characteristics it finds in your model. Other settings allow you to specify which search to pursue. Because many parameter settings directly affect the branch & cut and dynamic search algorithms, here is a general description of how branch & cut is implemented within ILOG CPLEX. 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. Applying Cutoff Values Applying Tolerance Parameters Applying Heuristics When an Integer Solution Is Found: the Incumbent Controlling Strategies: Diving and Backtracking Selecting Nodes Selecting Variables Changing Branching Direction Solving Subproblems Using Node Files

Applying Cutoff Values

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.

Applying Tolerance Parameters

ILOG CPLEX will use the value of the best integer solution found so far, as modified by the tolerance parameters ObjDif (absolute objective function difference) or RelObjDif (relative objective function difference) 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.

Applying Heuristics

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.

When an Integer Solution Is Found: the Incumbent

After 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.

Controlling Strategies: Diving and Backtracking

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

set mip strategy backtrack set mip strategy nodeselect set mip strategy variableselect set mip strategy bbinterval set mip strategy branch 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 reference manual ILOG CPLEX Parameters for more details about how this parameter influences the computation that makes the decision to backtrack.

Selecting Nodes

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

1 (Default) CPX_NODESEL_BESTEST CPX_NODESEL_BESTEST_ALT CPX_NODESEL_DFS In instances where Best Estimate node selection ( NodeSel = 2 or 3 ) is in effect, the BBInterval parameter sets 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 (zero) to make sure that Best Estimate is used every time backtracking occurs.

Selecting Variables

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

CPX_VARSEL_MININFEAS CPX_VARSEL_MAXINFEAS 0 (Default) CPX_VARSEL_PSEUDO CPX_VARSEL_STRONG CPX_VARSEL_PSEUDOREDUCED

Changing Branching Direction

After 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.

CPX_BRANCH_DOWN 0 (Default) CPX_BRANCH_UP Priority orders complement the behavior of these parameters. They are introduced in Issuing Priority Orders . They offer 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.

Solving Subproblems

ILOG CPLEX allows you to distinguish the algorithm applied to the initial relaxation of your problem from the algorithm applied to other continuous subproblems of a MIP. This distinction between initial relaxation and the other MIP subproblems may be useful when you have special information about the nature of your model. In this context, "other MIP subproblems" includes nodes of the branch & cut tree, problems re-solved after cutting plane passes, problems solved by node heuristics, and so forth. The parameter RootAlg ( CPX_PARAM_STARTALG ) enables you to specify which algorithm for ILOG CPLEX to apply to the initial relaxation. The parameter NodeAlg ( CPX_PARAM_SUBALG ) lets you specify the algorithm applied to other continuous subproblems. For more detail about these parameters, see Unsatisfactory Optimization of Subproblems .

Using Node Files

On difficult models that generate a great number of nodes in the tree, the amount of available memory for node storage can become a limiting factor. Node files can be an effective technique which uses disk space to augment RAM, at little or no penalty in terms of solution speed. The node-file storage-feature enables you to store some parts of the branch & cut tree in files while the branch & cut algorithm is being applied. If you use this feature, ILOG CPLEX will be able to explore more nodes within a smaller amount of computer memory. This feature includes several options to reduce the use of physical memory, and it entails a very small increase in runtime. Node-file storage as managed by ILOG CPLEX itself offers a much better option in terms of memory use and performance time than relying on swap space as managed by your operating system in this context. For more about the parameters controlling node files, see Use Node Files for Storage .