Nonconvex Piecewise Linear Functions: Advanced Formulations and Simple Modeling Tools

DOI10.1287/OPRE.2019.1973MaRDI QIDQ6195082zbMATH OpenOpenAlexFDO

Authors Joey Huchette, J. P. Vielma

Publication date 12 March 2024

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.00050

zbMATH Keywords

integer programmingpiecewise linear

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Abstract: We present novel mixed-integer programming (MIP) formulations for optimization over nonconvex piecewise linear functions. We exploit recent advances in the systematic construction of MIP formulations to derive new formulations for univariate functions using a geometric approach, and for bivariate functions using a combinatorial approach. All formulations are strong, small (so-called logarithmic formulations), and have other desirable computational properties. We present extensive experiments in which they exhibit substantial computational performance improvements over existing approaches. To accompany these advanced formulations, we present PiecewiseLinearOpt, an extension of the JuMP modeling language in Julia that implements our models (alongside other formulations from the literature) through a high-level interface, hiding the complexity of the formulations from the end-user.

Recommendations

• Mixed-integer models for nonseparable piecewise-linear optimization: unifying framework and extensions
• A note on ``A superior representation method for piecewise linear functions
• Locally ideal formulations for piecewise linear functions with indicator variables
• Piecewise-linear approximations of multidimensional functions
• Piecewise Linear Function Fitting via Mixed-Integer Linear Programming

Cited in

(8)

• Modeling combinatorial disjunctive constraints via junction trees
• Piecewise linear trees as surrogate models for system design and planning under high-frequency temporal variability
• Piecewise polyhedral relaxations of multilinear optimization
• Solving continuous and discrete nonlinear programs with BARON
• Global optimization algorithm for mixed-integer nonlinear programs with trigonometric functions
• LinA: a faster approach to piecewise linear approximations using corridors and its application to mixed-integer optimization
• Piecewise linear approximations in the balanced identification of models with differential equations
• A relax-fix-and-exclude algorithm for an MINLP problem with multilinear interpolations

This page was built for publication: Nonconvex Piecewise Linear Functions: Advanced Formulations and Simple Modeling Tools

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6195082)