Universal Method of Searching for Equilibria and Stochastic Equilibria in Transportation Networks

Baimurzina D. R.; Gasnikov A. V.; P. Dvurechensky; E. Ershov; Kubentaeva M. B.; Lagunovskaya A. A.

doi:10.1134/S0965542519010020

Publications

?

Universal Method of Searching for Equilibria and Stochastic Equilibria in Transportation Networks

Computational Mathematics and Mathematical Physics. 2019. Vol. 59. No. 1. P. 19–33.

Baimurzina D. R., Gasnikov A. V., Dvurechensky P., Ershov E., Kubentaeva M. B., Lagunovskaya A. A.

A universal method of searching for usual and stochastic equilibria in congestion population games is proposed. The Beckmann and stable dynamics models of an equilibrium flow distribution over paths are considered. A search for Nash(–Wardrop) stochastic equilibria leads to entropy-regularized convex optimization problems. Efficient solutions of such problems, more exactly, of their duals are sought by applying a recently proposed universal primal-dual gradient method, which is optimally and adaptively tuned to the smoothness of the problem under study. © 2019, Pleiades Publishing, Ltd.

Keywords: dual problem public transportation networks Beckmann’s model stable dynamics model transportation flows universal method of similar triangles

Метод увеличения пропускной способности сетевых каналов с использованием моделей транспортного равновесия

Zykov S. V., Маличенко С. В., Защита информации. Инсайд 2025 Т. 121 № 1 С. 1–7

The article announces an analogy of using transport equilibrium models in the problems of distributing computer network flows. The purpose of the study is to test the possibility of using transport models and algorithms to optimize routing in a software-defined network (SDN) and to build an optimal flow distribution method based on these models. To achieve this goal, integer optimization and computer modeling methods were used. ...

Added: December 18, 2024

Instances generation for a single machine scheduling problem

A. Lazarev, N. Pravdivets, Grishin E. et al., , in: 13th Multiconference on Control Problems (MCCP 2020) 6-8 October 2020, Saint Petersburg, RussiaVol. 1864.: IOP Publishing, 2021. Ch. 012057.

Added: December 16, 2022

Finding equilibria in the traffic assignment problem with primal-dual gradient methods for stable dynamics model and beckmann model

Kubentayeva M., Gasnikov A., Mathematics 2021 Vol. 9 No. 11 Article 1217

In this paper, we consider the application of several gradient methods to the traffic assignment problem: we search equilibria in the stable dynamics model (Nesterov and De Palma, 2003) and the Beckmann model. Unlike the celebrated Frank–Wolfe algorithm widely used for the Beckmann model, these gradients methods solve the dual problem and then reconstruct a ...

Added: October 29, 2021

A Stable Alternative to Sinkhorn’s Algorithm for Regularized Optimal Transport

Dvurechensky P., Gasnikov A., Omelchenko S. et al., , in: Mathematical Optimization Theory and Operations Research, 19th International Conference, MOTOR 2020, Novosibirsk, Russia, July 6–10, 2020, (Т. 12095).: Cham: Springer, 2020. P. 406–423.

In this paper, we are motivated by two important applications: entropy-regularized optimal transport problem and road or IP traffic demand matrix estimation by entropy model. Both of them include solving a special type of optimization problem with linear equality constraints and objective given as a sum of an entropy regularizer and a linear function. It ...

Added: February 5, 2021

On the Dual and Inverse Problems of Scheduling Jobs to Minimize the Maximum Penalty

Alexander A. Lazarev, Nikolay Pravdivets, Werner F., Mathematics 2020 Vol. 8 No. 7 Article 1131

In this paper, we consider the single-machine scheduling problem with given release dates and the objective to minimize the maximum penalty which is NP-hard in the strong sense. For this problem, we introduce a dual and an inverse problem and show that both these problems can be solved in polynomial time. Since the dual problem ...

Added: September 2, 2020

Primal-Dual Method for Searching Equilibrium in Hierarchical Congestion Population Games

Dvurechensky P., Gasnikov A., Gasnikova E. et al., В кн.: Proceedings of DOOR 2016 Conference, special issue of CEUR Workshop ProceedingsVol. 1623.: CEUR Workshop Proceedings, 2016. С. 584–595.

In this paper, we consider a large class of hierarchical congestion population games. One can show that the equilibrium in a game of such type can be described as a minimum point in a properly constructed multi-level convex optimization problem. We propose a fast primal-dual composite gradient method and apply it to the problem, which ...

Added: November 17, 2017

Urban Public Transport Development in Russia: Trends and Reforms

Ryzhkov A., Zyuzin P., / Series WP BRP "Urban and Transportation Studies". 2016. No. WP BRP 05/URB/2016.

The aim of the article is to present the ways of urban public transport development in Russia within the context of the transition towards the market economy. The article consists of two blocks: the trends of urban public transport development in the Russian Federation and the problems of urban public transport management. The first block ...

Added: December 8, 2016

A characterization of maximin tests for two composite hypotheses

A. Gushchin, Mathematical Methods of Statistics 2015 Vol. 24 No. 2 P. 110–121

We consider the problem of testing two composite hypotheses in the minimax setting. To find maximin tests, we propose a new dual optimization problem which has a solution under a mild additional assumption. This allows us to characterize maximin tests in considerable generality. We give a simple example where the null hypothesis and the alternative are strictly separated, ...

Added: June 18, 2015