This book is meant for students and practitioners of optimization, mainly integer and
nonconvex optimization, as an introduction to, and review of, the
... [Show More] recently developed
discipline of disjunctive programming. It should be of interest to all those who are
trying to overcome the limits set by convexity to our problem-solving capability.
Disjunctive programming is optimization over disjunctive sets, the first large class
of nonconvex sets shown to be convexifiable in polynomial time.
There are no prerequisites for the understanding of this book, other than some
knowledge of the basics of linear and integer optimization. Clarity of exposition
was a main objective in writing it. Where background material is required, it is
indicated through references.
Habent sua fata libelli, goes the Latin saying: books have their own fate. The
basic document on Disjunctive Programming is the July 1974 technical report
“Disjunctive Programming: Properties of the convex hull of feasible points. MSRR
#348”, which however has not appeared in print until 24 years later, when it was
published as an invited paper with a remarkable foreword by Gerard Cornuejols
and Bill Pulleyblank [7] (for a history of this episode see the introduction to [11]).
The new theory, which was laid out without implementation of its cutting planes,
let alone computational experience, stirred little if any enthusiasm at the time of its
inception. But 15 years later, when Sebastian Ceria, Gerard Cornuejols and myself
recast essentially the same results in a new framework which we called lift-andproject
[19], the reaction was quite different. This time our work was focused on
algorithmic aspects, with the cutting planes generated in rounds and embedded into
an enumerative (branch and cut) framework, and was accompanied by an efficient
computer code, MIPO, that was able to solve many problem instances that had been
impervious to solution by branch-and-bound alone. This has led to a general effort
on the part of software builders to incorporate cutting planes into a new generation
of integer programming solvers, with the outcome known as the revolution in the
state of the art in mixed integer programming that took place roughly in the period
1990–2005.
From a broader perspective, disjunctive programming is one of the early bridges
between convex and nonconvex programming.
v
Several friends and colleagues have contributed to the improvement of this
book through their comments and observations. Their list includes David Bernal,
Dan Bienstock, Gérard Cornuéjols, Ignacio Grossmann, Michael Juenger, Alex
Kazachkov, Tamas Kis, Andrea Qualizza, Thiago Serra, and an anonymous editor
of the Springer Series Algorithms and Combinatorics.
The research underlying the results reported on in this book w [Show Less]