LinA: a faster approach to piecewise linear approximations using corridors and its application to mixed-integer optimization
- In this paper, we address the problem of approximating and over/under-estimating
univariate functions with piecewise linear (PWL) functions with the minimum num-
ber of linear segments given a bound on the allowed pointwise approximation error.
Through a new geometric approach and building on the work of Ngueveu (Eur J Oper
Res 275:1058–1071, 2019), we develop new algorithms that can solve the problem in
quasi-logarithmic time on a very broad class of error types. Such algorithms find many
applications, mostly related to solving certain classes of (mixed-integer) nonlinear and
nonconvex programming (MINLP) problems by mixed-integer linear programming
(MILP) techniques. An efficient implementation of our algorithms is available as a
Julia package. Benchmarks are also provided to showcase how our method outper-
forms the state-of-the-art for this problem. Finally, we show how our algorithms can
be used to efficiently solve certain classes of MINLP problems through a case study
on multicommodity network design problems with congestion.