Computing Optimal Piecewise Linear Functions and Their Applications

• Applicant: Professor Steffen Rebennack, Ph.D.
• Subject Area: Mathematics
• Term: since 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 445857709

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. We want to use this fact for DC function fitting; a very rich function class which, for example, contains all two times continuous differentiable functions. 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. Our idea is to combine three different approaches from two disciplines to one algorithm: The MINLP sub-problems are dynamically approximated using PWL functions yielding MILP sub-problems. Tight optimality cuts are computed using the latest developments in stochastic MILP, requiring that all state variables are binary. This requires the third approach that is based on binary expansion. Therefore, results from the PWL function as well as the stochastic integer programming communities are combined. Only careful control of all approximation errors will yield a decomposition algorithm that can guarantee global optimality.

• DFG Programme: Research Grants