A Superior Representation Method for Piecewise Linear Functions

This is the authors' abstract. We don't add key points for this paper.

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 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.