Cutting

There are several classes of cutting plane algorithms available for the Optimizer to tighten a MIP formulation. Cutting planes (or just cuts) 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.

The naming of the controls governing cutting reflects their historical legacy and can be slightly misleading. What is referred to in the Xpress Optimizer as cover cuts started out as knapsack cover cuts but will today include several other classes of cuts, such as mixed integer rounding (MIR) cuts, clique cuts, flow-path cuts, multi-commodity flow (MCF) cuts, zero-half cuts, and more. These are all cuts derived directly from the problem constraints, sometimes referred to as combinatorial cuts. The related controls are called COVERCUTS and TREECOVERCUTS. 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 roughly 20 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 GOMORYCUTS and TREEGOMORYCUTS.

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. Once could conclude that it should be safe to reduce the number of rounds by setting COVERCUTS to a smaller number. However, there is a close interplay between cut rounds and local search heuristics. More rounds of root node cuts typically mean more local search heuristic calls, with different reference solutions. Thus, while increasinf 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).

CUTFREQ

Frequency of cutting during the tree search.

CUTDEPTH

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

COVERCUTS, TREECOVERCUTS

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

GOMCUTS, TREEGOMCUTS

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

CUTSELECT, TREECUTSELECT, MCFCUTSTRATEGY

Provide detailed control of the structural cuts created during the MIP solve.