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.
Citation
Working paper, SUNY Buffalo, October 2005.