Speaker
Sandra Ulrich Ngueveu
(Toulouse INP-ENSEEIHT / LAAS-CNRS)
Description
We present new algorithms that can solve 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 pointwise approximation error allowed. These new algorithms can solve the problem in quasi-logarithmic time on a very broad class of errors types. Such algorithms find many applications, for example 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 that will be presented.
