Access Restriction

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

   Open content in new tab
Source: ACM Digital Library