This Article Full Text (PDF) References 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 Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Keha, A. B. Articles by Nemhauser, G. L. Search for Related Content

A Branch-and-Cut Algorithm Without Binary Variables for Nonconvex Piecewise Linear Optimization

Industrial Engineering Department, Arizona State University, P.O. Box 875906, Tempe, Arizona 85287-5906
Department of Industrial Engineering, University at Buffalo, SUNY, 403 Bell Hall, Buffalo, New York 14260
School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332-0205
ahmet.keha{at}asu.edu
defarias{at}buffalo.edu
george.nemhauser{at}isye.gatech.edu

We give a branch-and-cut algorithm for solving linear programs (LPs) with continuous separable piecewise-linear cost functions (PLFs). Models for PLFs use continuous variables in special-ordered sets of type 2 (SOS2). Traditionally, SOS2 constraints are enforced by introducing auxiliary binary variables and other linear constraints on them. Alternatively, we can enforce SOS2 constraints by branching on them, thus dispensing with auxiliary binary variables. We explore this approach further by studying the inequality description of the convex hull of the feasible set of LPs with PLFs in the space of the continuous variables, and using the new cuts in a branch-and-cut scheme without auxiliary binary variables. We give two families of valid inequalities. The first family is obtained by lifting the convexity constraints. The second family consists of lifted cover inequalities. Finally, we report computational results that demonstrate the effectiveness of our cuts, and that branch-and-cut without auxiliary binary variables is significantly more practical than the traditional mixed-integer programming approach.

Subject classifications: piecewise linear function; special-ordered set; branch-and-cut.
History: Received March 2004; accepted June 2005.