Cutting

There are several classes of cutting planes available for the Optimizer to tighten a MIP formulation: mixed integer Gomory cuts, mixed integer rounding (MIR) cuts, clique cuts, implied bound cuts, zero-half cuts, and more. Each class of cutting planes (or just cuts) can be tuned individually through a dedicated CUTSEP*STRATEGY control, for example CUTSEPMIRSTRATEGY, CUTSEPCOVERSTRATEGY, or CUTSEPZEROHALFSTRATEGY. These accept values: -2 (automatic enforced), -1 (automatic), 0 (off), 1 (conservative), 2 (moderate), and 3 (aggressive). The value -2 behaves like -1 but protects the individual separator from being overridden by the meta control CUTSEPSTRATEGY.

The meta control CUTSEPSTRATEGY applies a single level to all separators simultaneously and is the simplest lever for a broad adjustment. For instance, setting

CUTSEPSTRATEGY = 0
CUTSEPMIRSTRATEGY = -2
CUTSEPZEROHALFSTRATEGY = 2

will disable all cut separators, but enforce an automatic separation strategy for MIR cuts and a moderate separation strategy for zero-half cuts.

Cutting planes will, in general, be created and added to the formulation in several rounds on the root problem and occasionally during the branch-and-bound search.

When considering the number of rounds of cuts applied to the problem, all classes of cutting planes are partitioned into two main groups that can be controlled separately. The first group consists of cutting planes derived directly from the problem constraints (or from aggregations of the problem constraints), sometimes referred to as combinatorial cuts or structural cuts. Essentially, these are all cut classes other than mixed integer Gomory cuts and lift-and-project cuts. The related controls are CUTMAXROUNDS and CUTMAXTREEROUNDS. These controls set an upper limit on the number of rounds of cuts to apply, on the root node or an in-tree node, respectively. The default settings of -1 will usually allow for 20 or more rounds on the root node and just one round on an in-tree node.

The other main group of cuts is derived from rows of the simplex tableau of the optimal linear relaxation solution (they are not available for quadratic problems). These are mixed integer Gomory cuts or lift-and-project cuts. The corresponding controls to limit the number of rounds for these cuts are CUTGOMMAXROUNDS and CUTGOMMAXTREEROUNDS.

For cutting in the tree, another important control is CUTFREQ. It sets the frequency by which to apply cuts during the branch-and-bound tree search. When set to a value k, cutting will be applied to every k'th level of the tree. Leaving it at -1 will let the Optimizer decide whether to apply cuts at any given node. This default strategy tends to create more frequent cutting near the top of the tree. Note that a setting of 0 will completely disable cutting during the tree search. You can use the CUTDEPTH control to limit the maximum tree depth at which the Optimizer will apply cutting. A setting of k will disable cutting for any node deeper than level k in the tree.

Another crucial aspect of cutting is the choice of how many cuts to add to the node problem. The more cuts, the harder it becomes to resolve the continuous relaxation. There is a tradeoff between the additional effort in solving the relaxations and the strengthening provided by cuts. The CUTSTRATEGY control provides three pre-set levels to determine how many cuts to add to the problem:

-1

Automatic.

 0

Turn cuts off completely.

+1

Low level of cuts.

+2

Medium level of cuts.

+3

High level of cuts.

The output log from a solve will usually provide some hints on whether it is beneficial to increase the CUTSTRATEGY control. Consider the following example output from a solve:

 Its Type    BestSoln    BestBound   Sols    Add    Del     Gap      GInf   Time
a        -4250519213. -983637913.7      1                 76.86%        0      0
d        -4186315351. -983637913.7      2                 76.50%        0      0
   1  K  -4186315351. -2301857560.      2    734      0   45.01%      122      1
   2  K  -4186315351. -2444516200.      2    510    173   41.61%      103      1
   3  K  -4186315351. -2479120937.      2    447    353   40.78%       98      1
   4  K  -4186315351. -2486387651.      2    389    302   40.61%       91      1
...
  16  K  -4186315351. -2568819556.      2    295    286   38.64%       71      3
  17  K  -4186315351. -2570860713.      2    290    284   38.59%       74      4
  18  K  -4186315351. -2571188037.      2    281    266   38.58%       71      4
  19  K  -4186315351. -2575283602.      2    276    269   38.48%       61      4
  20  K  -4186315351. -2587960341.      2    277    511   38.18%       77      4

Here one can observe that the Optimizer keeps adding a substantial number of cuts in each round. This is a clear indicator that it has identified many more violated cuts than it is allowed to add by the default CUTSTRATEGY setting. The first thing to try on such a problem is to set CUTSTRATEGY = 3. Indeed for this problem, the solve is clearly improved:

 Its Type    BestSoln    BestBound   Sols    Add    Del     Gap      GInf   Time
a        -4250519213. -983637913.7      1                 76.86%        0      1
d        -4186315351. -983637913.7      2                 76.50%        0      1
   1  K  -4186315351. -2500370863.      2   1574      0   40.27%      122      1
   2  K  -4186315351. -2791609815.      2   2207    730   33.32%      104      2
   3  K  -4186315351. -3016999540.      2   3113   1755   27.93%       92      3
   4  K  -4186315351. -3082444620.      2   3969   2889   26.37%      107      4
...
d        -3746982101. -3413070439.      8                  8.91%        0     24
  16  K  -3746982101. -3421885848.      8   4245   4215    8.68%      104     24
  17  K  -3746982101. -3429939240.      8   4243   4240    8.46%      100     26
  18  K  -3746982101. -3437132243.      8   4234   4219    8.27%      105     28
  19  K  -3746982101. -3441666577.      8   4204   4160    8.15%      108     31
d        -3744370125. -3441666577.      9                  8.08%        0     34
  20  K  -3744370125. -3445582328.      9   4193   7561    7.98%      104     34

Here, the strengthening provided by the additional cuts has clearly improved the best bound. Another positive side effect is that this has helped the heuristics to find even better solutions. So overall the MIP gap improved from 38% to 8%. There is, of course, a cost to this, which is the increase in cutting time from 4 seconds to 34 seconds. But this is a fairly large problem for which the branch-and-bound search will easily take much more than 30 seconds, so the improvement is well worth it.

If the emphasis is on finding a good solution quickly, the cutting part can often be too expensive, and it frequently happens that the best bound is improved only marginally after the first few rounds of cuts. One could conclude that it should be safe to reduce the number of root cutting rounds by setting CUTMAXROUNDS to a smaller value. However, there is a close interplay between cut rounds and LNS heuristics. More rounds of root node cuts typically mean more LNS heuristic calls, with different reference solutions. Thus, while increasing or decreasing the number of cut rounds often has a huge impact on the speed at which solutions are found, it is not clear a priori in which direction the impact goes. Finally, it might sometimes be beneficial to reduce the amount of in-tree cutting through the CUTFREQ control, to speed up the number of nodes solved.

On the other hand, when the emphasis is on solving to optimality, cutting is often crucial in order to improve the best bound. Here on can try setting CUTSTRATEGY = 3. If cutting is useful on the root it is often beneficial in the tree as well. Try e.g. setting CUTFREQ = 4, to cut fairly frequently.

Cutting Controls Summary

CUTSTRATEGY

Amount of cuts to add to the problem, expressed as one of a preset number of levels (-1 3).

CUTMAXROUNDS, CUTMAXTREEROUNDS

Maximum number of rounds of structural cuts to apply on the root node and on in-tree nodes, respectively.

CUTGOMMAXROUNDS, CUTGOMMAXTREEROUNDS

Maximum number of rounds of Gomory/lift-and-project cuts to apply on the root node and on in-tree nodes, respectively.

CUTFREQ

Frequency of cutting during the tree search.

CUTDEPTH

Maximum depth of a node in the tree on which cutting can be applied.

CUTSEPSTRATEGY

Meta-control to set the aggressiveness of all cut separators at once (-1 3).

CUTSEPMIRSTRATEGY, CUTSEPCOVERSTRATEGY, CUTSEPZEROHALFSTRATEGY, ...

Per-separator aggressiveness controls for individual cut classes (-2 3).

CUTAGGROWS

Strategy for row aggregation used when separating MIR, lifted cover and Strong Chvatal-Gomory (CG) cuts (-1 4).

CUTFROMCUTROWS

Strategy to use cutting planes already in the matrix as base rows for separating new MIR, lifted cover and Strong CG cuts (-1 3).