دانلود کتاب Linear Programming Computation

فهرست مطالب :

Preface to First Edition
Acknowledgments
Preface to Second Edition
References
Contents
About the Book
About the Author
Notation
Part I Foundations
1 Introduction
1.1 Error of Floating-Point Arithmetic
1.2 From Real-Life Issue to LP Model
1.3 Illustrative Applications
1.4 Standard LP Problem
1.5 Basis and Feasible Basic Solution
References
2 Geometry of Feasible Region
2.1 Feasible Region as Polyhedral Convex Set
2.2 Interior Point and Relative Interior Point
2.3 Face, Vertex, and Extreme Direction
2.4 Representation of Feasible Region
2.5 Optimal Face and Optimal Vertex
2.6 Graphic Approach
2.7 Heuristic Characteristic of Optimal Solution
2.8 Feasible Direction and Active Constraint
References
3 Simplex Method
3.1 Simplex Algorithm: Tableau Form
3.2 Getting Started
3.3 Simplex Algorithm
3.4 Degeneracy and Cycling
3.5 Finite Pivot Rule
3.6 Notes on Simplex Method
References
4 Implementation of Simplex Method
4.1 Miscellaneous
4.2 Scaling
4.3 LU Factorization of Basis
4.4 Sparse LU Factorization of Basis
4.5 Updating LU Factors
4.6 Crash Procedure for Initial Basis
4.7 Harris Rule and Tolerance Expending
4.8 Pricing for Reduced Cost
References
5 Duality Principle and Dual Simplex Method
5.1 Dual LP Problem
5.2 Duality Theorem
5.3 Optimality Condition
5.4 Dual Simplex Algorithm: Tableau Form
5.5 Dual Simplex Algorithm
5.6 Economic Interpretation of Duality: Shadow Price
5.7 Dual Elimination
5.8 Bilevel LP: Intercepting Optimal Set
5.9 Notes on Duality
References
6 Primal-Dual Simplex Method
6.1 Mixed Two-Phase Simplex Algorithm
6.2 Primal-Dual Simplex Algorithm
6.3 Self-Dual Parametric Simplex Algorithm
6.4 Criss-Cross Algorithm Using Most-Obtuse-Angle Rule
6.5 Perturbation Primal-Dual Simplex Algorithm
6.6 Notes on Criss-Cross Simplex Algorithm
References
7 Sensitivity Analysis and Parametric LP
7.1 Change in Cost
7.2 Change in Right-Hand Side
7.3 Change in Coefficient Matrix
7.3.1 Dropping Variable
7.3.2 Adding Variable
7.3.3 Dropping Constraint
7.3.4 Adding Constraint
7.3.5 Replacing Row/Column
7.4 Parameterizing Objective Function
7.5 Parameterizing Right-Hand Side
8 Generalized Simplex Method
8.1 Generalized Simplex Algorithm
8.1.1 Generalized Phase-I
8.2 Generalized Dual Simplex Algorithm: Tableau Form
8.2.1 Generalized Dual Phase-I
8.3 Generalized Dual Simplex Algorithm
8.4 Generalized Dual Simplex Algorithm with Bound-Flipping
References
9 Decomposition Method
9.1 D-W Decomposition
9.1.1 Starting-Up of D-W Decomposition
9.2 Illustration of D-W Decomposition
9.3 Economic Interpretation of D-W Decomposition
9.4 Benders Decomposition
9.5 Illustration of Benders Decomposition
9.6 Dual Benders Decomposition
References
10 Interior-Point Method
10.1 Karmarkar Algorithm
10.1.1 Projective Transformation
10.1.2 Karmarkar Algorithm
10.1.3 Convergence
10.2 Affine Interior-Point Algorithm
10.2.1 Formulation of the Algorithm
10.2.2 Convergence and Starting-Up
10.3 Dual Affine Interior-Point Algorithm
10.4 Path-Following Interior-Point Algorithm
10.4.1 Primal–Dual Interior-Point Algorithm
10.4.2 Infeasible Primal–Dual Algorithm
10.4.3 Predictor–Corrector Primal–Dual Algorithm
10.4.4 Homogeneous and Self-Dual Algorithm
10.5 Notes on Interior-Point Algorithm
References
11 Integer Linear Programming (ILP)
11.1 Graphic Approach
11.1.1 Basic Idea Behind New ILP Solvers
11.2 Cutting-Plane Method
11.3 Branch-and-Bound Method
11.4 Controlled-Cutting Method
11.5 Controlled-Branch Method
11.5.1 Depth-Oriented Strategy
11.5.2 Breadth-Oriented Strategy
11.6 ILP: with Reduced Simplex Framework
References
Part II Advances
12 Pivot Rule
12.1 Partial Pricing
12.2 Steepest-Edge Rule
12.3 Approximate Steepest-Edge Rule
12.4 Largest-Distance Rule
12.5 Nested Rule
12.6 Nested Largest-Distance Rule
References
13 Dual Pivot Rule
13.1 Dual Steepest-Edge Rule
13.2 Approximate Dual Steepest-Edge Rule
13.3 Dual Largest-Distance Rule
13.4 Dual Nested Rule
References
14 Simplex Phase-I Method
14.1 Infeasibility-Sum Algorithm
14.2 Single-Artificial-Variable Algorithm
14.3 Perturbation of Reduced Cost
14.4 Using Most-Obtuse-Angle Column Rule
References
15 Dual Simplex Phase-l Method
15.1 Dual Infeasibility-Sum Algorithm
15.2 Dual Single-Artificial-Variable Algorithm
15.3 Perturbation of the Right-Hand Side
15.4 Using Most-Obtuse-Angle Row Rule
References
16 Reduced Simplex Method
16.1 Reduced Simplex Algorithm
16.2 Dual Reduced Simplex Algorithm
16.2.1 Dual Reduced Simplex Phase-I:Most-Obtuse-Angle
16.3 Perturbation Reduced Simplex Algorithm
16.4 Bisection Reduced Simplex Algorithm
16.5 Notes on Reduced Simplex Algorithm
References
17 D-Reduced Simplex Method
17.1 D-Reduced Simplex Tableau
17.2 Dual D-Reduced Simplex Algorithm
17.2.1 Dual D-Reduced Phase-I
17.3 D-Reduced Simplex Algorithm
17.3.1 D-Reduced Phase-I: Most-Obtuse-Angle Rule
17.4 Bisection D-Reduced Simplex Algorithm
Reference
18 Generalized Reduced Simplex Method
18.1 Generalized Reduced Simplex Algorithm
18.1.1 Generalized Reduced Phase-I: Single Artificial Variable
18.2 Generalized Dual Reduced Simplex Algorithm
18.2.1 Generalized Dual Reduced Phase-I
18.3 Generalized Dual D-Reduced Simplex Algorithm
19 Deficient-Basis Method
19.1 Concept of Deficient Basis
19.2 Deficient-Basis Algorithm: Tableau Form
19.3 Deficient-Basis Algorithm
19.3.1 Computational Results
19.4 On Implementation
19.4.1 Initial Basis
19.4.2 LU Updating in Rank-Increasing Iteration
19.4.3 Phase-I: Single-Artificial-Variable
19.5 Deficient-Basis Reduced Algorithm
19.5.1 Phase-I: Most-Obtuse-Angle Rule
References
20 Dual Deficient-Basis Method
20.1 Dual Deficient-Basis Algorithm: Tableau Form
20.2 Dual Deficient-Basis Algorithm
20.3 Dual Deficient-Basis D-Reduced Algorithm: Tableau Form
20.4 Dual Deficient-Basis D-Reduced Algorithm
20.5 Deficient-Basis D-Reduced Gradient Algorithm:Tableau Form
20.6 Deficient-Basis D-Reduced Gradient Algorithm
Reference
21 Face Method with Cholesky Factorization
21.1 Steepest Descent Direction
21.2 Updating of Face Solution
21.3 Face Contraction
21.4 Optimality Test
21.5 Face Expansion
21.6 Face Algorithm
21.6.1 Face Phase-I: Single-Artificial-Variable
21.6.2 Computational Results
21.7 Affine Face Algorithm
21.8 Generalized Face Algorithm
21.9 Notes on Face Method
References
22 Dual Face Method with Cholesky Factorization
22.1 Steepest Ascent Direction
22.2 Updating of Dual Face Solution
22.3 Dual Face Contraction
22.4 Optimality Test
22.5 Dual Face Expansion
22.6 Dual Face Algorithm
22.6.1 Dual Face Phase-I
22.6.2 Computational Results
22.7 Dual Face Algorithm via Updating (BTB)-1
23 Face Method with LU Factorization
23.1 Decent Search Direction
23.2 Updating of Face Solution
23.3 Pivoting Operation
23.4 Optimality Test
23.5 Face Algorithm: Tableau Form
23.6 Face Algorithm
23.7 Notes on Face Method with LU Factorization
Reference
24 Dual Face Method with LU Factorization
24.1 Key of Method
24.2 Ascent Search Direction
24.3 Updating of Dual Face Solution
24.4 Pivoting Operation
24.5 Optimality Test
24.6 Dual Face Algorithm: Tableau Form
24.7 Dual Face Algorithm
24.8 Notes on Dual Face Method with LU Factorization
References
25 Simplex Interior-Point Method
25.1 Column Pivot Rule and Search Direction
25.2 Row Pivot Rule and Stepsize
25.3 Optimality Condition and the Algorithm
25.4 Computational Results
26 Facial Interior-Point Method
26.1 Facial Affine Face Interior-Point Algorithm
26.2 Facial D-Reduced Interior-Point Algorithm
26.3 Facial Affine Interior-Point Algorithm
Reference
27 Decomposition Principle
27.1 New Decomposition Method
27.2 Decomposition Principle: ``Arena Contest\'\'
27.3 Illustration on Standard LP Problem
27.4 Illustration on Bounded-Variable LP Problem
27.5 Illustration on ILP Problem
27.6 Practical Remarks
Appendix A On the Birth of LP and More
Appendix B MPS File
Appendix C Test LP Problems
Appendix D Empirical Evaluation for Nested Pivot Rules
Appendix E Empirical Evaluation for Primal and Dual Face Methods with Cholesky Factorization
Appendix F Empirical Evaluation for Simplex Interior-Point Algorithm
References
Index