Disjunctive Programming

by Egon Balas

Overview

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.

Product Details

ISBN-13:	9783030001476
Publisher:	Springer International Publishing
Publication date:	11/28/2018
Edition description:	1st ed. 2018
Pages:	238
Product dimensions:	6.10(w) x 9.25(h) x (d)

About the Author

Egon Balas is University Professor of Applied Mathematics and Thomas Lord Professor of Operations Research at the Tepper School of Business of Carnegie Mellon University. He is the author of over 250 technical papers with over 50 different coauthors from around the world. His field of expertise is Optimization/Operations Research, in particular he is one of the pioneers of Integer Programming and the originator of Disjunctive Programming.

Table of Contents

1 Disjunctive programming and its relation to integer programming.- 2 The convex hull of a disjunctive set.- 3 Sequential convexification of disjunctive sets.- 4 Moving between conjunctive and disjunctive normal forms.- 5 Disjunctive programming and extended formulations.- 6 Lift-and-project cuts for mixed 0-1 programs.- 7 Nonlinear higher-dimensional representations.- 8 The correspondence between lift-and-project cuts and simple disjunctive cuts.- 9 Solving (CGLP)k on the LP simplex tableau.- 10 Implementation and testing of variants.- 11 Cuts from general disjunctions.- 12 Disjunctive cuts from the V -polyhedral representation.- 13 Unions of polytopes in different spaces.- References.

Editorial Reviews

Balas provides a very thorough and authoritative account of the theory of disjunctive programming and its applications to 0-1 MILP. This book will be of interest to graduate students and researchers working in integer programming.” (Brian Borchers, MAA Reviews, September 22, 2019)

“The major strength of this book is the clear and nice style of presentation. Various concepts are illustrated with examples in an elegant manner. This book is recommended as a resource for both independent study and teaching purposes, but because of its rigorous style it can also be used as a valuable reference for research purposes. It is a distinguished contribution to the field, and we recommend it to students, researchers and practitioners in the area of optimization.” (Samir Kumar Neogy, Mathematical Reviews, July, 2019)

“The book is nicely written and all the chapters are well organized. Overall, this book offers a very good introduction to disjunctive programming. In fact, I find that all the chapters are interesting. The presentation is clear and lucid. … the book is an interesting piece of work and it is highly recommended for students, researchers and practitioners of optimization.” (Samir Kumar Neogy, zbMath 1414.90001, 2019)

From the Publisher