## Computational Techniques of the Simplex MethodLinear 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. |

### 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 |

321 | |

### Other editions - View all

### Common terms and phrases

Assume basic solution basic variables basis change bound flip break points BTRAN cbeg cluster coefficients columnwise computational corresponding Dantzig data structure defined degeneracy denoted determined Devex dj(t dot product double precision dual feasible dual infeasibilities dual logicals dual objective Dual-GX efficient enter the basis equation feasible basis fill-in finite GDPO implementation improving candidate incoming variable index set individual bounds inverse iteration leave the basis linear programming linked list logical variable lower bound lower triangular LP problem LU factorization matrix MPS format nonbasic variables nonnegative notation number of nonzeros numerical stability objective function objective value obtained operation optimal solution outgoing variable parameters performed permutation matrix permuted pivot element presolve primal procedure ratio test reduced costs remain feasible requires row and column row count scale selected simplex algorithm simplex method solve sparsity steepest edge Step steplength stored Suhl transformed type-0 variables upper bound zero