Continuous Piecewise Linear δ-Approximations for MINLP Problems. I. Minimal Breakpoint Systems for Univariate 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-12, Working Papers from Colorado School of Mines, Division of Economics and Business

Abstract: For univariate functions, we compute optimal breakpoint systems subject to the condition that the piecewise linear approximation (or, under- and overestimator) never deviates more than a given δ-tolerance from the original function, over a given finite interval. The linear approximators, under- and overestimators involve shift variables at the breakpoints leading to a small number of breakpoints while still ensuring continuity over the full interval. We develop two mixed integer non-linear programming models: one which yields the minimal number of breakpoints, and another in which, for a fixed number of breakpoints, their values are computed. Alternatively, we use two heuristics in which we compute the breakpoints subsequently, solving small mixed integer non-linear programming problems, with significantly fewer variables. The optimal breakpoints for the nonlinear functions can be used in the mixed integer linear programming problem replacement of the original non-linear programming problem or the mixed integer non-linear programming problem. Due to the δ-limited discretization error and the minimal number of breakpoints, the solution of the mixed integer linear programming problem can be obtained in reasonable time and serves a good approximation to the global optimum, which can be fed into a local non-linear programming or mixed integer non-linear programming solver for the final refinement.

Keywords: global optimization; nonlinear programming; mixed integer nonlinear programming; nonconvex optimization; overestimator; underestimator; inner approximation; outer approximation (search for similar items in EconPapers)
Pages: 40 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/wp201212.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:wp201212

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 ().