Dantzig (1963, p. 98) proposed to choose the pivot column such that the respective (negative) coefficient of the objective function is minimal.
This tool refers to the according pivot rule as Dantzig's rule of the steepest ascent.
For the case of degenerated corners, this rule may result in an endless loop, i.e. the algorithm cycles among basic solutions without increasing the objective value and finding an optimal solution.
Early Examples
The first (known) example that leads to endless cycles if Dantzig's rule is applied was found by Hoffman in 1951 (cf. Dantzig, 1963, p. 228).
Hoffman's example involved nine variables and three equality-constraints.
The (linear) coefficients of both, the objective function and the constraints are given by trigonometric expressions.
Beale (1955) found the following, much simpler example that is also referred to by Dantzig (1963):
| - | 3/4 | x1 | + | 20 | x2 | - | 1/2 | x3 | + | 6 | x4 | → | min |
| s. t. |
| 1/4 | x1 | - | 8 | x2 | - | | x3 | + | 9 | x4 | ≤ | 0 |
| 1/2 | x1 | - | 12 | x2 | - | 1/2 | x3 | + | 3 | x4 | ≤ | 0 |
| | | | | | | | x3 | | | | ≤ | 1 |
|
xi | ∈ | ℝ+ |
Note: Both, Beale and Dantzig, state the above problem in canonical form with seven variables and three equality-constraints.
Selecting “Dantzig's rule” in the tab “Solution” after loading the above example will result in an endless loop.
Clicking (repeatedly) on “Next tableau” will compute a series of basic solutions.
Every sixth tableau will be the same.
Note: Please avoid clicking on “Solve” as this will initiate intensive computations.
The algorithm will stop automatically after about 20-30 seconds and having computed several million tableaus by then.
Please be gentle with our computing resources!
Selecting any other of the pivot rules available on the tab “Solution” will avoid cycling of the algorithm and yield the optimal solution after a few updates.
Further Examples
Gass and Vinjamuri (2004) list a few more examples of linear programs that cycle under Dantzig's rule.
They are mostly similar to the above example by Beale (1955).
Noteworthy is the following example that traces back to Kuhn (cf. Gass and Vinjamuri, 2004; Balinski and Tucker, 1969) as it illustrates that cycling may also occur if a linear program is unbounded:
| - | 2 | x1 | - | 3 | x2 | + | | x3 | + | 12 | x4 | → | min |
| s. t. |
| - | 2 | x1 | - | 9 | x2 | + | | x3 | + | 9 | x4 | ≤ | 0 |
| 1/3 | x1 | + | | x2 | - | 1/3 | x3 | - | 2 | x4 | ≤ | 0 |
| 2 | x1 | + | 3 | x2 | - | | x3 | - | 12 | x4 | ≤ | 2 |
|
xi | ∈ | ℝ+ |
Note: Gass and Vinjamuri (2004) state the LP in canonical form.
Here, the constraints have been shortened to inequalities.
Balinski and Tucker (1969) use a form similar to ORTOOL's “reduced form”.
In both papers, the slack variables carry the lowest indices (x1, x2, and x3).
In ORTOOL, the slack variables (s1, s2, and s3) are considered as having the highest indices.
The optimal solution of Kuhn's example is (0, 2, 0, 2) with an objective value of -2.
Using Dantzig's rule, the simplex algorithm cycles with a cycle length of 6.
The objective value will never fall below 0.
The optimal value is effectively bounded by the third constraint.
Removing this constraint, the linear program does not have an optimal solution.
(Rather than removing the constraint, it can be set inactive on the tab “Specification of LP”.)
With Dantzig's rule, the simplex algorithm will still cycle and not detect that the LP is unbounded.
Again, any other of the other pivot rules available on the tab “Solution” will avoid cycling of the algorithm.
