On finding primal- and dual-optimal bases. (English) Zbl 0755.90056

Megiddo, Nimrod

ORSA J. Comput. 3, No. 1, 63-65 (1991).

Summary: We show that if there exists a strongly polynomial time algorithm that finds a basis which is optimal for both the primal and the dual problems, given an optimal solution for one of the problems, then there exists a strongly polynomial algorithm for the general linear programming problem. On the other hand, we give a strongly polynomial time algorithm that finds such a basis, given any pair of optimal solutions (not necessarily basic) for the primal and the dual problems. Such an algorithm is needed when one is using an interior point method and is interested in finding a basis which is both primal- and dual-optimal.

MSC:

90C05	Linear programming
90C60	Abstract computational complexity for mathematical programming problems
90-08	Computational methods for problems pertaining to operations research and mathematical programming

Keywords:

strongly polynomial time algorithm