Solver for Nonlinear Programming [BETA]

Provider:
Sun Microsystems, Inc.
Maintainer:
aksdb
Rating:
3.583335
Average: 3.6 (12 votes)
Application:
Calc
Tags:
calc, , solver, , optimization, , Nonlinear Programming,
Source code:
http://extensions.openoffice.org/source/browse/extensions/nlpsolver/
Post date:
Wednesday, 18 March, 2009 - 12:12
Statistics
Week: 139 - Month: 632 - Year: 7,597 - Timeline
Download extension
System Independent version - All releases
Compatible with OpenOffice 4: Unknown
User feedback:
Compatible with OpenOffice 4.x?

By default Calc ships with a solver engine for linear programming only. This allows the optimization of models to a certain degree.
However, if the formulas or constraints become more complex, nonlinear programming is required. That missing gap is now filled by the Solver for Nonlinear Programming extension.

Currently it incorporates two Evolutionary Algorithms which are able to handle floating point and integer variables as well as nonlinear constraints. For more information about their usage and restrictions, please refer to the documentation.

Both algorithms include work from Xiao-Feng Xie, who did a lot of research in this area.

The extension requires at least StarOffice 9 or OpenOffice.org 3.0.

Solver for Nonlinear Programming [BETA]

Version Operating system Compatibility Release date
0.9 System Independent 3.0, 3.1, 3.2, 3.3, 3.4 20/03/2009 - 06:51 More information Download

Comments

The Solver works very slow, but when I've read it's docs, I've say: "Cool! I like its idea"!
Now I unify the tables of measurement results by scale shift, multiplier and gamma-correction coefficients for every measure set. Because the tables are analog measurement results with some amount of noise and errors, it's hard to predict optimization function for the data. NLP Solver gives more precise result in comparison with Microsoft Office solver in my work. But the Microsoft solver seems to be extremely fast in comparison with this version of NLP-Solver.

that is the feature I waited for for so long, works better than I expected!

This is brilliant, and it works really well. Kudos for the documentation with code-examples!
Unfortunately, I should say did work really well... After upgrading from Intrepid (with manually installed OpenOffice 3.0) to Jaunty (which comes pre-packaged with OpenOffice 3.0) I can't get the extension to install properly. After accepting the license agreement, a "CannotRegisterImplementationException" error is thrown.

Well, there's no way to install this extension on OOO 3.0 with a message:
(com.sun.star.registry.CannotRegisterImplementationException)
{ { Message = "", Context = (com.sun.star.uno.XInterface) @0 } }

Well, it's a mess because the native solver is really very poor...

I'm using the 0.9 beta of the Sun non-linear solver with OOO 3.1 under Windows Vista-64 working with a 8 MB spreadsheet file.

I'm trying to maximize a value, and the solver runs and is able to improve and optimize my problem as the displayed Current Solution number in the enhanced Solver Status progress dialog states, but once either the solver computation completes the requested number of iterations, or after it hits the stagnation limits, or you hit Stop, the solver completes running and displays a much poorer (lower) result as the best one it asks whether to keep. So, for example, the optimization progress dialog might have found an optimal solution with a value of 0.49 in the progress dialog (which is very reasonable and probably correct), but the final chosen solution is a value of 0.35 once the optimization completes.

The basic problem happens with both evolutionary solvers included in the extension, with various combinations of optimizer options, optimizing both large and small numeric target values, and something similar happens for both minimizations and maximizations of the target cell. It looks like it is finding a nice solution, but displaying a fairly bad one instead of the best one in the end. The problems happen with both .ods files and .xls files.

I posted more details and a screenshot at the link below, in case anyone knows how I might workaround this or if I made some kind of obvious input error.
http://user.services.openoffice.org/en/forum/viewtopic.php?f=9&t=19079

[In case anyone is still seeing the mentioned install error, I fixed it by uninstalling and deleting the all of the ooo settings/dirs, downloading the full ooo 3.1 installer with Java, and finally reinstalling ooo and then the latest solver beta from here].

I tried using it with OO 3.01 on ubuntu jaunty and got the "(com.sun.star.registry.CannotRegisterImplementationException)
{ { Message = "", Context = (com.sun.star.uno.XInterface) @0 } }" error.
I also tried it with OO 3.1 (portable version from http://portableapps.com/) on windows XP and then it works fine.

To test the solver I tried some textbook examples with mixed succes. For example:

Maximize: x1 - x2
subject to: -x2^2 + x2 = 1
no reasonable solution was found (should be x1 = 0.5 and x2 = 1.25)

secondly a quadratic programming example

Min: (x1 - 6)^2 + (x2 - 8)^2
s.t.: x1 x2 x1 + 2*x2 x1 + x2 x1, x2 >=0
no good solution was found (shoud be x1 =4 and x2 = 4, the objective function is 20)

a good solution was found for:

Min: 20000 - 440*x1 - 300*x2 + 20*x1^2 + 12*x2^2 + x1*x2
st: x1 +x2 =100
x1>=0, x2>=0

I understand that with heuristic solvers global optima are not guaranteed but i expected a little more robustness from a heuristics solver.
On the other hand I am not that dissapointed because a spreadsheet combined with a NL heuristic solver would be realy nice and even better if it's open source and this is one of the first.

Let's see what the future will bring.

Which solver engine did you use? As I already wrote in the Wiki, I highly recommend DEPS for most numerical problems.
Let's start with the second (the quadratic programming) problem. I just rebuilt this scenario and the solver was able to deliver the expected value in all runs. Maybe you had a typo somewhere? Also make sure that you apply the variable bounds (x1 = 0) directly to the variable cells. Otherwise they are treated as constraints instead of bounds for the variables which makes a huge difference.

Regarding the first problem:
Don't forget that it is necessary to specify variable bounds (lower and upper limits). I specified 0

So yes, the solver can't magically solve all problems on its own. But with the right tuning (at least specifying variable bounds) it can behave very well ;-)

Thanks for your feedback!

After installing OO 3.1 on ubuntu jaunty I could install the solver without any problems.

So trying again to solve my test problems with the DEPS solver and checking for typos (none made), I've noticed that for the quadratic programming problem the global optimimum solution is found but only after clicking continu after the solver stagnates, however the solution does not stick to a single value after clicking continu again. Trying different values for stagnation limit and tolerance did not help.

I'm not sure what you mean when you say to apply variable bounds directly to the variable cells? If my variable x1 is in cell $B$11 I enter it in the left hand side of the solver dialog limiting conditions section and set the correct opperator and type in the value 7.

With the first problem I've tried your tips and this helps to some extent, the optimum is found but again the solver does not stick to a single value (or close to it) but keeps moving around it by large amounts unless i provide very tight bounds (but that is of course not helpfull because then I would know the the values of the variables and thus the solution and using a solver would be pointless).

Furthermore I've tried some simple pure LP, ILP, BIP and MIP problems with 2 to 5 variables and similar number of constraints which the standard linear solver can solve with ease (most i can do by hand). The same problem is encountered again with the DEPS solver not sticking to any optimum (local or global).

In my view the DEPS and SCO solver's strenght lies in the possibility that they could solve, or give a good enough solution to ill structured or poorly understood problems. At least from a viewpoint that solving is beyond the grasp of most peoples mathematical skills when for example 10 variables are involved.

with kind regards,
John

Great job. A big step ahead would be to make it possible to develop a post optimal analysis, as Frontline System's Solver does, because this feature is basic for a professional use of the extension.

Mariano A. Vizcaíno García

Yes, that is exactly what I mean. The solver only checks if the left-hand of a constraint matches one (or more) of the variable-cell-ranges. It then checks if the right-hand is a number or if the cell it refers to only contains a number (and not a formula). In that case it is interpreted as variable-bound, otherwise it's treated as normal constraint.
Theoretically it's also enough to have constraints only, but practically the bounds are necessary to allow a faster "startup" (since the bounds decide about the range, random numbers are generated from ... and if that range is essentially [-infinity to +infinity] then the solver takes ages until it pinned down a viable search region).

Hi all,

I tried to install the extension on OO3.1.1 (ooo310m19, build 9420) and Ubuntu 9.10 Karmic Koala and first ask for a Java Runtime Environment, after installing it now I get the following problem

can not activate factory because java.io.FileNotFoundException: /usr/lib/openoffice......

Hope this can be fixed
Cheers to all
Pablo

There is a known problem with Ubuntu and OpenOffice, which I wish the two communities would resolve once and for all. See
http://wiki.services.openoffice.org/wiki/Documentation/How_Tos/Installing_on_Debian_based_Distros
for details. Basically, the sick and only solution is to remove all of the Ubuntu OpenOffice, and reinstall from the OpenOffice distribution.

I did this, but the look and feel of filing is different. Also it took an entire day to track down the problem and get everything back.

Now this extension installs and works.

I've installed this extension on Ubuntu with 3.0.1 and Debian Lenny with 3.1.1 (from lenny-backports), it work fine in both cases. Described problem seems to be outdated

I finally installed the extension after reinstalling Ooo onto Ubuntu - it would be nice if the extension could be made distribution independent.

I cannot get it to work as I would expect with the problem I need to solve. I have found close solutions manually (trial and error), but I wanted the optimiser to get better locally extrema using the guesses in the cells to be changed. Essentially I am fitting a rational cubic Bezier curve to empirical data, with the target function being the sum of the squares of the error. Either I hit a stagnation limit on the first iteration, or no solution is found. I tried changing the stagnation limit, different comparators, different algorithms, but all yield the same result. I have tried adding constaints.

I note in one comment on this page a distinction between constraints and bounds, but it is not clear how this difference is conveyed to the solver.

Does it matter how I define the cells that are altered to affect the target cell? Eg, L2:O2, or L2;M2;N2;O2, or L2,M2,N2,O2
(A bit more of a hint on the syntax would not go amiss in the solver itself)

So I do not know whether there is a problem in my model or whether I am using the solver incorrectly.

Perhaps, someone could provide an example that makes minimal assumptions about mathematical knowledge using the samples in previous comments, showing how to set up the model, what happens when no constraints are added, how to set constraints, and how to tweak the solver.

The solver generates many solutions. But if a stagnation limit is hit or the user stops the solver, the solution candidates are not lost. Would it be possible for there to be a button that shows the solution candidates and for the user to choose which candidate to be inserted into the spreadsheet.

I install Solver for NLP.
Im using a macro for solver and I want to choose between NLP solving or traditional linear solving.
Depending on the conditions selected the problem needs NLP solving but I dont want to waste time when linear solving is good enough.

Thanks

Hello Sabena,

Does this answer your question?

[CODE]
Sub OptimizeDEPS
Dim Solver as Object
Set Solver =
CreateUnoService("com.sun.star.comp.Calc.NLPSolver.DEPSSolverImpl")
[/CODE]

OR:
com.sun.star.comp.Calc.NLPSolver.SCOSolverImpl

Thanks, great program, great extension, great community.
Best Regards

I tried this plug in this afternoon, both algorytm were unable to solve my equation, where should I submit the problem in order to get it fix?
best regards
Benjamin

This extension used to run fine with my earlier version of OpenOffice. Ever since installing Apache on my Mac, this solver extension no longer works.