A dual interior primal simplex method for linear programming. (English) Zbl 0658.90062

Tamura, Akihisa; Takehara, Hitoshi; Fukuda, Komei; Fujishige, Satoru; Kojima, Masakazu

J. Oper. Res. Soc. Japan 31, No. 3, 413-430 (1988).

This paper proposes a hybrid computational method (DIPS method) which works as a simplex method for solving a standard form linear program, and, simultaneously, as an interior point method for solving its dual. The DIPS method generates a sequence of primal basic feasible solutions and a sequence of dual interior feasible solutions interdependently. Along the sequences, the duality gap decreases monotonically. As a simple method, it gives a special column selection rule satisfying an interesting geometrical property.

MSC:

90C05	Linear programming
65K05	Numerical mathematical programming methods

Keywords:

dual interior primal simplex method; hybrid computational method; interior point method