INPUT OUTPUT
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
Recommended Books
Understanding and Using Linear Programming by J. Matousek and B. Gartner
Linear Programming: Methods and Applications by S. Gass
Algorithms in Java, Third Edition (Parts 1-4) by Robert Sedgewick and Michael Schidlowsky
Limits to Parallel Computation: P-completeness theory by R. Greenlaw and J. Hoover and W. Ruzzo
Linear Programming by V. Chvatal
Linear programming and extensions by G. Dantzig
Related Links
Related Problems
This page last modified on 2008-07-10
.
www.algorist.com