عنوان

Disjunctive programming /

(Number (ISBN

3030001482

(Number (ISBN

9783030001483

Erroneous ISBN

3030001474

Erroneous ISBN

9783030001476

Title Proper

Disjunctive programming /

General Material Designation

[Book]

First Statement of Responsibility

Egon Balas.

Place of Publication, Distribution, etc.

Cham, Switzerland :

Name of Publisher, Distributor, etc.

Springer,

Date of Publication, Distribution, etc.

[2018]

Specific Material Designation and Extent of Item

1 online resource (x, 238 pages)

Text of Note

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

Text of Note

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

Text of Note

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

Text of Note

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

Text of Note

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

0

8

8

8

8

Text of Note

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.

Source for Acquisition/Subscription Address

Springer Nature

Stock Number

com.springer.onix.9783030001483

International Standard Book Number

9783030001476

Convex domains.

Integer programming.

Linear programming.

Convex domains.

Integer programming.

Linear programming.

MATHEMATICS-- Applied.

MATHEMATICS-- Probability & Statistics-- General.

MAT-- 003000

MAT-- 029000

MAT002050

PBF

PBF

Number

Edition

Class number

Book number

Balas, Egon

Date of Transaction

20200823071432.0

Cataloguing Rules (Descriptive Conventions))

pn

Electronic name

[Book]

Y