A Superior Representation Method for Piecewise Linear Functions
Han-Lin Li, Hao-Chun Lu, Chia-Hui Huang, Nian-Ze Hu
INFORMS Journal on Computing · 2009 · Volume 21 · Issue 2
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 4 m 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 2 m ⌉ binary variables and 8 + 8 ⌈ log 2 m ⌉ additive constraints are used. Various numerical experiments demonstrate that the proposed method is more computationally efficient than current methods.
Keywords
mathematics, piecewise linear, programming, integer
Enable JavaScript for citation tools and additional paper interactions.