A simplex algorithm for piecewise-linear programming I: Derivation and proof

Robert Fourer*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

74 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. This three-part paper develops and analyzes a general, computationally practical simplex algorithm for piecewiselinear programming. Part I derives and justifies the essential steps of the algorithm, by extension from the simplex method for linear programming in bounded variables. The proof employs familiar finite-termination arguments and established piecewise-linear duality theory. Part II considers the relaxation of technical assumptions pertaining to finiteness, feasibility and nondegeneracy of piecewise-linear programs. Degeneracy is found to have broader consequences than in the linear case, and the standard techniques for prevention of cycling are extended accordingly. Part III analyzes the computational requirements of piecewise-linear programming. The direct approach embodied in the piecewise-linear simplex algorithm is shown to be inherently more efficient than indirect approaches that rely on transformation of piecewise-linear programs to equivalent linear programs. A concluding section surveys the many applications of piecewise-linear programming in linear programming, l1 estimation, goal programming, interval programming, and nonlinear optimization.

Original languageEnglish (US)
Pages (from-to)204-233
Number of pages30
JournalMathematical Programming
Volume33
Issue number2
DOIs
StatePublished - Nov 1985

Keywords

  • Linear Programming
  • Nondifferentiable Optimization
  • Piecewise-Linear Programming
  • Simplex Methods

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'A simplex algorithm for piecewise-linear programming I: Derivation and proof'. Together they form a unique fingerprint.

Cite this