Abstract
To optimize the quality of service through a telecommunication network, we propose an algorithm based on Lagrangian relaxation. The bundle-type dual algorithm is adapted to the present situation, where the dual function is the sum of a polyhedral function (coming from shortest path problems) and of a smooth function (coming from the congestion function).
Similar content being viewed by others
References
Babonneau, F., Vial, J.P.: Proximal-accpm with a nonlinear constraint and active set strategy to solve nonlinear multicommodity flow problems. Math. Program. (2008). DOI 10.1007/s10107-007-0151-3
Bertsekas, D., Gafni, E.M.: Two-metric projection methods for constrained optimization. SIAM J. Control Optim. 22, 936–964 (1983)
Cheney, E., Goldstein, A.: Newton’s method for convex programming and Tchebycheff approximations. Numer. Math. 1, 253–268 (1959)
Frangioni, A.: Solving semidefinite quadratic problems within nonsmooth optimization algorithms. Comput. Oper. Res. 23(11), 1099–1118 (1996)
Frangioni, A.: Generalized bundle methods. SIAM J. Optim. 13(1), 117–156 (2003)
Frank, M., Wolfe, P.: An algorithm for quadratic programming. Naval Res. Logist. Q. 3, 95–110 (1956)
Fukushima, M.: A nonsmooth optimization approach to nonlinear multicommodity network flow problems. J. Oper. Res. Soc. Jpn. 27(2), 151–176 (1984)
Gerla, M., Fratta, L., Kleinrock, L.: The flow deviation method: an approach to store-and-forward communication network design. Networks 3, 97–133 (1984)
Goffin, J.-L.: The ellipsoid method and its predecessors. In: Contesse, L., Correa, R., Weintraub, A. (eds.) Recent Advances in System Modelling and Optimization. Lecture Notes in Control and Information Sciences, vol. 87. Springer, Berlin (1984)
Goffin, J.-L., Gondzio, J., Sarkissian, R., Vial, J.-P.: Solving nonlinear multicommodity flow problems by the analytic center cutting plane method. Math. Program. 76, 131–154 (1997)
Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms. Springer, Heidelberg (1993). Two volumes
Kelley, J.E.: The cutting plane method for solving convex programs. J. SIAM 8, 703–712 (1960)
Kiwiel, K.C.: A dual method for certain positive semidefinite quadratic programming problems. SIAM J. Sci. Stat. Comput. 10(1), 175–186 (1989)
Kiwiel, K.C.: Proximity control in bundle methods for convex nondifferentiable minimization. Math. Program. 46(1), 105–122 (1990)
Kiwiel, K.C.: A Cholesky dual method for proximal piecewise linear programming. Numer. Math. 68, 325��340 (1994)
Kiwiel, K.C., Larsson, T., Lindberg, P.O.: Lagrangian relaxation via ballstep subgradient methods. Math. Oper. Res. 32(3), 669–686 (2007)
Lemaréchal, C.: Lagrangian relaxation. In: Jünger, M., Naddef, D. (eds.) Computational Combinatorial Optimization, pp. 112–156. Springer, Heidelberg (2001)
Lemaréchal, C., Sagastizábal, C.: Variable metric bundle methods: from conceptual to implementable forms. Math. Program. 76(3), 393–410 (1997)
Lemaréchal, C., Strodiot, J.-J., Bihain, A.: On a bundle method for nonsmooth optimization. In: Mangasarian, O.L., Meyer, R.R., Robinson, S.M. (eds.) Nonlinear Programming, vol. 4, pp. 245–282. Academic Press, New York (1981)
Lemaréchal, C., Nemirovskii, A.S., Nesterov, Y.E.: New variants of bundle methods. Math. Program. 69, 111–148 (1995)
Mahey, P., Ouorou, A., LeBlanc, L., Chifflet, J.: A new proximal decomposition algorithm for routing in telecommunication networks. Networks 31, 227–238 (1998)
McBride, R.D.: Advances in solving the multicommodity-flow problem. Interfaces 28(2), 32–41 (1998)
Moré, J.J.: Recent developments in algorithms and software for trust region methods. In: Bachem, A., Grötschel, M., Korte, B. (eds.) Mathematical Programming, the State of the Art, pp. 258–287. Springer, Berlin (1983)
Ouorou, A., Mahey, P., Vial, J.-P.: A survey of algorithms for convex multicommodity flow problems. Manag. Sci. 47(1), 126–147 (2000)
Pinar, M.C., Zenios, S.A.: Parallel decomposition of multicommodity network flows using a linear-quadratic penalty algorithm. ORSA J. Comput. 4(3), 235–249 (1992)
Schramm, H., Zowe, J.: A version of the bundle idea for minimizing a nonsmooth function: conceptual idea, convergence analysis, numerical results. SIAM J. Optim. 2(1), 121–152 (1992)
Schultz, G.L., Meyer, R.R.: An interior point method for block angular optimization. SIAM J. Optim. 1(4), 583–602 (1991)
Wolfe, P.: Convergence theory in nonlinear programming. In: Abadie, J. (ed.) Integer and Nonlinear Programming, pp. 1–36. North-Holland, Amsterdam (1970)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lemaréchal, C., Ouorou, A. & Petrou, G. A bundle-type algorithm for routing in telecommunication data networks. Comput Optim Appl 44, 385–409 (2009). https://doi.org/10.1007/s10589-007-9160-7
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-007-9160-7