Linear Program Simplex Solver

This program takes in an a definition of a linear program as input, then computes the optimal solution if it exists.

The revised Simplex method is used rather than the latest-and-greatest technique (interior point methods) due to its simplicity and fast execution in practice, even though polynomial-time execution is not guaranteed. The revised version differs from the ordinary version in that portions of the dictionary are calculated as needed rather than at every iteration, which saves a significant number of calculations. Also, my implementation uses eta matrices to avoid explicit matrix inversions, which are slow and can result in substantial rounding errors over time.

Written: December 2008

Language: C++

Download: