First off, my coding activity on solver is progressing very slow these days. Mostly because, besides my day job as a software engineer, I’ve been taking a class at a nearby college since January, and its class work (homework and programming assignments etc.) is taking up the bulk of my free time. This class finishes in May, so hopefully I will have more time to spend for the solver project once this is all done.
Also, for those who haven’t noticed, there is now a Windows binary available thanks to Kami’s contribution, so to those of you who have been waiting for a Windows version, now is your chance. :-) It’s available at the usual place.
Ok, so…, here is the update on my solver. I’m pretty much done with my revised simplex code, and now I’m shifting my focus to improving the (upper-and-lower) bounded revised simplex code. After a couple of test runs I’ve realized that the bounded simplex’s initial solution search is still pretty weak, so, that code needs to be improved first before anything else.
As an aside, here is an interesting page on Calc’s performance optimization bits by Michael and his gang.
Eike informed me that the previous binary I posted was not deployable with a regular OO.o build due to binary incompatibility with gcc (or g++ rather). I compiled my last binary using gcc 4.0, and gcc 4.0 apparently introduces compatibility symbols GLIBCXX_3.4.4 and GLIBCXX_3.4.6 which are not understood by a binary built using gcc 3.4.1 (such as a regular OO.o build). See Eike’s this blog entry for more details.
So, I downloaded gcc 3.4.1, and rebuilt my solver package. I ran
objdump -T scsolver.uno.so to make sure there were no GLIBCXX_3.4.x symbols (there weren’t). So, if you were having problem executing my solver using the previous binary, please try this one. Thanks.
Since not everybody who wants to use my solver has a version of OO.o derived from ooo-build, I have made available a separate binary package that can be installed on a regular OO.o. There is no functionality change since the last snapshot I uploaded here on my website, so if you are having trouble solving your model with my solver, sorry, this snapshot is not gonna help you.
Because now I work directly off of ooo-build cvs, the new changelog is located here. The old changelog is no longer maintained.
I’ve finally tracked down the problem of my solver not solving ANY models after having been integrated into ooo-build. It was due to Boost uBlas’s matrix resize function not preserving element values when resized. In my development environment (FC4) I use Boost 1.32.0 which resizes matrix gracefuly with all the unaffected elements’ values preserved unless the caller chooses otherwise. Somehow, this feature was introduced sometime between the version included in OO.o as of SRC680m148 (1.30.2) and the version I use on my system, and the version in OO.o does NOT preserve unaffected elements’ values when the matrix is resized.
Anyway, I’m very glad to finally have nailed this one down as I had spent a few days just for this alone! Now, I’ve finally sent off a patch to Michael. This patch also fixes a couple of other minor breakages occurred during the integration (wrt. string handling and compiler warning).
BTW, It’s very interesting to see that even a simple thing like a change log has a standard format. I never knew that, obviously.
I haven’t been active for this past month as I was a bit preoccupied with my personal life. First of all, I’m in the process of career transition, moving from working in natural science field into software engineering. As a result of this, writing code is no longer just my hobby activity but has become my professional career as well. Over the course of years of my involvement in OpenOffice.org, I have come to realize that software development is something more than just what I want to do in my spare time, and something I want to devote my entire professional life to. So, this transition is a huge step in the right direction for me.
Unfortunately, this has kept me busy for the past month or so and I couldn’t spend much time on developing solver. But I’m hopeful that I will start being active again real soon (and no, I won’t be getting paid for working on OpenOffice.org, so, that part will still remain my hobby activity even after this career change). Right now, my priority is to have my solver code integrated into ooo-build, and prepare for possible future upstreaming of this feature. Since my CVS account is not set up yet, Michael was kind enough to do the uploading for me, and to take a look at my code and make a few suggestions for improvement with a patch.
After the integration into ooo-build is complete, here is the list of things I am planning to work on (not in this particular order):
- Integration of bounded revised simplex – I’m convinced that certain types of models are best solved using this algorithm, while the existing revised simplex is still needed for all the other types.
- Support for solution with negative decision variables – the simplex algorithm does not allow a solution with negative decision variables by design. But there is a simple technique you can use to work around this limitation; split each variable into two variables and solve the model, and perform subtraction afterwards.
- Consider perhaps using an existing optimization library, such as lp_solve – while I still believe that writing and improving my own algorithms without external dependencies will be ideal in the long run, sometimes using an existing library may be worth looking into, especially when the authors of lp_solve have already spent a lot of time and effort on its development and improvement. Several people have already suggested lp_solve, so I should definitely look into it.
- Options dialog – for algorithms selection, precision, positive variables etc.
- Thread issues – still on the drawing board.
One of the things I wanted to do as a remedy to my simplex algorithm (refer to my last blog entry) was to switch to another algorithm for LU factorization which is used in my matrix inverse algorithm. The original LU factorization algorithm obviously was not robust enough to inverse an initial matrix generated in solving Markus’ model. This time, instead of blindly looking for a new algorithm to use all over the net, I decided to dive into Calc’s code to see what algorithm Calc uses internally for matrix inversion since Calc was able to inverse the very matrix my own algorithm was not.
Of course, I can’t just copy and paste Calc’s matrix inverse code, but luckily there was a reference within the code from which it was derived, and I just happened to have a copy of that very same reference which one of my friends was kind enough to lend to me a few weeks ago. Lucky me!
Anyway, now my solver can at least solves Markus’ model, though my solution differs from the Excel Solver’s solution that he included because of simplex’s positive variable limitation (his Excel solution included negative numbers). Adding support for negative numbers shouldn’t be too complex, but requires a bit more work.
The new snapshot (revision 101) is up which includes this new LU factorization algorithm.
Uploaded a new snapshot (rev. 100) for public consumption. In this release I’ve modified the model building algorithm – the algorithm responsible for converting a model in the spreadsheet form into a form the backend optimization algorithm can digest – to make it more robust, but this improvement is still not enough to solve those test files sent by Ludovic and Markus. Assuming that their models are actually feasible (I know at least Markus’ model is feasible as he also included Excel Solver’s solution), I have at least two more things in my mind that need to be done before my solver can solve their models.
Alternatively, I could use another variant of simplex that’s especially suited for the type of models they sent me – the type that has a specific upper or lower bound for each decision variable. But the code I wrote for the upper-and-lower-bounded simplex still has a few bugs to be sorted out before it can be plugged in for use. Not sure what the best course of action is…
In testing Ludovic’s model, I’ve discovered a bug in my two-phase initial solution search routine. Better take a close look at this.
Ok. I’ve just finished coding a new matrix inversion algorithm which uses LU factorization with forward and backward substitutions to derive an inverse matrix. This one should be a lot faster than the one I currently use in my simplex algorithm.
An update of the solver package with this new algorithm integrated will follow soon (probably tomorrow).
Wrote up an LU factorization algorithm for a square matrix of arbitrary size, and observed it to work pretty well on several small-sized matrices (n < 10). I expect this algorithm to perform reasonably on larger-sized matrices, though I still need to run some confirmation testing using larger-sized matrices (it does O(n^2) comparisons and 2n^3/3 flops). Once that’s done, I can then use this LU factorization algorithm as the building block for developing a matrix inversion algorithm.
I was somewhat frustrated by how the majority of matrix-related resources I’ve checked avoid showing specifics of matrix inversion algorithm. The reasoning is that such algorithm would be highly inefficient and one should consider directly solving a system of linear equations instead of inverting a matrix first then solving it. I have no doubt what they say is true, but the sad fact is that, sometimes one may need to explicitly compute an inverse matrix as part of another larger algorithm. :(