TY - JOUR A1 - Codsi, Julien A1 - Ngueveu, Sandra Ulrich A1 - Gendron, Bernard T1 - LinA: a faster approach to piecewise linear approximations using corridors and its application to mixed-integer optimization T2 - Mathematical Programming Computation N2 - 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. Y1 - 2025 UR - https://opus4.kobv.de/opus4-mpc/frontdoor/index/index/docId/292 SN - 1867-2949 VL - 17 IS - 2 SP - 265 EP - 306 PB - Springer Science and Business Media LLC ER -