I’ve released a pure-Ruby implementation of the Simplex algorithm for solving linear problems. It may be useful to you if you can only run Ruby, or if you want to learn about the Simplex algorithm from a simple implementation.

I really really didn’t want to write my own LP solver implementation. If someone else told me they had done this, I would smirk. It’s a notoriously hard algorithm to implement correctly.

My use case is allocating power through circuits to weapons and shields and things in imaginary space ships (see right) created by users in my web game (codenamed Fantasy Star Fleets). The optimal power allocation (given whichever power cores and couplings have been blown up by enemy action at the present time) is a linear program.

The game runs on Heroku, which is a terrific time-saver. Have you tried compiling the “pro” LP solvers packages for Heroku? Have you tried compiling them on Heroku for Ruby 2.0?

I spent most of a day trying to make that work with various different solvers. Then I gave up and spent an hour writing my own.

It works for me because the little space ships are little, so the problems are small. Plus they are all of a very standard simple form, so there is no chance of degeneracy or hard things in general.

To solve the maximization in standard form (which is the only kind it can do atm):

max x +  y

   2x +  y <= 4
    x + 2y <= 3

    x, y >= 0

Do this:

> simplex = Simplex.new(
  [1, 1],       # coefficients of objective function
  [             # matrix of inequality coefficients on the lhs ...
    [ 2,  1],
    [ 1,  2],
  ],
  [4, 3]        # .. and the rhs of the inequalities
)
> simplex.solution
=> [(5/3), (2/3)]

Although it may not be of much practical use outside the restricted Heroku environment, I’ve tried to make it clean and easy to learn from. You can run the algorithm step by step and inspect the tableau as you go along:

> simplex = Simplex.new([1, 1], [[2, 1], [1, 2]], [4, 3])
> puts simplex.formatted_tableau
 -1.000   -1.000    0.000    0.000            
----------------------------------------------
 *2.000    1.000    1.000    0.000  |    4.000
  1.000    2.000    0.000    1.000  |    3.000

> simplex.can_improve?
=> true
> simplex.pivot
=> [0, 3]

> puts simplex.formatted_tableau
  0.000   -0.500    0.500    0.000            
----------------------------------------------
  1.000    0.500    0.500    0.000  |    2.000
  0.000   *1.500   -0.500    1.000  |    1.000

In the project description on Github and Rubygems I call this a “naive” solver, and that it certainly is. For example, it assumes your problem has feasible origin (because in my use case this is always true). I’d like to improve it so that it doesn’t make this assumption, but I might not find the time.