Optimization with Disjunctive Constraints

The disjunctive cut principle of Balas and Jeroslow, and the related polyhedral annexation principle of Glover, provide new insights into cutting plane theory. This has resulted in its ability to not only subsume many known valid cuts but also improve upon them. Originally a set of notes were written for the purpose of putting together in a common terminology and framework significant results of Glover and others using a geometric approach, referred to in the literature as convexity cuts, and the algebraic approach of Balas and Jeroslow known as Disjunctive cuts. As it turned out subsequently the polyhedral annexation approach of Glover is also closely connected with the basic disjunctive principle of Balas and Jeroslow. In this monograph we have included these results and have also added several published results which seem to be of strong interest to researchers in the area of developing strong cuts for disjunctive programs. In particular, several results due to Balas [4,5,6,7], Glover [18,19] and Jeroslow [23,25,26] have been used in this monograph. The appropriate theorems are given without proof. The notes also include several results yet to be published [32,34,35] obtained under a research contract with the National Science Foundation to investigate solution methods for disjunctive programs. The monograph is self-contained and complete in the sense that it attempts to pool together existing results which the authors viewed as important to future research on optimization using the disjunctive cut approach.

Table of Contents:
I: Introduction.- 1.1 Basic Concepts.- 1.2 Special Cases of Disjunctive Programs and Their Applications.- 1.3 Notes and References.- II: Basic Concepts and Principles.- 2.1 Introduction.- 2.2 Surrogate Constraints.- 2.3 Pointwise-Supremal Cuts.- 2.4 Basic Disjunctive Cut Principle.- 2.5 Notes and References.- III: Generation of Deep Cuts Using the Fundamental Disjunctive Inequality.- 3.1 Introduction.- 3.2 Defining Suitable Criteria for Evaluating the Depth of a Cut.- 3.3 Deriving Deep Cuts for DC1.- 3.4 Deriving Deep Cuts for DC2.- 3.5 Other Criteria for Obtaining Deep Cuts.- 3.6 Some Standard Choices of Surrogate Constraint Multipliers.- 3.7 Notes and References.- IV: Effect of Disjunctive Statement Formulation on Depth of Cut and Polyhedral Annexation Techniques.- 4.1 Introduction.- 4.2 Illustration of the Tradeoff Between Effort for Cut Generation and the Depth of Cut.- 4.3 Some General Comments with Applications to the Generalized Lattice Point and the Linear Complementarity Problem.- 4.4 Sequential Polyhedral Annexation.- 4.5 A Supporting Hyperplane Scheme for Improving Edge Extensions.- 4.6 Illustrative Example.- 4.7 Notes and References.- V: Generation of Facets of the Closure of the Convex Hull of Feasible Points.- 5.1 Introduction.- 5.2 A Linear Programming Equivalent of the Disjunctive Program.- 5.3 Alternative Characterization of the Closure of the Convex Hull of Feasible Points.- 5.4 Generation of Facets of the Closure of the Convex Hull of Feasible Points.- 5.5 Illustrative Example.- 5.6 Facial Disjunctive Programs.- 5.7 Notes and References.- VI: Derivation and Improvement of Some Existing Cuts Through Disjunctive Principles.- 6.1 Introduction.- 6.2 Gomory’s Mixed Integer Cuts.- 6.3 Convexity or Intersection Cuts with Positive Edge Extensions.- 6.4Reverse Outer Polar Cuts for Zero-One Programming.- 6.5 Notes and References.- VII: Finitely Convergent Algorithms for Facial Disjunctive Programs with Applications to the Linear Complementarity Problem.- 7.1 Introduction.- 7.2 Principal Aspects of Facial Disjunctive Programs.- 7.3 Stepwise Approximation of the Convex Hull of Feasible Points.- 7.4 Approximation of the Convex Hull of Feasible Points Through an Extreme Point Characterization.- 7.5 Specializations of the Extreme Point Method for the Linear Complementarity Problem.- 7.6 Notes and References.- VIII: Some Specific Applications of Disjunctive Programming Problems.- 8.1 Introduction.- 8.2 Some Examples of Bi-Quasiconcave Problems.- 8.3 Load Balancing Problem.- 8.4 The Segregated Storage Problem.- 8.5 Production Scheduling on N-Identical Machines.- 8.6 Fixed Charge Problem.- 8.7 Project Selection/Portfolio Allocation/Goal Programming.- 8.8 Other Applications.- 8.9 Notes and References.- Selected References.