LinA: a faster approach to piecewise linear approximations using corridors and its application to mixed-integer optimization

作     者：Codsi, Julien Ngueveu, Sandra Ulrich Gendron, Bernard 

作者机构：Univ Montreal Dept Informat & Rech Operat Montreal PQ Canada Princeton Univ Princeton NJ 08544 USA Univ Toulouse LAAS CNRS CNRS INP Toulouse France Univ Montreal CIRRELT Montreal PQ Canada 

出 版 物：《MATHEMATICAL PROGRAMMING COMPUTATION》 (Math. Program. Comput.)

年 卷 期：2025年第17卷第2期

页      面：265-306页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0835[工学-软件工程] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：FMJH Program PGMO EDF-Thales-Orange Soutien a la Mobilite Internationale (SMI) de Toulouse INP Natural Sciences and Engineering Council of Canada (NSERC) through the Undergraduate Student Research Awards 

主　　题：Piecewise linear functions Approximation Overestimation Underestimation Guaranteed tolerance Piecewise linear regression with bounded error MINLP MILP Julia package 

摘      要：In this paper, we address the problem of approximating and over/under-estimating univariate functions with piecewise linear (PWL) functions with the minimum number 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 outperforms 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.