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

Kleinschmidt, Peter; Lee, Carl W.; Schannath, Heinz

Math. Program. 37, 153-168 (1987).

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.

MSC:

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

Keywords:

Hirsch-conjecture; dual transportation polyhedra; primal transportation problems; assignment algorithm; average complexity

Citations:

Zbl 0555.90071; Zbl 0441.90062

References:

[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