Premium
The Existence of a Short Sequence of Admissible Pivots to an Optimal Basis in LP and LCP
Author(s) -
Fukuda K.,
Lüthi HJ.,
Namiki M.
Publication year - 1997
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.1997.tb00083.x
Subject(s) - mathematics , sequence (biology) , linear programming , combinatorics , linear complementarity problem , bounded function , basis (linear algebra) , class (philosophy) , simplex algorithm , complementarity (molecular biology) , simplex , discrete mathematics , mathematical optimization , nonlinear system , mathematical analysis , computer science , genetics , physics , geometry , quantum mechanics , artificial intelligence , biology
We say an LP (linear programming) is fully nondegenerate if both the primal and the dual problems are nondegenerate. In this paper, we prove the existence of a sequence of | B ∖ B | admissible pivot from any basis B (not necessarily feasible) to the unique optimal basis B , if the given LP has an optimal solution and is fully nondegenerate. Here admissible pivots are those pivots (satisfying certain sign conditions) that exist if the current LP dictionary is not terminal, i.e., neither optimal, inconsistent nor dual inconsistent. A natural extension of the result to LCPs (linear complementarity problems) with sufficient matrices is given. The existence itself does not yield a strongly polynomial pivot algorithm for LPs but provides us with a good motivation to study the class of admissible pivot methods for LPs, as opposed to the narrower class of simplex methods for which the shortest sequence of pivots is not known to be polynomially bounded.