Dobrovoczki P., Kis T.: Disjunctive cuts for modeling R3 → R piecewise linear functions. Optimization and Algorithms (OPAL) 5-9 June 2023, Veszprém, Hungary
Modeling Rd → R piecewise linear functions with mixed integer linear programming is a challenging problem with several applications. Suppose there is a rectangular grid, a function f defined on the convex hull of the grid and a triangulation (simplicial decomposition) of the cells of the grid. Consider ˆf, a piecewise linear approximation of the function f, which is defined equal to f on the grid points and as the linear interpolation of f between grid points. The goal is to describe ˆf with a linear inequality system. There exists such formulation for the case d = 2 by Huchette and Vielma (2019), however their method, as a whole, cannot be straightforwardly generalized to higher dimensions. We present a general framework to model a certain class of disjunctive constraints. We characterize the facets of the corresponding convex hull of polyhedra and also describe an efficient separation algorithm. We apply these results along with an efficient representation of SOS2 sets to describe R3 → R piecewise linear functions. We tested our method on a series of benchmark instances and we summarize our computational results.