A simplex algorithm for piecewise-linear programming II: Finiteness, feasibility and degeneracy

Robert Fourer*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

The simplex method for linear programming can be extended to permit the minimization of any convex separable piecewise-linear objective, subject to linear constraints. Part I of this paper has 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 nondegeneracy of all such solutions. Part II now shows how these assumptions 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. An analysis of the algorithm's computational requirements and a survey of applications will be presented in Part III.

Original languageEnglish (US)
Pages (from-to)281-315
Number of pages35
JournalMathematical Programming
Volume41
Issue number1-3
DOIs
StatePublished - May 1 1988

Keywords

  • Linear programming
  • nondifferentiable optimization
  • piecewise-linear programming
  • simplex methods

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'A simplex algorithm for piecewise-linear programming II: Finiteness, feasibility and degeneracy'. Together they form a unique fingerprint.

Cite this