Computational Techniques of the Simplex Method
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.
THE SIMPLEX METHOD
LARGE SCALE LP PROBLEMS
DESIGN PRINCIPLES OF LP SYSTEMS
DATA STRUCTURES AND BASIC OPERATIONS 69
LP PREPROCESSING 97
Other editions - View all
algorithm Assume basic solution basic variables basis change bound flip break points BTRAN cbeg coefficients columnwise computational corresponding cºx data structure defined degeneracy denoted determined Devex dot product double precision dual feasible dual logicals dual objective Dual-GX efficient enter the basis equation feasible basis fill-in finite flink GDPO implementation improving candidate incoming variable index set inverse iteration leave the basis linear programming logical variable lower bound lower triangular LP problem LU factorization matrix MPS format multiplier nonbasic variables nonnegative notation number of nonzeros numerical stability objective function objective value obtained operation optimal solution outgoing variable parameters performed 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