Nonconvex Piecewise Linear Functions: Advanced Formulations and Simple Modeling Tools

Joey Huchette () and Juan Pablo Vielma ()
Additional contact information
Joey Huchette: Department of Computational and Applied Mathematics, Rice University, Houston, Texas 77005
Juan Pablo Vielma: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Operations Research, 2023, vol. 71, issue 5, 1835-1856

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.

Keywords: Optimization; piecewise linear; integer programming (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2019.1973 (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:inm:oropre:v:71:y:2023:i:5:p:1835-1856

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().