Abstract
This paper proposes an implementation of a constrained analytic center cutting plane method to solve nonlinear multicommodity flow problems. The new approach exploits the property that the objective of the Lagrangian dual problem has a smooth component with second order derivatives readily available in closed form. The cutting planes issued from the nonsmooth component and the epigraph set of the smooth component form a localization set that is endowed with a self-concordant augmented barrier. Our implementation uses an approximate analytic center associated with that barrier to query the oracle of the nonsmooth component. The paper also proposes an approximation scheme for the original objective. An active set strategy can be applied to the transformed problem: it reduces the dimension of the dual space and accelerates computations. The new approach solves huge instances with high accuracy. The method is compared to alternative approaches proposed in the literature.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Babonneau F., du Merle O., Vial J.-P. (2006). Solving large scale linear multicommodity flow problems with an active set strategy and Proximal-ACCPM. Oper. Res. 54(1): 184–197
Bar-Gera H. (2002). Origin-based algorithm for traffic assignment problem. Transp. Sci. 36(4): 398–417
Bertsekas D.P., Gafni E.M. (1983). Projected newton methods and optimization of multicommodity flows. IEEE Trans. Autom. Control 28: 1090–1096
Bertsekas D.P., Gallager R.G. (1987). Data Networks. Prentice-Hall, Englewood Cliffs
Castro, J., Montero, L., Rosas, D.: Using ACCPM in a simplicial decomposition algorithm for the traffic assignment problem. Technical report, Statistics and Operations Research Department, Universitat Politecnica de Catalunya (2002)
Daneva, M., Lindberg, P.O.: The stiff is moving—conjugate direction Franck–Wolfe methods with applications to traffic assignment. Technical report, Linkoping University, Department of Mathematics (2004)
Dijkstra E.W. (1959). A note on two problems in connexion with graphs. Numer. Math. 1: 269–271
Frangioni A., Gallo G. (1999). A bundle type dual-ascent approach to linear multicommodity min-cost flow problems. Inf. J. Comput. 11: 370–393
Frank H., Wolfe P. (1956). An algorithm for quadratic programming. Naval Res. Logist. Q. 3: 95–110
Fratta L., Gerla M., Kleinrock L. (1973). The flow deviation method: an approach to store-and-forward communication network design. Networks 3: 97–133
Gafni E.M., Bertsekas D.P. (1984). Two-metric projection methods for constrained optimization. SIAM J. Control Optim. 22(6): 936–964
Glineur F. (2002). Improving complexity of structured convex optimization problems using self concordant barriers. Eur. J. Oper. Res. 143: 291–310
Goffin J.-L., Gondzio J., Sarkissian R., Vial J.-P. (1996). Solving nonlinear multicommodity flow problems by the analytic center cutting plane method. Math. Program. 76: 131–154
Kelley J.E. (1960). The cutting plane method for solving convex programs. J. SIAM 8: 703–712
Kleinrock L. (1972). Nets, Stochastic Message Flow and Delay, Communications. Dover, New York
Larsson T., Patriksson M. (1995). An augmented lagrangean dual algorithm for link capacity side constrained traffic assignment problems. Transp. Res. 29: 433–455
Larsson T., Di Yuan (2004). An augmented lagrangian algorithm for large scale multicommodity routing. Comput. Optim. Appl. 27(2): 187–215
Leblanc, L.: Mathematical programming algorithms for large scale network equilibrium and network design problems. Ph.D. thesis, IE/MD Dept, Northwestern University, Evanston IL (1973)
Leblanc, L., Helgason, R.V., Boyce, D.E.: Improved efficiency of the Frank–Wolfe algorithm for convex network programs. Transportation Science (1985)
Mahey P., Ouorou A., Leblanc L., Chifflet J. (1998). A new proximal decomposition algorithm for routing in telecommunication networks. Networks 31(4): 227–238
McBride R.D. (1998). Progress made in solving the multicommodity flow problem. SIAM J. Optim. 8(4): 947–955
Nesterov Y. (2004). Introductory Lectures on Convex Optimization: A Basic Course. Kluwer, Dordrecht
Nesterov Y. (2005). Smooth minimization of non-smooth functions. Math. Program. 103(1): 127–152
Nesterov Y., Vial J.-P. (1999). Homogeneous analytic center cutting plane methods for convex problems and variational inequalities. SIAM J. Optim. 9(3): 707–728
Ouorou A., Mahey P., Vial J.-P. (2000). A survey of algorithms for convex multicommodity flow problems. Manage. Sci. 46: 126–147
Patriksson M. (1994). The Traffic Assignment Problem—Models and Methods. VSP, Utrecht
Poljak B.T. (1977). Subgradient methods: a survey of Soviet research. In: Lemaréchal, C., Mifflin, R. (eds) Nonsmooth Optimization, pp 5–30. Pergamon Press, Oxford
Sheffi Y. (1985). Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Models. Prentice-Hall, New Jersey
Shor N. (1998). Nondifferentiable optimization and polynomial problems. Kluwer, Boston
Weintraub A., Ortiz C., Gonzales J. (1985). Accelerating convergence of the Franck-Wolfe algorithm. Transp. Res. 19: 113–122
Wolfe, P.: Convergence theory in nonlinear programming. In: Abadie, J. (ed.) Integer and Nonlinear Programming, pp. 1–36 (1970)
Author information
Authors and Affiliations
Corresponding author
Additional information
An erratum to this article can be found at http://dx.doi.org/10.1007/s10107-007-0191-8
Rights and permissions
About this article
Cite this article
Babonneau, F., Vial, JP. ACCPM with a nonlinear constraint and an active set strategy to solve nonlinear multicommodity flow problems. Math. Program. 120, 179–210 (2009). https://doi.org/10.1007/s10107-007-0151-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-007-0151-3