Singleton Column wrong reduction/ constant computation

[olivierjuan]

Using Papilo 2.2.0 with only col singleton enabled I got an issue when reducing this problem.

It should be trivally reduced to 0 but instead it is trivially reduced to -10:

Minimize
 obj: 100000 x1 + 100000 x2
Subject To
 c1: - 0.000555555555555556 x1 + 0.000555555555555556 x2
     - 0.000555555555555556 x3 + 0.000555555555555556 x4  = 0
Bounds
 0 <= x3 <= 0.0001
 0 <= x4 <= 0.0001
End

ttt1.zip Attached is a zip file containing the lp file, mps file and params for papilo cli. I can reproduced it with older versions of papilo (2.1.0) at least

[alexhoen]

Hi Olivier,

Thanks for reporting first of all.

I am wondering which problem you want to specify. Should the variables x1 and x2 be free? If this is the case, then there are missing lines in the MPS file

BOUNDS
 UP bnd       x3                         0.0001
 UP bnd       x4                         0.0001
 FR bnd 	  x1
 FR bnd       x2
ENDATA

• If I run the problem as you uploaded it, then I get a infeasible solution Column 0 violates lower column bound () (-0.0001 ! >= 0). This is definitely a bug and I will look into it.
• If I add those to lines I get the unbounded problem min 200000 x2 -100000 x3 + 100000 x4. Then x1 need to be fixed to infinity to account for the unbounded problem. Though this is mathematical correct such cases should be avoided. WIll look also in that

[olivierjuan]

Hi, my name is Olivier actually.

no x1 and x2 are both positive which is the default in LP file if no bounds are given.

BTW, thank you for looking into it

[alexhoen]

Sorry :sob:

The solution should be the following

• skip substituting variable if the upper/lower-bound is implied and the (remaining) activity can be infinity
• then the constraint can be relaxed by getting rid of x3 and x4 so that it simplifies to -c * 0.0001 <=c x1 -c x2 =< 0.0001 c * ub
• Due to the transaction-based design in PaPILO this has to be done in subsequent calls since deleting one of the two variables locks the constraints making it unable to access it
• Deleting one variable transforms the constraint in a ranged row and unfortunaltey, applying the same logic for ranged rows is currently not applied. (and I noticed that there is a bug in triggering recalculation of the singletonCols)

this should be a first dirty hack that accounts for this specific problem. I will tune it and then merge it to main https://github.com/scipopt/papilo/tree/49-singleton-cols-on-infinity-activity

Unfortunately, making SingletonCols more sophisticated will take more time

[olivierjuan]

This is solving the reported issue but unfortunately, it does not solve the issue completely with ColSingleton.

Again a similar problem with only 2 variables:

Minimize
 obj: 999.940476190476 x1
Subject To
 c1: 0.000555555555555556 x1 + 0.000555555555555556 x2  = 0.0008
Bounds
      x2 Free
End

x1 is positive and the problem should be reduced to 0 but instead it is reduced to 1439.9142

49.zip

[alexhoen]

this was just a quick fix. I will look deeper into it to provide a more stable fix.

[alexhoen]

I found some time to look at this issue again and my initial claims were somehow false. The problem is that the problem is "numerical ill-conditioned" in that sense that the activity defined by the constraint is close to the feasible tolerance.

0.0001 * 0.000555555555555556 < = 9.9999999999999995e-07

Hence, PaPILO is allowed to set x3 to the upper-bound and then when calculating the value for the substituted variable for x1 it goes horribly wrong.

Scaling in PaPILO should actual work here, but unfortunately that is currently not implemented. (PaPILO is part of SCIP and there SCIP does the scaling for PaPILO) An alternativ would be increase the feasible tolerance so that PaPILO does not think it can fix x3 to the upper bound. Hence, this works:

# the feasibility tolerance  [Numerical: [0,0.10000000000000001]]
numerics.feastol = 9.9999999999999995e-09

To fix this in general this is unfortunately a little bit harder. Hope that work-around works for now. We try to find a consistent solution.

Regarding the second issue:

when I ran the instance from 49.zip on the current main branch I get a objective value:

problem is solved [optimal solution found] [objective value: 1.9514477459554253e-13 (double precision)]

In the process x1 got substituted, x2 fixed to the correct value. When re-caluclating x1 due to numerical inaccuracies of the compiler x1 is unfortunately a little bit more than 0. Since it is wihtin the feasible tolerance it would be okay by papilo. Nevertheless, we merged a commit that should resolve this issue.

If the issue persist please try the newest main branch and please report it happens again!

[alexhoen]

For primal presolving this issue is not fixed with merge-commit 72aa8c41.

The constraint is scaled after substituting the variable in the objective.

Feel free to reopen the issue if issue still persists