A convergent criss-cross method. (English) Zbl 0581.90052

The author presents a new criss-cross method different from that of S. Zionts [Manage. Sci. 15, 426-445 (1969)] for solving linear programming problems. Using this method one can start from a neither primal nor dual feasible solution and obtain an optimal solution in a finite number of steps if one exists. The novelty of the method lies in the fact that even if the starting solution or any intermediate solution is a primal or dual feasible solution, it will not go into the primal or dual simplex method. The finiteness of the method is established, and a numerical example is included. The author points out that the efficiency of the method in comparison with the simplex method of Zionts’ criss- cross method is still an open question.
Reviewer: J.Parida


90C05 Linear programming
65K05 Numerical mathematical programming methods
Full Text: DOI


[1] Balinsky M.L., SIAM Review 11 (3) pp 347– (1969) · Zbl 0225.90024
[2] Bland R.G., Mathematics of Operations Research 2 (2) pp 102– (1977) · Zbl 0408.90050
[3] Dantzig G.B., Linear programming and extensions (1963) · Zbl 0108.33103
[4] Rockafellar R.T., Combinatorial Mathematics and its Applications pp 104– · Zbl 0124.12004
[5] Zionts S., Management Science 15 (7) pp 426– (1969) · Zbl 1231.90294
[6] Zionts S., Management Science 19 (4) pp 406– (1972) · Zbl 0247.90034
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.