Model status goes from infeasible to optimal when shutting down presolve

[lpierezan]

Describe the bug

The attached model is infeasible when run with a presolve and optimal when run without a presolve. Is this a bug or would it be expected somehow? Thanks

To Reproduce

Download and change the extension of the file attached below to mps

(note: attached as txt to be uploaded) model_min_custo_2.txt

Run the following code

import pyscipopt
from pyscipopt import Model

_mps_file = 'model_min_custo_2'

for presolve in [
    pyscipopt.SCIP_PARAMSETTING.DEFAULT,
    pyscipopt.SCIP_PARAMSETTING.OFF, 
]:
    model = Model()
    model.hideOutput()
    model.readProblem(f'{_mps_file}.mps')
    model.setPresolve(presolve)
    model.optimize()
    print(f'presolve {presolve} - status: {model.getStatus()}')

The result:

presolve 0 - status: infeasible
presolve 3 - status: optimal

Expected behavior The same final status regardless of whether or not you have presolve.

System

• OS: Win 11
• SCIP version: 8.0.4
• pyhton version: 3.9.16
• How did you install pyscipopt? pip

[Opt-Mucca]

That should not be expected behaviour..... Thanks for pointing this out! @alexhoen Is this of interest to you?

[alexhoen]

Thanks for reporting. That is obviously not the desired behavior. We will open a ticket and take a look at it. I could reproduce it, but it would be great if you could tell us the githash you were using.

btw the uploaded file is not viable, at least SCIP throws an error. I removed manually the "infinity" upper bound of x1 model_min_custo_2.txt

[Opt-Mucca]

The file should be viable after changing the infinity bound. I tested with some large values and the solution path for presolve enabled / disabled is the same as reported

[alexhoen]

Just wanted to upload a "viable" instance file

[lpierezan]

Hi @alexhoen , thanks for your interest.

Sharing some tests I did:

1. Running the original mps with gurobi returns optimal status. But I get a warning about the range of coefficients.

2. I changed in the mps a single coefficient, on the order of 2e-08, and also removed the bound 1E20. Then the gurobi warning disappears and the solution remains. But even so the scip continues to indicate infeasible.

model_min_custo_2_fix.txt

3. Running on HiGHS (with highspy 1.5.3) I also get optimal solution status, either with presolve on or off.

I believe the root of the problem is these large ranges in my instances, I will work to improve this. Thanks

[alexhoen]

We looked deeper into the problem and the statement that the problem is infeasible is actual correct. Nevertheless, a solution exists that is slightly infeasible. Since the violations are within epsilon tolerance per definition is also correct. So this is the rare case where these seemingly contradicting results are actually both correct.

Typically, presolving helps to get rid of numerical difficulties and is here able to return the correct result. If you want to convince yourself that the problem is infeasible you can try to run Exact-SCIP with exact rational arithmetic.

Nevertheless, while analyzing our problem we discovered a bug. Thanks for reporting.

[lpierezan]

Thanks for the analysis. I would expect a solution whose violations are within the specified tolerances to be considered feasible. So, in a way, using presolve indirectly implies smaller tolerances.

It's nice to know about Exact-SCIP, I will use it to study this further.

[alexhoen]

No that is the wrong conclusion. From a mathematical standpoint the instance is infeasible. Due to the arithmetic a small tolerance is allowed and this makes in this particular edge case the problem "feasible". Also I would argue that the goal of presolving is also to get rid of numerical difficulties which is the case here

[Joao-Dionisio]

Olá, @lpierezan :) Can this issue be closed?

[lpierezan]

Olá @Joao-Dionisio :) yes, thanks!

[lpierezan]

Hello everyone, especially @alexhoen, sorry for returning to this issue, but I did some more tests and would like to share my context better and ask a question.

Context

I have a multi-stage optimization pipeline. At each stage I solve a model and, if there is a viable solution, I just "fix" (*) the value of some variables and change the objective function to create the model for the next stage. So, from a mathematical point of view, if the first stage is viable, the following ones should be as well. But in practice, the viable solutions found by scip have small violations and in the next stage, presolve makes reductions that make the model infeasible (that's what it seems).

(*) "fix" actually means: places a lower and upper bound around the value of the variable in the solution, with a window of the order of 1e-4, to give more flexibility to the solver.

Question

Here is a model in nl format (generated by pyomo) at an intermediate stage of my pipeline. model_33.nl.txt

When running through the pyscipopt interface I get 'optimal' status regardless of the presolver being turned on or not. But only when presolve is turned on the log indicate at the end:

solution violates original bounds of variable <x318> [0,0.0001] solution value <-0.0001>
best solution is not feasible in original problem

• This error margin for the message (1e-4) is much greater than the configured tolerance (numerics/feastol = 1e-06).
• This occurs even when changing the emphasis to numerics.

Is this final message expected? Should I then interpret the solution returned by scip as infeasible despite the staus returned saying otherwise?

Thanks

System Information

I´m now with scip installed by conda:

[alexhoen]

We were able to locate the error and there were multiple problems:

• The constraint -10000000 x <= -10 was normalized to x >= c with c smaller than the feasible tolerance. Hence the constraint was incorrectly simplified to x >= 0.
• When calculating the activities (Chapter 2 in https://opus4.kobv.de/opus4-zib/files/6037/Presolve.pdf) of a constraint SCIP stores the activities and subtracts the coefficient a to obtain the activity for the subset S/a for Constraint Propagation. If a is a large number and the remaining numbers are very precise (multiple decimal digits) this can lead to a loss in precision since not enough memory is allocated.

In general, I would avoid defining coefficients by 8 decimal points since this can be numerically unstable.

In this particular case, defining a smaller feasible tolerance and epsilon and lowering the threshold to recalculate the activities should have resolved the issue.

Nevertheless, we will provide a fix addressing the above issues by skipping normalization if potential numerical unstable and increasing the precision to calculate the activity. We are waiting for the last performance evaluation on the fix before merging it. We will provide the hash so you can re-evaluate it.

EDIT: checking out the newest PaPILO version should help also since there were applied some bugfixes for numerical unstable problems.

Thanks for reporting and helping SCIP improve!!

[alexhoen]

This should be the commit that returns the correct solution: 6b2dd64cee2d728a673ffd6b854be8f873f11a94

Would be great if you could approve this :-)

[lpierezan]

Hi @alexhoen , thank you for this insightful analysis. I don't have the time at the moment to evaluate the proposed solution in depth, but I have already achieved better results based on your observations above. For me the issue can be closed, thank you!