Abstract
A textured decomposition-based algorithm with parallel processing capability is proposed for solving the large-scale multicommodity network flow problem (MFP) popular in communication networks and transportation systems. It is shown that the algorithm will always converge to one of the stationary points characterized by the textured decomposition. A modification to the MFP and sufficient conditions are developed to guarantee that the convergent stationary point is the unique minimum solution of the modified MFP and is the global minimum solution of the MFP in its limit. To avoid an ill-conditioned problem, a practical two-stage textured decomposition-based algorithm is proposed to get a more elaborate approximate global minimum solution. A simulation example for this two-stage algorithm is given in which only few iterations are needed to converge. Assuming two processors are available, a speedup ratio around 10:1 is estimated, based on incorporating a projected Newton method with this two-stage algorithm.
| Original language | English |
|---|---|
| Pages (from-to) | 397-402 |
| Number of pages | 6 |
| Journal | Proceedings of the American Control Conference |
| DOIs | |
| State | Published - 1990 |
| Externally published | Yes |
| Event | Proceedings of the 1990 American Control Conference - San Diego, CA, USA Duration: 23 05 1990 → 25 05 1990 |