Issue 8808

Hi Falko,
1 4 U.
Peter

Even this issue is not covered by our PCD for 2.0 I consider this a
useful feature that should be discussed in the feature commission..

Started

Such a feature would be very useful!

Sorry, no chance to get a solver for the Q. 

It would be very useful.

Created attachment 16029 [details]
Demonstration prototype of a possible Solver implementation.

Usage note on the prototype spreadsheet SolverPrototype.sxc.  Do not run model 
within a browser, run-time errors occur.  Save spreadsheet on local disk drive 
and open spreadsheet from local drive.

Hi,

after a short look, I'd like to say 'Great work' and thanks for the efforts.

FRank

Hello Niklas, here is a prototype for a solver. Please have a look at it, thank
you. I set CC on bh.

Created attachment 16216 [details]
New version received from Jim

Hi, looks promising great work. I had some trouble with third test but maybe I'm
doing it wrong. Your approach is similar to Excel, you should take a look at
gnumeric's solver too, it has a slightly different approach.  Where do you
intend to ultimately store the run setup? Excel 2k automatically keeps the last
solver senario per sheet, this is useful but not perfect. It also allows for
saving the senario in a series of cells. It would be perferiable IMO to have a
solver function that has all the senario parameters and settings in one cell,
e.g. =solver(B2; max; B3:B8; (B9>1;B10<30;B11=int); 1000; 0.001; ...). That way
you can quickly setup optimizations for many rows or columns of you analysis.

Re: saving the optimization parameters.  The next iteration should include 
the "Load" and "Save" options to save to specific location on the worksheet. 

This feature is a really useful business tool. BUinsess users are still using
Excel because of the solver feature, and if we implement this, it will be one
less barrier to OOo being adopted in business.

Adding myself to CC.

Created attachment 20595 [details]
Some code which solve linear system.

Created attachment 20749 [details]
New version, improved memory gestion and adding over and under determined systems.

Created attachment 21035 [details]
Some minor improvments.

*** Issue 39387 has been marked as a duplicate of this issue. ***

Just to let people know, I've started doing some work on
maximization/minimization of linear/non-linear systems, plus some interface
work.  You can find the details and current status at:

http://kohei.us/ooo/solver/index.html

Kohei

Created attachment 26871 [details]
Solver UNO Component (UI demo)

This attachment contains what I have done so far.  I have implemented:

* UNO AWT Dialog for basic operations to define a constrained linear model.
* One linear optimization algorithm (revised simplex) for solving a constrained
linear model (included, but not yet linked to the main component).

Note: this is for UI demo purpose only!  It does not solve a model yet despite
what the name (solver!) suggests.  Ok, going forward...

My near-term plan (~2 months):

* Complete one additional linear algorithm (bounded revised simplex) which
yields higher performance on identical models.  But this algorithm requires a
slightly different model format, so some UI change may be necessary.

* Fix the ugliness of my UI code.  I have studied a great deal on how to write a
"good" C++ code after I did the initial UI coding, so, now that code looks very
disorganized and ugly! hence needs to be fixed.  This means my internal UI code
will change drastically in the next few months.

* Have the component actually use the enclosed LP algorithm to solve something.
 Again, that's the sole purpose of the existence of this component. Right? ;-)

My mid-term plan (~4-6 months):

* Complete a non-linear algorithm to solve (un)constrained non-linear models.
* Integrate Yoann's code for solving under-determined linear systems.

Of course, bug fixes must be done whenever they are discovered... *sigh*

Comments are welcome.

Kohei

Created attachment 27505 [details]
Solver component source code (rev. 62)

This new code implements all of my 2-month plan items plus some more.

Some highlights are:

* This version *does* solve a linear model by using the revised simplex method,
but it does so only in stdout.

* The code for the bounded revised simplex method is included, but not being
used from the UI yet.

* A prototype for unconstrained non-linear model by the Quasi-Newton BFGS is
included under numeric/python_code (yes it is written in Python).  Yet to be
finished and ported to C++ code.

* Lots of refinements in code.  Approximately 2000 lines have been added since
the last attachment.

Kohei

I've uploaded a new snapshot to my website:

http://kohei.us/ooo/solver/

This snapshot solves a constrained linear model, but not a non-linear model yet.
 I've also made a binary UNO package for Linux for those who want to test out
the program.

This feature was also one of the Google Summer of Code tasks, but unfortunately
we didn't get anything out of it.  So I'm doing from where I left off before the
summer.

Kohei

I'm attaching a small example that doesn't seem to work with your snapshot (the
values in the file are what is claimed as the solution).

Also, I seem to get a crash instead of an error message if a model is infeasible
(an unhandled ModelInfeasible exception).

But it's great to see real progress here.

Created attachment 29846 [details]
Example that doesn't work

Thanks Niklas for your quick feedback!

Catching a ModelInfeasible exception was supposed to be fixed with that
snapshot, but it must've slipped.  It's fixed now.

The scenario you've attached did indeed fail.  Luckily I've pin-pointed the
problem during my test and fixed it.  (It was due to the lambda calculation
routine incorrectly disallowing a zero value.)

A new snapshot (rev. 71) is up on my website with the above two issues fixed.

http://kohei.us/ooo/solver/

Kohei

*** Issue 56080 has been marked as a duplicate of this issue. ***

Just to give you guys an update:

My current focus is to make my linear algorithm (simplex for those are familiar)
more robust.  Since my last announcement here I have made many changes to my
code, and my solver is a lot better shape now.  But there is still much work
ahead.  But hopefully, after making several changes to my linear algorithm to my
satisfaction, I will start working on adding a non-linear support.

As usual, a binary package is available for Linux platform from my website:

http://kohei.us/ooo/solver/

The latest is revision 101.

Kohei

(warn: I didn't read the source code of the actual solver)

I was just asking myself if it may help if we use an external package such as
scipy.optimize (i am sure that there is a c++ version of this...):

http://www.scipy.org/documentation/apidocs/scipy/scipy.optimize.html
(BSD license but it may change)

I may I miss something so feel free to comment.

Good work kohei !

@manens: Thanks for the link.  Unfortunately, to use an external package it
needs to be submitted under JCA before I can read the code.  As I understand it,
we can not use BSD-licensed code because of its advertising clause.  But, if the
license is changed such that I could take a look at their implementation, I
would love to take a look for a good reference.

One interesting remark.  When I visited the link, I noticed that they used the
non-linear constrainted algorithm originally developed by Stephan Nash.  A while
ago I was contacted by his brother John Nash who is also in the operations
research field.  One of his advices for me was to take a look at his brother's
(S. Nash) publication as a reference for devising a constrained non-linear
algorithm, which I'm intending to do.

Kohei

I'm looking for somewhere to be involved and, with a background in OR, thought
this might be the place to start.  First comment though is that it would be
better to use existing optimisation code.

From http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html there
are three open source lp solvers:

    * CLP (linear) and SBB (integer), supervised by John Forrest. Current
versions are available under the Common Public License written by IBM
Corporation. They are part of the COIN-OR project which encompasses a variety of
software for operations research, especially optimization; COIN-OR was initially
sponsored by IBM but is now an independent non-profit organization.

    * GLPK (GNU Linear Programming Kit), supervised by Andrew Makhorin. Version
4.6 is available under the GNU General Public License, version 2 or higher. A
primal-dual interior point method is also provided. Input options include the
GNU MathProg language (a subset of AMPL).

    * lp_solve, supervised by by Kjell Eikland and Peter Notebaert. Version 5.1
is now available, under the GNU Lesser General Public License. Utilities are
provided for handling various input formats, including GLPK's MathProg modeling
language. Several alternative basis factorization packages can be used
interchangeably. 

GLPK and lp_solve both look pretty promising on the solver side, CLP looks a bit
funny.

@mayesk : would you be interested in writing a hook for those libraries you
suggested?  I'll give you a pointer of course.  --Kohei

Also not to forget the wiki page if you are interested.

http://wiki.services.openoffice.org/wiki/Optimization_Solver

@mayesk: i think a good solver is crucial for calc. an example of such
an integration of glpk and lp_solve for LP und QP is gnumeric. i suggest you
to have a look at their implementation: http://www.gnome.org/projects/gnumeric/

One important thing to comment: we can't use GPL'ed code.  While gnumeric's
solver is excellent it is a GPL'ed program.  This will also rule out GLPK as
it's GPL.

We could use LGPL'ed code, but such code would still have to be kept separate to
avoid licensing problem.  Please note that all code that needs to be integrated
into OO.o must be submitted under JCA.

I have already designed and developed a framework for solver facility that can
accommodate multiple algorithms, so I would advise extending it to add more
algorithms.  If someone is interested in using a 3rd party's optimization
library, try to hook it into the current framework.

If someone needs help to get started with the current framework, let me know so
that I can provide help.

Kohei

Created attachment 35881 [details]
patch set for scsolver

I was planning to upload this patch set after I get one remaining stuff done,
but anyway...

Current status: the bounded simplex algorithm that I've been working on is
nearing completion, but still needs some work in the initial solution search
routine (a rather tough one, I might add).  So, my plan is to finish that up
first, then perhaps look at integrating lp_solve into the mix.  I have to admit
things are moving slowly these days because of my class work.  But once that
finishes in May I'll try to pick up speed to move it along further.

@all: I haven't been keeping up to date with documenting my code since there
have been nobody showing interest to help me (except for folks at Novell).  But
if there is any interest in giving me a helping hand, I'll be glad to put
together some how-to docs for any brave soul.

Right now, my solver is a part of ooo-build - the build maintained by Novell and
other distro maintainers.  Compiling my solver code involves compiling the whole
suite because we are now in the process of integrating it into the main code
base.  The initial integration work has already been done.  This unfortunately
means that setting it up for hacking solver won't be easy but I think this step
is necessary at this stage.

I don't periodically report my status here, but if anybody wants to keep track
of my activity, here is the ChangeLog that I always update.

http://cvs.gnome.org/viewcvs/ooo-build/scratch/scsolver/ChangeLog?view=markup

For any Q's, just contact me.

Thanks,
Kohei

change issue type to PATCH, and change status to STARTED.

Hi all,

Ok.  Here is my short-term plan.  Instead of trying to finish my on-going
simplex algorithm (which will potentially take a long time to finish), I will
prioritize integration of lp_solve into the current solver framework so that at
least OO.o users can have a decent-quality solver available.

If anybody is already familiar with lp_solve, I'll be glad to receive any
suggestions, development help etc.

Thanks,
Kohei

All,

I have uploaded a new snapshot up on my website:

http://kohei.us/ooo/solver/

Note that, in this snapshot, you need to install two separate packages:
scsolver.uno.zip and lpsolve.uno.zip, or it will not function properly.

I haven't made a formal announcement in my blog yet due to time constraints
(which I will do shortly), but if you guys could try out this snapshot and give
me feedback I'd appreciate it.

The change since the last snapshot is minimal, but it now uses lp_solve as the
backend optimization engine.  So, you may have a better luck in solving some
complex models that my own algorithm could not.

Thanks guys,
Kohei

Now that OpenOffice 2 has finally made it natively to the Mac (NeoOffice 2 Alpha
is out), how about providing binary packages for that platform?
Building OOo (or Neo, for that matter) is an immensely tedious task not everyone
wants to go through...
I can't provide my support here, since my Mac would take far too long and I
don't have 40GB of spare HD storage.
Are UNO extensions even compatible with NeoOffice? How about Universal Binaries?

onitake: are you volunteering for this?  

I can only build for Linux because that's all the time and resource (read:
hardware) I have available.  But if you are interested in trying this out please
do.  I'm just volunteering for this without receiving any external support or
fund.  So, any help you can provide, please do provide it.  Thanks.

By the way, building ooo-build only takes around 3 to 5 GB of HD space, not
40GB.  In fact, the machine I used to use only had 20GB diskspace in total, but
I managed to build the whole suite and provide the binary package, just to give
you an idea.

Like I said, if you want to explore into Mac version, great.  If you don't, just
be patient until someone with time, resource and interest shows up and take on
the issue.

I've built OOo on Linux before, thus I didn't believe it either...
But the NeoOffice developers say so on their build page:
http://www.planamesa.com/neojava/en/build.php
(it's 20GB, actually, not 40)

Also, it seems there will be separate versions for PowerPC and Intel Macs. That
means, no Universal Binary of the Solver is needed.

What I'm asking myself, is there a way to only build the neccessary components
to create Uno plugins?

testing new version with OOo 2.0.2 (the version, which comes with ubuntu 6.06
... custom build for this debian flavour)
install: works, single button comes as a floating toolbar
testing: build a small example, nothing special. it crashed once while clicking
around but the second time it solved. it told me about a solution, but it only
calculated all to 0. 
i'll try another example, perhaps it will do some more then

@onitake: please see the separate email I sent to you. :-)

@mysteron: Not good.  You used the stock OO.o that came with Ubuntu, correct? 
That version may already have my Solver preinstalled which may be causing
conflict.  Do you see "Tools > Solver" entry?  If yes, then it has my Solver
pre-installed.

Can you send me the test case with your model saved on that document?  I'd like
to see if it's the component installation problem or something else.  Thanks.

well yes, the solver is installed. i've not seen it, nice.

i know the problem: i've entered integer values at the constraints. i changed it
to cell-references and now it works. i simply thought i can enter values in
those fields. at least there is no warning or explanation. 

in my opinion, those constraints should also work for ranges of cells compared
to a single value. in this ubuntu version it pops up a warning with an
incomplete message (warnung box should be two lines, but only one visible)

another problem: values in solver window should be saved in the document. in
present state (i talk about the ubuntu ooo version) they are only saved in the
running session, after reopening the document everything is forgotten.

but anyway. at least a start with much potential. 

@mysteron: You've raised two issues:

1) direct RHS (right-hand-side) value in a constraint should just work.

I agree with this.  I'll work on this to get the fix in by the next snapshot. 
The fix shouldn't be too complicated.

2) values in solver window should be saved in the document.

That's what the Save and Load buttons are for (do you have these buttons in your
Ubuntu version?)  When you hit Save, your solver model gets stored as a metadata
in your document, but note that you still need to save your document to commit
it into the file.  Maybe a nice information dialog telling the user that he/she
still needs to save the document to permanently save the model would be a nice
option.

Perhaps we can do it smarter by automatically loading the saved model into the
solver window when the window is opened for the first time.

Actually, I get a crash (unhandled std::out_of_range) now with the
solver_error.ods from above. Other files seem to work well.

Doesn't lp_solve allow integer constraints? Making use of that capability
certainly seems easier than implementing it yourself. Also, the implicit
non-negative constraint can probably be dropped easily.

nn: Oops.  I'll fix the unhandled out_of_range exception right away.  As to the
integer constraint and positive number constraint, I'll get those implemented as
part of the Options dialog work.  Thanks.  --Kohei

I've uploaded newer versions that fixes the crash bug.  Both packages need to be
updated.  The crash occurred so frequently that I've removed the previous
version from my website. :/

Feedback & test appreciated.  --Kohei

Just to let you all know, I'm in the process of upstreaming my code via cws as
we speak.  May take a little while due to my unfamiliarity with the upstreaming
process, but it'll happen sooner or later.

Kohei

adding dependency to this issue...

*** Issue 74216 has been marked as a duplicate of this issue. ***

User Experience requested only minor string changes
(http://ux.openoffice.org/servlets/ReadMsg?list=discuss&msgNo=205), so we should
be able to get this into QA soon. Kohei, what's the current state of the
scsolver02 CWS?

Sorry about the late response.  I'm a little swamped with tasks at the moment. 
I'll take another look at the cws hopefully soon and see if there are any
remaining issues.

With all the noise that some people make around this not being integrated, it
seems we should try to finish this one before adding more oox details that still
need some time before integration anyway.

There are currently three issues with it:

1) Localization - currently we use resource manager from tools that is not UNO.
 Since there is now a UNO localization API, it makes sense to use it instead, to
make it a complete UNO component.

2) Custom menu build issue - there is an issue with rebuilding the module when
--enable-scsolver is given.  It keeps appending the Solver menu item everytime
it is rebuilt.  I haven't figured out how to fix that one yet.  Needs more time.

3) Licensing - there has been a concern among several potential contributors to
the scsolver about licensing of this component.  It would be better if we could
submit this component as a pure LGPL instead of under the JCA, to make it easier
to accept more contributions.

Non-JCA would mean it's not part of OOo, but rather a third-party component for
it (at least that's my understanding, someone correct me if I'm wrong). I'd very
much prefer to have it under JCA.

If the trick with tools resources works, I think we should leave it that way for
now, and change it later. I'd be happy to have almost anything integrated *now*,
so we can get this out of the second-class, ooo-build-only corner.

> Non-JCA would mean it's not part of OOo, but rather a third-party component
> for it (at least that's my understanding, someone correct me if I'm wrong).

Sure - there are plenty of bits of OO.o that are not under JCA and yet are
included: berkeleydb, big chunk of mozilla (at one stage), stlport, icu etc.
wrt. LGPL pieces: libxml2, libwpd, libegg jump to mind: so there should be no
issue there: but I guess, well worth checking with Sun legal, and there is the
'external' process I suppose: http://external.openoffice.org/

mmeeks, the examples *are* third-party libraries, not stuff that we (OOo) are
doing ourselves.

Non-JCA doesn't necessarily mean it's not part of OO.o.  In fact, it doesn't
really matter whether this piece is considered "external" or "part of OO.o", as
long as the functionality is provided with the OO.o.  Isn't that what matters
ultimately?

This Solver project has historically been a community effort - well, it's just
my own effort for 99.9% of the code.  And I'm a little concerned about the
possible overhead it might incur by making this too coupled with the main code
base (and the upstream development process, in particular).

I believe that, for the long term, we would benefit more by leaving this piece
external with a pure LGPL license, and use it as a means to encourage more
community participation.  We'll likely need a lot of help from those who are
specialized in this field to bring this piece to the next level, and I don't
think the current project structure is well optimized for that.

So, it would be great if someone could check with Sun legal if it's possible to
keep this code LGPL only, and integrate it as an external component.  I realize
there is no precedent for something like this, but trust me, it is worth the effort.

Kohei, we would be happy to help you with the integration of your contribution
in the main code base following the project guidelines. This implies shared
ownership and licensing under LGPL. We are confident that this is the way the
collaboration can do well with the best support from all participants.
As this seems not to be an option for you we start to implement a solution
within the spreadsheet project. You are welcome to join this effort.

Personally, I don't really see the difference in terms of licensing between this
functional module and the extensions which can also be licensed under the LGPL.
So might I ask Sun Legal, where does the problem lie ? Unless, of course, the
decision is one of a particular ownership strategy that Sun management has not
seen fit to divulge to the community ? As has been pointed out, there are
already other forms of licensing in parts of the code integrated within OOo,
under alternative permissive with certain restrictions licenses. Whilst I can
understand that having all the code "under one hat" so to speak, makes life a
hell of a lot easier for those who have to manage, sell, defend it, etc, we are
not exactly breaking new ground (in terms of code management) with a code
submission such as this, and indeed I would say again that is has been done
before, and could be done again. Obviously, this is not what is wanted by the
historical entity of the project.

Alex


And yes, I am a practising lawyer, and specialize in the field of intellectual
property.

Alex 

Kohei made the right decision. We look forward to using his solver in a fork of OO.o

OpenOffice.org and Sun. You failed in a spectacular and slow way. Goodbye. We
will tell the world about you.

sajer - not sure who you are, but it's rather unfair & too early to judge
failure or success; we have a lot to be grateful to Sun for; and (at least)
Novell is committed to continuing working with OO.o; I'd encourage you to follow
our lead in that too :-)

*** Issue 82426 has been marked as a duplicate of this issue. ***

send fix to kyledeaner1234@mail2web.com i will be joining the admin. also all 
fixes should be e-mailed to me

Target 3.0

The new implementation, based on lpsolve, is on CWS "calcsolver".

reassigning to QA for verification

Created attachment 51378 [details]
testcasespecification

Created attachment 51379 [details]
Testdocument

Created attachment 51380 [details]
Testdocument

Please find the spec here:
http://specs.openoffice.org/calc/features/Solver.odt

Found fixed on cws calcsolver using Solaris and Windows build

reopen. Cellrange selection not as in the testspecification and not what the
user would expect. Only the targetcell and value selection work. All the other
range-selection fields don't work as expected:
They all insert a cell-range, not a single cell (despite only a single cell
being selected), and all ranges are in the form of $C$3:D4 (i.e. first part
absolute addressing, the second part is missing the $ - for a single-cell
selection the dialog would show $C$3:C3

So: Addressing-type is wrong, and it allows a range for the limiting conditions,
whereas a single-cell selection is to be expected.

forgot: I tried with DEV300_m28 on linux and mac

Hi,

this Issue is fixed as the Solver is implemented.

The strange references problem is Issue 92030 .

Frank

integrated in OOo3.o

Created attachment 70502

Created attachment 71271

Created attachment 71330