pivotcriterium

Pivot criterion, or pivotcriterion, refers to a rule or heuristic used in pivot-based algorithms, especially the simplex method in linear programming, to decide which variable enters the basis and which leaves it.

In each iteration of the primal simplex, a nonbasic variable is chosen to enter the basis to improve the objective, and a basic variable is chosen to leave to preserve feasibility. The leaving variable is determined by the minimum ratio test, ensuring that the new solution remains feasible. The entering variable is selected according to a specified rule that directs the direction and magnitude of improvement in the objective value.

Common pivot criteria include Dantzig's rule, which selects the entering variable with the largest positive reduced cost (the greatest potential objective improvement); Bland's rule, which always selects the entering variable with the smallest index to avoid cycling; and lexicographic pivoting, which resolves ties by a fixed ordering of variables. Other variants, such as the steepest-edge or Devex criteria, aim to improve numerical stability or reduce computational effort by guiding the pivot step more efficiently.

Impact and properties: Pivot criteria influence the practical performance of the algorithm, including iteration count and numerical stability, but not the final optimal solution. Some criteria provide guarantees against cycling and degenerate behavior (e.g., Bland's rule), while others are heuristics that may perform better on specific problem classes but lack worst-case guarantees.

Applications: While rooted in linear programming, pivot criteria also appear in related areas that use pivot-based updates, such as parametric programming and certain network-flow or simplex-like methods. The choice of criterion is a practical consideration that interacts with problem structure, data conditioning, and solver implementation.