Update on scsolver

Share Button

I’ve made several updates on scsolver that I think is worth mentioning.

First, I’ve finally put an option to solve to a specific value in addition to the minimize and maximize options. But this only works for linear programming models. For non-linear models, if you select to solve to a specific value, you’ll get “Goal not set” error message.

Also, I’ve noticed that the integer constraint option was not working at all; even when this option was selected, the integer constraint was not enforced. This is also fixed. It was just a simple silly mistake I had overlooked which caused this bug.

As far as the non-linear programming backend algorithm goes, I’ve put quite some effort into improving the algorithm a bit. Unfortunately not all of that improvement is available from the UI yet, but the line search algorithm used by the default quasi-Newton algorithm has been switched to a new one that uses quadratic fit line search. This one is a lot more robust than the old algorithm, which was basically a hand-crafted version of golden section search and was quite limiting. The quadratic fit also scales better with search distance. So, hopefully this will improve the overall stability of the algorithm a little. Having said that, writing a robust non-linear algorithm is a huge task, so I have no doubt in my mind that I still have a long way to go.

I will also drop the binary releases of scsolver on Linux, since it’s not easy to build a binary that works universally across different flavors and versions of Linux distros. Also, building from the sources is quite easy on Linux these days. If you have any doubt, see this page for the instructions on how to build it to see if you agree with me on it being “easy”.

Another way to get scsolver, if you are comfortable building the OOo itself from the sources, is to build ooo-build with the --enable-scsolver option. With that, you’ll get the scsolver package already integrated in Calc in place of Calc’s default Solver. So, there is now quite a few ways to get scsolver working on your system. By the way this build option also works on Windows.

Ok, I think that’s all the updates I need to mention. Now, what’s coming next? Well, I have a few things in mind. First, I’d like to re-organize the UI a little, to make it easier and more intuitive to switch between different algorithms. I’m well aware that no single algorithm can solve all models of different shapes and sizes, so I believe it’s important to provide different algorithms for different problem types, especially for non-linear problems. This also includes adding more specialized per-algorithm options to control its run-time behavior.

Another thing I have in mind is some sort of output window to show the running status of the iteration. This is useful for the backend algorithm to give real-time feedback of what’s going on.

I’d also like to do something about the terrible focus problem that the UI is suffering from right now. But quite frankly I don’t have a good idea on how to fix it yet. That may be a limitation of the current UNO AWT API. The worst case, I could reduce the number of child dialogs or avoid having multiple dialogs altogether. Anyway, this is in the back of my mind.

Of course, I will continue working on improving the non-linear algorithms. Currently the non-linear algorithms don’t deal with constraint problems yet, but I’ll get to that eventually.

scsolver code documentation

Share Button

Inspired by the on-line OOo code documentation that Thorsten put together, I have decided to do the same for my humble scsolver project. I’m pleasantly surprised how good of class diagram that doxygen generates with GraphViz, since the last time I tried doxygen the diagram was very minimalistic only because I didn’t have GraphViz available on my system. Still the digram looks a little too noisy for my taste, but it’s very impressive.

Calc Solver moved to Google Code

Share Button

I’ve moved the repository for my Calc Solver project out of ooo-build to Google Code. The new project home is http://code.google.com/p/scsolver/.

Calc Solver release (minor update)

Share Button

Only 3 days after the last release, I’m releasing a minor update of the Calc Solver extension. This release includes the following new additions:

  • Russian translation (contributed from Konstantin Lavrov)
  • German translation (ported from the ooo-build builtin version)
  • Menu integration to make it appear in Tools – Solver… below the Goal Seek menu entry (also contributed from Konstantin Lavrov)

I am very grateful to the impressive (and fast!) work that Konstantin did on the Russian translation as well as the menu integration improvement. Thank you, Konstantin! :-)

Calc Solver release

Share Button

I just released a new version of Calc Solver after more than a year since the last release. A lot of effort has gone into this release mostly to re-package it as a true UNO extension, and also to make it available for the Windows version of OO.o beginning with this release.

The UI has been localized for French and Japanese, thanks to Laurent Godard and Kazunari Hirano. Laurent also helped me on various UNO related issues, so I would really like to acknowledge his help. Thank you Laurent. :-) The system language should be automatically picked up and the appropriate translation texts should be displayed for English, French and Japanese. If this doesn’t work for you, please let me know.

The ride was quite bumpy, however, to get Solver to build on Windows. Since this was my first attempt to build anything non-trivial on Windows, I had to spend a few days (and nights) studying how the MSVC compiler works so that I could build a DLL. There was also an issue with multi-thread vs single-thread libraries, so I had to manually select the default libraries to be all single-threaded for the Solver as well as the lpsolve code. Not to mention I didn’t know how to set up a build environment since GNU make in cygwin didn’t work too reliably due to file path separator and the driver letter issues. In the end, I came up with a custom DOS batch script with everything hardcoded to semi-automate the build process, but that’s far from being elegant. I’m just wondering if there is any better way to set up a build environment on Windows… Question: what do Windows developers use these days to build C++ projects?

On the Linux side, the Solver extension installed and worked fine, but I’ve experienced a major problem with installing it in the Extension Manager UI. But as long as it’s installed from the command line using unopkg, it works fine. I still haven’t figured out why installing with the Extension Manager caused a problem but installing with unopkg didn’t.

Oh I almost forgot. If you use Go-oo version of OO.o (aka ooo-build) or any variant of it with my Solver already included, you don’t need to install this extension. It’s already there in Tools – Solver.

Anyway, enough talk. Enjoy! :-) And please report me any problems you may experience.

History of Calc Solver

Share Button

I’ve been trying to avoid writing a piece like this simply because if I wrote one, there would be a lot of bitterness involved, and I don’t like to put a blame on anybody. But when I saw a lot of confusion over the state of my Calc Solver in Barcelona (not the least of which is Louis’ announcement on Calc Solver for 3.0 during his keynote speech, which was truly a bad surprise for me), as well as this statement by Stefan Taxhet (st) in the issue page outlining Sun’s intention to duplicate the entire work I did (for free), I felt like it was time for me to explain what actually happened surrounding my effort to write an Optimization Solver for Calc.

Background (Why I started this)

Back when the OO.o project just started, the Calc team was requesting for two features from the community. One was advanced statistical analysis add-on, and the other was linear and non-linear optimization solver. Back then, I had already submitted more than a few bug-fix patches most of which were accepted and integrated (aside from this 2 and half year old patch which would probably never be integrated and I had already lost my hopes for) and started feeling comfortable with Calc’s code base. As the next step, I wanted to do something bigger, like a full-fledged feature, to try to prove to those Sun guys that they can count on hobbyist hackers writing a significant piece of code.

There was already some effort on writing a Solver for Calc well before I started working on my own (back in 2004). One was written in OO.o Basic (initiated by Jim Thompson), and the other was written in Java as a UNO component (Arun Gaikwad). Unfortunately Jim could not continue his work due to unavailability of spare time because of his other responsibilities (here is his last email post to sc-dev mailing list). Arun’s work was promising, but he insisted on integrating his work under GPL, which was not possible at the time because OO.o was licensed under SISSL/LGPL. The consensus back then was to convince Arun to submit his work under LGPL as an external component, which would legally permit OO.o to include it without compromising the license under which OO.o was distributed. But the effort to convince Arun failed, and we were back to square one.

During that time, I had already started my own effort on writing a Solver. My intention was to write a Solver component that would allow a clean integration into OO.o by writing one from scratch. But since I didn’t have any idea on how to write a solver, my effort started from buying books (I bought three) and studying on the subject of operations research. I didn’t want to announce it at that time simply because I didn’t even know whether I could go anywhere with this, so I worked on this in my spare time, studying the books, writing and testing the algorithms in Python (with the intention of re-writing them in C++ later), and investigating UNO’s AWT dialog framework because I didn’t want the kludge of adding a Basic layer to my component just for the dialogs.

After months of hacking, finally, the breakthrough happened. Since I felt comfortable that I could go somewhere with this effort of mine, I made an announcement on the sc-dev mailing list. Here is my first announcement on the sc-dev mailing list, and the later update. After that, I was making constant status updates in the Solver issue page as well as the sc-dev mailing list so that the world (and more importantly the Hamburg team) knows that I was working on this, to avoid duplication of effort. Everything was going reasonably well.

Google Summer of Code (GSOC) 2005

That year was the first year of Google Summer of Code. I didn’t think much about that event because I was not a student, and I didn’t think I would be involved in any way. But to my surprise, Sun decided to post the Solver task as one of the student projects, without even contacting me, despite the fact that they must have known my effort since I diligently made my update known to the public, both on the mailing list as well as the issue page. And the description of the task sounded as if the task was never touched by anyone. I was confused. I thought to myself, they could have at least contacted me how much work was already done before submitting that task to Google as if it was never touched. Because of that, I was forced to upload my interim code to the issue page to make it clear that part of the work that was planned for GSOC was already finished.

The very next day I uploaded my code, I received privately an angry email from someone who wanted to work on this task, but felt unfair because I uploaded my code to the issue page the very next day of the GSOC announcement. He was telling me how he didn’t appreciate what I did because he had just wasted 2 hours of his time writing a proposal. I felt humiliated. It was not I who decided to register that task as GSOC task, and I was not even contacted! And I am the one getting this angry email even after I put so much effort writing that code I wrote all in my spare time? Who is being unfair now!?

So, I forwarded that email to Erwin Tenhumburg, Louis Suarez Potts and Niklas Nebel, expressing my dissatisfaction on how they decided to register this task with GSOC even though the work was already on-going and they should have at least contacted me on the status of the effort. Only Erwin replied to my email. After exchanging several emails between Erwin and myself, they decided to put me as co-mentor of this GSOC task, and put Niklas as the Sun contact in case I need help from Sun. This is how I ended up mentoring the project for GSOC 2005. My memory is vague, but I believe I was the only mentor who was not a Sun employee but a free-lance hobbyist contributor that year.

But mentoring a student, totally on my own time was not very easy. I did my best, but unfortunately the project was not successful. In the end, there was no single line of code contributed from the student. Again, I don’t mean to put a blame on anyone, and if I had to pick one, I would certainly pick myself to take the blame. But it simply didn’t work out.

Post GSOC and Joining ooo-build

After the GSOC, I went back to what I was doing before the GSOC, which was to continue to improve the simplex algorithm for linear programming. At that time, there was one avid user of my Solver from Belgium (Ludvic Ansiaux), who was testing it for every version I released. He helped me sort out lots of bugs in my optimizer algorithm and some UI issues, so I have to give him a huge thank you for what he did. To this day, I have never received any help on testing as big as his.

But my progress was slowing down, and I was starting to realize the difficulty of writing a good Solver component, especially the backend optimizer code. I was simply losing my motivation because of lack of progress. But I forced myself to go on, simply because I didn’t want all of what had done to be wasted.

Then around January of 2006, Michael Meeks contacted me, telling me that he was interested in integrating my Solver code into ooo-build – the build used by Linux distributors (such as Debian, Ubuntu, SuSE) to ease the pain of integrating new code and distro-specific code into OO.o because of the upstream’s lack of interest in integrating patches. I was simply delighted, and didn’t think twice about joining them and making my Solver officially a part of ooo-build. It was also when the Solver code was morphed into a full fledged module named ‘scsolver’, after Michael reorganized my source tree to fit the OO.o build system. My excitement was back once again, and I was very delighted to see my Solver distributed in the default OO.o build that comes with openSuSE 10.1.

That’s also when I got my first software engineer position at SlickEdit after years of non-IT work in environmental science field. Unfortunately, however, this also meant that more time was spent on my new job, not because the new job required more hours but because my previous job didn’t constrain me as much in terms of work hours (in other words, I had more free time then). But I managed to go on improving the linear optimizer. In the end, however, with Michael’s suggestion, I decided to ditch my own linear optimizer in favor of using lp_solve maintained by Kjell Eikland and Peter Notebaert, and focus my effort on writing non-linear optimizer instead. That was actually the right decision because lp_solve is simply a much better optimizer than the one I wrote myself.

At that time, other Linux distributors such as Debian and Ubuntu started including my Solver, suffice it to say that brought more excitement to me.

GSOC 2006

Jody Goldberg decided to register this Solver project as a GSOC task for the year 2006, and he and I signed up as the co-mentors of this task. But unfortunately it didn’t attract any students that year, and as a consequence, there was no single line of code contributed. There was someone else from the Novell side assigned to work on this, and he did work on the code awhile as far as I can tell. But in the end there was no code either.

Then CWS was created

In September of 2006, Michael told me that it was now time to upstream the Solver code. He created a CWS for this (called scsolver02), and I began working toward putting my code into CWS. This was not an easy task, however. For one thing, I had to make the Solver related code a configure-time option (with --enable-scsolver option), which meant that I needed to find a way to make building of lpsolve and scsolver modules optional. Now, for someone who was not very familiar with OO.o’s quite convoluted, unorthodox build system, this seemed like a huge mountain of task (and it was). But I managed to find a way by looking at other optional modules and trying to make sense of it and do something similar for the lpsolve and scsolver modules.

Besides the above configure issue, I also needed to find a way to make the Solver menu item in the Tools menu optional, which as we discovered was not as easy as it seemed. But I had to solve these two issues because, obviously, without them being solved, there would be no chance of integration. So I investigated further.

I believe there was a little confusion even among Sun engineers with regard to how to implement a conditional menu item. I initially asked Eike on the sc-dev mailing list, and he referred me to the framework-dev mailing list instead. So I asked the question there, which resulted in this thread. In short, the discussion started from how to conditionally add a menu item, to how to make my Solver component a pure UNO component to make it truly an optional feature. But there was one problem: I was using the internal string resource manager API to localize the strings, but there was no UNO equivalent of string resource manager (an effort only recently included). I wasn’t really sure in which direction the discussion was going, and I don’t really remember if there was any consensus as to what the next step would be (as far as scsolver02 cws integration is concerned). But the discussion ended, and I was somewhat left confused, unsure of what to do next.

The specification woes

In addition to the above task, Michael Meeks told me (perhaps against his belief) to write a specification which he said was sadly something I needed to write in order to get my code accepted upstream. I knew how much he was against this whole specification process. Although I was not in favor of the specification process myself, I was not that much against it at the time. That said, I had no doubt in my mind that writing a specification for this Solver feature would require a fair amount of time. In the end, I accepted the task, somewhat unfavorably, in order to get things moving.

Please note that I was doing all of this completely on my own time, and no one was paying me to do any of this. I had to make a lot of sacrifice with my precious family time to allocate some time to work on this, but I was still left with only 30 minutes up to an hour of time available each day. Suffice it to say that my progress was very very slow, and since there was no coding involved, my motivation was all time low. But I kept going, believing that someday all of this would end.

Then the specification template really brought me tons of agony. Apparently there was some sort of Basic macro embedded in the template itself, to control some list boxes present in the template. It was designed to run a custom Basic macro every time the value of a list box changes. However, there was some hard-coded file path in the Basic code that prevented any of this from running properly (someone told me later that the code would only run properly inside Hamburg), so every time I changed the value of a list box, I’d get a run-time error message. Not to mention I couldn’t author the dialog description part of my specification because of that. I found myself debugging the basic code, wondering why on earth I had to debug a code when I was supposed to write up a documentation for the feature! My level of frustration was rising rapidly.

After three days of struggling with the misbehaving basic code, I asked for help, on the spec-dev mailing list. Then I soon found out that this was not a new problem and others were experiencing it as well. Two days had passed since I posted my request for help and I was still not getting any reply, so I asked again if anybody was there to comment. Still no reply from Sun. My frustration was at its peak because I was really trying to get the spec completed so that I could integrate the CWS and go back to the fun of coding again. This spec writing (debugging?) non-sense dragged me on for weeks.

Then my patience had run out, and I finally exploded. At that time, Michael was also running a piece on how the spec process was broken, in a very humorous way. So I emailed him and dumped my frustration with this whole specification process. I feel sorry that he had to listen to all my rant, but he was kind enough to listen to all of what I had to say, then after some private email talk between him and someone over at Sun, he eventually initiated this infamous specification thread. I don’t want to go into the details of the discussion we had on that thread (it’s all public for those who care), but it’s probably sufficient to say that nothing really has changed, except for the fact that now we are allowed to write a specification on the wiki, instead of using the Writer template. What I was quietly hoping to see out of this discussion was that we could finally abolish this painful specification process, but that unfortunately didn’t happen. (In retrospect, I was probably a bit too naive to have expected that from Sun. I should have known better.)

So, I was back to having to write a specification. This time on the wiki, but the same process nonetheless. After that thread had settled, I already told Michael that, after finishing the integration of the CWS, I did not want to go through the pain of upstreaming again, and that I would like to continue my work in ooo-build only. But deep down, I even had little motivation left to continue at that point, and I was more or less thinking about what I was going to say as my last word to the project, though part of myself was still wanting to stay with the project (after all, I loved hacking the OO.o code). I was torn. For the record, I tried to write a specification even under that kind of mental state, but my fingers would refuse to move, and I found myself sitting in front of my computer not doing a thing.

After joining Novell and licensing change

Long story short, I joined Novell in March 2007. I had already decided to leave the project before that, but Novell decided to pick me up. When Novell asked me whether I would be willing to change the license of the Solver code to LGPL only, I simply agreed. The change in licensing made perfect sense since the entire code was owned by myself (~99%), with a small fraction contributed from Novell and Debian, under LGPL.

But that did not mean that I lost interest in contributing the code upstream. Quite the opposite. Since it was made clear back when we were having a licensing discussion with Arun that LGPL code would be perfectly acceptable for upstream integration, I didn’t even expect that changing the license to pure LGPL would make much difference. As I said in my last comment in the issue page, my hope was to bring this functionality to all users of OO.o, but under a slightly different, more liberal license to make it fair to all the work and support those Novell guys have given me to make all of this possible. I truly believed what we were asking was a small, small favor, and I believed that we deserve at least that much after all we had done to the project.

Then Louis Suarez Potts announced Sun’s intension to develop a Solver for 3.0. I was there, witnessing his announcement on Calc Solver for 3.0 first-hand. Again, since it was never communicated with me, I was not quite sure what that announcement meant, until I saw this comment from Stefan Taxhet in the issue page.

So what happens next?

I simply don’t know, but one thing is clear. If Sun insists on rewriting all the work I’ve already done just to ensure that they own all the code in OO.o, even though it is legally permissible to integrate my code under a pure LGPL license as an external component, then perhaps I need to re-think my relationship with the project. Because that would be a clear sign that the goal of this project is no longer to work with community developers (i.e. those who contribute code, not talk) and create a vibrant open-source project where contributors feel they are making a difference, but to take advantage of free labor to further the corporate goal of Sun Microsystems, by protecting vigorously Sun’s total ownership of the code base as well as the development process in their entirety.

But I’d love to be proven wrong. I’d love to be proven that Sun still are willing to work with us, to make OO.o truly a wonderful product as well as a project attractive to prospective code contributors. But there is nothing I, as a single insignificant mere mortal can do to influence the behemoth that is Sun. It’s impossible to make an even slightest change in how the project is run, even after countless hours of coding and more than 10,000 lines of code generation (which I received no compensation for and involved quite a lot of personal sacrifice). In the end, I made no difference at all. Sad, truly sad.

Constraint parsing bug

Share Button

One avid user of my Calc Solver from Belgium found a rather serious, and a little embarrassing bug and brought it to my attention (thank you, Ludovic!). It was the way I convert a constraint formula from the spreadsheet format to the internal model, which utterly fails to do it correctly when the left-hand-side cell contains a constant value. I need to fix this sooner rather than later since I believe this is rather a severe bug that should not be left in the code knowingly (now that I know it…).

So, I’ll spend my next available time trying to fix it, and put it into ooo-build first. Then bring the fix to scsolver02 cws afterwards. I’ll have to hold off the upstream integration work for now.

scsolver02 CWS

Share Button

Ah, my first CWS. :-) It’s intended for upstreaming the solver code that I’ve been working on for years to the main codebase.

There are still many tasks to be completed however, such as writing a spec file and working out build integration details. Now, that‘s taking more time than actually writing code (exaggerated of course, but it feels that way). The main issue at the moment is how to conditionally show the solver menu item, since it makes no sense to show this menu when the solver is not enabled at build time.
I’m also having a weird problem with the spec file template. Reading through the Basic code indicates that I’m supposed to have additional file called autotext placed in order to design UI? Two hard-coded URLs are found in the code, but neither URLs seem to work. Hmm…

This much has been done so far:

  • created two new modules lpsolve and scsolver and populated them.
  • made a new configure option –enable-scsolver, which is disabled by default.
  • ran build tests three times to make sure it builds, with or without –enable-scsolver.

Upstreaming scsolver

Share Button

I’m in the process of upstreaming my solver (a.k.a scsolver – its cvs module name) to the OpenOffice.org repository at the moment. So, with everything else put on hold, all my effort is shifting toward making that happen.

Typically, any new code to the OO.o is upstreamed via a process known as the child work space (CWS), which is basically a front-end to the CVS repository (soon to be SVN’ed, I suppose? ;-) ) designed to ease the management of source control from different parties, including external contributors such as myself.

But CWS can be a bit intimidating and confusing to the un-initiated. For instance, it took me a great deal of trouble to figure out how to add new top-level modules. All sorts of emails went back and forth, and in the end, thanks especially to Petr, I was able to at least add new stub modules directories in cvs HEAD, and filed an issue to have the right person (Jens?) add cvs alias to those modules so that they can be checked out for further work.

Also, because my code has dependency on lp_solve, which itself is an external project, the right steps needed to be taken as outlined in the external project page to make sure that we are complying with the license of that particular software. Not sure how long this process will take, but at least I did my part (or did I?).

Anyway, things are moving along. :-) Michael was kind enough to create a new cws for me, so hopefully once those modules get aliased for checkout I’ll be able to start working on putting my code in that cws.

Oh yeah, also not to forget that patch for lpsolve that maho wants to commit. ;-)

Solver new snapshot available

Share Button

I’ve uploaded a new snapshot of Solver up on the usual place. The difference from the last snapshot is that the Solver now uses lp_solve as the backend LP optimizer. lp_solve is quite a robust optimizer currently developed and maintained by Kjell Eikland and Peter Notebaert. It has an excellent track record with users across many industries, so if you have a model that my Solver failed to solve previously, try out this snapshot to see if it will do a better job for you.

Now that the UNO package version of my Solver is finally out after a long 4-month hiatus , my next immediate task is to work on integrating this lp_solve-based Solver into ooo-build. For this, I will take a different integration strategy.

To recap, the strategy I took to implement the lp_solve-based Solver (this snapshot) was to add a UNO layer to lp_solve to turn it into a UNO library, and add a UNO hook to the main Solver component to glue the two separate components. This strategy was necessary despite its over-complexity and obvious overhead because, currently, it is not possible to include a shared library into a UNO package unless it provides a UNO service, or the package registration will simply fail. This is because OO.o expects every library included inside a package to export a certain set of callback functions for component registration, or it will balk at it.

The integration into the build, however, will be much simpler because there is no need for component registration. So I can simply have the Solver core library dynamically link to it and avoid the overhead of UNO. The downside of this is that I have to write additional code for it ;-), but I expect it to take only a minimal amount of effort.