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

Steffen Rebennack () and Josef Kallrath ()
Additional contact information
Steffen Rebennack: Division of Economics and Business, Colorado School of Mines
Josef Kallrath: Department of Astronomy, University of Florida

No 2012-13, Working Papers from Colorado School of Mines, Division of Economics and Business

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

Keywords: global optimization; NLP; nonconvex; overestimator; underestimator; inner approximation; outer approximation (search for similar items in EconPapers)
Pages: 34 pages
Date: 2012-10
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://econbus-papers.mines.edu/working-papers/wp201213.pdf First version, 2012 (application/pdf)

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:mns:wpaper:wp201213

Access Statistics for this paper

More papers in Working Papers from Colorado School of Mines, Division of Economics and Business Contact information at EDIRC.
Bibliographic data for series maintained by Jared Carbone ().