Optimization Online


Mathematical Programming Formulations for Piecewise Polynomial Functions

Bjarne Grimstad(bjarne.grimstad***at***gmail.com)
Brage R. Knudsen(brage.rugstad.knudsen***at***gmail.com)

Abstract: This paper studies mathematical programming formulations for solving optimization problems with piecewise polynomial (PWP) constraint functions. We elaborate on suitable polynomial bases as a means of efficiently representing PWPs in mathematical programs, comparing and drawing connections between the monomial basis, the Bernstein basis, and B-splines. The theory is presented for both continuous and semi-continuous PWPs. Using a disjunctive formulation, we then exploit the characteristic of common polynomial basis functions to significantly reduce the number of nonlinearities, and to suggest a bound-tightening technique for PWP constraints. Upon a standard big-M reformulation yielding an MINLP model, we derive three extensions using logarithmic number of binary variables, Bernstein cuts and an expanded Bernstein basis. Numerical results from solving three test sets of MINLPs to global optimality compares the formulations. The proposed framework shows promising numerical performance, and facilitates the solution of PWP-constrained optimization problems using standard MINLP software.

Keywords: Piecewise polynomials, Splines, Mixed integer programming, Disjunctions

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )


Download: [PDF]

Entry Submitted: 02/17/2018
Entry Accepted: 02/17/2018
Entry Last Modified: 02/17/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society