Wednesday, September 2, 2009

The amazing computational world of DIY Simplex

Operations Research students seldom get to look into details of sophisticated implementations of a sparse simplex solver for linear programming. The same is true for O.R practice where your focus is how best to use such tools. But if you work for a setup that cannot afford the steep royalty you have to pay for such tools, you can build your own in a few months. Its more likely to be about 100 times slower than Gurobi or CPLEX on large problems. If your LPs are small sized (less than 50,000 rows), it may do a decent job, but hey, the experience is quite amazing, and I highly recommend it. For one, the system of linear equations that you solved since high school will never seem the same. And you can read a couple of important journal papers authored by Suhl and Suhl (i kid you not). The dual method is the best default choice. If you have starting trouble, trying using 'Gooplex', google's first draft LP solver. Its a toy solver, but the code implementation looks professional and is a good starting point.

On the other hand, there's always COIN-OR, the good quality open source repository.

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.