.png){kind=icon}
.png){kind=icon}
Return
Optimistic MILP modeling of non-linear optimization problems
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2014.03.020.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 is an element of R-L, partitioned into hyper-rectangular subdomains through a grid defined by n(i) points on the l-axis (l = 1,...,L), the number of potential simplexes is L!Pi(L)(l=1)(n(l)-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 E-l=1(L) (n(l)-1). The method generalizes to the splitting of U into L-dimensional bounded polytopes in RI 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. (C) 2014 Elsevier B.V. All rights reserved.
Keywords:
Nonlinear programming
OR in Energy
Piecewise linear approximation
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W