Efficient Tree Handling Procedures for Allocation/Processing Networks.
TEXAS UNIV AT AUSTIN CENTER FOR CYBERNETIC STUDIES
Pagination or Media Count:
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 allocationprocessing 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
- Operations Research