| Document Type
|
:
|
BL
|
| Record Number
|
:
|
859098
|
| Main Entry
|
:
|
Balas, Egon
|
| Title & Author
|
:
|
Disjunctive programming /\ Egon Balas.
|
| Publication Statement
|
:
|
Cham, Switzerland :: Springer,, [2018]
|
| Page. NO
|
:
|
1 online resource (x, 238 pages)
|
| ISBN
|
:
|
3030001482
|
|
|
:
|
: 9783030001483
|
|
|
:
|
3030001474
|
|
|
:
|
9783030001476
|
| Contents
|
:
|
Intro; Preface; Contents; 1 Disjunctive Programming and Its Relation to Integer Programming; 1.1 Introduction; 1.2 Intersection Cuts; 1.3 Inequality Systems with Logical Connectives; 1.4 Valid Inequalities for Disjunctive Sets; 1.5 Duality for Disjunctive Programs; 2 The Convex Hull of a Disjunctive Set; 2.1 The Convex Hull Via Lifting and Projection; 2.1.1 Tightness of the Lifted Representation; 2.1.2 From the Convex Hull to the Union Itself; 2.2 Some Facts About Projecting Polyhedra; 2.2.1 Well Known Special Cases; 2.2.2 Dimensional Aspects of Projection
|
|
|
:
|
2.2.3 When Is the Projection of a Facet a Facet of the Projection?2.3 Projection with a Minimal System of Inequalities; 2.4 The Convex Hull Via Polarity; 3 Sequential Convexification of Disjunctive Sets; 3.1 Faciality as a Sufficient Condition; 3.2 A Necessary Condition for Sequential Convexifiability; 4 Moving Between Conjunctive and Disjunctive Normal Forms; 4.1 The Regular Form and Basic Steps; 4.2 The Hull Relaxation and the Associated Hierarchy; 4.3 When to Convexify a Subset; 4.4 Parsimonious MIP Representation of Disjunctive Sets
|
|
|
:
|
4.5 An Illustration: Machine Sequencing Via Disjunctive Graphs4.5.1 A Disjunctive Programming Formulation; 4.5.2 A Tighter Disjunctive Programming Formulation; 4.6 Disjunctive Programs with Trigger Variables; 5 Disjunctive Programming and Extended Formulations; 5.1 Comparing the Strength of Different Formulations; 5.1.1 The Traveling Salesman Problem; 5.1.2 The Set Covering Problem; 5.1.3 Nonlinear 0-1 Programming; 5.2 Proving the Integrality of Polyhedra; 5.2.1 Perfectly Matchable Subgraphs of a Bipartite Graph; 5.2.2 Assignable Subgraphs of a Digraph
|
|
|
:
|
5.2.3 Path Decomposable Subgraphs of an Acyclic Digraph5.2.4 Perfectly Matchable Subgraphs of an Arbitrary Graph; 6 Lift-and-Project Cuts for Mixed 0-1 Programs; 6.1 Disjunctive Rank; 6.2 Fractionality of Intermediate Points; 6.3 Generating Cuts; 6.4 Cut Lifting; 6.5 Cut Strengthening; 6.6 Impact on the State of the Art in Integer Programming; 7 Nonlinear Higher-Dimensional Representations; 7.1 Another Derivation of Lift-and-Project Cuts; 7.2 The Lovász-Schrijver Construction; 7.3 The Sherali-Adams Construction; 7.4 Lasserre's Construction; 7.5 The Bienstock-Zuckerberg Lift Operator
|
|
|
:
|
8 The Correspondence Between Lift-and-Project Cuts and Simple Disjunctive Cuts8.1 Feasible Bases of the CGLP Versus (Feasible or Infeasible) Bases of the LP; 8.2 The Correspondence Between the Strengthened Cuts; 8.3 Bounds on the Number of Essential Cuts; 8.4 The Rank of P with Respect to Different Cuts; 9 Solving (CGLP)k on the LP Simplex Tableau; 9.1 Computing Reduced Costs of (CGLP)k Columns for the LP Rows; 9.2 Computing Evaluation Functions for the LP Columns; 9.3 Generating Lift-and-Project Cuts by Pivoting in the LP Tableau
|
| Abstract
|
:
|
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.
|
| Subject
|
:
|
Convex domains.
|
| Subject
|
:
|
Integer programming.
|
| Subject
|
:
|
Linear programming.
|
| Subject
|
:
|
Convex domains.
|
| Subject
|
:
|
Integer programming.
|
| Subject
|
:
|
Linear programming.
|
| Subject
|
:
|
MATHEMATICS-- Applied.
|
| Subject
|
:
|
MATHEMATICS-- Probability Statistics-- General.
|
| Dewey Classification
|
:
|
519.7/7
|
| LC Classification
|
:
|
T57.74.B35 2018eb
|