Understanding cutting planes and how to make use of them

The main idea behind cutting planes or valid inequalities is to cut a region in the feasible space of the LP relaxation, without eliminating any feasible integer solutions. Ideally, we aim to arrive to a state where we can cut all of the excess around the integer feasible points - ultimately yielding the convex hull of the integer feasible set - so the solution of the LP relaxation  becomes identical to an integer feasible solution. 

Creating weak formulations can often happen, especially when they represent the more natural way of thinking about the underlying business problem. See How to distinguish a weak MIP formulation? for more details.

Gurobi-implemented cutting planes are quite generic, in the sense that they look for common structures that show up very frequently. When you see lack of progress in the lower bound, one of the things to try is to raise or adjust the intensity of Gurobi cuts generation through the Cuts parameter and observe if they solve the issue. Here, it also makes sense to think about meta-parameters that might have an effect on cutting planes, e.g., MIPFocus. In many cases though, your model will have very specialized types of constraints where it is not easy for Gurobi to pick up what is the right way to strengthen the formulation. This is where the problem knowledge should be used to add strengthening cuts.

The two base guidelines for strengthening the formulation through additional cuts are the following:

1. We should be able to prove that the feasible region of the new formulation with the additional cuts is tighter than the feasible region of the original formulation. This proof is two-fold: 

• To prove that all feasible fractional solutions to the new formulation are also feasible with respect to the original formulation 

• To prove that there exists at least one fractional solution to the original formulation that is not feasible with respect to the new formulation 

  Example: To visually illustrate this concept, below are two figures showing the feasible space of the LP relaxation associated with two equivalent formulations. We can see that the LP relaxation of formulation 2 - the disaggregated form - is much stronger than that of formulation 1 - the aggregated form - according to the above criteria.

  Formulation 1:

  

  Formulation 2:

            

2.  Generally speaking, we aim at keeping all feasible integer solutions. However, on occasion, depending on the strengthening type, we might allow ourselves to cut off integer feasible solutions, as long as we don't eliminate all the optimal solutions of the model.  

   Example: Dual-based strengthening. Sometimes, we can base our strengthening arguments on the objective. By inspecting the objective function (e.g., a cost structure), we can make deductions about feasible solutions that would not be relevant nor interesting for the problem. We can use these arguments to tighten some variables coefficients. There, we potentially cut off feasible solutions and could conceivably cut off some optimal solutions as well, but never all optimal solutions.

   This is a valid technique that is used in the context of other solver functionalities, e.g., symmetry breaking. 

We give below some examples of globally valid strengthening ideas through additional valid cuts, based on the primal feasible region specified by the constraints in the model. In all of those examples, we don’t eliminate any optimal solution at all.  

Mixed-Integer Rounding (MIR) and Clique cuts

Consider the MIP model below and its undesirable LP relaxation solution:

One way to cut off this solution is to combine and round the constraints, resulting in adding a MIR cut as follows: 

Alternatively, one could think about representing the problem as a conflict graph, where nodes represent resources and edges indicate conflicts that prevent them from being used simultaneously. Consequently, at most one binary in a clique can be 1. This would result in a clique-type cut as follows: 

Disaggregation

Disaggregation is to separate a constraint to its component parts. Consider the following MIP problem:

The underlying logic here is that if any of the x variables has the value 1, then y has to be 1 as well. Conversely, if y is equal to 0, then all of the x variables should be 0. This logic could be represented by the below disaggregated form: 

There is a tradeoff around this particular type of cuts that could be summarized as follows:

This tradeoff is often debatable and highly depends on the objective and problem structure. One might even argue that the aggregated form allows MIP solvers to detect structures and make smarter deductions, and disaggregation might prevent this possibility. The general advice is to follow a selective disaggregation approach and gradually put its effect to the test. It is noteworthy to keep in mind that experimenting with disaggregation is mostly worthwhile, if proving optimality is of considerable interest for the application and business value.

Resolving disjunctions

The underlying motivation in this type of cuts is to reach additional (algebraic) derivations, by attempting to resolve disjunctions. The goal is to eventually assess the added value, or conversely the redundancy, of those additional conclusions.

Let us consider the following example:

By breaking down the disjunctive logic behind the absolute value function, taking into account the variables range, we can reach the following – seemingly trivial - valid deduction: 

The question here is whether this added final cut can help strengthen the formulation? To answer this question, we will translate the above example into a MIP model, by introducing a binary variable z (analogous to the way Indicator constraints in the General Simple Constraints are represented): 

If we consider the LP relaxation of the above MIP model, we can see that the added cut can help us eliminate the following fractional feasible solution: x=y=0, z=0.5. Hence, it results in a tighter LP feasible region. 

Helpful cuts for MIPs with only binary variables 

Gurobi considers a few types of cuts that are designed specifically for binaries and could be of particular help, e.g., zero-half cuts, clique cuts and cover cuts. 

Additionally, it is noteworthy that most models with binary variables have a fundamental underlying graph structure (e.g., conflict graphs). It makes sense to try to grasp this structure, if relevant, and consider what can be deduced in this context to help tighten the formulation (e.g., clique cuts).

Finally, it could be helpful in this on-and-off setup to distinguish between the decisions that could already be pre-computed versus the decisions that could be left for the model to decide upon. If some decisions could be fixed beforehand, this might significantly reduce the decision space and the scope of optimization by eliminating considerable parts of the model a-priori.

Our Tech Talks on how to improve weak formulations are a great way to get started with this topic:

• Tech Talk & Chat– Converting Weak to Strong MIP Formulations - Gurobi Optimization
• Tech Talk & Chat– Converting Weak to Strong MIP Formulations, Part II - Gurobi Optimization

The material above is highly based on the content covered there.

Furthermore, we recommend the following references to the interested reader:

• Wolsey, Laurence A. Integer programming. John Wiley & Sons, 2020. (Chapter 8 & 9)
• Achterberg, Tobias. Constraint integer programming. Diss. 2007. (Chapter 8)

Further information

• How to distinguish a weak MIP formulation? 
• General modeling tips to improve a MIP formulation