Issue 124091 - Solver detects linear models as nonlinear
Solver detects linear models as nonlinear
 Status: RESOLVED FIXED None Calc Application editing (show other issues) 4.0.1 All All P3 Normal (vote) --- AOO issues mailing list regression

 Reported: 2014-01-23 14:56 UTC by John Foreman 2016-09-01 17:13 UTC (History) 4 users (show) elish issues kschenk tkralphs DEFECT 4.1.0-dev ---

Attachments
Example model attached, see bug description for model formulation (282.10 KB, application/vnd.oasis.opendocument.spreadsheet)
2014-01-23 14:56 UTC, John Foreman
no flags Details
Workaround (1.19 KB, patch)
2014-03-16 22:13 UTC, Pedro Giffuni
no flags Details | Diff

 Note You need to log in before you can comment on or make changes to this issue.
 John Foreman 2014-01-23 14:56:53 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``` Edwin Sharp 2014-01-23 20:39:41 UTC ```G2=0 with AOO410m1(Build:9750) - Rev. 1560574 Rev.1560574 G2=1e30 with OpenOffice.org 3.0.1 Win 7``` Ted Ralphs 2014-01-24 05:57:43 UTC ```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.``` Edwin Sharp 2014-01-24 08:00:09 UTC `Thank you Ted` Ariel Constenla-Haile 2014-01-24 17:13:41 UTC ```(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!``` Ted Ralphs 2014-01-31 23:56:22 UTC `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.` Pedro Giffuni 2014-03-16 22:13:15 UTC ```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.``` Ted Ralphs 2014-03-19 04:41:17 UTC ```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?``` Pedro Giffuni 2014-03-26 19:47:54 UTC ```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?``` SVN Robot 2015-09-24 02:36:25 UTC ```"pfg" committed SVN revision 1704975 into trunk: i124091 - Drop check for nonlinearity``` SVN Robot 2015-09-29 15:04:01 UTC ```"pfg" committed SVN revision 1705873 into trunk: i124091 - Reinstate the check for nonlinearity but turn it into an option.``` Kay 2016-09-01 17:13:24 UTC `Changed to RESOLVED. Waiting verfication.`