Numerical methods for the problem of traffic flow equilibrium in the Beckmann and the stable dynamic models

A. V. Gasnikov ; P. E. Dvurechensky ; Yu. V. Dorn ; Yu. V. Maksimov

Matematičeskoe modelirovanie, Tome 28 (2016) no. 10, pp. 40-64.

Résumé

In this work we propose new computational methods for transportation equilibrium problems. For Beckmann's equilibrium model we consider Frank–Wolfe algorithm in a view of modern complexity results for this method. For Stable Dynamic model we propose new methods. First approach based on mirror descent scheme with Euclidean prox-structure for dual problem and randomization of a sum trick. Second approach based on Nesterov's smoothing technique of dual problem in form of Dorn–Nesterov and new implementation of randomized block-component gradient descent algorithm.

Détail

Keywords: equilibrium transportation models, Nash–Wardrop equilibrium, Beckmann's model, Stable Dynamic model, Frank–Wolfe algorithm, Mirror descent algorithm, dual averaging, randomization, randomized component gradient descent algorithm.

Bibliographie

[1] A. V. Gasnikov, Iu. V. Dorn, Iu. E. Nesterov, S. V. Shpirko, “O trekhstadiinoi versii modeli statsionarnoi dinamiki transportnykh potokov”, Matematicheskoe modelirovanie, 26:6 (2014), 34–70 | Zbl

[2] M. P. Vashchenko, A. V. Gasnikov, E. G. Molchanov, L. Ia. Pospelova, A. A. Shananin, Vychislimye modeli i chislennye metody dlia analiza tarifnoi politiki zheleznodorozhnykh gruzoperevozok, VTs RAN, M., 2014

[3] M. Frank, P. Wolfe, “An algorithm for quadratic programming”, Naval research logistics quarterly, 3:1–2 (1956), 95–110 | DOI | MR

[4] L. J. LeBlanc, R. V. Helgason, D. E. Boyce, “Improved efficiency of the Frank–Wolfe algorithm for convex network programs”, Transportation Science, 19:4 (1985), 445–462 | DOI | MR | Zbl

[5] H. Bar-Gera, “Origin-based algorithm for the traffic assignment problem”, Transportation Science, 36:4 (2002), 398–417 | DOI | Zbl

[6] H. Bast, D. Delling, A. Goldberg, M. Müller-Hannemann, T. Pajor, P. Sanders, D. Wagner, R. F. Werneck, Route Planning in Transportation Networks, Microsoft Technical Report, 2015, arXiv: 1504.05140

[7] B. Cox, A. Juditsky, A. Nemirovski, Decomposition techniques for bilinear saddle point problems and variational inequalities with affine monotone operators on domains given by linear minimization oracles, 2015, arXiv: 1506.02444 | MR

[8] L. V. Kantorovich, “Mathematical methods of organizing and planning production”, Management Science, 6:4 (1960), 366–422 | DOI | MR | Zbl

[9] Y. E. Nesterov, “Efficiency of coordinate descent methods on large scale optimization problem”, SIAM Journal on Optimization, 22:2 (2012), 341–362 | DOI | MR | Zbl

[10] Y. E. Nesterov, “Subgradient methods for huge-scale optimization problems”, Math. Program., Ser. A, 146:1–2 (2013), 275–297 | MR

[11] M. Beckmann, C. B. McGuire, C. B. Winsten, Studies in the economics of transportation, RM-1488, RAND Corporation, Santa Monica, 1955

[12] P. Steenbrink, Optimization of transport networks, John Wiley Sons, 1974

[13] Y. Sheffi, Urban transportation networks: Equilibrium analysis with mathematical programming methods, Prentice-Hall Inc., Englewood Cliffs, N.J., 1985

[14] M. Patriksson, The traffic assignment problem. Models and methods, VSP, Utrecht, Netherlands, 1994

[15] A. V. Gasnikov, S. L. Klenov, E. A. Nurminskii, Ia. A. Kholodov, N. B. Shamrai, Vvedenie v matematicheskoe modelirovanie transportnykh potokov, 2-e izd., ed. A. V. Gasnikov, MTsNMO, M., 2013, 427 pp.

[16] D. Monderer, L. S. Shapley, “Potential games”, Games and economic behavior, 14:1 (1996), 124–143 | DOI | MR | Zbl

[17] W. Sandholm, Population games and Evolutionary dynamics. Economic Learning and Social Evolution, MIT Press, Cambridge, 2010 | MR

[18] M. Jaggi, “Revisiting Frank–Wolfe: Projection-free sparse convex optimization”, Proceedings of the 30th International Conference on Machine Learning (Atlanta, Georgia, USA, 2013) https://sites.google.com/site/frankwolfegreedytutorial/

[19] S. Bubeck, “Theory of convex optimization for machine learning”, Foundations and Trends in Machine Learning, 8:3–4 (2015), 231–357, arXiv: 1405.4980 | DOI | Zbl

[20] Z. Harchaoui, A. Juditsky, A. Nemirovski, “Conditional gradient algorithms for norm-regularized smooth convex optimization”, Math. Program. Ser. B, 152 (2015), 75–112 http://www2.isye.gatech.edu/ñemirovs/ccg_revised_apr02.pdf | DOI | MR | Zbl

[21] Yu. Nesterov, Complexity bounds for primal-dual methods minimizing the model of objective function, CORE Discussion Papers 2015/03, 2015 https://www.uclouvain.be/cps/ucl/doc/core/documents/coredp2015_3web.pdf

[22] D. Challet, M. Marsili, Y.-C. Zhang, Minority Games: Interacting Agents in Financial Markets, Oxford University Press, 2005 | MR | Zbl

[23] I. Abraham, A. Fiat, A. V. Goldberg, R. F. Werneck, “Highway dimension, shortest paths and provably efficient algorithms”, Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, 2010, 782–793 | DOI | MR | Zbl

[24] M. A. Bender, M. Farach-Colton, G. Pemmasani, S. Skiena, P. Sumazin, “Lowest common ancestors in trees and directed acyclic graphs”, Journal of Algorithms, 57:2 (2005), 75–94 | DOI | MR | Zbl

[25] J. Fischer, V. Heun, “Theoretical and practical improvements on the RMQ-problem, with applications to LCA and LCE”, Combinatorial Pattern Matching, Springer, 2006, 36–48 | MR | Zbl

[26] Yu. Nesterov, A. de Palma, “Stationary dynamic solutions in congested transportation Networks: Summary and Perspectives”, Networks Spatial Econ., 2003, no. 3(3), 371–395 | DOI

[27] Yu. Nesterov, “Gradient methods for minimizing composite functions”, Math. Prog., 140:1 (2013), 125–161 | DOI | MR | Zbl

[28] A. Nemirovski, Lectures on modern convex optimization analysis, algorithms, and engineering applications, SIAM, Philadelphia, 2013 http://www2.isye.gatech.edu/\allowbreakñemirovs/Lect_ModConvOpt.pdf

[29] Y. Nesterov, “Primal-dual subgradient methods for convex problems”, Math. Program. Ser. B, 120:1 (2009), 261–283 | DOI | MR

[30] A. Juditsky, G. Lan, A. Nemirovski, A. Shapiro, “Stochastic approximation approach to stochastic programming”, SIAM Journal on Optimization, 19:4 (2009), 1574–1609 | DOI | MR | Zbl

[31] A. Gasnikov, Yu. Nesterov, V. Spokoiny, “On the efficiency of a randomized mirror descent algorithm in online optimization problems”, Comp. Math. Math. Phys., 55:4 (2015), 580–596 | DOI | MR | Zbl

[32] A. Shapiro, D. Dentcheva, A. Ruszczynski, Lecture on stochastic programming. Modeling and theory, MPS-SIAM series on Optimization, 2014 | MR

[33] G. Lan, A. Nemirovski, A. Shapiro, “Validation analysis of mirror descent stochastic approximation method”, Mathematical Programming, 134:2 (2012), 425–458 | DOI | MR | Zbl

[34] S. Boucheron, G. Lugoshi, P. Massart, Concentration inequalities: A nonasymptotic theory of independence, Oxford University Press, 2013 | MR | Zbl

[35] A. V. Gasnikov, P. E. Dvurechenskii, D. I. Kamzolov, Iu. E. Nesterov, V. G. Spokoinyi, P. I. Stetsiuk, A. L. Suvorikova, A. V. Chernov, “Poisk ravnovesii v mnogostadiinykh transportnykh modeliakh”, Trudy MFTI, 7:4 (2015), 143–155

[36] A. V. Gasnikov, P. E. Dvurechenskii, Iu. E. Nesterov, “Stokhasticheskie gradientnye metody s netochnym orakulom”, Trudy MFTI, 8:1 (2016), 41–91

[37] B. T. Polyak, Introduction to optimization, Hardcover, 1987

[38] A. V. Gasnikov, E. V. Gasnikova, Yu. E. Nesterov, A. V. Chernov, “Efficient Numerical Methods for Entropy-Linear Programming Problems”, Comp. Math. Math. Phys., 56:4 (2016), 514–524 | DOI | MR | Zbl

[39] Yu. Dorn, A. Gasnikov, Yu. Maximov, Yu. Nesterov, “Computational methods for the stochastic equilibrium stable dynamic model”, Book of Abstracts ECCOMAS. Thematic Conference CM3 — Computational Multi Physics, Multi Scales and Multi Big Data in Transport Modeling, Simulation and Optimization New Challenges for the Greening of Transport (University of Jyväskylä, May 25–27, 2015), 83–86 http://www.mit.jyu.fi/scoma/cm3/downloads/CM3_Book

[40] Y. Nesterov, “Smooth minimization of non-smooth function”, Math. Program. Ser. A, 103:1 (2005), 127–152 | DOI | MR | Zbl

[41] A. Nemirovski, S. Onn, U. Rothblum, “Accuracy certificates for computational problems with convex structure”, Mathematics of Operations Research, 35:1 (2010), 52–78 | DOI | MR | Zbl

[42] Y. E. Nesterov, “Efficiency of coordinate descent methods on large scale optimization problem”, SIAM Journal on Optimization, 22:2 (2012), 341–362 | DOI | MR | Zbl

[43] O. Fercoq, P. Richtarik, Accelerated, Parallel and Proximal Coordinate Descent, 2013, arXiv: 1312.5799 | MR

[44] Z. Qu, P. Richtarik, Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity, 2014, arXiv: 1412.8060 | MR

[45] K.-H. Borgwardt, The simplex method: A probabilistic analysis. Algorithms and Combinatorics, Study and Research Texts, Springer-Verlag, Berlin, 1987 | MR

[46] A. Schrijver, Theory of Linear and Integer Programming, John Wiley Sons, 1998 | MR

[47] D. Spielman, S.-H. Teng, “Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time”, Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, ACM, 2001, 296–305 | DOI | MR | Zbl

[48] R. K. Ahuja, T. L. Magnati, J. B. Orlin, Network flows: Theory, algorithms and applications, Prentice Hall, 1993 | MR | Zbl

[49] O. Pele, M. Werman, “Fast and robust earth mover's distances”, ICCV'09 (2009) http://www.cs.huji.ac.il/w̃erman/Papers/ICCV2009.pdf

[50] A. V. Gasnikov, E. V. Gasnikova, E. I. Ershov, P. E. Dvurechenskii, A. A. Lagunovskaia, “Poisk stokhasticheskikh ravnovesii v transportnykh modeliakh ravnovesnogo raspredeleniia potokov”, Trudy MFTI, 7:4 (2015), 114–128