SIMPLEX ALGORITHM FOR PIECEWISE-LINEAR PROGRAMMING II: FINITENESS, FEASIBILITY AND DEGENERACY.

Robert H Fourer*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

33 Scopus citations

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 languageEnglish (US)
Pages (from-to)281-315
Number of pages35
JournalMathematical Programming, Series B
Volume41
Issue number3
StatePublished - Sep 1 1988

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design
  • Software
  • Management Science and Operations Research
  • Safety, Risk, Reliability and Quality
  • Mathematics(all)
  • Applied Mathematics

Fingerprint Dive into the research topics of 'SIMPLEX ALGORITHM FOR PIECEWISE-LINEAR PROGRAMMING II: FINITENESS, FEASIBILITY AND DEGENERACY.'. Together they form a unique fingerprint.

Cite this