How does presolve work?

Presolve transforms your model into an equivalent model that theoretically has the following properties:

• The presolved model is infeasible if and only if the original model is infeasible.
• The presolved model is unbounded if and only if the original model is unbounded.
• If the presolved model has an optimal solution, then its objective value is identical to the optimal objective value of the original model.
• Any feasible (or optimal) solution of the presolved model can be mapped to a feasible (or optimal) solution of the original model.

Moreover, the goal of presolve is that the presolved model will be smaller and easier to solve.

The optimize() function calls presolve to generate a presolved model p with the properties above and an "uncrush" mapping u: p -> m that can be used to map solutions of the presolved model p back to solutions of the original model m. Then, the presolved model is solved to find an optimal solution s' of p. Afterwards, this solution s' is mapped back to the original model by applying s := u(s').

Now, for numerical reasons, the properties above may not exactly be true, which means that s might be slightly infeasible or slightly sub-optimal for m. In this case (if s' came from a simplex solve or a barrier solve with crossover), we perform a few additional simplex iterations on the original model m starting from the basis that corresponds to s, in order to clean up infeasibilities and recover optimality.

The method Model.presolve() in the Gurobi Python interface returns a model p that has the properties above. This model might be a little bit different from the one of optimize(), due to some technical reasons.

If you call p = m.presolve() followed by p.optimize(), you will get an optimal solution for p, and this solution will have the same objective value as an optimal solution for m. But because you do not have access to the mapping u: p -> m, you cannot convert this solution for p back into a solution for m.

Many of the variables in p will be equivalent to the variables in m, which means that the mapping for these variables will be the identity function, but this is not true for all variables. For example, one presolve reduction is the "parallel columns" reduction. This merges two variables with identical objective and constraint coefficients into a single variable. For example, consider this problem:

max  3 x1 + 3 x2 + 4 y + 5 z 
s.t. 2 x1 + 2 x2 + 3 y       <= 4 
     5 x1 + 5 x2       + 2 z <= 7 
                   2 y +   z <= 2 
     0 <= x1 <= 7 
     0 <= x2 <= 10

Variables x1 and x2 are "parallel". Presolve replaces these variables by a single variable x, which represents the sum of the two original variables:

max  3 x + 4 y + 5 z 
s.t. 2 x + 3 y       <= 4 
     5 x       + 2 z <= 7 
           2 y +   z <= 2 
     0 <= x <= 17 

Assume there is a solution with x=15 for this model. The uncrush function u could map this solution to x1=7, x2=8.

As a user, you would only see in this presolved model that there is some variable x that you weren't aware of and that this variable has a solution value of 15. You don't know how to get the solution values for your original variables x1 and x2.

Having said this, the presolve() method is mostly a debugging tool. Usually, you would write out this model to an *.lp file and inspect it manually.

Further information

• What does "Presolve: All rows and columns removed" mean?
• How do I export a model from Gurobi?
• Presolve Reductions in Mixed Integer Programming (report, 2016)
• What are dual reductions?