### Benefit-Cost Analysis of Coding Techniques for the Primal Transportation AlgorithmBenefit-Cost Analysis of Coding Techniques for the Primal Transportation Algorithm

Access Restriction
Subscribed

 Author Srinivasan, V. ♦ Thompson, G. L. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1973 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract A computer code for the transportation problem that is even more efficient than the primal-dual method is developed. The code uses the well-known (primal) MODI method and is developed by a benefit-cost investigation of the possible strategies for finding an initial solution, choosing the pivot element, finding the stepping-stone tour, etc. A modified Row Minimum Start Rule, the Row Most Negative Rule for choice of pivot, and a modified form of the Predecessor Index Method for locating stepping-stone tours were found to perform best among the strategies examined. Efficient methods are devised for the relabeling that is involved in moving from one solution to another. The 1971 version of this transportation code solves $\textit{both}$ 100 × 100 assignment and transportation problems in about 1.9 seconds on the Univac 1108 Computer, which is approximately the same time as that required by the Hungarian method for 100 × 100 assignment problems.An investigation of the effect on mean solution time of the number of significant digits used for the parameters of the problem indicates that the cost parameters have a more significant effect than the rim parameters and that the solution time “saturates” as the number of significant digits is increased. The Minimum Cost Effect, i.e. the fact that total solution time asymptotically tends to the time for finding the initial solution as the problem size is increased (keeping the number of significant digits for the cost entries constant), is illustrated and explained. Detailed breakup of the solution times for both transportation and assignment problems of different sizes is provided. The paper concludes with a study of rectangular shaped problems. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1973-04-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 20 Issue Number 2 Page Count 20 Starting Page 194 Ending Page 213

#### Open content in new tab

Source: ACM Digital Library