This Article Full Text (PDF) e-companion Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Vielma, J. P. Articles by Nemhauser, G.

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

H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
jvielma{at}isye.gatech.edu
sahmed{at}isye.gatech.edu
gnemhaus{at}isye.gatech.edu

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.

Subject classifications: mixed-integer programming; piecewise-linear functions.
History: Received September 2008; revision received January 2009; accepted April 2009.