A TRANSPORTATION ALGORITHM AND CQDE Merrill M.' d: The University & Michigan Ann Arbor, Michigan *Preprint Number 44'. April 1960 First Dr.rft "..,'.. -'.; -. *This paper is released for limited circulation in' Lorre to facilitate liscussion. Any proposed. re:ren.e'or ue of materi. al in this.pper shoull. be ci'ared.with the a uthor.......

I/Y<

A TRANSPORTATION ALGORITHM AND CODE Merrill Mo Flood The University of Michigan Introduction The transportation problem and the assignment problem are two alternative names for the Hitchcock distribution proble. prl. s problem has received considerable attention in recent years because of its importance in a wide variety of practical situations, and especially for industrial operations research ap?. ea t caions We refer the. interested reader to other sourcesl for a discussion of practical applications, and for further references to the many techniques that have been offe arerd for solving this -rPobleni. Solution techniques seem to fall into two broad ls claes. c ss consists of variants of the Simplex Miethod of Dantzig2, including the earliest work by Hitchcock3 and Kantorovich4; also including some previous work by the present author.. T.he other class consists of variants of the Hungarian Method of K.uhn-, inrcluding the present paper. Gererally speaking, the Hungarian'Method seems to- be superior to the $implex Mirethod, for this special case of the general linea-r prograr..inTg probl]em, but efforts to eteend the idea of the Hungarian IMethod to the general linear prograrmlming problem have not produced computationai techniques superior to the Simplex Miethod for the moe eneral Ca... The Hungariran. Method, and the Hitchcock distri4bution problem, seem imIportant enough to merit further development the present paper discusses a.new variant that has proved to be effective computationally.* *Acknowledgement. I am very grateful to the IBM Research Center for supporting my work on the computer program for this algorithm, and for the use of the IBM 704 at the Center in testing the computational qualfity of the program. This work wsas done largely dur3ing two sunmmers at the Centner, while serving as a Gon-..sultant to I?3M,4 including the period of the Combinatorial Problems Institute during July of 1959. I am especially indebted to V. V. Van Ness, at the Center, for programming advice and for generous help in running test problems on the Center's IBM 704.

-2- - Problem The assignment problem is stated as follows: Devise an efficient computational algorithm for permuting the rows of a. given square matrix so as to minimize its traceo If the rows (or columns) of the matrix are not distinct then this special case is known as the transportation problem, and is exactly the product distribution problem of Hitchcock3 when stated in this form.. The problem rzy be rewritten in l ea-' programming form as follows: Find non-negative integers xij, subject to the restrictions n nm xij - ri and L x. ~ cj j=l i=l _f1l ril. m n that minimize the quantity Z Zdijxij; where ri, cj, di, m, and n are i=1 =.1 given positive integers. Under this foraulation, the problem is usually called an assignment problem if ri I cj i1 otherwise it is usually called a transportation problem. Hungarian Method It is evident that the solution to the assignment problem is not changed by adding a constant to each element of a'line" of the matrix, where a line is either a rorw or a column. It is also evident that if the addition of such constants yields a matrix of non-negative elements, but such that the trace is zero after some permutation of the rows, then this permutation is the solution we seek. The Hungarian Miethod proceeds in this fashion, always keeping the matrix non-negative while increasing the number of null elements that can be brought to the main Adiagonal by a row permutation. The mathematical basis for the Hungarian Method is provided by a constructive proof of the following theorem of K nig7 and Ergervary:

~..'..'...'.. KSnig-Ergervary Theorem If D is a square array of two kinds of marks, say zeros and plusses, and if: " a) x is the maximum number of zeros that c an be foqund. in the array such that no'two of them are in. the seme line,.and, j. cc.r- such th..t b) yis the miinimum number if.ine': that a.n fd such thates every zero of the array' is cort ine n isn o'ne of themi then x = y. The present author has shown:else:were..hotw the rows and columns of ~. ~...... a (0, +) matrix can be per ruteda into.the folloiag,. gsanlaardi' form. i 2 3 14 ~- C\J'\ 4 ~ ~ s ~.... l..' -'.' ~~~^,~: 1'~0.. ~c. 4-+ -4- ~.. +,..-" ~, —-:'-':i 4 -:+ m-2 ______ c + + + + + m+3 c +'.+. i +. + t _ g I 6 - - - I 1 - I. - 1 s D m +4 +_ _ 1 -+ + 1 + + + + denotes a subarray each of o elements may be o plus, I. a.... - o ~ m: —3 [ ~ i__ __I_ _ - - - -.- o o +____. +.. The subarrays of the stanrdard form have the following forms': _' denotes a subarray each of whose elemnents maybe zero or plus,'-" denotes a square subarray all -of,ho'se main. diagonal elements are zeros, denotes a subarray with at least one zero in each row, ~[ denotes a subaray with at least one.-ro in each column,. T denotes a subarray with no zeros. In this formn, the zeros are all contained with. in the columns passing through Dll, D22, - Drnam and the rows passing through- i'+L m+l and Dm+ m+-2 Consequently, if unity is added to each element of each of these lines, in turn,

-4the new matrix will have all elements positive; hence, unity can next be subtracted from every element of the matrix without producing any negative element. Since more was subtracted than was. added, to the matrix as a whole, this process must eventually terminates it does so when the zero elements fill the main diagonal in the standard form. The HiEugarian Method proceeds by two kinds of moves. One type of move involves finding a permutation that produces a standard form, so that the lines are identified for the additions to be mad.e The other type of move consists in adding and. subtracting to this set of lines until no further such unit changes can be made. Following Kuhn's6 terminology, we shall say that two zeros are "independent" if they are not on the same line. Also, a set of lines is called a "co ver if every zero is on soe line of the cover, A 7minimal cover" is:~ is't. lne t eove one containing the fewest lines By the K nig-Ergervary theorem, the maximal number of independent zeros is equal to the number of lines in a minimal cover. For further convenience, we shall call the number of elements in a set the "cardinal" of the seto We shall use the phrase "trial set' to denote any set of independent zeros chosen to that every zero of the matrix is on line with at least one of the independent zeros of the trial set; a "trial zero" is any zero in a trial set. The phrase "trial.cover" refers to a cover obtained using a specific trial set, and in the specific vra;y described nexto Fo.rm the trial cover, for a given trial set, as follows: 1).Include in the trial cover each line'containing a trial zero, that also includes a zero (called a "candidate") in some per-. pendicular line containing no trial zero. Consider these lines in the trial cover deleted from the matrix, and repeat this step until no further lines are added to the trial cover in this wayo 2) Include in the trial cover each row containing a trial zero, in the matrix remaining after the deletions of step 1).

.;., -— 5~ ~ ~~. ~ ~'"'~. ~~'^. ~~''. ^-'.~..:'-^-^.'^ ^...:~.....'-'..: 3) Include in a "candidate s zeros noted during ste-p 1). It follows easily, by an inspection of the standard form, that the trial cover is a minimal cover if the trial set is a maximal set; also, if the cardinal of the trial cover exceeds the order of the trial set then the trial set is not maximal. The Hungarian Method proceeds generally as follows: a) Choose a trial set.' If the order of this trial set is equal to the order of the matrix then the required permutation is the one that would permute the rows So as to place these zeros on the main diagonal. If not, go next to. step b). b). Consider the trial cover. If the cardinal of the trial cover is less than the order of the matrix then add a positive constant to all lines in the trial cover and subtract this constant from all lines of the matrix, choosing as this.constant the largest integer that will. leave all elements of the matrix non-negative; we call this constant the "fuse" for the cover and go next to step c). If the cardinal of the trial cover is not less that the order of the:matrix, go next to step d) c) Add to the trial set any new zeros that are.eligible. If the cardinal of the new trial set is less than the order of the matrix then return to step b), otherwise the process ends. d) The trial set is not mimximal. Delete all zeros from the trial set that are on two lines of the minimal cover; such zeros are called "degenerates." Add to the trial set from the candidate set, forming a new trial set, using candidates on the paired lines (of the trial cover) that led to the deletion of zeros from the trial set at the start'.of step d).. If the cardinal of the new trial set is less than the order of the matrix then.trn to step b), otherwise the process ends. This brief description of the Hungarian Method, including one specific. method for finding trial sets and trial covers, is intended only to indicate the general nature of the method. A more detailed and precise description of the steps actually used, in the variant presented in this paper, will be given in following sections; the variant actually used differs somewhat from the one described above, and choices left arbitrary above are made entirely definite in the computer code, but the differences-are not significant for present purposes.

Initial Problem Preparation It would be possible to solve an assignment problem, or a transportation problem, by use of the Hungarian Method from beginning to end. However, there are:a number of improvements that can be made easily, and several of these are discussed in the present paper and used, to advantage, in the IBM 704 code. We first list some of these, and describe them briefly; then principal features will be illustrated by simple numerical examples. Compression Subroutine. Lines of the matrix (row or column) having a~ *.... the same pattern of zero entries are combined. Except when determining fuses, compression leaves the procedures unchanged.. Reduction Subroutine. Each compressed line is made to have at least as many zeros as its frequency requires. Thus, if a compressed line includes of the original rows then it is made to have zeros in compressed columns that include at least X of the"original columns. Isolation Subroutine. The trial set is chosen by first selecting "isolated" zeros that stand alone in some compressed line. One or both of the compressed lines through such an isolate are then deleted, after their zeros are exhausted, and new isolates are added to the trial set until no isolate remains. Shortening Subroutine. If a compressed line has no more zeros than its frequency requires, then all these zeros.are added to the trial set. Zero Subroutine. A zero is chosen in a compressed line that contains: zeros in the fewest perpendicular lines. When several such zeros exist, perhaps even in more than one compressed line, that one is chosen which has the most lines parallel to it through zeros in the compressed line perpendicular to it; if a tie still remains, the zero is chosen arbitrarily from among tied cases. These Subroutines yield a trial set and also reduce the elements of the matrix.

Compression Example 3 2 1 4 5 8 2:1 4 2 2 0 3 1 5 o 0 + 1, 3. 4 0 1 0 2- 3 + 0 +0 3.. 1 1 3 2- 0 4 3+.0 3... 3 0 2 1 3 + O 0 + - 4 5 0 2. 2 3 1 5 The first and fifth rows,. with.frequencies' 2 ad compress into a new first-. row with frq:uery.6 similarly the first and f ifth columns compress Reduction Ei The first-compressed row reuires 6 zeros' but on.ly 2; similarly. the first compressed column requires 8'zeros and has none The smallest amount that can be subtracted from the. first cmpr-essed row, and yield a new zbro, is. I the fuse)) to-retain the old zero in the first compressed row and is. 11 t?,ve fase) to-retain'th..... second coluT, we must add 1 to the second columxn. 3 2 4 5 8 2 1 4.2 2 31'2. 1 0 20. -2 + 0 + O0 3 1 4 O-.0: 2, 4.1'. O 20.2 6. + + + 0 2,3 3 1 3 2 0. = 1 4 2 ~0 1-' 3 + + 0 + 2 + 2 3 1 3 ~..o 2 1'3' 1. 2 1.i:~.3 l ~' + 4 5 03 1 2 3.'0 o 1.2 125 o ~...__ _ _.... _ _ ~.,]~;. +1.'. 4 o0 1.2 +1 Compressed Rows 2 and 3, and compressed Column 1, all require redudtion; consider compressed Column 1 next, with fuse lo.

-83 2 1 4 5 3 2 4 5 2 1 o 2 0 4 2 0 O 2 o 3 3 4 1 1 0 2 3 3 1 1 3 1 4 2 0 4 = 3 2 0 3 3 3 1 0 2 1 3 2 1 2 0 4 4 o0 1 2 3 0 0 1 1 -1 -1 Here, no compression is possible and only Row 5 andL Column 5 require reduction; consider ow'5 next, with fuse lo 3 2 1 5 3 3 4 5 200 0 1 3 3 0 3 5 0 3 3 3 1 0 1 3 2 0 1 3 + 0 + 3 4 2 0 31 0 5 3 3 3 4- + 0 3 2 1 0 2 20 2 2 2 0 + 0 0 0 4 3 0 0 1 1- 2 0 0 0 2,3 +1 +1 No further compression is possible, so the reduction is complete. Isolation Subroutine The trial set is obtained by choosing isolated zeros (in the compressed matrix) as shown next, where the entry replacing the zero is the frequency for that trial zero and the subscripts indicate the order in;hich the isolated zeros were choseno 0 0 4 2 0 0 0 1 2 32 + 0 + 0 32 + 24 + 3 + + 0 + +2 +.+ - + 31 0 i- + + 31 1 + 33 o0 + 33 0 16

-9Note that lines are treated as though they were deerte a.ter there freownty goes to 0. Thi ex:ple does anot stress the of': trCg -ur choice of tlhe trial set, but recompressiJOn ornovaly octcur7as,'eer' to~a 4..rn..; t-e process as lines are deetec Shortieni b1 Saibrout ine When the reduJeda / Sand moa:rtsp:.' acts~''he -g no s. l further Isolat.e, re unA. pe ps at o. of line s during coxstr uct.on of a trial se-t, th hen teho:e., Sculbrou tine ay add zertos o tth treial set, as indiated for othe i". g-'.: + 2 3 o 0 +$ ~ + 0 -~ ~ ~0'0' - 2 3 2 10 0 + 2 02 - 0 O. 0 3.+ 0 Zero Subroutine hren reuced, and copresse'.a atr ea s tags we,>..-t application of the $solation and- Shorten ing E Sfub rotie:s yield, no fth e; trial. zeros- then the Zero Subroutine takes effect, The following e<sle ilustrates this process.~ 2 4 O 3 4 5 C, 0 5. - 0 0" 2 0 0. + 2 0.0 2 - 0 + 0 2 b 0 The tri"al ero in Row.3 sA CGolmt 1 is hn c bca it is i the. i ne having fewest zeros,.t.L in Coaay 14, ad is preee' the in Row'2 because Row 3 has more zeros, with 6, tfhas. 2ohas Be, $2 w^ith only 5 iFue Rul. e~ The Reduction Subroutine is usually ix SV if ec.. - compressed line is first reduced enough in one step to yield the e q aed

-10number of zeros; this will sometimes mean the use of more than one fuse in a single stepo The fuses are selected according to the "Fuse Rule," which states simply that just enough fuses are selected, in increasing order of numerical size, to yield the required number of zeros for the line being reduced. The following example illustrates application of the Fuse Rule. 3 2 1 4 5 3 2 I 4 5 2 1 0 2 0 41 2 0 0 2 0 2 3 1 10: 21 3 13 1 1 0. 3 1: 4 2 0 4 3 0.4.2 0.2 3I' 1 0 2 1 +1 3 3 2 1 3 0 4 4 0 0 1 2 4 13 0 0 1 i -1 -2 The fue f for Column 1 is 1, because Rows 1 and 3 yield 5 zeros to meet the requirement of 3. The fuse for Column 5 is 2, because Row 4 (and fuse =1) does not yi eld the 5 zeros required for Column 5; the next larger entry in Column 5 is 2, and.this becomes the actual fuse used when the Fuse Rule is applied to Column 5 Actually, for this example, our reduction using the Fuse Rule has completed the problem, except for finding the trial set which then proves to be a solution. Many problems are completely solved by the first trial set, after the initial preparation. When they are not completely solved, the reduction in the matrix is lerge enough1 to mak e a substantial cut in comarputational time required to complete the solution by some other procedure. For example, the Simplex Method could be used after this initial preparation with the trial set a part of tbh first trial basis. We shall return next to the Hungarian Method, and illustrate the use of the trial cover by a numerical exnample.

-11-. ~ ~....... Trial Cover Example We use the Isolation Subroutine example to illustrate the procedure for forming a trial cover. The trial set is shown as numerical entries in the compressed matrix, where a 0 denotes a zero in the compressed matrix that is not in the trial seto 3 3 4 5 5 3 + 2 + 3 + + 2 + 3 + + 3 4 i+ 3 0 1 We first note that the trial zeros in positions (3> )' ar (.4 4) are candidates, and this leads immediately to the inclusion of compressed Rows 3 and 4 in the trial cover; this is so because compressed Column 4 includes five lines but only four trial zeros. Similarly, the trial zero in position (2, 3) is a candidate, and places Column 3 in the trial cover. After-deleting compressed Rows 3 and 4, and compressed Column 3, the following array remains. 3 3 5 5 3 + + 3 + +. + In this array, the zero in position (1, 1) is a candidate, and the first column is added to the trial cover; thus, compressed Column of the original matrix is in the trial cover T No zeros remain, after deleting Column 1, so the trial cover is complete; it consists of compressed lines (R3, R4, Cl) C3). Note that. the cardinal of the trial cover is 14, and is equal to the cardinal of the\ trial set, so it follows that the trial set is maximal. Our next example shows how the trial cover is formed when the trial set is not maximal.

-123 3 4 5 5 3* + 0* + 3'+ + 0* - 3 + + + 3* 4 + 0* 4 4 * The trial cover includes compressed lines (R3, R4, CIl C3). with cardinal 14, while the cardinal of the trial set is 10. The candidate zeros are marked by asteriskso The zero in position (4, 3) must be removed from the trial set because it lies in intersecting paired lines of the trial cover; after its removal the trial set is increased by using candidate zeros in lines R4 and C3' FORTRAN Codes Two separate FORTFAT II codes were written and tested, based on the general principles of the algorithm. The earlier of these, called "CODE I," used recompression at intermediate stages of Step 1B but the later one, called "CODE II " did not. There were other important differences between CODES I and II. and neither code proceeds exactly as in the flow diagram for the algorithm We shall discuss only CODE II in the present paper; results with CODE I were 10 reported previouslyl. CODE II was written to include provision for measuring the computing time required, in any particular run, for each of several stages within.the whole runm This was madeposs e possible by the use of an internal clock that could be read MI m.de posoib. uld be read and recorded, at any point during the calculation, when required by the code. Provision was made for reading the clock at 12 such points in the code, including 7 clock readings at points normally passed more than once during a problem; these repeated clock readings can be made the first 20 times the point is reached, or fewer at each point if desired. Clock readings may also be taken.at the start and end of the computing cycle on a problem, and are always taken at the beginning and end of work on a problem.

' 13Alori. thm Flow Diagram lines using Fuse trt Reduce-t ucompre sse~ Compress ~ - Rule.... 1' —d~ Reduce Choose trial set I s cardional of trial Yes Stop compressed using.Isolation.set equal to order lines Shortening, and of matr.x' | o () Zero Slubroutines ~)~ Form trial Is cardinal of trial:Y cover cover cveless than....' orer of matrix No (1D) ~Find the Add the fuse| S.'fubotra.ct the Are there fuse for to each line L fuse from. any eligible Yes. the- trial, of the tx iai l' e<ach el eent. new zeros:ovr cov er covethe mtrix'for the o -' trial set Add. eligible. Is card.inal zeros to the. -of trial set Yes top trial set ] equal to.-r i.~ order of'.No matrix? " Delete al.to the.' A.dd eligible,s cardinal Yes Sto' degenerates trial set, non-degener-. of trial frois he -f rom the r ate zeros to set equal' - trial set' candidate the tr ial to order of set, choos- set matrix? ing only.. candidates on line..ith a de-,_. -.... ~ ~ ~ ~

CODE II also provides for a count of the number of times each of 17 points.is reached during the calculation of each problerm CODE II includes a subroutine that may be called in to compose a problem of any desired size, up to the dimensional limit of 60x150 for the cost matri L. The cost matrix and the row' cd olumn frequencies, are generated by the subroutine using a pseudorrandom number technique..:. Although CODE II was written and compiled to handle a transportation problem having at most 60 rows and 150 columnsr, it would be quite. a simple matter to recomp-ile the code to handle any problem hatving fewer than 24, 000 elements in the cost matrixo Other special features of CODE 1; that will not be discussed in any detail in this paper on pr for selecting.among a few alternative algorithms and several options on control Qf output' data. We next present a condensed flow'diagram for the CODE II FORTAN Sub~r2outines, a.;.l here aI.CLOtCK aridC IBICAT'OR. readings are taken during a computationo This will be useful.'for our subsequent discussion of times and frequencies through various computing stages of actual problems run. The name of the FORTAN II Subroutine appears first in.each boxof the flow diagranm CLOCK X entries.show the points during the computation at. which clock readings may be taken.' INDICArOR Y entries show the points during the computation at which counts are made of the frequencies of passing these points.. b. CODE II is represented correctly by this FORTRAN Plow Diagram, but differs in several respects from the Algorithm Flow Diagram. For example, the matrix is not recompressed at' each step in CODE II that is indicated by the' Algorithm FIlow Dia'gram and several other important changes have been made. in CODE II to facilitate the use of FORTIAJo

FORTRAN Flow Diagram Preliminary = P P7 MIN a P9 I ndicator 5 Intput Data Clock 2 -Clock 11 Add column isolates to trial set and delete ___M__._-:___________. appropriate lines ~...~~ -~~~-. I Indicator 11 Reu.c': 11 t..~'..:... l Hv SEv. r in's.' using se.. Rule.. Aidd row isolates to trial set and: delete Clock 31. - appropriate lines, ___;_________;~____:Yes.Was an isolate added.,-P..1'^-Z N,.,.,o by P.7?. ~. id. cataor 3..'.']aa last zero added. to - ____ ttrial set by zero.Li;st all zero. in z.eatroix P1. -Yik:T _.'. subrorutine, or is No: ~tr.ial set empty?. - * /..., ~r^I',. ~l | -- Is cardinal of trial.Pl1 ~ ~I lI set equal to order I Ind icator 8 3 P6 - No,- of matrix? GCour.t zer os in.atrix lines. P13 P7- o__ Was P6 immediately Indiator 15 P3 Yes. preeced P by P4? | PO cator 13 cor Clock 5':____^~~~~:______._ - Cloc__Clock..- P3. Reduce columns -~. -~ ~....just compressed Debug Data Indicator 13 ~ P4 * Clock. L _ t __._ P 1 P14 Compress parallel columns Clock 21 with commron isolates. Indicator 16..... ___ -. _ ~ ~ ^ ~ ~ ~ ~ -.'-.-~.~ - lOutput Data P13 Yes Can al co. pressed- column Clock 6 NHo ~ be reduce?. MIN I Reduce rows ~ Compress parallel' rows just compressed. with common isolates - r ~...... | ~ ~P4 P:14 -lYes _ Can a comprressed. row be e No'. reaGce *LT Indicator. 14I P7

......:..' -:.... FORTRAN Flow Diagram.. P5.. p G.' -.'Indicator 7 Indicator 17 Clock. 3.'. Add to trial cover for.'~....".'~,:'~.- each column contain-. Label. deleted rows ing iatrial zero not....yet ~co.vered. -P8. t' ri~al" -....:...''ft_, ~~P-~~ ~~~~..~ 17. qINo -". coaver. less then-order'.''. No.o._ Are there."a.ny. " ".;. Yes of matrix?:: Ye. degenerate zeros?.. Find. the,fuse for the - ake.'all zer.os.n... r' in cover'.''...atrix non-degenerate' -' indicator: 18'....'. 1 -covered rows andr. SUb'.. "tra.ct fuse $rm'.'..Add to trial cover each ~ ~'.'trtfuse fom.. -. line cointaining bth " elements'ofcolums' a~ ral zer. and not ete....'c and:idate, and'i'ete:'.' elet.'o'',* ~these lines from /mtr-ix. __ Ws weleme dts ofi. atl:..: elements'of uatrix'' Were any lines added toth P17. "No reduced by preceding:~ LYes__. trial cover'just'~ IS' ls'.stepT'..!.No _ _preceding? C'.'l-oc'k-~ ^''..'8.... A to trial'over'for'''.....trial zeron t..:.nt y c~~~-.''overed ___.____.____~.'_________ -'~~~.~.. ~ V;4. ~~pro7.-.a~..,:_..... t.'~ l:~......' ~ ~-.'' Indicator:.' Indicator 9... Is-cardinal of trial -e~gte~.. No~^. cover.less than 5 No.__ Ar. there any zere oseft. ef "Yes'."o' "f ".".' trix.'.' Yes,.. Y in.lines.not deleted.?..'.... ]...~ ~^.~ e'^'. ~ i ~ " ~ ~ - - - - - - - ^ ~ /: I ~ S u b t r a c t fu s e fr o..: nd.icato^ r1080' -4'. ~.~.'~..''.'. ~elements of. mcrere' ~:.:..,. ~.......ws and...~ad.fuse to Add'a zero to trial set. lements of coln:.. using.. zeroo su routine..'not covered ~P-'~.:.,'.G'-. ~ *.: ~ D^eete ~. degenerates.fr..'~...:'"'trial- zero.'~. ~::.~ ~~.- matrix Indicatr''' " ~'."... "': ~ "; - ""-'' "."~~~~~~~~A....... d a eo 6 r"l'- e..''' lmn.sofclA'

There is also a coding error in CODE II, but this error results only in stopping a few problems before the computation is entirely completed. CODE II is arranged'so thatl this case results in a special output, through. Subroutine PO, that provides the data necessary to complete the problem easily. This output, like'several others iincluded. in CODE I1, automatically indicates the point of error whether due. to machine difficulty or some other unexpected trouble. These possible sources of error will be ignored throughout the rest of our discussion, since they are rare and, recognizab leo Computational Results..';We P.re sWnt our con pulationr resUlts first in termns of CLOCK times. For example^ T CLOCK 2CCl XK 21. rep:.i:x.^ents actual total computing time; if SU3ROUTIEE PO is used, then actual total: coxmputing time. is T CLOK 7-CLOCK L-...As another exTamile, -'3 j CL;K; 8-CLOCK. 3 represents actual computing time used.In going once through SUB 3R UTIES P5, P8, P15, P16 if CLOCK 9 was not read meanwhileo This latter example illustrates' one way in ich in wic dividual CLOCK readings may be used to trace cycle, times in various portions of the- complete run. Similarly, if C9~ 4 follows CLICK 9 (or' f;LK 5, 6, 8 or 31) then SUB OUT IE P3 (rather than SUBROUT INE P) followed SUBROUTLNE P6; in this general nmnner'the.computing tilu- taken for various segmentSs of the run.can be determined-. a run, in v erY y fmay ~ff nt, ay^ but this feature will not be discussed in.. the present -paper.... Suff ce it to say that this feature permits the use of IN- DICATOR readings, in conjurction with CLOCK readings, to follow the path and'timing of coputationl steps in considerable detail when appropriate intermediate. ~outputs are.avai lableo We turn now to CLOCK results on one particular problem. (#Ell6.1), in order to show the kind of timing data obtained Thisisthe tonly problem that

has been computed also by a competing code, called B-TFL, perhaps the fastest standard IBM 704 code (SHARE 64)* available for the transportation problem. This problem was a 29x116 pseudorandom transportation problem thatok 3*03. minutes with CODE II, in comparison with 3 17 minutes with IB-TFL; this dif-. ference isso small tat the two codes may be considered equally efficient for this one 29x116 problem. 0n a second pseudorandom problem (#,E116.2), of size 29x116, CODE II took 1.90 minutes........ f...::'.-: The beginning of the flow through - El16 I my be follwed by noting CLOCK readings, as follows: ime 0124 525 2^ ^ " 30 631 3 37 39 cetc. LOCK. 1131:4 54 15, 4. 15 5 ______ 7 1. ii5 Time |5 6o 6o0 6o(6|(57O7221etc. | 73 79 9 5 0etc. CLOCK 2 22 2 2 3 2 2 8122 33 8^ * ROUTINE. P7 | no P77 IP7 P7 "" P' P, P7' | P7 |'1': | P6 P "... ~ ~. -~.,,o'.... io.. t....': In other words, the -initial coessedreducton throh P2 took 0.24 minutes. Then the P4 —>P6-3-Pl3 cycle was repeated 9 times in 0.340minutes, to oomplete:the compressed isolate columns reduction. Next the P7 cycle wasrepeated 6 ~ -...:;..:. -".... — list..., -. -...e.....; times, in.02 minutestolst the isolated zero. Next the P *P8P.sequence took 0.05 minutes to find a trial cover: fus.e and reduction before rese.q.e.c.e..d...... - turning to P4-p6 —P7. Since we had arranged to. hve only 9 readings on CLOCK 2,..e.. h. - 2........ -we cannot trace the path throlugh all 4te subroutines after 72 minutes. We do obtain, the first 10 tmtes at which COCKS3 and 8 are read and from tese data, algorithm, which is aother variant of Kuin:s Hurrli.n etho.

time, and the portion from P1i6 back to P5 through P -:P6-aP7-~P12 takes about 0o09 minutes each timeo The Indicators not only show fPrequencies wcith which each of several points are passed during the computationss but also m be.sed to assist in. tracing the actual path of the computation through the run~ The Indicator readings for problem i,11. ll6 follow. Inct -i 15 r 5 _ Frequency'_ 27 142217 I11 099 1.5 0 15, 79 0 < 1____ _ _ ___ ____ c r _t,!_..c ~,___ Subroutine 1_ IP64L P3L PI.P2L P P17-i For example, since 12 = 116 0 it is.sen. that Pl4 s Pi7 were not used; also find. that the paths usel:~ w ere' s follows I. Indicator-: 3 5 7 13 4 15 Stop *...................................Start 1... 3I. 15 5 127 15 1 1568f 7158... l h -. 1''...~'.. ~' This shows ta;t ubrou, ine P7. as en e:d 99 times- of these 15 led to P12, 15 to P6 68 back through P7, and i to Stop. It sho.ra also that Subroutine P7 was entered i5 e times 3, ad6 from 6 from3 an 68 from itself. Other pseud.orandom problems were genuerted, a' solved by CODE 11 with ~results as folos

-20Nber') - MIedian | Smallest Largest Input Dimensi on Solved i Computing: Computing Computing Output ~.:Time.Time Tim me Time — ___________ ___________ - In minutes 58x145'. 1 1 2 1. 3.. 1. 272 41*? 29x116 2 2.'47 90- 3-03. 18 29x9 1 3.53 35. 82.1 20x29 13.25. 18.36.14 9xlO..|?.45*", |013'*' | o65'* ~? | 9x10.. *':. -.* — 13 -6.? Actually, these problems were not quite completed. but the output.-is aadequa.te for easy completion. **All times too high because intermediate outputs were obtained. Several other small problems were -run, for various tests, each of which was constructed for some particular purpose. Among these were one 9x9 assignment problem (unit rim totals). and 30 5x15 assignment problems (unit column rim totals). The 30 5x15 assignment problems each took less than 0002 minutes conputing time. except for one that was not quite completed —due to the same error -n CODE II that kept the 58x145 problems from finishing. The 9x9 assignment "problem was constructed carefully to stretch CODE.II, and. did in fact require 0o26 minutes computing plus system time... - Test runs with the recompression subroutines (P3, P13, P14) omitted in CODE II have shown that their inclusion shortens computataion times appreciably for larger problems. Experience with CODE I, where complete recompression was done at each step rather than recompression only of lines having common isolates' as in CODE II, indicates the desirability of more extensive'recompression than is used in CODE II however, the'FORTRAN techniques used in CODE I are not effective in accomplishing more extensive recompression. Comparative tests of other alternatives have suggested various improvements that can easily be made in CODE II, but without deviating from the essential steps of our mathematical algorithm, and data on segmental computing times have helped in choosing among some of these alternativeso

-21Conclusions CODE II makes effective use of the Hungarian Method for solving transportation and assignment problems on the IBM 704. Computing experience indicates that CODE II is now as fast as the IB-TFL code, or any other existing code, and. CODE II would surely be improved further if rewrittetn to gain effeciency and speed.o The mathem acal algorithm supporting;CD" TII makes essential use of several reduction stepsJ, preliminary to the execution of zero covering and selecItion' sub outl ns bsecd on the present author's':pro of the K.nig-Ergeqrvary. Theoremo These Po eliminary reductions should be useful with other codes for the Hitchcock dcistribution problem, whether based upon the Hungarian Method, the Simplex Method, or any other method.. The techniques emplooyvdA in CODE II, for ob ervn., g timing a.nd frequencies of passages throughb egrarnts of a particular computation, are very useful' in de termining achoices urnong alternative codes. Experience with CODE II has provdede:timing and frequeqnucy d.ata that shows where further substantial improvements may possibly be made in CODE II, while holding to t;he.same mathematicaiL algoritlm o

-22References la. C. W. Churchman, Ro L. Ackoff and E. L. Arnoff. Introduction to Oprations Research, Wiley (1957), Chapters 11 and 12. b. Merrill M. Flood^ The- Traveling Salesman Problem, i Operations Research, Volo 4, No. 1, February 1956, pp. 61-75 2. George B. Dantzig. "application of the Simplex Nl ethod to a Transportation Problem. In.: To C. Koopmans (Ed.), Activity Analysis of Production and Allocation, Wiley (1951). 3. Frank Lo Hitchcock. "The Distribution of a Product from Several Sources to Numerous Localities,' Journal of athemtics and Physics, Vol. 20, (1941) pp. 224230. 4. Lo Katorovitch. "On the Translocation of wasss " geent Science Vol. 5, No. 1, October 1958, pp. 1-4. 5. Merrill M. Flood. "On the Hitchcock Distribution Problem," Pacific Journal of mhtemathtic, Vol. 3, No.. 2, June 1953; pp. 369-386. 6. H. W Kuhn "The- Hungarian Method for the Assignment Problem, Naval Research Logiscs urte rly VNo. V1o 2; arch-June 1955, Ppo 83-98. 7. Denes KSnig.'Uber Graphen und ihre Anwendung auf Determinantentheorie und Mengerniehre"':, taem c Annalen, Vol. 77, (1916), pp 453-465. 8. J. Egeo.gervary. "Matrixok Kormbinatorius Tulajdonsagairol," Mathematikai es Fizikai Lapok, Vol. 389 (1931), pp. 16-28. 9. Merrill MO Flood. "An Alternative Proof of a Theorem of K8nig as an Algorithm for the Hitchcock Distribution Problem." In: R. Bellman (Edo), Proceedings of the Symposia in Applied Mathematics, Vol. 10 (1960), to be published by the American Mathematical' Society. 10 Merrill M. Flood. "A Transportation Code.." In: Philip Wolfe (Edo), The ID Smposiu on Mathematical Prograsming, The RAND Corporation (196017 pp. 79-80 (abstract). ~ 11. L. R. Ford, Jr. and D. R. Fulkerson.."Solving the Transportation Problem,' RMenament Science, Vol. 3, No. 1, October 1956, pp. 24-32,

UNIVERSITY OF MICHIGAN 3 9015 02826 3427