Aggregation of network flow problems
Aggregation is a fundamental and widely used method of model simplification in management science, operations management, economics, database systems and related fields. It has also been used as a technical device in algorithm and software design for large scale optimization problems, particularly network flow problems. This class of problems is particularly amenable to aggregation owing to the special structural properties of networks. This research investigates aggregation of the capacitated transshipment problem. The author establishes a new framework for aggregation of this class of problems and provide an important characterization of arc types as a necessary preliminary to implementation. An aggregation procedure and a partition refinement process which generates a sequence of successively restricted aggregate problems are developed within this framework. A disaggregation methodology is defined that maps a feasible basic solution of the current aggregate problem to a basic solution of the next aggregate problem in the sequence. This map is incorporated into a complete algorithm which employs the aggregation-disaggregation concepts developed here. Finally, the results of this research are verified and tested in a computer implementation. (Author).
What people are saying - Write a review
We haven't found any reviews in the usual places.
SUMMARY AND CLASSIFICATION
AGGREGATION OF A NETWORK FLOW PROBLEM
ELEMENT GRAPH FOR MODEL SCHEMA OF NP
28 other sections not shown
AALOC adjusted arcs adjusted-reinstated aggregate arcs aggregate node aggregate problem AGNET Appendix arc i,j arc subset arcs corresponding array B(xr backpath basic arcs basic solution basic submatrix basis tree binary tree calling sequence capacitated transshipment problem column complete algorithm cost defined Definition directed graph disaggn disaggregation map DMGA DMGB DMGC ENDIF Example feasible fixed weight flow conservation genus Geoffrion GNET GO TO Step GOTO heuristic index set ISTAR iteratively modeling framework N(r+l,m N(r+l,nr+l necessary conditions network flow NjSTAR node set partition NODESR nonbasic notation NP(R Nr(i nr+l NUMARC OOB arcs optimal solution original arcs partition refinement partitioned adjacency matrix predecessor graph reinstated arcs replacement rule representative arcs RS4min simple refinement simplex method SNPr+1 SOLN solution of NPr stopping criterion structural aggregation procedure structural respecification maps submatrices surrogate problems tail nodes Theorem tuple vector x t(p