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
Related Problems
Previous Problem
Next Problem
View the graph for this
file
Bulletin Board
About ``The Algorithm Design Manual''.
Send us Mail
The Stony Brook Algorithm Repository -- go to front page
This page last modified on Wed Mar 07, 2001
.