Mixed-Integer Models for Nonseparable Piecewise-Linear Optimization: Unifying Framework and Extensions

• 成果类型: Article
• 署名作者: Vielma, Juan Pablo; Ahmed, Shabbir; Nemhauser, George
• 署名单位: University System of Georgia; Georgia Institute of Technology
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1090.0721
• 发表日期: 2010
• 页码: 303-315
• 关键词: programming-problems; outer-approximation; binary variables; algorithm; nonconvex; concave; representability

摘要

We study the modeling of nonconvex piecewise-linear functions as mixed-integer programming (MIP) problems. We review several new and existing MIP formulations for continuous piecewise-linear functions with special attention paid to multivariate nonseparable functions. We compare these formulations with respect to their theoretical properties and their relative computational performance. In addition, we study the extension of these formulations to lower semicontinuous piecewise-linear functions.