# Computational Techniques of the Simplex Method

Springer Science & Business Media, Dec 31, 2002 - Mathematics - 325 pages
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.

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