On the Minimum Number of Linear Pieces Required to Approximate Nonlinear Functions under an Accuracy Constraint

Abstract

The approximation of nonlinear functions by piecewise linear functions is a tool commonly used when dealing with mixed-integer nonlinear problems. Typically, by replacing nonlinearities by piecewise linear functions one can transform the problem into a mixed-integer linear problem, which may be substantially easier to solve. However, using approximate functions can produce solutions that are infeasible for the original problem or far from optimal. To control these errors it is useful to bound the error created during the function approximation process. Moreover, obtaining a piecewise linear function with few pieces usually results in an easier to solve mixed-integer linear problem. This leads us to study the Corridor Fitting Problem. It consists in building a piecewise linear function with the minimum number of pieces which approximates a nonlinear function given a bound on the approximation error on each point of the domain. The Corridor Fitting Problem has primarily been addressed for univariate functions or via heuristic approaches for multivariate functions. Notably, for the latter setting, no exact algorithms or established relaxations are currently known. In this work, we explore this aspect and propose exploitable relaxations of the Corridor Fitting Problem in Rm based on a discretization of the domain. We show that a structure of hypergraph coloring problem is induced by the discretization of the domain. We define four relaxations making use of this hypergraph coloring problem. We provide new best upper bounds for the classical instance set in R2 and we derive the first lower bounds for these instances, closing more than a third of the instances from the literature.

41 pages (including appendices), 7 figures