A Survey of Algorithms for Convex Multicommodity Flow Problems

References

• Ahuja R. V., Magnanti T. L., Orlin J. B.Network Flows: Theory, Algorithms, and Applications (1993) (Prentice Hall, Englewood Cliffs, NJ) Google Scholar
• Assad A. Multicommodity network flows—a survey. Networks (1978) 8:37–91Crossref, Google Scholar
• Authie G.Contribution à l'optimisation de flots dans les réseaux. Un multiprocesseur expérimental pour l'étude des itérations asynchrones (1987) . Thèse de doctorat d'état, LAAS, Toulouse, FranceGoogle Scholar
• Bertsekas D. P. Projected Newton methods for optimization problems with simple constraints. Siam J. Control Optim. (1982) 20:221–246Crossref, Google Scholar
• Bertsekas D. P., Gafni E. M. Projected Newton methods and optimization of multicommodity flows. IEEE Trans. Automat. Contr. (1983) AC-28:1090–1096Crossref, Google Scholar
• Bertsekas D. P., Gendron R., Tsai W. K.Implementation of an optimal multicommodity network flow algorithm based on gradient projection and a path flow formulation (1984) . Report LIDS-P-1364, MIT Laboratory for Information and Decision Systems, Cambridge, MAGoogle Scholar
• Bertsekas D. P., Gallager R. G.Data Networks (1987) (Prentice-Hall, Englewood Cliffs, NJ) Google Scholar
• Bertsekas D. P., Tsitsiklis J. N.Parallel and Distributed Computation (1989) (Prentice-Hall, Englewood Cliffs, NJ) Google Scholar
• Cantor D., Gerla M. Optimal routing in a packet-switched computer network. IEEE Trans. Comput. (1974) C-23(10):1062–1069Crossref, Google Scholar
• Cheney W., Goldstein A. Newton's method for convex programming and Chebishev approximation. Num. Math. (1959) 1(5):253–268Crossref, Google Scholar
• Chifflet J., Mahey P., Reynier V. Proximal decomposition for multicommodity flow problems with convex costs. Telecommunication Systems (1994) 3:1–10Crossref, Google Scholar
• Choi I. C., Goldfarb D., Coleman F., Li Yuying. Solving multicommodity network flow problems by an interior point method. (1990) (Large-Scale Numerical Optimization, SIAM) 58–69Google Scholar
• Dantzig G. B., Wolfe P. The decomposition algorithm for linear programming. Econometrica (1961) 29(4):767–778Crossref, Google Scholar
• du Merle O., Goffin J. L., Vial J. P. On improvements to the analytic center cutting plane method. Comput. Optim. Applications (1998) 11:37–52Crossref, Google Scholar
• Eckstein J. E.Splitting methods for monotone operators with applications to parallel optimization (1989) . Ph.D. Thesis, Department of Civil Engineering, Massachusetts Institute of Technology, Cambridge, MAGoogle Scholar
• Eckstein J. E., Fukushima M. Some reformulations and applications of the alternating direction method of multipliers. Large Scale Optimization: State of the Art (1993) (Kluwer Academic Publishers B.V., The Netherlands) 119–138Google Scholar
• Eckstein J. E. Parallel alternating direction multiplier decomposition of convex programs. J. Optim. Theory and Applications (1994) 80:39–62Crossref, 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(4):669–693Link, Google Scholar
• Florian M., Guelat J., Spiess H. An efficient implementation of the PARTAN variant of the linear approximation method for network equilibrium problem. Networks (1987) 17:319–339Crossref, Google Scholar
• Ford L. R., Fulkerson D. R.Flows in Networks (1962) (Princeton University Press, Princeton, NJ) Crossref, Google Scholar
• Franck M., Wolfe P. An algorithm for quadratic programming. Naval Res. Logist. Quart. (1956) 3:95–110Crossref, Google Scholar
• Fratta L., Gerla M., Kleinrock L. The flow deviation method: An approach to store-and-forward communication network design. Networks (1973) 3:97–133Crossref, Google Scholar
• Fukushima M. A nonsmooth optimization approach to nonlinear multicommodity network flow problems. J. Oper. Res. Soc. Japan (1984) 27(2):151–177Google Scholar
• Gabrel V., Minoux M.Large scale LP relaxations for minimum cost multicommodity flow problems with step increasing cost functions and computational results (1996) . Technical Report 96/17, Laboratoire MASI, Université Paris 6, FranceGoogle Scholar
• de Ghellinck G., Vial J.-P. A polynomial Newton method for linear programming. Algorithmica (1986) 1:425–453Crossref, 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. Programming (1997) 76:131–154Crossref, Google Scholar
• Goffin J.-L., Haurie A., Vial J.-P. Decomposition and nondifferentiable optimization with the projective algorithm. Management Sci. (1992) 38(2):284–302Link, Google Scholar
• Goldberg A. V., Tarjan R. E. Finding minimum cost circulations by canceling negatives cycles. J. Assoc. Comput. Mach. (1989) 36(4):873–886Crossref, Google Scholar
• Gondran M., Minoux M.Graphes et Algorithmes (1979) (Eyrolles, France) Google Scholar
• Gondzio J., Sarkissian R., Vial J.-P. Using an interior point method for the master problem in a decomposition approach. European J. Oper. Res. (1997) 101(3):577–587Crossref, Google Scholar
• Hossein P. A., Bertsekas D. P., Tseng P. Relaxation methods for network flow problems with convex arc costs. SIAM. J. Control Optim. (1987) 5(25):1219–1243Google Scholar
• Hu T. C. Multi-commodity network flows. Oper. Res. (1963) 11:344–360Link, Google Scholar
• Ibaraki S., Fukushima M. Primal-dual proximal point algorithm for multicommodity network flow problems. J. Oper. Res. Soc. Japan (1994) 37(4):297–309Google Scholar
• Idrissi H., Lefebvre O., Michelot C. Applications and numerical convergence of the partial inverse method. Optimization (1989) (Springer Verlag, Germany) 39–54Lecture Notes in Math. 1405Crossref, Google Scholar
• Jones K. L., Lustig I. J., Farvolden J. M., Powell W. B. Multicommodity network flows: The impact of formulation on decomposition. Math. Programming (1993) 62:95–117Crossref, Google Scholar
• Karzanov A. V., McCormick S. T. Polynomial methods for separable convex optimization in totally unimodular linear spaces with applications to circulations and co-circulations in networks. SIAM J. Comput. (1997) 26:1245–1275Crossref, Google Scholar
• Kelley J. E. The cutting plane method for solving convex programs. J. Soc. Indust. Appl. Math. (1960) 8:703–712Crossref, Google Scholar
• Kennington J. F. A survey of linear cost multicommodity network flows. Oper. Res. (1978) 2(26):209–236Link, Google Scholar
• Kleinrock L.Communication Nets: Stochastic Message Flow and Delay (1964) (McGraw-Hill, New York) Google Scholar
• Lasdon L. S.Optimization Theory for Large Systems (1970) (Macmillan, New York) Google Scholar
• LeBlanc L.Mathematical programming algorithms for large scale network equilibrium and network design problems (1973) . Ph.D. Dissertation, IE/MS Dept., Northwestern University, Evanston ILGoogle Scholar
• LeBlanc L., Morlok E., Pierskalla W. An efficient approach to solving the road network equilibrium traffic assignment problem. Trans. Res. (1975) 9:309–318Crossref, Google Scholar
• LeBlanc L., Helgason R., Boyce D. E. Improved efficiency of the Frank-Wolfe algorithm for convex network programs. Transportation Sci. (1985) 19:445–462Link, Google Scholar
• Lemaréchal C. Méthodes de sous-gradients. Bulletin de la Direction des Etudes et Recherches EDF (1974) C(2):5–14Google Scholar
• Mahey P., Oualibouch S., Pham D. T. Proximal decomposition on the graph of a maximal monotone operator. SIAM J. Optim. (1995) 5(2):454–466Crossref, Google Scholar
• Mahey P., Ouorou A., LeBlanc L., Chifflet J. A new proximal decomposition algorithm for routing in telecommunication networks. Networks (1998) 31:227–238Crossref, Google Scholar
• Medhi D. Bundle-based decomposition for large scale convex optimization: Error estimate and application block-angular linear programs. Math. Programming (1994) 66(1):79–102Crossref, Google Scholar
• Minoux M. Network synthesis and optimum network design problems: Models, solution methods and applications. Networks (1989) 19(John Wiley & Sons, New York) 313–360Google Scholar
• Nagamochi H.Studies on multicommodity flows in directed networks (1988) . thesis, Eng. Dr. thesis, Kyoto University, JapanGoogle Scholar
• Ouorou A.Décomposition proximale des problèmes de multiflot à critère convexe (1995) (Application aux problèmes de routage dans les réseaux de communication. Thèse Doctorale, Université Blaise Pascal, Clermont-Ferrand, France) Google Scholar
• Ouorou A., Mahey P. Minimum mean cycles canceling method for nonlinear multicommodity flow problems. European J.Oper. Res. (1996) . ForthcomingGoogle Scholar
• Patriksson M.The traffic assignment problem: models and methods (1994) (Topics in Transportation, VSP,Utrecht, The Netherlands) Google Scholar
• Pinar M. C., Zenios S. Parallel decomposition of multicommodity network flows using a linear quadratic penalty algorithm. ORSA J. Computing (1992) 4(3):235–249Link, Google Scholar
• Pinar M. C., Zenios S. A. A comparative study of parallel decompositions for multicommodity flow problems. Parallel Algorithms and Applications (1993) 1:255–271Crossref, Google Scholar
• Rockafellar R. T. Monotone operators and the proximal point algorithm. SIAM. J. Control and Optim. (1976) 14:877–898Crossref, Google Scholar
• Rockafellar R. T.Convex Analysis (1970) (Princeton University Press, Princeton, NJ) Crossref, Google Scholar
• Rockafellar R. T. Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res (1976) 1:97–116Link, Google Scholar
• Schultz G. L., Meyer R. R. An interior point method for block angular optimization. SIAM J. Optim. (1991) 1(4):583–602Crossref, Google Scholar
• Schwartz M., Cheung C. The gradient projection algorithm for multiple routing in message-swicthed networks. IEEE Trans. on Communications (1976) COM-24:449–456Crossref, Google Scholar
• Schwartz M., Stern T. E. Routing techniques used in computer communication networks. IEEE Trans. on Communications (1980) COM-28:539–552Crossref, Google Scholar
• Spingarn J. E. Partial inverse of a monotone operator. Appl. Math. Optim. (1983) 10:247–265Crossref, Google Scholar
• Spingarn J. E. Applications of the method of partial inverse to convex progr decomposition. Math. Programming (1985) 32:199–223Crossref, Google Scholar
• Stern T. E. A class of decentralized routing algorithms using relaxation. IEEE Trans. Communications (1977) COM-25:1092–1102Crossref, Google Scholar
• Tseng P. Dual ascent methods for problems with strictly convex costs and linear constraints: A unified approach. SIAM J. Control and Optim. (1990) 28:214–242Crossref, Google Scholar
• Tseng P., Bertsekas D. P. Relaxation methods for problems with strictly convex separable arc costs and linear constraints. Math. Programming (1987) 38:303–321Crossref, Google Scholar
• Von Hohenbalken B. Simplicial decomposition in nonlinear programming algorithms. Math. Programming (1977) 13:49–68Crossref, Google Scholar
• Wolfe P. A method of conjugate subgradients for minimizing nondifferentiable functions. Nondifferentiable Optimization, Math. Programming Study (1975) 3:145–173Crossref, Google Scholar
• Zangwill W.Nonlinear Programming: A Unified Approach (1969) (Prentice-Hall, Englewood Cliffs, NJ) Google Scholar
• Zenios S. A., Censor Y. Massively parallel row-action algorithms for some nonlinear transportation problems. SIAM J. Optim. (1991) 1:373–400Crossref, Google Scholar