A branch-and-cut algorithm without binary variables for nonconvex piecewise linear optimization

Ahmet B. Keha, Ismael R. De Farias, George L. Nemhauser

Research output: Contribution to journalArticlepeer-review

60 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)847-858
Number of pages12
JournalOperations Research
Volume54
Issue number5
DOIs
StatePublished - Sep 2006

Keywords

  • Branch-and-cut
  • Piecewise linear function
  • Special-ordered set

Fingerprint Dive into the research topics of 'A branch-and-cut algorithm without binary variables for nonconvex piecewise linear optimization'. Together they form a unique fingerprint.

Cite this