Abstract
The simplex method for linear programming can be extended to permit the mininimzation of any convex separable piecewise-linear objective, subject to linear constraints. Part I of this paper developed a general and direct simplex algorithm for piecewise-linear programming, under convenient assumptions that guarantee a finite number of basic solutions, existence of basic feasible solutions, and nondegenerarcy of all such solutions. Part II now shows how these assumption can be weakened so that they pose no obstacle to effective use of the piecewise-linear simplex algorithm. The theory of piecewise-linear programming is thereby extended, and numerous features of linear programming are generalized or are seen in a new light.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 281-315 |
| Number of pages | 35 |
| Journal | Mathematical Programming, Series B |
| Volume | 41 |
| Issue number | 3 |
| State | Published - Sep 1 1988 |
ASJC Scopus subject areas
- Computer Graphics and Computer-Aided Design
- Software
- Management Science and Operations Research
- Safety, Risk, Reliability and Quality
- General Mathematics
- Applied Mathematics