A Klee-Minty cube is a deformed hypercube used to exhibit exponential worst-case behavior of a specified pivot rule for the simplex method in linear programming (Klee and Minty 1972). One standard scaled version maximizes
 |
(1)
|
subject to 
and
 |
(2)
|
for 
. Starting at the origin,
the simplex method with Dantzig's largest-positive-reduced-cost
rule visits all 
vertices, taking 
pivots (Vanderbei). This statement concerns that pivot
rule and starting point, rather than every algorithm
for linear programming.
The table shows the path in two and three dimensions. Labels give the visit order, starting with 0. For display, coordinates are rescaled by 
; the three-dimensional drawing is projected onto
a plane. These display transformations do not define a
different pivoting problem.
| pivot path | dimension | path length |
|  | 4 vertices, 3 pivots |
|  | 8 vertices, 7 pivots |
For example, the three-dimensional constraints are
 |  |
(3)
| |
 |  |
(4)
| |
 |  |  |
(5)
|
together with 
, 
, and 
, and the objective is to maximize 
.
