Branch & Cut
Concept
IloCplex, like all CPLEX technologies, uses branch & cut search when solving mixed integer programming (MIP) models. The branch & cut search procedure manages a search tree consisting of nodes. Every node represents an LP or QP subproblem to be processed; that is, to be solved, be checked for integrality, and perhaps be further analyzed. Nodes are called active if they have not yet been processed. Once a node has been processed, it is no longer active. IloCplex processes active nodes in the tree until either no active nodes are available or some limit has been reached.
A branch is the creation of two new nodes from a parent node. Typically a branch is accomplished by modifying the bounds on a single variable, with the new bounds remaining in effect for that new node and for any of its descendants. For example, if a branch is made upon a binary variable, that is, one whose lower bound is 0 and whose upper bound is 1, then the result will be two new nodes, one node with a modified upper bound of 0 (the downward branch, in effect requiring this variable to take only the value 0), and the other node with a modified lower bound of 1 (the upward branch, placing the variable at 1). The two new nodes will thus have completely distinct solution domains.
A cut is a constraint added to the model. The purpose of adding any cut is to limit the size of the solution domain for the continuous LP or QP problems represented at the nodes, while not eliminating legal integer solutions. The desired outcome is thus to reduce the number of branches required to solve the MIP problem.
An example of a cut would be the observation that the following constraint involving three binary (0-1) variables:
can be strengthened by adding the following cut to the model:
No feasible integer solutions are ruled out by the cut, but some fractional solutions, for example (0.0, 0.4, 1.0), can no longer be obtained in any LP or QP subproblems at the nodes, possibly reducing the amount of searching needed.
The branch & cut method, then, consists of performing branches and applying cuts at the nodes of the tree. A more detailed outline of the steps involved follows.
The branch & cut tree is initialized to contain the root node as the only active node. The root node of the tree represents the entire problem, ignoring all of the explicit integrality requirements. Potential cuts are generated for the root node but, in the interest of keeping problem size reasonable, not all such cuts are applied to the model immediately. The notion of an incumbent solution, that is, the best known solution that satisfies all the integrality requirements, is established at this point for later use in the algorithm. Ordinarily, no such solution is available at this stage, but the user can specify a starting solution using the method setVectors(). Alternatively, when solving a sequence of modified problems, the user can set the parameter MIPStart to value 1 to indicate that the previous problem's solution should be used as a starting incumbent for the present problem.
When processing a node, IloCplex starts by solving the continuous relaxation of its subproblem; that is, the subproblem without integrality constraints. If the solution violates any cuts, IloCplex may add some or all of them to the node problem and resolves it. This is iterated until no more violated cuts are detected (or deemed worth adding at this time) by the algorithm. If at any point in the addition of cuts the node becomes infeasible, the node is pruned (that is, it is removed from the tree).
Otherwise, IloCplex checks if the solution of the node problem satisfies the integrality constraints. If so, and if its objective value is better than that of the current incumbent, the solution of the node problem is used as the new incumbent. If not, branching will occur, but first a heuristic method may be tried at this point, to see if a new incumbent can be inferred from the LP/QP solution at this node, and other methods of analysis may be performed on this node. The branch, when it occurs, is performed upon a variable whose present solution value violates its integrality requirement. This results in two new nodes being added to the tree for later processing.
Each node, after its relaxation is solved, possesses an optimal objective function value Z. At any given point in the algorithm, there is a node whose Z value is better (smaller, in the case of a minimization problem, or larger for a maximization problem) than all the others. This so-called Best Node value can be compared to the objective function value of the incumbent solution. The resulting MIP Gap, expressed as a percentage of the incumbent solution, serves as a measure of progress toward finding and proving optimality. When active nodes no longer exist, then these two values will have converged to each other, and the MIP Gap will thus be zero, signifying that optimality of the incumbent has been proven.
It is possible to tell IloCplex to terminate the branch & cut procedure sooner than a completed proof of optimality. For example, a time limit or a limit on the number of nodes to be processed can be set. Indeed, under default settings, IloCplex will terminate the search when the MIP Gap has been brought lower than 0.0001 (0.01%), because it is often the case that much computation is invested in moving the Best Node value after the eventual optimal incumbent has been located. This termination criterion on the MIP Gap can be changed by the user, of course.
