COmPwise: Computing Optimal Piecewise Linear Functions and Their Applications

Funding period: June 1, 2021 - May 31, 2025.

Piecewise linear (PWL) functions consist of affine segments. This property makes PWL functions especially interesting; both practically as well as computationally. Practically, because affine functions are easy to interpret and to handle; computationally, because PWL functions can be represented with mixed-integer linear programming (MILP) techniques. In fact, PWL functions are commonly used in various disciplines. In mathematical optimization, PWL functions are used to approximate non-linear functions in an effort to solve mixed integer non-linear programming (MINLP) problems with MILP techniques. We intend to contribute on two fronts. First, for PWL function computation, we want to enhance and extend existing methods and models, design new algorithms and tailor approaches towards special applications. Second, we want to incorporate PWL function approximation in Benders decomposition algorithms to design an exact algorithm for MINLP problems (of special structure). Specifically, the first front is concerned with methods allowing the computation of PWL functions to discrete data as well as continuous functions. We focus on methods that can guarantee to compute an optimal PWL function. To this end, we want to enhance computational performance of existing methods for univariate function fitting. This is achieved through model strengthening and design of specialized algorithms. We want to investigate logarithmic re-formulations and we want to exploit that fitting convex PWL functions is computationally much more efficient. Algorithmically, combinatorial Benders decomposition seems fit to take advantage of the Big-M structure of the existing MILP formulation and to derive strong optimality cuts. For two-dimensional problems, we want to develop the first exact method – there are only heuristic methods available in the literature. Our idea is to adapt latest re-formulation tricks that resulted in the currently best performing algorithms for univariate function fitting. On the second front, we want to design Benders algorithms for (non-convex) MINLP problems possessing a decomposable structure, for example an L-shaped constraint matrix.