Continuous Piecewise Linear δ-Approximations for MINLP Problems. II. Bivariate and Multivariate Functions

Following up on Rebennack and Kallrath (2012), in this paper, for functions depending on two variables, using refinement heuristics, we automatically construct triangulations subject to the condition that the continuous, piecewise linear approximation, under- or overestimation never deviates more than a given δ-tolerance from the original function over a given domain. This tolerance is proven by solving subproblems over each triangle to global optimality. The continuous, piecewise linear approximators, under- and overestimators involve shift variables at the vertices of the triangles leading to a small number of triangles while still ensuring continuity over the full domain. On a set of test functions, we demonstrate the numerical behavior of our approach. For functions depending on more than two variables we provide appropriate transformations and substitutions which allow to use one- or two-dimensional δ-approximators. We address the problem of error propagation when using these dimensionality reduction routines. The automatic refinement triangulation provides an alternative to separation or transformation techniques applied to bivariate functions followed by one-dimensional piecewise linear approximation. We discuss and analyze the tradeoff between one-dimensional and two-dimensional approaches. To demonstrate the methodology we apply it to a cutting stock problem in which we compute minimal area rectangles hosting a given number of circles; we prove optimality for one literature problem which so far had been solved only with finite gap.