Incorrect results: column constrained to equal zero is solved as non-zero

[natebragg]

In the attached mps file, column 28 is clearly constrained to be equal to zero on row 29. However, after reading and solving this file, the column solution gives a value of 1.0000000000000007.

opEq.mps.gz

[natebragg]

And here's a simplified version that assigns column 28 a value of 1.0000000000000002 opEq2.mps.gz

Note that I tried to condense this further by combining two constraints but the issue went away. So, I think this might be close to a minimal example.

[jjhforrest]

This a tolerance/scaling issue.  The problem is actually infeasible as given if preprocessing is turned off.  With preprocessing Cbc gives message -

Cgl0013I Postprocessed model is infeasible - possible tolerance issue - try without preprocessing

During preprocessing the problem is reduced to one with one binary variable - part of debug mps file is -

 L  R0000000  L  R0000001 COLUMNS     C0000000  OBJROW    1.     C0000000  R0000000  536870911.     C0000000  R0000001   -1.00000101 RHS     RHS       R0000000  536870910.     RHS       R0000001   -1.00000101

which is satisfied with C0000000 at a value of 0.9999999981373549.

As there is only one binary variable left, it is easy to see that the problem is infeasible, but in general preprocessing fixes such variables

• that is the point of preprocessing.  It would be nearly impossible with a mixture of continuous and integer variables and a lot of work in general.

Hopefully the Cgl0013 message is enough to alert a user that  there is a scaling problem. If you just solve the problem as an LP the solution has -

      0 C0000000 1.862647e-09       1 C0000001    1.862647e-09       3 C0000003                        1       6 C0000006    1.862647e-09

 and has all integer variables within a tolerance of integrality.

On 02/05/2022 19:35, natebragg wrote:

In the attached mps file, column 28 is clearly constrained to be equal to zero on row 29. However, after reading and solving this file, the column solution gives a value of 1.0000000000000007.

opEq.mps.gz https://github.com/coin-or/Cbc/files/8605302/opEq.mps.gz

— Reply to this email directly, view it on GitHub https://github.com/coin-or/Cbc/issues/497, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABWJYHGFPY4W7T5EQZRDNZ3VIAOABANCNFSM5U4X5RJQ. You are receiving this because you are subscribed to this thread.Message ID: @.***>

[natebragg]

Thank you for the detailed explanation. However, it's left me confused. I read your response as stating that the preprocessing step turns an infeasible problem into a feasible one with an incorrect solution. Why exactly would I want that? If I have an infeasible problem, wouldn't I want to know that?

Also, forgive my ignorance, but if C0000000 has a solution of ~1, then how is it easy to see that the problem is infeasible? There is no indication as far as I can see in the result of running CBC that the problem was supposed to be infeasible.

Also, how do I turn off preprocessing programmatically to verify this myself?

[jjhforrest]

On 03/05/2022 14:48, natebragg wrote:

Thank you for the detailed explanation. However, it's left me confused. I read your response as stating that the preprocessing step turns an infeasible problem into a feasible one with an incorrect solution. Why exactly would I want that? If I have an infeasible problem, wouldn't I want to know that?

You don't want it - that is why you get message Cgl0013I Postprocessed model is infeasible - possible tolerance issue - try without preprocessing

Also, forgive my ignorance, but if C0000000 has a solution of ~1, then how is it easy to see that the problem is infeasible?

—

 L R0000000     C0000000  R0000000  536870911.

RHS     RHS       R0000000  536870910.

is feasible with C0000000 approximately1 but not when == 1 as 536870911

536870910 by 1

Reply to this email directly, view it on GitHub https://github.com/coin-or/Cbc/issues/497#issuecomment-1116121133, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABWJYHG5DROHN2LNQDDIOETVIEVCNANCNFSM5U4X5RJQ. You are receiving this because you commented.Message ID: @.***>

[natebragg]

I see that now, but how can I tell this programmatically? I've embedded CBC as a solver within another context, and I'm controlling it programmatically using the functions exposed in Cbc_C_Interface.h; there seems to be no way to get this status as such. In practice, a human being won't be reviewing the warning messages printed to standard out as I have to turn logging off. The functions I'm calling all indicate that the problem succeeded.

Also, it seems that turning off preprocessing programmatically is done using Cbc_setParameter(model, "preprocess", "off"); is there any documentation about what each of the various options do? I could only find their values by looking in CbcParameters.cpp.

[jjhforrest]

On 03/05/2022 15:11, natebragg wrote:

I see that now, but how can I tell this programmatically? I've embedded CBC as a solver within another context, and I'm controlling it programmatically using the functions exposed in Cbc_C_Interface.h; there seems to be no way to get this status as such. In practice, a human being won't be reviewing the warning messages printed to standard out as I have to turn logging off. The functions I'm calling all indicate that the problem succeeded.

I never use the C interface, but you should be able to register a callback to notice that Cgl0013.

Also, how do I turn preprocessing off programmatically? That seems to be the solution to my problem.

  Cbc_setParameter( mip, "preprocess", "off" );

— Reply to this email directly, view it on GitHub https://github.com/coin-or/Cbc/issues/497#issuecomment-1116147268, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABWJYHCQ4MELORO42CBUHBLVIEX2LANCNFSM5U4X5RJQ. You are receiving this because you commented.Message ID: @.***>

[natebragg]

While trying to find out where my program generation is having issues, I have reduced the problem to the following two programs, which between them have only a single difference: in one, column 14 has BV bounds, the other it has FX. With preprocessing off, the BV version has a solution but the FX version is infeasible. This seems like it should not be possible. The logs are very unrevealing. This seems like it has to be a bug, so I'm wondering how I went wrong. Any help?

The program is:

y = 1
(1 - x) * y = 0

where x is binary and y is either an integer or continuous, and to multiply I take the convex relaxation using McCormick envelopes. This seems like it should solve whether y is an integer or not.

opEqCont.mps.gz opEqInt.mps.gz

[jjhforrest]

FX means fixed to 1.  The solution with BV has C0000014 at value 0

The equation R0000008 is C14==0

The continuous relaxation of BV is UP 1.0

On 04/05/2022 00:46, natebragg wrote:

While trying to find out where my program generation is having issues, I have reduced the problem to the following two programs, which between them have only a single difference: in one, column 14 has BV bounds, the other it has FX. With preprocessing off, the BV version has a solution but the FX version is infeasible. This seems like it should not be possible. The logs are very unrevealing. This seems like it has to be a bug, so I'm wondering how I went wrong. Any help?

The program is:

|y = 1 (1 - x) * y = 0 |

where x is binary and y is either an integer or continuous, and to multiply I take the convex relaxation using McCormick envelopes. This seems like it should solve whether y is an integer or not.

opEqCont.mps.gz https://github.com/coin-or/Cbc/files/8616897/opEqCont.mps.gz opEqInt.mps.gz https://github.com/coin-or/Cbc/files/8616898/opEqInt.mps.gz

— Reply to this email directly, view it on GitHub https://github.com/coin-or/Cbc/issues/497#issuecomment-1116765972, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABWJYHHZ33NHIRFXL2QM22TVIG3DXANCNFSM5U4X5RJQ. You are receiving this because you commented.Message ID: @.***>

[natebragg]

I retract my previous comments. I was confused.