Optimistic MILP modeling of non-linear optimization problems

Riccardo Rovatti, D’Ambrosio, Claudia, Andrea Lodi and Silvano Martello

European Journal of Operational Research, 2014, vol. 239, issue 1, 32-45

Abstract: 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.

Keywords: Nonlinear programming; OR in Energy; Piecewise linear approximation (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221714002495
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:239:y:2014:i:1:p:32-45

DOI: 10.1016/j.ejor.2014.03.020

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().