Issues with presolving an LP problem

[Jamie Noss]

Continuing from

https://groups.google.com/forum/#!searchin/gurobi/memory%7Csort:date/gurobi/0VhfVay3wHw/j4z4EEOqGQAJ

and

https://groups.google.com/forum/#!searchin/gurobi/memory/gurobi/lr2uUwcqkwU/0sTxGTCcpxcJ

So, I'm solving an LP problem but am using the barrier method. I'm finding a few issues with the consistency between explicitly calling presolve and/or letting optimize() call presolve() (I'll open a new thread for that though).  I'm also seeing a mem consumption issue. If you look at the plot below, it appears that mem is not being discarded as you have stated. Everything post the black verticle line is either a call to Model.optimize() or Model.presolve(). Evering to the left is building and adding the constraints to the model.

Presolve called only by optimize:

gc.collect()

m.optimize()

Explicit presolve and also by optimize:

m = m.presolve()

m.Params.Presolve = 1

gc.collect()

m.optimize()

Explicit presolve, not by optimize:

m = m.presolve()

m.Params.Presolve = 0

gc.collect()

m.optimize()

The final solutions also differ by an absolute tolerance of ~>0.3.

It looks to me like presolve isn't the 1st thing done by optimize(), might this be yield better consistency?

The problem sizes look odd to me:

### Presolve called only by optimize

```

presolve:  1549467495.668863

optimize:  1549467495.69171

Optimize a model with 34256 rows, 1264 columns and 40106720 nonzeros

Presolve removed 0 rows and 18392 columns (presolve time = 6s) ...

Presolve removed 0 rows and 18392 columns (presolve time = 10s) ...

Presolve removed 0 rows and 18392 columns

Presolve time: 11.99s

Presolved: 1264 rows, 17128 columns, 20053360 nonzeros

```

### Explicit presolve and also by optimize

```

presolve:  1549463229.307963

Presolve removed 18392 rows and 0 columns (presolve time = 5s) ...

Presolve removed 18392 rows and 0 columns

optimize:  1549463239.7434938

Optimize a model with 15864 rows, 1264 columns and 20052096 nonzeros

...

Presolve removed 0 rows and 0 columns (presolve time = 5s) ...

Presolve time: 6.45s

Presolved: 1264 rows, 17128 columns, 20053360 nonzeros

```

### Explicit presolve, not by optimize

```

presolve:  1549469150.320121

Presolve removed 18392 rows and 0 columns (presolve time = 6s) ...

Presolve removed 18392 rows and 0 columns (presolve time = 10s) ...

Presolve removed 18392 rows and 0 columns

optimize:  1549469161.0602088

Optimize a model with 15864 rows, 1264 columns and 20052096 nonzeros

```

I'm I even right in thinking that presolve returns the presolved AND remaining unsolved parts of the model, and not just the presolved soln? The doc just states that it returns the presolved version of the model.

When I run a much larger version (I'll add the number of NZs later) I get the following error from calling m.presolve()

Error code -1: Unable to create presolved model

But when I don't explicitly call presolve and just call m.optimize() it runs (for too long so I end up killing it) but passes the presolve stage.

There seem to be a few issues at hand here.

Thanks,

Jamie

[Jamie Noss]

Posting Tobia's response from https://groups.google.com/d/msg/gurobi/0VhfVay3wHw/R4si6KPOGQAJ (hope this is cool with you)

"Yes, calling presolve() expliticly is not necessarily 100% identical to the presolve that 

is called implicitly when you call optimize() directly. So, you may see slightly different 
memory usage patterns and different results. 

Moreover, when you just call optimize(), it will at the end translate the presolved 
solution back to the original model and check feasibility therein. If the solution turns 
out to violate some constraints, Gurobi will try to fix those violations on the original 
model. Of course, this will not be done if you pass the presolved model to optimize(), 
because then, optimize() doesn't know any "original" model on which it could check 
feasibility. 

The barrier algorithm is typically using much more memory than the simplex algorithm, 
mostly because it needs to explicitly build the AA^T system. 

Tobias"

[Jamie Noss]

So I guess this sounds like user error on my behalf.

However, I am left confused and have a few questions:

• What's the intended functionality of Model.presolve() if Model.presolve().optimize() doesn't yield a complete and/or correct solution such as Model.optimize() yields?
• Is it possible to do as I've intended, call Model.presolve().optimize() and get the correct result? The rationale is to reduce mem as (I presumed) both Model instances aren't needed.
• I no longer understand the semantics of presolve. If Model.presolve() pre-solves the problem such that it can remove nonzeros(?) (by solving them), why are they still needed by the solver optimize() for a correct solution, if they've already been solved? Doesn't this imply that they shouldn't have been removed?
• What does presolve actually do?

Many thanks for your help,

  Jamie

[Tobias Achterberg]

Presolve is transforming your original model into a presolved model that has (in theory)
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 m.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.

So, what is the purpose of the m.presolve() method? It returns a model p that has the
properties above, just like the one that is internally used by optimize(). It might be a
little bit different from the one of optimize(), which is due to some technical reasons.

If you now call p.optimize(), you will get am 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 identify 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 3x1 + 3x2 + 4y + 5z
s.t. 2x1 + 2x2 + 3y <= 4
5x1 + 5x2 + 2z <= 7
2y + z <= 2
0 <= x1 <= 7
0 <= x2 <= 10

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

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

Now, let's assume we have a solution with x = 15 for this model. Then, 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 this manually.



Best regards,

Tobias

[Jamie Noss]

Thank you for the very detailed response, this helps tremendously! I understand now. I'll revert back to just calling Model.optimize().

Thanks again.