A simplex algorithm for piecewise-linear programming III: Computational analysis and applications

Robert Fourer*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

40 Scopus citations

Abstract

The first two parts of this paper have developed a simplex algorithm for minimizing convex separable piecewise-linear functions subject to linear constraints. This concluding part argues that a direct piecewiselinear simplex implementation has inherent advantages over an indirect approach that relies on transformation to a linear program. The advantages are shown to be implicit in relationships between the linear and piecewise-linear algorithms, and to be independent of many details of implementation. Two sets of computational results serve to illustarate these arguments; the piecewise-linear simplex algorithm is observed to run 2-6 times faster than a comparable linear algorithm, not including any additional expense that might be incurred in setting up the equivalent linear program. Further support for the practical value of a good piecewise-linear programming algorithm is provided by a survey of many varied applications.

Original languageEnglish (US)
Pages (from-to)213-235
Number of pages23
JournalMathematical Programming
Volume53
Issue number1-3
DOIs
StatePublished - Jan 1992

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 III: Computational analysis and applications'. Together they form a unique fingerprint.

Cite this