A Bundle Type Dual-Ascent Approach to Linear Multicommodity Min-Cost Flow Problems

References

• Ali A. I. , Kennington J. MNETGEN program documentation. (1977) . Technical report IEOR 77003, Department of Industrial Engineering and Operations Research, Southern Methodist University Google Scholar
• Ali A. I. , Kennington J. L. , Liang T. T. Assignment with en-route training of navy personnel. Nav. Res. Log. (1993) 40 581 592 Crossref, Google Scholar
• Ali A. I. , Kennington J. , Shetty B. The equal flow problem. EJOR (1988) 36 107 115 Crossref, Google Scholar
• Ahuja R. K. , Magnanti T. L. , Orlin J. B. Network Flows (1993) (Prentice Hall, Englewood Cliffs, NJ) Google Scholar
• Assad A. A. Multicommodity network flows—A survey. Networks (1978) 8 37 91 Crossref, Google Scholar
• Barnhart C. Dual ascent methods for large-scale multicommodity flow problems. Nav. Res. Log. (1993) 40 305 324 Crossref, Google Scholar
• Bertsekas D. P. Linear Network Optimization (1991) (The MIT Press, Cambridge, MA) Google Scholar
• Barnhart C. , Hane C. A. , Jhonson E. L. , Sigismondi G. A column generation and partitioning approach for multicommodity flow problems. Telecomm. Systems (1995) 3 239 258 Crossref, Google Scholar
• Barnhart C. , Hane C. A. , Vance P. Integer multicommodity flow problems. (1996) . Center for Transportation Studies Working paper. Center for Transportation Studies, MIT Google Scholar
• Bhatt S. N. , Leighton T. A framework for solving VLSI layout problems. J. Comput. System Sci. (1984) 28 300 343 Crossref, Google Scholar
• Barnhart C. , Sheffy Y. A network-based primal-dual heuristic for multicommodity network flow problems. Trans. Sci. (1993) 27 102 117 Link, Google Scholar
• Castro J. PPRN 1.0 user's guide DR 94/06. (1994) (Statistics & Operations Research Department, Universitat Politècnica de Catalunya) Google Scholar
• Chen H. , Dewald C. G. A generalized chain labelling algorithm for solving multicommodity flow problems. Comput. Oper. Res. (1974) 4 437 465 Crossref, Google Scholar
• Cappanera P. , Frangioni A. Symmetric and asymmetric parallelization of a cost-decomposition algorithm for multicommodity flow problems. (1996) . Technical report TR 36/96, Dipartimento di Informatica, Università di Pisa (submitted to INFORMS Journal on Computing) Google Scholar
• Crainic T. G. , Frangioni A. , Gendron B. Bundle-based relaxation methods for multicommodity capacitated fixed charge network design problems. (1998) . Publication CRT-98-45, Centre de Recherche sur les Transports, Universite' de Montreal (submitted to Discrete Applied Mathematics) Google Scholar
• Carraresi P. , Frangioni A. , Nonato M. Applying bundle methods to optimization of polyhedral functions: An applications-oriented development. Ricerca Operativa (1996) 25 5 49 Google Scholar
• CPLEX Optimization Using the CPLEX callable library version 3.0. (1994) (CPLEX Optimization Inc.) Google Scholar
• Castro J. , Nabona N. An implementation of linear and nonlinear multicommodity network flows. EJOR (1996) 92 37 53 Crossref, Google Scholar
• Castro J. A specialized interior point algorithm for multicommodity network flows. SIAM J. Optim. (1999) . to appear on Google Scholar
• Dharma P. , Shapiro J. A. Augmented lagrangeans for linearly constrained optimization using AMPL. (1995) . CIV 518 Final Report Google Scholar
• Dantzig G. B. , Wolfe P. The decomposition principle for linear programs. Oper. Res. (1960) 8 101 111 Link, Google Scholar
• Ford L. R. , Fulkerson D. R. A suggested computation for maximal multicommodity network flows. Management Sci. (1958) 5 79 101 Link, Google Scholar
• Farvolden J. M. , Powell W. B. , Lustig I. J. A primal partitioning solution for the arc-chain formulation of a multicommodity network flow problem. Oper. Res. (1993) 41 669 693 Link, Google Scholar
• Frangioni A. Solving semidefinite quadratic problems within nonsmooth optimization algorithms. Comput. O.R. (1996) 23 1099 1118 Crossref, Google Scholar
• Frangioni A. Dual-ascent methods and multicommodity flow problems. (1997) . Ph.D. thesis TD 5/97, Dipartimento di Informatica, Università di Pisa Google Scholar
• Frangioni A. Generalized bundle methods. (1998) . TR 04/98, Dipartimento di Informatica, Università di Pisa (submitted to SIAM J. Optim.) Google Scholar
• Gregory J. W. , Fourier R. Linear programming FAQ. (1998) . http://www.mcs.anl.gov/otc/guide/faq/linear-programming-faq.html Google Scholar
• Geoffrion A. M. , Graves G. W. Multicommodity distribution system by benders decomposition. Management Sci. (1971) 20 822 844 Link, Google Scholar
• Goldfarb D. , Grigoriadis M. D. A computational comparison of the dinic and network simplex methods for maximum flow. Ann. O.R. (1988) 13 83 128 Crossref, Google Scholar
• Goffin J.-L. , Gondzio J. , Sarkissian R. , Vial J.-P. Solving nonlinear multicommodity flow problems by the analytic center cutting plane method. Math. Prog. (1997) 76 131 154 Crossref, Google Scholar
• Grigoriadis M. D. , Khachiyan L. G. Fast approximation schemes for convex programs with many blocks and coupling constraints. SIAM J. Optim. (1994) 4 86 107 Crossref, Google Scholar
• Grigoriadis M. D. , Khachiyan L. G. Coordination complexity of parallel price-directive decomposition. Math. O.R. (1996) 21 321 340 Link, Google Scholar
• Grigoriadis M. D. , Khachiyan L. G. An exponential-function reduction method for block-angular convex programs. Networks (1995) 26 59 68 Crossref, Google Scholar
• Grigoriadis M. D. , Khachiyan L. G. Approximate minimum-cost multicommodity flows in O(ε−2KNM) time. Math. Prog. (1996) 75 477 482 Crossref, Google Scholar
• Gallo G. , Pallottino S. Shortest path algorithms. Ann. O.R. (1988) 13 3 79 Crossref, Google Scholar
• Garg N. , Vazirani V. V. , Yannakakis M. Approximate max-flow min-(multi)cut theorems and their applications. Proc. 25th STOC (1993) 698 707 Crossref, Google Scholar
• Ho J. K. , Loute E. An advanced implementation of the dantzig-wolfe decomposition algorithm for linear programming. Math. Prog. (1981) 20 303 326 Crossref, Google Scholar
• Ho J. K. , Loute E. Computational experience with advanced implementation of decomposition algorithms for linear programming. Math. Prog. (1983) 27 283 290 Crossref, Google Scholar
• Hiriart-Urruty J.-B. , Lemaréchal C. A Series of Comprehensive Studies in Mathematics. Convex Analysis and Minimization Algorithms (1993) 306 (Springer-Verlag, Berlin) Crossref, Google Scholar
• Held M. , Wolfe P. , Crowder H. Validation of subgradient optimization. Math. Prog. (1974) 6 62 88 Crossref, Google Scholar
• Jones K. L. , Lustig I. J. Input format for multicom-modity flow problems. Program in Statistics and Operations Research (1992) (Department of Civil Engineering and Operations Research, Princeton University) Google Scholar
• Jones K. L. , Lustig I. J. , Farvolden J. M. , Powell W. B. Multicommodity network flows: The impact of formulation on decomposition. Math. Prog. (1993) 62 95 117 Crossref, Google Scholar
• Klein P. , Agrawal A. , Ravi R. , Rao S. Approximation through multicommodity flow. Proc. 31st FOCS (1990) 726 727 Crossref, Google Scholar
• Kelley J. E. The cutting-plane method for solving convex programs. J. SIAM (1960) 8 703 712 Google Scholar
• Kennington J. L. A survey of linear cost multicommodity network flows. Oper. Res. (1978) 26 209 236 Link, Google Scholar
• Kennington J. L. A primal partitioning code for solving multicommodity flow problems. (1978) . Technical report 79008, Department of Industrial Engineering and Operations Research, Southern Methodist University Google Scholar
• Kiwiel K. C. Proximity control in bundle methods for convex nondifferentiable optimization. Math. Prog. (1990) 46 105 122 Crossref, Google Scholar
• Kamath A. P. , Karmarkar N. K. , Ramakrishnan K. G. Computational and complexity results for an interior point algorithm on multicommodity flow problems. (1994) . Unpublished manuscript Google Scholar
• Kontogiorgis S. A. Alternating directions methods for the parallel solution of large-scale block-structured optimization problems. (1994) . Technical report MP-TR-94-13 (Ph.D. thesis), University of Wisconsin-Madison Google Scholar
• Kennington J. , Shalaby M. An effective subgradient procedure for minimal cost multicommodity flow problems. Management Sci. (1977) 23 994 1004 Link, Google Scholar
• De Leone R. , Gaudioso M. , Monaco M. F. Nonsmooth optimization methods for parallel decomposition of multicommodity flow problems. Ann. O.R. (1993) 44 299 311 Crossref, Google Scholar
• Leong T. , Shor P. , Stein C. Implementation of a combinatorial multicommodity flow algorithm. Proc. DIMACS Conf. (1993) New Brunswick Crossref, Google Scholar
• Larsson T. , Patriksson M. , Strämberg A.-B. Conditional subgradient optimization—Theory and applications. EJOR (1996) 88 382 403 Crossref, Google Scholar
• Medhi D. Bundle-based decomposition for large-scale convex optimization: Error estimate and application to block-angular linear programs. Math. Prog. (1994) 66A 79 102 Crossref, Google Scholar
• Du Merle O. , Goffin J.-L. , Vial J.-P. On the comparative behaviour of kelley's cutting plane method and the analytic center cutting plane method. (1996) . Technical report, HEC, Université de Genève Google Scholar
• Minoux M. Network synthesis and optimum network design problems: Models, solution methods and applications. Networks (1989) 19 313 360 Crossref, Google Scholar
• Polak G. G. On a parametric shortest path problem from primal-dual multicommodity network optimization. Networks (1992) 22 283 295 Crossref, Google Scholar
• Powell W. B. , Sheffi Y. The load planning problem of motor carriers: Problem description and a proposed solution approach. Trans. Res. (1983) 17A 471 480 Google Scholar
• Plotkin S. , Shmoys D. B. , Tardos É. Fast approximation algorithms for fractional packing and covering problems. Proc. 32nd FOCS (1991) 495 505 Crossref, Google Scholar
• Plotkin S. A. , Tardos É. Improved bounds on the max-flow min-cut ratio for multicommodity flows. Proc. 25th STOC (1993) 690 697 Crossref, Google Scholar
• Pinar M. C. , Zenios S. A. On smoothing exact penalty functions for convex constrained optimization. SIAM J. Optim. (1994) 4 486 511 Crossref, Google Scholar
• Shultz G. L. , Meyer R. R. An interior point method for block-angular optimization. SIAM J. Optim. (1991) 1 583 602 Crossref, Google Scholar
• Schramm H. , Zowe J. A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results. SIAM J. Optim. (1992) 2 121 152 Crossref, Google Scholar
• Tardos É . Approximate min-max theorems and fast approximation algorithms for multicommodity flow problems. (1994) . Unpublished manuscript Google Scholar
• Vanderbei R. J. LOQO: An interior point code for quadratic programming, SOR 94-15 . (1994) (Princeton University) Google Scholar
• Vanderbei R. J. , Carpenter T. J. Symmetric indefinite systems for interior point methods. Math. Prog. (1993) 58 1 32 Crossref, Google Scholar
• Zenios S. A. On the fine-grain decomposition of multicommodity transportation problems. SIAM J. Optim. (1991) 1 643 669 Crossref, Google Scholar
• Zahorik A. , Thomas L. J. , Trigeiro W. W. Network programming models for production scheduling in multi-stage, multi-item capacitated systems. Management Sci. (1984) 30 308 325 Link, Google Scholar
• Zakarian A. A. Nonlinear jacobi and ε-relaxation methods for parallel network optimization. (1995) . Technical report MP-TR-95-17, (Ph.D. thesis), University of Wisconsin-Madison Google Scholar
• Zakeri G. Multi-coordination methods for parallel solution of block-angular programs. (1995) . Technical report MP-TR-95-08, (Ph.D. thesis), University of Wisconsin-Madison Google Scholar