Transportation problems which can be solved by the use of Hirsch-paths for the dual problems. (English) Zbl 0642.90070

Summary: M. L. Balinski [Math. Oper. Res. 9, 629-633 (1984; Zbl 0555.90071)] uses his signature method for the proof of the Hirsch-conjecture [see G. B. Dantzig, Bull. Amer. Math. Soc. 70, 499-500 (1964)] for dual transportation polyhedra to obtain an efficient algorithm for the assignment problem. We will show how to extend this method to other primal transportation problems, including transportation problems with unit demands. We then prove that Balinski’s assignment algorithm is equivalent, cycle by cycle, to that of M. S. Hung and W. O. Rom [Oper. Res. 28, 969-982 (1980; Zbl 0441.90062)]. We demonstrate that, under some assumptions for our probability model, a modification of the latter algorithm has an average complexity of O(n 2log n) and present some computational results confirming this. We also present results that indicate that this modification compares favorably with Balinski’s algorithm and other codes.


90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90C27 Combinatorial optimization
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] M.L. Balinski, ”On two special classes of transportation polytopes,”Mathematical Programming Study 1 (1974) 43–58.
[2] M.L. Balinski, ”The Hirsch conjecture for dual transportation polyhedra,”Mathematics of Operations Research 9 (1984) 629–633. · Zbl 0555.90071
[3] M.L. Balinski, ”Signature methods for the assignment problem,”Operations Research 33 (1985) 527–536. · Zbl 0583.90064
[4] M.L. Balinski ”A competitive (dual) simplex method for the assignment problem,”Mathematical Programming 34 (1986) 125–141. · Zbl 0596.90064
[5] R.E. Burkard and U. Derigs,Assignment and Matching Problems: Solution Methods with FORTRAN-Programs (Springer, Berlin, Heidelberg, New York, 1980). · Zbl 0436.90069
[6] G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, New Jersey, 1963).
[7] G.B. Dantzig, ”Eight unsolved problems from mathematical programming,”Bulletin of the American Mathematical Society 70 (1964) 499–500.
[8] L.R. Ford and D.R. Fulkerson,Flows, in Networks (Princeton University Press, Princeton, New Jersey, 1962).
[9] D. Goldfarb, ”Eflicient dual simplex algorithms for the assignment problem,”Mathematical Programming 33 (1985) 969–982. · Zbl 0578.90051
[10] M.S. Hung and W.D. Rom, ”Solving the assignment problem by relaxation,”Operations Research 28 (1980) 969–982. · Zbl 0441.90062
[11] V.L. Klee and P. Kleinschmidt, ”The d-step conjecture and its relatives,”Mathematics of Operations Research to appear. · Zbl 0632.52007
[12] V.L. Klee and D.W. Walkup, ”The d-step conjecture for polyhedra of dimensiond<6,”Acta Mathematica 133 (1967) 53–78. · Zbl 0163.16801
[13] J. Riordan,An Introduction to Combinatorial Analysis (Wiley, New York, 1958). · Zbl 0078.00805
[14] R. Silver, ”An algorithm for the assignment problem,”Communications of the Association of Computing Machinery 3 (1960) 603–606. · Zbl 0097.32501
[15] N. Tomizawa, ”On some techniques useful for solution of transportation network problems,”Networks 1 (1972) 179–194. · Zbl 0253.90015
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.