Zade rule

The Zadeh rule belongs to a family of historically determined improvements that, during the course of the simplex method, hold additional data in addition to the current basis of the simplex method.

Among all the variables that can be entered into the basis, the rule selects the one that was least often entered into the basis, intuitively hoping that the variables can give a significant improvement in several iterations, but which give a slight improvement at each iteration.

Additional data structures in the Zade algorithm can thus be modeled as the number of occurrences that maps all variables to integers and shows how many times a particular variable has entered the basis. At each iteration, the algorithm selects for input into the basis a variable corresponding to the minimum value in this list.

Note that the rule does not uniquely determine which variable will be selected if the number of entries in the basis is equal.

By constructing a family of Markov decision-making processes in which the algorithm requires a superpolynomial number of steps, it was shown that the Zade rule has at least superpolynomial complexity in the worst case.

The result was presented by at the 2011 conference of the "Integer Programming and Combinatorial Optimization" ^[3] . Norman Zadeh, although he was no longer engaged in scientific work at this time, was present at the conference and fulfilled his promise ^[4] .