Apache OpenOffice (AOO) Bugzilla – Issue 124091
Solver detects linear models as nonlinear
Last modified: 2016-09-01 17:13:24 UTC
Created attachment 82374 [details] Example model attached, see bug description for model formulation On a simple LP model, both Excel and LibreOffice solve the model, but OpenOffice says it's nonlinear. OpenSolver which implements Clp/Cbc also solves the model implying this is not a COIN-OR problem but rather an issue prior to reaching COIN-OR. Example spreadsheet attached. Model: Max G2 By changing B2:C101 S.t. B2:B101 binary C2:E101 >= 0
G2=0 with AOO410m1(Build:9750) - Rev. 1560574 Rev.1560574 G2=1e30 with OpenOffice.org 3.0.1 Win 7
It looks like the line where the error is triggered is here: https://fisheye6.atlassian.com/browse/ooo/main/sccomp/source/solver/solver.cxx?r=1413471#to377 I believe the problem is that it is checking for linearity not analytically (as it probably should), but numerically, by changing the value of each variable by +/-2 and then checking to see whether the values of dependent cells change by approximately +/-2*coefficient. In the example sheet, it looks like there are cells that are sums and products of many other cells and the round-off error is probably accumulating to the point where it determines that something is non-linear because two numbers that should be equal are differing by more than some tolerance somewhere. This way of checking for linearity is not very robust. I guess that it would be pretty easy to fix this problem. I don't really see a reason why it should be difficult to determine whether the model is linear analytically, but I haven't looked at the big picture of how the model is being analyzed yet. I am one of the developers at COIN-OR and could look into this and other improvements to the interface if there is interest.
Thank you Ted
(In reply to Ted Ralphs from comment #2) > I am one of the developers at COIN-OR and could look into this and other > improvements to the interface if there is interest. Of course, you are more than welcome!
I was able to build the latest Open Office snapshot (trunk revision 1563031) on OS X (had to fix a few bugs that I reported). Commenting out the line that reports the error (model being nonlinear) allows the model attached here to solve successfully. I'll keep poking at it.
Created attachment 82876 [details] Workaround I did some testing to see what condition triggered the error and it doesn't appear to be caused by the linearity test but to the second condition: "fTwo is zero". This untested work-around should keep things going further.
I'm not sure I understand your patch, Pedro. To me, it seems as though both lines are part of the linearity test. I can't easily find where the approxEqual function is defined but from the comment in the code, I guess it involves taking the ratio of the two numbers so that it if one of them is zero, this causes a problem. Aside from that, the two lines are testing the same thing: fTwo = fInitial + 2.0 * fCoeff fInitial = fTwo - 2.0 * fCoeff I'm not sure I see why the two tests should be separate. It still just looks like a tolerance issue to me. The approxEqual function is saying that two values that should actually be considered equal (for this purpose) are not equal. Can you say more?
Sorry for the delay in answering, I am not really following the issue and I have been busy on other things. I only separated the checks to see which of the conditions is causing the solver to stop. Running my patch still won't get you a numerical answer: ____ No solution found. The epsilon level is invalid. ____ The reply is better though as the problem is not really in the linearity. Do we have more test cases?
"pfg" committed SVN revision 1704975 into trunk: i124091 - Drop check for nonlinearity
"pfg" committed SVN revision 1705873 into trunk: i124091 - Reinstate the check for nonlinearity but turn it into an option.
Changed to RESOLVED. Waiting verfication.