Cutting
There are several classes of cutting plane algorithms available for use by the Optimizer to tighten a MILP 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 historic legacy and can lead to some confusion. 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, zero-half cuts, etc. These are all cuts derived directly from the constraints of the problem. The related controls are called COVERCUTS and TREECOVERCUTS. Both of these controls set an upper limit on the number of rounds of cuts to apply, on the root node or on 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 tree. Note that a setting of 0 will completely disable cutting during the tree search. The CUTDEPTH control can be used to limit the depth in the tree at which cutting will be applied. A setting of k will disable cutting for any node deeper than level k in the tree.
Another very important aspect of cutting is the choice of how many cuts to add to the node problem. The more cuts that are added, the harder it becomes to resolve the continuous relaxation. So the tradeoff is between the additional effort in solving the relaxations versus the strengthening of the problem provided by the 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 + -4250519213. -983637913.7 1 76.86% 0 0 + -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 + -4250519213. -983637913.7 1 76.86% 0 1 + -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 ... + -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 + -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. In such cases it should be safe to reduce the number of rounds, by setting COVERCUTS to a smaller number. There are counter examples, like the one illustrated above, where it is beneficial to increase cutting, simply because cutting is so strong here. Likewise, it might be beneficial to reduce the amount of in-tree cutting through the CUTFREQ control, in order 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.