Symmetric and Asymmetric Parallelization of a Cost-Decomposition Algorithm for Multicommodity Flow Problems

References

• Bertsekas D. P.Linear Network Optimization: Algorithms and Codes (1991) (MIT Press, Cambridge, MA) Google Scholar
• Cappanera P. Parallelizzazione di un algoritmo di decomposizione per problemi di flusso di costo minimo di tipo multicommodity. Master's thesis (1996) . Department of Computer Science, University of Pisa, Pisa, ItalyGoogle Scholar
• Castro J. A specialized interior-point algorithm for multicommodity network flows. SIAM J. Optim. (2000) 10:852–877Crossref, Google Scholar
• Castro J., Frangioni A., Palma J. M., Dongarra J., Hernandez V. A parallel implementation of an interior-point algorithm for multicommodity network flows. Lecture Notes in Computer Science (2001) No. 1981(Springer-Verlag)301–315Vector and Parallel Processing—VECPAR 2000Crossref, Google Scholar
• Crainic T. G., Frangioni A., Gendron B. Bundle-based relaxation methods for multicommodity capacitated fixed charge network design problems. Discrete Appl. Math. (2001) 112:73–99Crossref, Google Scholar
• Cray Research Inc. (1994a) . PVM and HeNCE Programmer's Manual, Eagan, MNGoogle Scholar
• Cray Research Inc. (1994b) . SHMEM Technical Note for C, Eagan, MNGoogle Scholar
• De Leone R., Gaudioso M., Monaco M. F. Nonsmooth optimization methods for parallel decomposition of multicommodity flow problems. Ann. Oper. Res. (1993) 44:299–311Crossref, Google Scholar
• De Leone R., Meyer R. R., Kontogiorgis S., Zakarian A., Zakeri G. Coordination in coarse-grained decomposition. SIAM J. Optim. (1994) 4:777–793Crossref, Google Scholar
• De Silva A., Abramson D. A parallel interior point method and its application to facility location problems. Comput. Optim. Appl. (1998) 9:249–273Crossref, Google Scholar
• Ferris M. C., Horn J. D. Partitioning mathematical problems for parallel solution. Math. Programming (1998) 80:35–61Crossref, Google Scholar
• Ferris M. C., Mangasarian O. L. Parallel constraint distribution. SIAM J. Optim. (1992) 1:487–500Crossref, Google Scholar
• Ferris M. C., Mangasarian O. L. Parallel variable distribution. SIAM J. Optim. (1994) 4:815–832Crossref, Google Scholar
• Frangioni A. Solving semidefinite quadratic problems within nonsmooth optimization algorithms. Comput. Oper. Res. (1996) 23:1099–1118Crossref, Google Scholar
• Frangioni A. Dual-ascent methods and multicommodity flow problems. (1997) . Ph.D. thesis TD5/97, Dipartimento di Informatica, Università di Pisa, Pisa, ItalyGoogle Scholar
• Frangioni A. Generalized bundle methods. SIAM J. Optim. (2002) . ForthcomingCrossref, Google Scholar
• Frangioni A., Gallo G. A bundle type dual-ascent approach to linear multicommodity min cost flow problems. INFORMS J. Comput. (1999) 11:370–393Link, Google Scholar
• Gnanendran S. K., Ho J. K. Load balancing in the parallel optimization of block-angular linear programs. Math. Programming (1993) 62:41–67Crossref, Google Scholar
• Grigoriadis M. D., Khachiyan L. G. An exponential-function reduction method for block-angular convex programs. Networks (1995) 26:59–68Crossref, Google Scholar
• Hennessy J. L., A Patterson D.Computer Architecture: A Quantitative Approach (1990) (Morgan Kaufmann, San Francisco, CA) Google Scholar
• Ho J. K., Lee T. C., Sundarraj R. P. Decomposition of linear programs using parallel computation. Math. Programming (1988) 42:391–405Crossref, Google Scholar
• Klein P., Agrawal A., Ravi R., Rao S. Approximation through multicommodity flow. Proc. 31th IEEE Ann. Sympos. Foundations of Comput. Sci. (1990) 726–727Crossref, Google Scholar
• Kontogiorgis S. A., De Leone R., Meyer R. R. Alternating directions splittings for block angular parallel optimization. J. Optim. Theory Appl. (1996) 90:1–29Crossref, Google Scholar
• Lustig I. J., Li G. An implementation of a parallel primaldual interior-point method for block-structured linear programs. Comput. Optim. Appl. (1992) 1:141–161Crossref, Google Scholar
• Medhi D. Parallel bundle-based decomposition for large-scale structured mathematical programming problems. Annals of Operations Research (1990) 22:101–127Crossref, Google Scholar
• Meyer R. R., Schultz G. L. An interior point method for block-angular optimization. SIAM J. Optim. (1992) 1:121–152Google Scholar
• Patton P. C., Carey G. F. Performance limits for parallel processors. Parallel Supercomputing: Methods, Algorithms and Applications (1989) (John Wiley & Sons, New York) 1–16Google Scholar
• Pinar M. C., Zenios S. A. Parallel decomposition of multicommodity network flows using a linear-quadratic penalty algorithm. ORSA J. Comput. (1992) 4:235–249Link, Google Scholar
• Zenios S. A. On the fine-grain decomposition of multicommodity transportation problems. SIAM J. Optim. (1991) 1:643–669Crossref, Google Scholar
• Zenios S. A. Data-parallel computing for network-structured optimization problems. Comput. Optim. Appl. (1993) 3:199–242Crossref, Google Scholar
• Zenios S. A., Mulvey J. M. Vectorization and multitasking of nonlinear network programming algorithms. Math. Programming (1988) 42:449–470Crossref, Google Scholar