Input | Output |
Input Description: A set of linear inequalities, a linear objective function.
Problem: Find the assignment to the variables maximizing the objective function while satisfying all inequalities.
Excerpt from The Algorithm Design Manual: The standard algorithm for linear programming is called the While the basic simplex algorithm is not too difficult to program, there is a considerable art to producing an efficient implementation capable of solving large linear programs. For example, large programs tend to be sparse (meaning that most inequalities use few variables), so sophisticated data structures must be used. There are issues of numerical stability and robustness, as well as which neighbor we should walk to next (so called pivoting rules). Finally, there exist sophisticated interior-point methods, which cut through the interior of the simplex instead of walking along the outside, that beat simplex in many applications.
Implementations
Lp_solve (rating 10)
COINOR (rating 9)
pulp (rating 8)
ceres-solver (rating 8)
gosl (rating 8)
Elemental (rating 8)
GLPK (rating 8)
NEOS (rating 8)
Netlib (rating 0)