Nonconvex Piecewise Linear Functions: Advanced Formulations and Simple Modeling Tools
成果类型：
Article
署名作者：
Huchette, Joey; Vielma, Juan Pablo
署名单位：
Rice University; Massachusetts Institute of Technology (MIT)
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.2019.1973
发表日期：
2023
页码：
1835-1856
关键词：
摘要：
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.
来源URL：