Computational Techniques of the Simplex Method

Front Cover
Springer Science & Business Media, Dec 31, 2002 - Mathematics - 325 pages
0 Reviews
Linear Programming (LP) is perhaps the most frequently used optimization technique. One of the reasons for its wide use is that very powerful solution algorithms exist for linear optimization. Computer programs based on either the simplex or interior point methods are capable of solving very large-scale problems with high reliability and within reasonable time. Model builders are aware of this and often try to formulate real-life problems within this framework to ensure they can be solved efficiently. It is also true that many real-life optimization problems can be formulated as truly linear models and also many others can well be approximated by linearization. The two main methods for solving LP problems are the variants of the simplex method and the interior point methods (IPMs). It turns out that both variants have their role in solving different problems. It has been recognized that, since the introduction of the IPMs, the efficiency of simplex based solvers has increased by two orders of magnitude. This increased efficiency can be attributed to the following: (1) theoretical developments in the underlying algorithms, (2) inclusion of results of computer science, (3) using the principles of software engineering, and (4) taking into account the state-of-the-art in computer technology.
Theoretically correct algorithms can be implemented in many different ways, but the performance is dependent on how the implementation is done. The success is based on the proper synthesis of the above mentioned (1-4) components. Computational Techniques of the Simplex Method is a systematic treatment focused on the computational issues of the simplex method. It provides a comprehensive coverage of the most important and successful algorithmic and implementation techniques of the simplex method. It is a unique source of essential, never discussed details of algorithmic elements and their implementation. On the basis of the book the reader will be able to create a highly advanced implementation of the simplex method which, in turn, can be used directly or as a building block in other solution algorithms.

From inside the book

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

THE LINEAR PROGRAMMING PROBLEM
3
12 General form
4
121 Computational form
5
122 Computational form 2
13
13 Concluding remarks
17
THE SIMPLEX METHOD
19
21 Theoretical background
20
211 Basis and solution
21
82 LU factorization
134
821 Determining a sparse LU form
136
822 Implementing the LU factorization
143
823 Maintaining triangularity during iterations
149
824 Operations with the LU form
155
83 Concluding remarks
158
THE PRIMAL ALGORITHM
161
91 Solution feasibility infeasibility
162

212 The geometry of constraints
23
213 Neighboring bases
26
22 The primal simplex method
28
222 Improving a nonoptimal basic feasible solution
29
223 Algorithmic description of the simplex method
33
224 Finding a basic feasible solution
34
225 The twophase simplex method
37
23 Duality
38
24 The dual simplex method
40
242 Improving a dual feasible solution
41
243 Algorithmic description of the dual simplex method
43
244 Further properties of the primaldual relationship
46
25 Concluding remarks
47
LARGE SCALE LP PROBLEMS
49
32 Instances of large problems
51
33 Structure
52
34 Fillin
53
35 Numerical difficulties
55
COMPUTATIONAL TECHNIQUES
57
DESIGN PRINCIPLES OF LP SYSTEMS
59
41 Requirements of LP software
60
42 Computer hardware
62
43 The software side of implementing LP solvers
65
DATA STRUCTURES AND BASIC OPERATIONS
69
51 Storing sparse vectors
70
52 Operations involving sparse vectors
71
522 Dot product of sparse vectors
74
54 Linked lists
76
55 Implementation of forwardbackward linking
80
56 Concluding remarks
84
PROBLEM DEFINITION
87
62 Processing the MPS format
93
LP PREPROCESSING
97
711 Contradicting individual bounds
100
715 Removing fixed variables
101
716 Redundant and forcing constraints
102
718 Implied free variables
104
719 Singleton columns
105
7111 Reducing the sparsity of A
107
7112 The algorithm
108
7113 Implementation
109
72 Scaling
110
73 Postsolve
116
731 Unscaling
117
732 Undo presolve
118
733 Undo reformulation
119
BASIS INVERSE FACTORIZATION
121
81 Product form of the inverse
122
811 General form
123
812 Sparsity exploiting form
124
813 Implementing the PFI
129
814 Operations with the PFI
131
92 Optimality conditions
164
93 Improving a nonoptimal basic feasible solution
167
931 The logic of the ratio test
173
932 Extensions to the ratio test
175
933 Algorithmic description of PSMG
176
934 Computational considerations
178
94 Determining the reduced costs
181
941 Computing dj
182
943 Updating dj
183
95 Selecting an incoming improving variable
184
951 Dantzig pricing
187
953 Sectional pricing
188
954 Normalized pricing
189
955 A general pricing framework
198
96 Improving an infeasible basic solution
203
961 Analysis of wt
208
962 The logic of the ratio test
217
964 Computational considerations
224
965 Adaptive composite pricing in phase1
227
97 Handling degeneracy
230
971 Antidegeneracy column selection
232
972 Wolfes ad hoc method
234
973 Expanding tolerance
237
974 Perturbation shifting
241
98 Starting bases
244
982 Crash bases
246
983 CPLEX basis
253
984 A tearing algorithm
255
985 Partial basis
259
THE DUAL ALGORITHM 101 Dual feasibility infeasibility
261
102 Improving a dual feasible solution
262
1021 Dual algorithm with type1 and type2 variables
263
1022 Dual algorithm with all types of variables
266
1023 Bound flip in dual
267
1034 Extended General Dual algorithm
270
103 Improving a dual infeasible solution
277
1031 Analysis of the dual infeasibility function
281
1032 Dual phase1 iteration with all types of variables
284
104 Row selection dual pricing
292
1041 Dantzig pricing
293
1043 Devex
296
1044 Pricing in dual phase1
297
106 Degeneracy in the dual
298
Chapter 11 VARIOUS ISSUES
301
1111 Parameter file
302
1113 Algorithmic parameters
303
113 Some alternative techniques
306
1132 Row basis
307
114 Modeling systems
310
115 A prototype simplex solver
311
Index
321
Copyright

Other editions - View all

Common terms and phrases

References to this book

All Book Search results »

Bibliographic information