×

Multicommodity network flows: A survey. II: Solution methods. (English) Zbl 1480.90087

Summary: The multicommodity network flow (MCNF) problem is an important and challenging topic in many scheduling and routing applications. As a follow-up survey paper to the previous one that focus on the MCNF applications and formulations, this paper first introduces the conventional MCNF solution methods such as price-directive, resourcedirective, and basis partitioning methods, then summarizes recent progress in applying approximation algorithms, interior-point algorithms, quadratic programming algorithms, and heuristics to solve the linear or integral multicommodity network flow problems. Finally the computational performance of different solution methods in literature is compared and directions for future research are suggested.

MSC:

90B10 Deterministic network models in operations research
90C05 Linear programming
90C10 Integer programming

Software:

KORBX; MINOS; OSL; IPM; PPRN
PDFBibTeX XMLCite
Full Text: Link

References:

[1] Aggarwal, A., Oblak, M., & Vemuganti, R. (1995, Dec). A heuristic solution procedure for multicommodity integer flows. Computers & Operations Research, 22(10), 1075-1087. · Zbl 0841.90062
[2] Ahuja, R., Magnanti, T., & Orlin, J. (1993). Network flows: theory, algorithms and applications. Englewood Cliffs, NJ: Prentice Hall. · Zbl 1201.90001
[3] Albrecht, C. (2000). Provably good global routing by a new approximation algorithm for multicommodity flow. In Ispd ’00: Proceedings of the 2000 international symposium on physical design (pp. 19-25). New York, NY, USA: ACM Press.
[4] Albrecht, C. (2001, May). Global routing by new approximation algorithms for multicommodity flow. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 20(5), 622-632.
[5] Ali, A., Helgason, R., Kennington, J., & Lall, H. (1980). Computational comparison among three multicommodity network flow algorithms. Operations Research, 28(4), 995-1000. · Zbl 0445.90086
[6] Ali, A., & Kennington, J. (1977). Mnetgen program documentation (Technical Report 77003). Dallas: Department of IEOR, Southern Methodist University.
[7] Alvelos, F., & Valério de Carvalho, J. (2000). Solving the multicommodity flow problem by branch-and-price (Tech. Rep.). Braga, Portugal: Departamento de Produção e Sistemas, Universidade do Minho.
[8] Assad, A. (1978). Multicommodity network flows-a survey. Networks, 8(1), 37-91. · Zbl 0381.90040
[9] Assad, A. (1980, Octobor). Solving linear multicommodity flow problems. In Proceedings of the ieee international conference on circuits and computers iccc 80 (pp. 157-161).
[10] Atkinson, D., & Vaidya, P. (1995). A cutting plane algorithm for convex programming that uses analytic centers. Mathematical Programming, 69(1, Ser.B), 1-43. 1813-713X Copyright © 2018 ORSTW · Zbl 0855.90094
[11] Awerbuch, B., & Leighton, T. (1993). A simple local-control approximation algorithm for multicommodity flow. In Proceedings of the 34th annual ieee symposium on foundations of computer science (pp. 459-468). IEEE. Awerbuch, B., & Leighton, T. (1994). Improved approximations for the multi-commodity flow problem and local competitive routing in networks. In Proceedings of the twenty-sixth annual acm symposium on theory of computing (pp. 487-496). New York, NY, USA: ACM Press.
[12] Bahiense, L., Barahona, F., & Porto, O. (2000). Solving steiner tree problems in graphs with lagrangian relaxation (RC 21846). Yorktown Heights, NY: Research Division, IBM T.J. Watson Research Center.
[13] Barahona, F., & Anbil, R. (2000). The volume algorithm: producing primal solutions with a subgradient method. Mathematical Programming, 87(3, Ser. A), 385-399. · Zbl 0961.90058
[14] Barahona, F., & Anbil, R. (2002, Apr). On some difficult linear programs coming from set partitioning. Discrete Applied Mathematics, 118(1-2), 3-11. · Zbl 0995.90069
[15] Barahona, F., & Chudak, F. (1999). Near-optimal solutions to large scale facility location problems (RC 21606). Yorktown Heights, New York: IBM Research Division, T.J. Watson Research Center.
[16] Barahona, F., & Chudak, F. (2000). Solving large scale uncapacitated facility location problems. In P. Pardalos (Ed.), Approximation and complexity in numerical optimization : continuous and discrete problems (v.42) (pp. 48-62). Dordrecht: Kluwer Academic Publishers. · Zbl 0965.90027
[17] Barnhart, C. (1988). A network-based primal-dual solution methodology for the multicommodity network flow problem (Unpublished doctoral dissertation). Transportation Systems Division, M.I.T., Cambridge, MA
[18] Barnhart, C. (1993, April). Dual-ascent methods for large-scale multicommodity flow problems. Naval Research Logistics, 40(3), 305-324. · Zbl 0780.90030
[19] Barnhart, C., Hane, C., & Vance, P. (1996, Jun). Integer multicommodity flow problems. In W. Cunningham, S. Mc-Cormick, & M. Queyranne (Eds.), Integer programming and combinatorial optimization, proceedings of the 5th international conference (ipco v) held in vancouver, bc, canada (Vol. 1084, pp. 58-71). Berlin Heidelberg: Springer. · Zbl 1415.90132
[20] Barnhart, C., Hane, C., & Vance, P. (2000). Using branch-and-price-and-cut to solve origin-destination integer multi-commodity flow problems. Operations Research, 48(2), 318-326.
[21] Barnhart, C., Johnson, E., Hane, C., & Sigismondi, G. (1995). An alternative formulation and solution strategy for multicommodity network flow problems. Telecommunication Systems, 3, 239-258.
[22] Barnhart, C., Johnson, E., Nemhauser, G., Savelsbergh, M., & Vance, P. (1998). Branch-and-price: column generation for solving huge integer programs. Operations Research, 46(3), 316-329. · Zbl 0979.90092
[23] Barnhart, C., & Sheffi, Y. (1993, May). A network-based primal-dual heuristic for the solution of multicommodity network flow problems. Transportation Science, 27(2), 102-117. · Zbl 0791.93010
[24] Bertsekas, D. (1985). A unified framework for primal-dual methods in minimum cost network flow problems. Mathe-matical Programming, 32(2), 125-145. · Zbl 0567.90023
[25] Bertsekas, D. (1998). Network ptimization: continuous and discrete models. P.O. Box 391, Belmont, MA 02178-9998: Athena Scientific. · Zbl 0997.90505
[26] Bertsekas, D., Hossein, P., & Tseng, P. (1987). Relaxation methods for network flow problems with convex arc costs. SIAM Journal on Control and Optimization., 25(5), 1219-1243. · Zbl 0641.90036
[27] Bienstock, D. (1999). Approximately solving large-scale linear programs. i: Strengthening lower bounds and accelerating convergence (Tech. Rep. No. CORC Report 1999-1). New York, NY: Department of IEOR, Columnbia University.
[28] Bienstock, D. (2002). Potential function methods for approximately solving linear programming problems: theory and practice. New York: Kluwer Academic Publishers. · Zbl 1088.90001
[29] Bienstock, D., Chopra, S., Günlük, O., & Tsai, C.-Y. (1998). Minimum cost capacity installation for multicommodity network flows. Mathematical Programming, 81(2, Ser. B), 177-199. · Zbl 0922.90064
[30] Bienstock, D., & Iyengar, G. (2004). Solving fractional packing problems in o * ( 1 ϵ ) iterations. In Stoc ’04: Proceedings of the thirty-sixth annual acm symposium on theory of computing (pp. 146-155). New York, NY, USA: ACM Press.
[31] Brunetta, L., Conforti, M., & Fischetti, M. (2000, Apr). A polyhedral approach to an integer multicommodity flow problem. Discrete Applied Mathematics, 101(1-3), 13-36. · Zbl 0944.90008
[32] Cappanera, P., & Frangioni, A. (2003). Symmetric and asymmetric parallelization of a cost-decomposition algorithm for multicommodity flow problems. INFORMS Journal on Computing, 15(4), 369-384. · Zbl 1238.90022
[33] Carolan, W., Hill, J., Kennington, J., Niemi, S., & Wichmann, S. (1990). An empirical evaluation of the korbx algorithms for military airlift applications. Operations Research, 38(2), 240-248.
[34] Castro, J. (2000a, Aug). Solving difficult multicommodity problems through a specialized interior-point algorithm (Tech. Rep. No. DR20000-14). Pau Gargallo 5, 08028 Barcelona, Spain: Statistics and Operations Research Dept., Universitat Politèc-nica de Catalunya.
[35] Castro, J. (2000b). A specialized interior-point algorithm for multicommodity network flows. SIAM Journal on Opti-mization, 10(3), 852-877. · Zbl 0955.90087
[36] Castro, J. (2001, Aug). Solving quadratic multicommodity problems through an interior-point algorithm (Tech. Rep. No. DR20001-
[37] Pau Gargallo 5, 08028 Barcelona, Spain: Statistics and Operations Research Dept., Universitat Politècnica de 1813-713X Copyright © 2018 ORSTW Catalunya.
[38] Castro, J., & Frangioni, A. (2001). A parallel implementation of an interior-point algorithm for multicommodity network flows. In V. H. J.M.L.M. Palma J. Dongarra (Ed.), Vector and parallel processing-vecpar 2000 : 4th international conference, porto, portugal, june 21-23, 2000 (Vol. 1981, pp. 301-315). Springer. · Zbl 1044.90526
[39] Castro, J., & Nabona, N. (1996, Jul). An implementation of linear and nonlinear multicommodity network flows. European Journal of Operational Research, 92(1), 37-53. · Zbl 0912.90125
[40] Chardaire, P., & Lisser, A. (2002a). Minimum cost multicommodity flow. In P. Pardalos & M. Resende (Eds.), Handbook of applied optimization (pp. 404-421). Oxford University Press.
[41] Chardaire, P., & Lisser, A. (2002b). Simplex and interior point specialized algorithms for solving non-oriented multi-commodity flow problems. Operations Research, 50(2), 260-276. · Zbl 1163.90383
[42] Chifflet, J., Mahey, P., & Reynier, V. (1994). Proximal decomposition for multicommodity flow problems with convex costs. Telecommunication Systems, 3(1), 1-10.
[43] Choi, I., & Goldfarb, D. (1990). Solving multicommodity network flow problems by an interior point method. In T. Coleman & Y. Li (Eds.), Large-scale numerical optimization (ithaca, ny, 1989), (pp. 58-69). Philadelphia, PA: SIAM. · Zbl 0726.90025
[44] Chudak, F., & Eleutério, V. (2005, June). Improved approximation schemes for linear programming relaxations of combinatorial optimization problems. In M. Junger & K. V. (Eds.), nteger programming and combinatorial optimization, proceedings of the 11th international conference (ipco xi) held in berlin, germany (Vol. 3509, pp. 81-96). Berlin Heidelberg: Springer-Verlag. · Zbl 1119.90325
[45] Costa, M.-C., Létocart, L., & Roupin, F. (2005, Apr). Minimal multicut and maximal integer multiflow: a survey. European Journal of Operational Research, 162(1), 55-69. · Zbl 1132.90306
[46] De Leone, R., Meyer, R., & Kontogiorgis, S. (1994, Feb). Alternating directions methods for the parallel solution of large-scale block-structured optimization problems (Tech. Rep.). Computer Sciences Technical Report 1217, Computer Science, University of Wisconsin-Madison.
[47] Detlefsen, N., & Wallace, S. (2001). The simplex algorithm for multicommodity networks. Networks, 39(1), 15-28. · Zbl 0992.90003
[48] Druckerman, J., Silverman, D., & Viaropulos, K. (1991). Ibm optimization subroutine library guide and reference, [Computer software manual].
[49] Kingston, NY.
[50] Eckstein, J., & Fukushima, M. (1994). Some reformulations and applications of the alternating direction method of multipliers. In W. Hager, D. Hearn, & P. Pardalos (Eds.), Large scale optimization : State of the art (gainesville, fl, 1993) (pp. 115-134). Kluwer Academic Publishers. · Zbl 0816.90109
[51] Evans, J. (1976, Jun). A combinatorial equivalence between a class of multicommodity flow problems and the capacitated transportation problem. Mathematical Programming, 10(3), 401-404. · Zbl 0333.90050
[52] Evans, J. (1978a, Jul). On equivalent representations of certain multicommodity networks as single commodity flow problems. Mathematical Programming, 15(1), 92-99. · Zbl 0392.90029
[53] Evans, J. (1978b, Mar). The simplex method for integral multicommodity networks. Naval Research Logistics Quarterly, 25(1), 31-37. · Zbl 0384.90102
[54] Evans, J. (1978c). A single-commodity transformation for certain multicommodity networks. Operations Research, 26(4), 673-680. · Zbl 0395.90028
[55] Evans, J. (1981). The multicommodity assignment problem: a network aggregation heuristic. Computers & Mathematics with Applications, 7(2), 187-194. · Zbl 0449.90065
[56] Evans, J. (1983). A network decomposition/aggregation procedure for a class of multicommodity transportation problems. Networks, 13(2), 197-205.
[57] Evans, J., Jarvis, J., & Duke, R. (1977, Dec). Graphic matroids and the multicommodity transportation problem. Mathematical Programming, 13(3), 323-328. · Zbl 0375.90071
[58] Farvolden, J., Powell, W., & Lustig, I. (1993). A primal partitioning solution for the arc-chain formulation of a multi-commodity network flow problem. Operations Research, 41(4), 669-693. · Zbl 0782.90032
[59] Fleischer, L. (2000). Approximating fractional multicommodity flow independent of the number of commodities. SIJDM: SIAM Journal on Discrete Mathematics, 13(4), 505-520. · Zbl 0968.68068
[60] Frangioni, A. (1997). Dual ascent methods and multicommodity flow problems (Unpublished doctoral dissertation). Diparti-mento di Informatica, Università di Pisa.
[61] Frangioni, A., & Gallo, G. (1999). A bundle type dual-ascent approach to linear multicommodity min-cost flow problems. INFORMS Journal on Computing, 11(4), 370-393. · Zbl 1034.90534
[62] Frank, M., & Wolfe, P. (1956). An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3, 95-110.
[63] Freund, Y., & Schapire, R. (1999, Apr). Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29, 79-103. · Zbl 0964.91007
[64] Garg, N., & Könemann, J. (1998). Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In IEEE (Ed.), 39th annual symposium on foundations of computer science: proceedings: November 8-11, 1998, palo alto, california (pp. 300-309). 1109 Spring Street, Suite 300, Silver Spring, MD 20910, USA: IEEE Computer Society Press. 1813-713X Copyright © 2018 ORSTW
[65] Gendron, B., Crainic, T., & Frangioni, A. (1999). Multicommodity capacitated network design. In P. Soriano & B. Sansò (Eds.), Telecommunications network planning. Boston: Kluwer Academic Publisher.
[66] Geoffrion, A. (1970). Primal resource-directive approaches for optimizing nonlinear decomposable systems. Operations Research, 18, 375-403. · Zbl 0201.22301
[67] Geoffrion, A., & Graves, G. (1974). Multicommodity distribution system design by benders decomposition. Management Science, 20(5), 822-844. · Zbl 0304.90122
[68] Goffin, J., Haurie, A., & Vial, J.-P. (1992, Feb). Decomposition and nondifferentiable optimization with the projective algorithm. Management Science, 38(2), 284-302. · Zbl 0762.90050
[69] Goffin, J.-L., Gondzio, J., Sarkissian, R., & Vial, J.-P. (1997). Solving nonlinear multicommodity flow problems by the analytic center cutting plane method. Mathematical Programming, 76(1, Ser.B), 131-154. · Zbl 0881.90050
[70] Goldberg, A. (1992). A natural randomization strategy for multicommodity flow and related algorithms. Information Processing Letters, 42(5), 249-256. · Zbl 0773.90026
[71] Goldberg, A., Oldham, J., Plotkin, S., & Stein, C. (1998). An implementation of a combinatorial approximation algo-rithm for minimum-cost multicommodity flow. In R. Bixby, E. Boyd, & R. Ríos-Mercado (Eds.), Integer programming and combinatorial optimization, proceedings of the 6th international conference (ipco vi) held in houston, tx, usa (Vol. 1412, pp. 338-352). Berlin: Springer. · Zbl 0911.90153
[72] Goldberg, A., & Tarjan, R. (1988). A new approach to the maximum-flow problem. Journal of the ACM, 35(4), 921-940. · Zbl 0661.90031
[73] Goldberg, A., & Tarjan, R. (1989). Finding minimum-cost circulations by canceling negative cycles. Journal of the Association for Computing Machinery, 36(4), 873-886. · Zbl 0697.68063
[74] Goldberg, A., & Tarjan, R. (1990). Solving minimum-cost flow problems by successive approximation. Mathematics of Operations Research, 15(3), 430-466. · Zbl 0727.90024
[75] Gratzer, F., & Steiglitz, K. (1972). A heuristic approach to large multicommodity flow problems. In 22nd international symposium on computer-communications networks and teletraffic (pp. 311-324).
[76] Graves, G., & McBride, R. (1976). The factorization approach to large-scale linear programming. Mathematical Program-ming, 10(1), 91-110. · Zbl 0331.90036
[77] Grigoriadis, M., & Khachiyan, L. (1994). Fast approximation schemes for convex programs with many blocks and coupling constraints. SIAM Journal on Optimization, 4(1), 86-107. · Zbl 0808.90105
[78] Grigoriadis, M., & Khachiyan, L. (1995a). An exponential-function reduction method for block-angular convex pro-grams. Networks, 26(2), 59-68. · Zbl 0856.90089
[79] Grigoriadis, M., & Khachiyan, L. (1995b). A sublinear-time randomized approximation algorithm for matrix games. Operations Research Letters, 18(2), 53-58. · Zbl 0857.90144
[80] Grigoriadis, M., & Khachiyan, L. (1996a). Approximate minimum-cost multicommodity flows inÕ(ϵ −2 KN M ) time. Mathematical Programming, 75(3, Ser. A), 477-482. · Zbl 0874.90085
[81] Grigoriadis, M., & Khachiyan, L. (1996b). Coordination complexity of parallel price-directive decomposition. Mathe-matics of Operations Research, 21(2), 321-340. · Zbl 0857.90100
[82] Grigoriadis, M. D., & White, W. W. (1972a). Computational experience with a multicommodity network flow algorithm. In R. Cottle & J. Krarup (Eds.), Optimization methods for resource allocation (proc. nato conf., elsinore) (pp. 205-226). English Univsity Press, London.
[83] Grigoriadis, M. D., & White, W. W. (1972b). A partitioning algorithm for the multicommodity network flow problem. Mathematical Programming, 3(3), 157-177. · Zbl 0254.90059
[84] Grinold, R. (1972). Steepest ascent for large scale linear programs. SIAM Review, 14(3), 447-464. · Zbl 0281.90044
[85] Hadjiat, M., Maurras, J.-F., & Vaxès, Y. (2000, Jun). A primal partitioning approach for single and non-simultaneous multicommodity flow problems. European Journal of Operational Research, 123(2), 382-393. · Zbl 0967.90014
[86] Hartman, J., & Lasdon, L. (1972). A generalized upper bounding algorithm for multicommodity network flow problems. Networks, 1(4), 333-354. · Zbl 0253.90030
[87] Held, M., Wolfe, P., & Crowder, H. (1974). Validation of subgradient optimization. Mathematical Programming, 6(1), 62-88. · Zbl 0284.90057
[88] Ibaraki, S., Fujishima, M., & Ibaraki, T. (1992). Primal-dual proximal point algorithm for linearly constrained convex programming problems. Computational Optimization and Applications, 1(2), 207-226. · Zbl 0767.90062
[89] Ibaraki, S., & Fukushima, M. (1994, Dec). Primal-dual proximal point algorithm for multicommodity network flow problems. Journal of the Operations Research Society of Japan, 37(4), 297-309. · Zbl 0828.90035
[90] Jewell, W. (1958). Optimal flow through networks (Unpublished doctoral dissertation). Interim Tech. Report No. 8, OR Center, M.I.T., Cambridge, MA
[91] Jewell, W. (1966). A primal-dual multicommoidyt flow algorithm (Tech. Rep. No. ORC 66-24). Berkeley: Operations Research Center, University of California.
[92] Jones, K., Lustig, I., Farvolden, J., & Powell, W. (1993). Multicommodity network flows: the impact of formulation on decomposition. Mathematical Programming, 62(1), 95-117. · Zbl 0802.90039
[93] Kallio, M., & Ruszczyński, A. (1994, March). Parallel solution of linear programs via nash equilibria (Tech. Rep.). Laxenburg, 1813-713X Copyright © 2018 ORSTW Austria: WP-94-015, IIASA.
[94] Kamath, A., & Palmon, O. (1995). Improved interior point algorithms for exact and approximate solution of mul-ticommodity flow problems. In Proceedings of the sixth annual acm-siam symposium on discrete algorithms (san francisco, ca, 1995) (pp. 502-511). ACM, SIAM. · Zbl 0847.90051
[95] Kamath, A., Palmon, O., & Plotkin, S. (1995). Fast approximation algorithm for minimum cost multicommodity flow. In Proceedings of the sixth annual acm-siam symposium on discrete algorithms (pp. 493-501). New York, NY, USA: ACM Press. · Zbl 0847.90050
[96] Kapoor, S., & Vaidya, P. (1996). Speeding up Karmarkar’s algorithm for multicommodity flows. Mathematical Program-ming, 73(1, Ser. A), 111-127. · Zbl 0848.90056
[97] Karakostas, G. (2002). Faster approximation schemes for fractional multicommodity flow problems. In Soda ’02: Proceedings of the thirteenth annual acm-siam symposium on discrete algorithms (pp. 166-173). Philadelphia, PA, USA: Society for Industrial and Applied Mathematics. · Zbl 1258.90073
[98] Karger, D., & Plotkin, S. (1995). Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows. In Proceedings of the twenty-seventh annual acm symposium on the theory of computing (pp. 18-25). New Yourk, NY, USA: ACM Press. · Zbl 0922.90065
[99] Karmarkar, N. (1984). A new polynomial-time algorithm for linear programming. Combinatorica, 4(4), 373-395. · Zbl 0557.90065
[100] Kazanov, A. (1994). Minimum cost multiflows in undirected networks. Mathematical Programming, 66(3, Ser. A), 313-325. · Zbl 0820.90040
[101] Kazanov, A. (1997). Multiflows and disjoint paths of minimum total cost. Mathematical Programming, 78(2, Ser. B), 219-242. · Zbl 0889.90064
[102] Kennington, J. (1977, Jun). Solving multicommodity transportation problems using a primal partitioning simplex technique. Naval Research Logistics Quarterly, 24(2), 309-325. · Zbl 0375.90073
[103] Kennington, J. (1978). A survey of linear cost multicommodity network flows. Operations Research, 26(2), 209-236. · Zbl 0377.90097
[104] Kennington, J., & Helgason, R. (1980). Algorithms for network programming. New York: Wiley-Interscience. · Zbl 0452.90054
[105] Kennington, J., & Shalaby, M. (1977, May). An effective subgradient procedure for minimal cost multicommodity flow problems. Management science, 23(9), 994-1004. · Zbl 0366.90118
[106] Klein, P., Plotkin, S., Stein, C., & Tardos, É. (1994). Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts. SIAM Journal on Computing, 23(3), 466-487. · Zbl 0809.68077
[107] Klein, P., & Young, N. (1999, June). On the number of iterations for dantzig-wolfe optimization and packing-covering approximation algorithms. In G. Cornuejols, R. Burkard, & G. Woeginger (Eds.), Integer programming and combinatorial optimization, proceedings of the 7th international conference (ipco vii) held in graz, austria (Vol. 1610, pp. 320-327). London, UK: Springer-Verlag. · Zbl 0954.90004
[108] Könemann, J. (1998). Faster and simpler algorithms for multicommodity flow and other fractional packing problems (Unpublished master’s thesis). Computer Science, Universität des Saarlandes, Saarbrücken, Germany.
[109] Kontogiorgis, S. (1995). Alternating directions methods for the parallel solution of large-scale block-structured optimization problems (Unpublished doctoral dissertation). Computer Science, University of Wisconsin-Madison.
[110] Leighton, T., Makedon, F., Plotkin, S., Stein, C., Tardos, É., & Tragoudas, S. (1995, Apr). Fast approximation algorithms for multicommodity flow problems. Journal of Computer and System Sciences, 50(2), 228-243. · Zbl 0826.68055
[111] Lin, S.-Y., & Lin, H., C. (1997). A computationally efficient method for nonlinear multicommodity network flow. Networks, 29(4), 225-244. · Zbl 0882.90038
[112] Lomonosov, M. (1985). Combinatorial approaches to multiflow problems. Discrete Applied Mathematics, 11(1), 1-93. · Zbl 0598.90036
[113] Luby, M., & Nisan, N. (1993). A parallel approximation algorithm for positive linear programming. In Stoc ’93: Proceedings of the twenty-fifth annual acm symposium on theory of computing (pp. 448-457). New York, NY, USA: ACM Press. · Zbl 1310.68224
[114] Lustig, I., & Rothberg, E. (1996, Feb). Gigaflops in linear programming. Operations Research Letters, 18(4), 157-165. · Zbl 0855.90083
[115] Lustig, R., I.J.and Marsten, & Shanno, D. (1991). Computational experience with a primal-dual interior point method for linear programming. Linear Algebra and its Applications, 152, 191-222. · Zbl 0731.65049
[116] Mahey, P., Ouorou, A., LeBlanc, L., & Chifflet, J. (1998, Jul). A new proximal decomposition algorithm for routing in telecommunication networks. Networks, 31(4), 227-238. · Zbl 1015.90020
[117] Maier, S. (1972). A compact inverse scheme applied to a multicommodity network with resource constraints. In R. Cottle & J. Krarup (Eds.), Optimization methods for resource allocation (proc. nato conf., elsinore) (pp. 179-203). English Univsity Press, London.
[118] Mamer, J., & McBride, R. (2000, May). A decomposition-based pricing procedure for large-scale linear programs: an application to the linear multicommodity flow problem. Management Science, 46(5), 693-709. · Zbl 1231.90292
[119] Marsten, R., Subramanian, R., Saltzman, M., Lustig, I., & Shanno, D. (1990). Interior point methods for linear pro-gramming: just call newton, lagrange, and fiacco and mccormick! Interfaces, 20(4), 105-116.
[120] Maurras, J.-F., & Vaxès, Y. (1997). Multicommodity network flow with jump constraints. Discrete Mathematics, 165-166, 481-486. · Zbl 0872.90038
[121] McBride, R. (1985). Solving embedded generalized network problems. European Journal of Operational Research, 21(1), 82-92. 1813-713X Copyright © 2018 ORSTW · Zbl 0565.90038
[122] McBride, R. (1998a). Advances in solving the multicommodity-flow problem. Interfaces, 28(2), 32-41.
[123] McBride, R. (1998b, Nov.). Progress made in solving the multicommodity flow problem. SIAM Journal on Optimization, 8(4), 947-955. · Zbl 0912.90128
[124] McBride, R., & Mamer, J. (1997). Solving multicommodity flow problems with a primal embedded network simplex algorithm. INFORMS Journal on Computing, 9(2), 154-163. · Zbl 0885.90040
[125] McBride, R., & Mamer, J. (2001, Dec.). Solving the undirected multicommodity flow problem using a shortest path-based pricing algorithm. Networks, 38(4), 181-188. · Zbl 0993.90074
[126] McCallum, J., C.J. (1977). A generalized upper bounding approach to a communications network planning problem. Networks, 7(1), 1-23. · Zbl 0357.90069
[127] Meyer, R., & Zakeri, G. (1999). Multicoordination methods for solving convex block-angular programs. SIAM Journal on Optimization, 10(1), 121-131. · Zbl 0953.90039
[128] Monteiro, D., & Adler, I. (1989). Interior path following primal-dual algorithms. part i: Linear programming. Mathe-matical Programming, 44(1, Ser. A), 27-41. · Zbl 0676.90038
[129] Murray, S. (1992). An interior point approach to the generalized flow problem with costs and related problems (Unpublished doctoral dissertation). Department of Operations Research, Stanford University.
[130] Murtagh, B., & Saunders, M. (1978). Large-scale linearly constrained optimization. Mathematical Programming, 14(1), 41-72. · Zbl 0383.90074
[131] Murtagh, B., & Saunders, M. (1992). Minos 5.4 release notes, appendix to minos 5.1 user’s guide (Tech. Rep.). Stanford University.
[132] Muthukrishnan, S., & Suel, T. (1998). Second-order methods for distributed approximate single-and multicommodity flow. In M. Luby, J. Rolim, & M. Serna (Eds.), Randomization and approximation techniques in computer science. second international workshop, random’98. proceedings (Vol. 1518, pp. 369-383). Berlin: Springer.
[133] Nagamochi, H., Fukushima, M., & Ibaraki, T. (1990, Jul). Relaxation methods for the strictly convex multicommodity flow problem with capacity constraints on individual commodities. Networks, 20(4), 409-426. · Zbl 0715.90047
[134] Nemirovski, A. (2005). Prox-method with rate of convergence o(1/t) for variational inequalities with lipschitz contin-uous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1), 229-251. · Zbl 1106.90059
[135] Nesterov, Y. (2005a). Excessive gap technique in nonsmooth convex minimization. SIAM Journal on Optimization, 16(1), 235-249. · Zbl 1096.90026
[136] Nesterov, Y. (2005b). Smooth minimization of non-smooth functions. Mathematical Programming, 103(1), 127-152. · Zbl 1079.90102
[137] Oldham, J. (1999). Multicommodity and generalized flow algorithms: theory and practice (Unpublished doctoral dissertation). Department of Computer Science, Stanford University.
[138] Ouorou, A. (2000, Feb). A primal-dual algorithm for monotropic programming and its application to network opti-mization. Computational Optimization and Applications, 15(2), 125-143. · Zbl 0947.90089
[139] Ouorou, A., & Mahey, P. (2000, Mar). A minimum mean cycle cancelling method for nonlinear multicommodity flow problems. European Journal of Operational Research, 121(3), 532-548. · Zbl 0964.90005
[140] Ouorou, A., Mahey, P., & Vial, J.-P. (2000, Jan). A survey of algorithms for convex multicommodity flow problems. Management Science, 46(1), 126-147. · Zbl 1231.90110
[141] Palmon, O. (2001). Optimization issues in network routing (Unpublished doctoral dissertation). Department of Computer Science, Stanford University.
[142] Pinar, M., & Zenios, S. (1992). Parallel decomposition of multicommodity network flows using a linear-quadratic penalty algorithm. ORSA Journal on Computing, 4(3), 235-249. · Zbl 0759.90028
[143] Plotkin, S., Shmoys, D., & Tardos, É. (1995, May). Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research, 20(2), 257-301. · Zbl 0837.90103
[144] Polak, G. (1992, May). On a parametric shortest path problem from primal-dual multicommodity network optimization. Networks, 22(3), 283-295. · Zbl 0770.90045
[145] Radzik, T. (1995). Fast deterministic approximation for the multicommodity flow problem. Mathematical Programming, 78(1, Ser. A), 43-58. · Zbl 0893.90057
[146] Rockafellar, R. (1984). Network flows and monotropic optimization. New York, NY: John Wiley. · Zbl 0596.90055
[147] Rosen, J. (1964). Primal partition programming for block diagonal matrices. Numerische Mathematik, 6, 250-260. · Zbl 0129.34102
[148] Saigal, R. (1967). Multicommodity flows in directed networks (Tech. Rep. No. ORC Report 66-25). Operations Research Center, University of California, Berkeley.
[149] Schneur, R. (1991). Scaling algorithms for multicommodity flow problems and network flow problems with side constraints (Unpublished doctoral dissertation). M.I.T., Cambridge, MA
[150] Schneur, R., & Orlin, J. (1998). A scaling algorithm for multicommodity flow problems. Operations Research, 146(2), 231-246. · Zbl 0996.90013
[151] Schrijver, A. (1991). Short proofs on multicommodity flows and cuts. Journal of Combinatorial Theory, 53(1, Ser. B), 32-39. · Zbl 0760.05074
[152] Copyright © 2018 ORSTW
[153] Schultz, G., & Meyer, R. (1991). An interior point method for block angular optimization. SIAM Journal on Optimization, 1(4), 583-602. · Zbl 0754.90038
[154] Shahrokhi, F., & Matula, D. (1990, Apr). The maximum concurrent flow problem. Journal of the ACM, 37(2), 318-334. · Zbl 0696.68071
[155] Shetty, B., & Muthukrishnan, R. (1990, Sep). A parallel projection for the multicommodity network model. Journal of the Operational Research Society, 41(9), 837-842. · Zbl 0711.90021
[156] Soun, Y., & Truemper, K. (1980). Single commodity representation of multicommodity networks. SIAM Journal on Algebraic and Discrete Methods, 1(3), 348-358. · Zbl 0498.90033
[157] Truemper, K. (1977). Unimodular matrices of flow problems with additional constraints. Networks, 7(4), 343-358. · Zbl 0373.90023
[158] Truemper, K., & Soun, Y. (1979). Minimal forbidden subgraphs of unimodular multicommodity networks. Mathematics of Operations Research, 4(4), 379-389. · Zbl 0424.90073
[159] Vaidya, P. (1989). Speeding-up linear programming using fast matrix multiplication. In 30th annual symposium on foundations of computer science (pp. 332-337). IEEE.
[160] Vance, P., Barnhart, C., Johnson, E., & Nemhauser, G. (1994). Solving binary cutting stock problems by column generation and branch-and-bound. Computational Optimization and Applications, 3(2), 111-130. · Zbl 0801.90080
[161] Wang, I.-L. (2003). Shortest paths and multicommodity network flows (Unpublished doctoral dissertation). School of Industrial and System Engineering, Georgia Institute of Technology.
[162] Wang, I.-L. (2018). Multicommodity network flows: A survey, part I: Applications and formulations. International Journal of Operations Research, 15(4), 145-153. · Zbl 1480.90086
[163] Yamakawa, E., Matsubara, Y., & Fukushima, M. (1996, Dec). A parallel primal-dual interior point method for multi-commodity flow problems with quadratic costs. Journal of the Operations Research Society of Japan, 39(4), 566-591. · Zbl 0874.90087
[164] Ye, Y. (1994). Toward probabilistic analysis of interior-point algorithms for linear programming. Mathematics of Operations Research, 19(1), 38-52. · Zbl 0799.90086
[165] Young, N. (1995). Randomized rounding without solving the linear program. In Proceedings of the sixth annual acm-siam symposium on discrete algorithms (pp. 170-178). New Your, NY, USA: ACM Press. · Zbl 0849.90100
[166] Young, N. (2001). Sequential and parallel algorithms for mixed packing and covering. In Focs ’01: Proceedings of the 42nd ieee symposium on foundations of computer science (pp. 538-546). Washington, DC, USA: IEEE Computer Society.
[167] Zakeri, G. (1995). Multi-coordination methods for parallel solution of block-angular programs (Unpublished doctoral dissertation). Computer Science, University of Wisconsin.
[168] Zenios, S., Pinar, M., & Dembo, R. (1995, May). A smooth penalty function algorithm for network-structured problems. European Journal of Operational Research, 83(1), 229-236. · Zbl 0905.90065
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.