Efficient Tree Handling Procedures for Allocation/Processing Networks.

摘要

Processing network problems are minimum cost network flow problems in which the flow entering (or leaving) a node may be constrained to do so in given proportions. These problems include many practical large-scale linear programming applications. In this paper a special class of processing network problems called allocation/processing (AP) network problems is described. AP network problems model a realistic situation in which a single raw material is allocated to factories and the resulting finished products are distributed to customers. A special partitioning method (PPR algorithm) is introduced for the solution of AP network problems. This algorithm maintains a working basis as well as a so-called representative spannng tree. A method for updating the representative spanning tree is discussed which avoids tracing a number of cycles at each iteration. A FORTRAN implementation (PPRNET) of the PPR algorithm is described. Comparative computational results are presented for randomly generated AP network problems which were solved by PPRNET and MINOS. These results indicate that significant computational gains are possible with the use of special purpose processing network codes. (Author)