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

Juan Pablo Vielma (jvielmaisye.gatech.edu)
Shabbir Ahmed (sahmedisye.gatech.edu)
George Nemhauser (gnemhausisye.gatech.edu)

Abstract: We study the modeling of non-convex 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 non-separable 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.

Keywords: Mixed Integer Programming, Piecewise Linear Functions

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Citation: To appear in Operations Research

Download: [PDF]

Entry Submitted: 09/30/2008
Entry Accepted: 09/30/2008
Entry Last Modified: 09/01/2009

Modify/Update this entry