Linear Programming
From NEOS
Software for linear programming (including network linear programming) consumes more computer cycles than software for all other kinds of optimization problems combined . There is a proliferation of linear programming software with widely varying capabilities and user interfaces. The most recent survey of linear programming software for desktop computers carried out by OR/MS Today (19 (1992), pp. 44-59) gave details o n 49 packages!
The basic problem of linear programming is to minimize a linear objective functi on of continuous real variables, subject to linear constraints. For purposes of describin g and analyzing algorithms, the problem is often stated in the standard form
where x is the vector of unknowns, c is the cost vector, and A is the constraint matrix. The feasible region described by the constraints is a polytope, or simplex, and at least one member of the solution set lies at a vertex of this polytope.
The simplex algorithm, so named because of the geometry of the feasible set, underlies the vast majority of available software packages for linear programming. However, this situation may change in the future, as more software for interior-point algorithms becomes available.
