Tag: scsolver

Recent activities

Kohei Yoshida

So, I have several things going on at the moment:

  • I have just registered for my final exam for the class I’ve been taking since December. This class has certainly been an eye-opener, especially for someone like myself who’d been coding in high-level languages with only a vague understanding of low level architectural stuff.
  • I’ve started looking at lp_solve for possible integration into Calc Solver, and solicited for some interests. This Solver task, admittedly, has become much, much, more than what one person can handle. So, strategic change is necessary to keep things moving. I’ve also updated the wiki page to add more content.
  • Created a new wiki page for Statistical Data Analysis Tool project, to hopefully mobilize the near-death-experienced-yet-still-important project for Calc. There is no content on this page yet as it is still pretty much a skeleton. I wonder if this project will ever gain enough momentum to get it going…

Duh!

Kohei Yoshida

In my quest to improve the initial solution search algorithm I wrote for the bounded revised simplex, I had spent almost a whole day trying to understand what the heck I was trying to do there when I first wrote this code! I wrote that code originally in Python almost a year ago, ported straight to C++, and the code had been there ever since.

Anyway, long story short, I finally gave up and decided to rewrite the algorithm, which only took a few hours to complete! (not entirely done, but the core part is done.) Well, duh! Lesson learned: sometimes it’s quicker to rewrite it if the code looks hopelessly convoluted, and your hunch tell you that the code should be much, much, simpler for what it’s designed to do. You never know. Sometimes you are right.

By the way, what a great artist! His songs just keep playing in my head.

Current status

Kohei Yoshida

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.

Solver binary (take 2)

Kohei Yoshida

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.

First scsolver binary package after ooo-build integration

Kohei Yoshida

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.

Boost fix

Kohei Yoshida

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.

Update on what I’ve been up to these days

Kohei Yoshida

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.

New LU factorization in matrix inverse algorithm

Kohei Yoshida4 Comments

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.

Solver update (rev. 100)

Kohei Yoshida

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…