Apache OpenOffice (AOO) Bugzilla – Full Text Issue Listing |
Summary: | Need a solver | ||
---|---|---|---|
Product: | Calc | Reporter: | skiani <skiani> |
Component: | code | Assignee: | frank |
Status: | CLOSED FIXED | QA Contact: | issues@sc <issues> |
Severity: | Trivial | ||
Priority: | P3 | CC: | alex.thurgood, apulsifer, bettina.haberer, harald.schilly, issues, jimthompson5802, kamataki, kami911, khirano, le.farfadet.spatial, lohmaier, manens, mattfewins, mmeeks, norbert.notz, ooo, pagalmes.lists, rouben, stp, stx123, yoshimit |
Version: | OOo 1.0.1 | Keywords: | oooqa |
Target Milestone: | --- | ||
Hardware: | All | ||
OS: | All | ||
URL: | http://wiki.services.openoffice.org/wiki/Optimization_Solver | ||
Issue Type: | FEATURE | Latest Confirmation in: | --- |
Developer Difficulty: | --- | ||
Issue Depends on: | 70117 | ||
Issue Blocks: | 15522 | ||
Attachments: |
Description
skiani
2002-10-29 15:21:46 UTC
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 |