A Computational Study of the Effects of Problem Dimensions on Solution Times for Transportation Problems.
Abstract
The paper presents an indepth study of the influence of problem structure on the computational efficiency of the primal simplex transportation algorithm. The input for the study included over 1000 randomly generated problems with 185 different combinations of the number of sources, the number of destinations and the number of variables. Objective function coefficients were generated using three different probability distributions to study the effects of variance and skewness in these parameters. Every problem was solved using three different starting procedures, and the following data were collected for each problem: (1) Time required to obtain an optimal solution; (2) time required to obtain an initial basic solution; (3) number of artificial variables in the initial basic solution; (4) number of basis changes; (5) average time to perform a change of basis; (6) average number of basic variables in the 'stepping stone path' in each change of basis; (7) average number of variables considered before selecting one to enter the basis. (Modified author abstract)
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1973
- Accession Number
- AD0774031
Entities
People
- A. Napier
- D. Klingman
- G. Terry Ross
Organizations
- University of Texas at Austin