A superior representation method for piecewise linear functions

Han-Lin Li*, Hao Chun Lu, Chia Hui Huang, Nian Ze Hu

*Corresponding author for this work

Research output: Contribution to journalArticle

22 Scopus citations

Abstract

Many nonlinear programs can be piecewisely linearized by adding extra binary variables. For the last four decades, several techniques of formulating a piecewise linear function have been developed. By expressing a piecewise linear function with m+1 break points, the current method requires us to use m additional binary variables and 4m constraints, which causes heavy computation when m is large. This study proposes a superior way of expressing the same piecewise linear function, where only [log 2m] binary variables and 8 + 8[log 2m] additive constraints are used. Various numerical experiments demonstrate that the proposed method is more computationally efficient than current methods.

Original languageEnglish
Pages (from-to)314-321
Number of pages8
JournalINFORMS Journal on Computing
Volume21
Issue number2
DOIs
StatePublished - 1 Mar 2009

Keywords

  • Integer
  • Mathematics
  • Piecewise linear
  • Programming

Fingerprint Dive into the research topics of 'A superior representation method for piecewise linear functions'. Together they form a unique fingerprint.

  • Cite this