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 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.
Return to Algorithms or Linear Programming Directory
