product iamge

Linear Programming Computation

This document was uploaded by one of our users. The uploader already confirmed that they had the permission to publish it. If you are author/publisher or own the copyright of this documents, please report to us by using this DMCA report form.

Download
Search on Amazon

Simply click on the Download Book button.

Yes, Book downloads on Ebookily are 100% Free.

Sometimes the book is free on Amazon As well, so go ahead and hit "Search on Amazon"

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.

Author(s): Ping-Qi Pan
Edition: 2
Publisher: Springer
Year: 2023

Language: English
Pages: 738
City: Singapore

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