Issue 124091 - Solver detects linear models as nonlinear
Summary: Solver detects linear models as nonlinear
Alias: None
Product: Calc
Classification: Application
Component: editing (show other issues)
Version: 4.0.1
Hardware: All All
: P3 Normal (vote)
Target Milestone: ---
Assignee: AOO issues mailing list
QA Contact:
Keywords: regression
Depends on:
Reported: 2014-01-23 14:56 UTC by John Foreman
Modified: 2016-09-01 17:13 UTC (History)
4 users (show)

See Also:
Issue Type: DEFECT
Latest Confirmation in: 4.1.0-dev
Developer Difficulty: ---

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.
Description 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

B2:B101 binary
C2:E101 >= 0
Comment 1 Edwin Sharp 2014-01-23 20:39:41 UTC
G2=0 with
AOO410m1(Build:9750)  -  Rev. 1560574

G2=1e30 with 3.0.1

Win 7
Comment 2 Ted Ralphs 2014-01-24 05:57:43 UTC
It looks like the line where the error is triggered is here:

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.
Comment 3 Edwin Sharp 2014-01-24 08:00:09 UTC
Thank you Ted
Comment 4 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!
Comment 5 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.
Comment 6 Pedro Giffuni 2014-03-16 22:13:15 UTC
Created attachment 82876 [details]

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.
Comment 7 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?
Comment 8 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?
Comment 9 SVN Robot 2015-09-24 02:36:25 UTC
"pfg" committed SVN revision 1704975 into trunk:
i124091 - Drop check for nonlinearity
Comment 10 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.
Comment 11 Kay 2016-09-01 17:13:24 UTC
Changed to RESOLVED. Waiting verfication.