Cuts are constraints added to a model to restrict (cut away) noninteger solutions that would otherwise be solutions of the LP relaxation. The addition of cuts usually reduces the number of branches needed to solve a MIP.

In the following descriptions of cuts, the term subproblem includes the root node (that is, the LP relaxation). Cuts are most frequently seen at the root node, but they may be added by ILOG CPLEX at other nodes as conditions warrant.

ILOG CPLEX generates its cuts in such a way that they are valid for all subproblems, even when they are discovered during analysis of a particular subproblem. If the solution to a subproblem violates one of the subsequent cuts, ILOG CPLEX may add an LP constraint to reflect this condition.

A clique is a relationship among a group of binary variables such that at most one variable in the group can be positive in any integer feasible solution. Before optimization starts, ILOG CPLEX constructs a graph representing these relationships and finds maximal cliques in the graph.

If a constraint takes the form of a knapsack constraint (that is, a sum of binary variables with nonnegative coefficients less than or equal to a nonnegative right-hand side), then there is a minimal cover associated with the constraint. A minimal cover is a subset of the variables of the inequality such that if all the subset variables were set to one, the knapsack constraint would be violated, but if any one subset variable were excluded, the constraint would be satisfied. ILOG CPLEX can generate a constraint corresponding to this condition, and this cut is called a cover cut.

A MIP problem can be divided into two subproblems with disjunctive feasible regions of their LP relaxations by branching on an integer variable. Disjunctive cuts are inequalities valid for the feasible regions of LP relaxations of the subproblems, but not valid for the feasible region of LP relaxation of the MIP problem.

Flow covers are generated from constraints that contain continuous variables, where the continuous variables have variable upper bounds that are zero or positive depending on the setting of associated binary variables. The idea of a flow cover comes from considering the constraint containing the continuous variables as describing a single node in a network where the continuous variables are in-flows and out-flows. The flows will be on or off depending on the settings of the associated binary variables for the variable upper bounds. The flows and the demand at the single node imply a knapsack constraint. That knapsack constraint is then used to generate a cover cut on the flows (that is, on the continuous variables and their variable upper bounds).

Flow path cuts are generated by considering a set of constraints containing the continuous variables that describe a path structure in a network, where the constraints are nodes and the continuous variables are in-flows and out-flows. The flows will be on or off depending on the settings of the associated binary variables.

Gomory fractional cuts are generated by applying integer rounding on a pivot row in the optimal LP tableau for a (basic) integer variable with a fractional solution value.

A GUB constraint for a set of binary variables is a sum of variables less than or equal to one. If the variables in a GUB constraint are also members of a knapsack constraint, then the minimal cover can be selected with the additional consideration that at most one of the members of the GUB constraint can be one in a solution. This additional restriction makes the GUB cover cuts stronger (that is, more restrictive) than ordinary cover cuts.

In some models, binary variables imply bounds on continuous variables. ILOG CPLEX generates potential cuts to reflect these relationships.

MIR cuts are generated by applying integer rounding on the coefficients of integer variables and the right-hand side of a constraint.

Each time ILOG CPLEX adds a cut, the subproblem is re-optimized. CPLEX repeats the process of adding cuts at a node until it finds no further effective cuts. It then selects the branching variable for the subproblem.

Parameters control the way each class of cuts is used. Those parameters are listed in Table 5.4.

The default value of each of those parameters is 0 (zero). By default, ILOG CPLEX automatically determines how often (if at all) it should try to generate that class of cut. A setting of -1 indicates that no cuts of the class should be generated; a setting of 1 indicates that cuts of the class should be generated moderately; and a setting of 2 indicates that cuts of the class should be generated aggressively. For disjunctive cuts, a setting of 3 is permitted, which indicates that disjunctive cuts should be generated very aggressively.

In the Interactive Optimizer, the command set mip cuts all i applies the value i to all classes of cut parameters. That is, you can set them all at once.

The cuts-factor parameter controls the number of cuts ILOG CPLEX adds to the model. The problem can grow to cuts-factor times the original number of rows in the model (or in the presolved model, if the presolver is active). Thus, a cuts-factor of 1.0 would mean that no cuts will be generated, which may be a more convenient way of turning off all cuts than setting them individually. The default cuts-factor value of 4.0 works well in most cases, as it allows a generous number of cuts while in rare instances it also serves to limit unchecked growth in the problem size.

Set the cuts-factor parameter in the:

• Interactive Optimizer with the command set mip limits cutsfactor .

• Concert Technology Library with the function IloCplex::setParam(CutsFactor, n).

• Callable Library with the routine CPXsetdblparam(env, CPX_PARAM_CUTSFACTOR, n).

The cuts aggregation parameter controls the number of constraints allowed to be aggregated for generating MIR and flow cover cuts. Set this parameter in the:

• Interactive Optimizer with the command set mip limits aggforcut .

• Concert Technology Library with the function IloCplex::setParam(AggCutLim, i).

• Callable Library with the routine CPXsetintparam(env, CPX_PARAM_AGGCUTLIM, i) .

The gomorypass parameter controls the number of passes for generating Gomory fractional cuts. Set this parameter in the:

• Interactive Optimizer with the command set mip limits gomorypass.

• Concert Technology Library with the function IloCplex::setParam(FracPass, i).

• Callable Library with the routine CPXsetintparam(env, CPX_PARAM_FRACPASS, i).

The parameter will not have any effect if the parameter for set mip cuts gomory has a nonzero value. The gomorycand parameter controls the number of variable candidates to be considered for generating Gomory fractional cuts. Set this parameter in the:

• Interactive Optimizer with the command set mip limits gomorycand.

• Concert Technology Library with the function IloCplex::setParam(FracCand, i).

• Callable Library with the routine CPXsetintparam(env, CPX_PARAM_FRACCAND, i).