Linear Programming Computation

This monograph represents a historic breakthrough in the field of linear programming (LP)since George Dantzig first discovered the simplex method in 1947. Being both thoughtful and informative, it focuses on reflecting and promoting the state of the art by highlighting new achievements in LP. This new edition is organized in two volumes. The first volume addresses foundations of LP, including the geometry of feasible region, the simplex method and its implementation, duality and the dual simplex method, the primal-dual simplex method, sensitivity analysis and parametric LP, the generalized simplex method, the decomposition method, the interior-point method and integer LP method. The second volume mainly introduces contributions of the author himself, such as efficient primal/dual pivot rules, primal/dual Phase-I methods, reduced/D-reduced simplex methods, the generalized reduced simplex method, primal/dual deficient-basis methods, primal/dual face methods, a new decomposition principle, etc. Many important improvements were made in this edition. The first volume includes new results, such as the mixed two-phase simplex algorithm, dual elimination, fresh pricing scheme for reduced cost, bilevel LP models and intercepting of optimal solution set. In particular, the chapter Integer LP Method was rewritten with great gains of the objective cutting for new ILP solvers {\it controlled-cutting/branch} methods, as well as with an attractive implementation of the controlled-branch method. In the second volume, the `simplex feasible-point algorithm' was rewritten, and removed from the chapter Pivotal Interior-Point Method to form an independent chapter with the new title `Simplex Interior-Point Method', as it represents a class of efficient interior-point algorithms transformed from traditional simplex algorithms. The title of the original chapter was then changed to `Facial Interior-Point Method', as the remaining algorithms represent another class of efficient interior-point algorithms transformed from normal interior-point algorithms. Without exploiting sparsity, the original primal/dual face methods were implemented using Cholesky factorization. In order to deal with sparse computation, two new chapters discussing LU factorization were added to the second volume. The most exciting improvement came from the rediscovery of the reduced simplex method. In the first edition, the derivation of its prototype was presented in a chapter with the same title, and then converted into the so-called `improved' version in another chapter. Fortunately, the author recently found a quite concise new derivation, so he can now introduce the distinctive fresh simplex method in a single chapter. It is exciting that the reduced simplex method can be expected to be the best LP solver ever. With a focus on computation, the current edition contains many novel ideas, theories and methods, supported by solid numerical results. Being clear and succinct, its content reveals in a fresh manner, from simple to profound. In particular, a larger number of examples were worked out to demonstrate algorithms. This book is a rare work in LP and an indispensable tool for undergraduate and graduate students, teachers, practitioners, and researchers in LP and related fields. 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 Organized into two volumes. this book represents a real breakthrough in the field of linear programming (LP). The first volume addresses fundamentals, including geometry of feasible region, simplex method, implementation of simplex method, duality and dual simplex method, sensitivity analysis and parametric LP, generalized simplex method, decomposition method, interior-point method and integer LP method, as well as reflects the state of art by highlighting new results, such as efficient primal and dual pivot rules, primal and dual Phase-I methods. The second volume introduces contributions of the author himself, such as reduced and D-reduced-simplex methods, generalized reduced and dual reduced simplex methods, deficient-basis and dual deficient-basis-simplex methods, and face and dual face methods with Cholesky factorization, as well as with LU factorization. As a monograph, this book is a rare work in LP, containing many noval ideas and methods, supported by complete computational results. As revealed from the perspective of theory, the most recently achieved results, such as reduced and D-reduced simplex methods, as well as ILP solvers--- controlled-cut and controlled-branch methods, are very significant and promising, though there are no computational results available at this stage. With a focus on computation, the content of this book ranges from simple to profound, clear and fresh. In particular, all algorithms are accompanied by examples for demonstration whenever possible. As a milestone of LP, this book is an indispensable tool for undergraduate and graduate students, teachers, practitioners and researchers, in LP and related fields