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 on 49 packages!
The basic problem of linear programming is to minimize a linear objective function of continuous real variables, subject to linear constraints. For purposes of describing and analyzing algorithms, the problem is often stated in the standard form
where is the
vector of unknowns,
is the cost
vector, and
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.
Up To:
[ OTC Home Page | NEOS Guide | NEOS Server | Optimization Tree ]
Updated 28 March 1996
