Implementation and Computational Study on an In-Core, Out-of-Core Primal Network Code

This paper presents extensive computational experience with a special-purpose primal simplex code using the augmented threaded index method for solving capacitated and uncapacitated transshipment and transportation problems. This code is distinguished from other codes for solving such problems in that not all of the data resides in central memory simultaneously; thus, it is referred to as an in-core, out-of-core code. The major advantages of such a code over an in-core code are (1) it can solve problems that the latter can not solve because of central memory requirements; (2) even for problems that the latter can solve, it requires less central memory, which is critical for fast job processing on multiprogrammed computer systems; and (3) the code can also be used as an in-core code.The design of such codes presents numerous computational difficulties in selecting the best starting and pivot procedures in order to minimize central as well as peripheral processing time. We present computational experience with various pivot, start and capacity buffer procedures, as well as different buffer sizes. Computational results are also provided for different types of network problems, including assignment, transportation, and minimum cost flow problems. These computational results are compared with in-core, out-of-kilter, negative cycle, and primal simplex network codes for problem sizes that these codes could solve.