O'Reilly logo

An Introduction to Optimization, 4th Edition by Stanislaw H. Zak, Edwin K. P. Chong

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

CHAPTER 18

NONSIMPLEX METHODS

18.1 Introduction

In previous chapters we studied the simplex method and its variant, the revised simplex method, for solving linear programming problems. The method remains widely used in practice for solving LP problems. However, the amount of time required to compute a solution using the simplex method grows rapidly as the number of components n of the variable x n increases. Specifically, it turns out that the relationship between the required amount of time for the algorithm to find a solution and the size n of x is exponential in the worst case. An example of an LP problem for which this relationship is evident was devised by Klee and Minty in 1972 [76]. Below, we give a version of the Klee-Minty example, taken from [9]. Let n be given. Let

equation

Consider the following LP problem:

equation

The simplex algorithm applied to the LP problem above requires 2n − 1 steps to find the solution. Clearly, in this example the relationship between the required amount of time for the simplex algorithm to find a solution and the size n of the variable x is exponential. This relationship ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required