Klee-Minty problem

The Klee-Minty problem is a typical example of this class of problem where — is the nonnegativity constraint and -t- is the complementary constraint used to obtain a variable. 

In the three-dimensional case, the possible combinations (vertices) of active constraints for the Klee-Minty problem are 2 " = 2 = 8 and, by sorting them from the smallest objective function value, the result is (columns = constraints rows = vertices)... 

Table 10.1 shows the maximum number of iterations with respect to the problem dimensions that should be required by the Simplex method and by the Attic method to solve the linear programming problems with these features (e.g., the Klee-Minty problem). 

Let us consider the Klee-Minty problem with ny = 4. The problem becomes... 

Figure 10,2 Graphical representation ofthe Klee—Minty three-dimensional problem (10.46) and (10.47).

Klee and Minty (Luenberger and Ye, 2008) showed that the Simplex strategy of passing through adjacent vertices may require prohibitive computational times. Let us consider the following problem ... 

---