New LU factorization in matrix inverse algorithm

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)

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…