Disjunctive Programming

Disjunctive Programming is a technique and a discipline initiated by the author in the early 1970's, which has become a central tool for solving nonconvex optimization problems like pure or mixed integer programs, through convexification (cutting plane) procedures combined with enumeration. It has played a major role in the revolution in the state of the art of Integer Programming that took place roughly during the period 1990-2010. The main benefit that the reader may acquire from reading this book is a deeper understanding of the theoretical underpinnings and of the applications potential of disjunctive programming, which range from more efficient problem formulation to enhanced modeling capability and improved solution methods for integer and combinatorial optimization.**Egon Balas** is University Professor and Lord Professor of Operations Research at Carnegie Mellon University's Tepper School of Business. Front Matter ....Pages i-x Disjunctive Programming and Its Relation to Integer Programming (Egon Balas)....Pages 1-16 The Convex Hull of a Disjunctive Set (Egon Balas)....Pages 17-39 Sequential Convexification of Disjunctive Sets (Egon Balas)....Pages 41-47 Moving Between Conjunctive and Disjunctive Normal Forms (Egon Balas)....Pages 49-68 Disjunctive Programming and Extended Formulations (Egon Balas)....Pages 69-77 Lift-and-Project Cuts for Mixed 0-1 Programs (Egon Balas)....Pages 79-89 Nonlinear Higher-Dimensional Representations (Egon Balas)....Pages 91-96 The Correspondence Between Lift-and-Project Cuts and Simple Disjunctive Cuts (Egon Balas)....Pages 97-105 Solving (CGLP)k on the LP Simplex Tableau (Egon Balas)....Pages 107-119 Implementation and Testing of Variants (Egon Balas)....Pages 121-143 Cuts from General Disjunctions (Egon Balas)....Pages 145-193 Disjunctive Cuts from the V -Polyhedral Representation (Egon Balas)....Pages 195-213 Unions of Polytopes in Different Spaces (Egon Balas)....Pages 215-231 Back Matter ....Pages 233-238 Disjunctive Programming is a technique and a discipline initiated by the author in the early 1970's, which has become a central tool for solving nonconvex optimization problems like pure or mixed integer programs, through convexification (cutting plane) procedures combined with enumeration. It has played a major role in the revolution in the state of the art of Integer Programming that took place roughly during the period 1990-2010. The main benefit that the reader may acquire from reading this book is a deeper understanding of the theoretical underpinnings and of the applications potential of disjunctive programming, which range from more efficient problem formulation to enhanced modeling capability and improved solution methods for integer and combinatorial optimization. Egon Balas is University Professor and Lord Professor of Operations Research at Carnegie Mellon University's Tepper School of Business.