Optimistic MILP modeling of non-linear optimization problems

We present a new piecewise linear approximation of non-linear optimization problems. It can be seen as a variant of classical triangulations that leaves more degrees of freedom to define any point as a convex combination of the samples. For example, in the traditional Union Jack approach a (two-dimensional) variable domain is split by a rectangular grid, and one has to select the diagonals that induce the triangles used for the approximation. For a hyper-rectangular domain U∈RL, partitioned into hyper-rectangular subdomains through a grid defined by nl points on the l-axis (l=1,…,L), the number of potential simplexes is L!∏l=1L(nl-1), and an MILP model incorporating it without complicated encoding strategies must have the same number of additional binary variables. In the proposed approach the choice of the simplexes is optimistically guided by one between two approximating objective functions (one convex, one concave), and the number of additional binary variables needed by a straightforward implementation drops to only ∑l=1L(nl-1). The method generalizes to the splitting of U into L-dimensional bounded polytopes in RL in which samples can be taken not only at the vertices of the polytopes but also inside them thus allowing, for example, off-grid oversampling of interesting regions. When addressing polytopes that are regularly spaced hyper-rectangles, the methods allows modeling of the domain partition with a logarithmic number of constraints and binary variables. The simultaneous use of both convex and concave piecewise linear approximations reminds of global optimization techniques, which are, on the one side, stronger because they lead to convex relaxations and not only approximations of the problem at hand, but, on the other hand, significantly more arduous from a computational standpoint. We show theoretical properties of the approximating functions, and provide computational evidence of the impact of their use within MILP models approximating non-linear problems.