Optimization Online


A special ordered set approach to discontinuous piecewise linear optimization

Ismael de Farias (defarias***at***buffalo.edu)
Ming Zhao (mzhao***at***buffalo.edu)
Hongxia Zhao (zhongxia***at***eng.buffalo.edu)

Abstract: Piecewise linear functions (PLFs) are commonly used to approximate nonlinear functions. They are also of interest in their own, arising for example in problems with economies of scale. Early approaches to piecewise linear optimization (PLO) assumed continuous PLFs. They include the incremental cost MIP model of Markowitz and Manne and the convex combination MIP model of Dantzig. Later, Beale and Tomlin gave an approach alternative to MIP for continuous PLO based on the concept of special ordered set (SOS). It is well established today that the SOS approach is considerably more efficient than MIP for continuous PLO. Recently, Croxton, Gendron, and Magnanti studied three MIP models for discontinuous PLO that are correct when the PLFs are lower semi-continuous, and showed that they give the same LP relaxation bound. Here we present a SOS approach for discontinuous PLO that gives the same LP relaxation bound as their MIP models. In addition to the usual advantages of SOS over MIP for PLO, our SOS approach is more robust than MIP in the sense that it solves PLO even when some of the PLFs are not lower semi-continuous.

Keywords: piecewise linear optimization, discontinuous piecewise linear function, special ordered set, mixed-integer programming

Category 1: Integer Programming

Citation: Working paper, SUNY Buffalo, October 2005.

Download: [PDF]

Entry Submitted: 10/14/2005
Entry Accepted: 10/14/2005
Entry Last Modified: 10/18/2005

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society