Bilevel optimization in flow networks: A message-passing approach

Bo Li, David Saad, Chi Ho Yeung

Research output: Contribution to journalLetter, comment/opinion or interviewpeer-review


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.
Original languageEnglish
Article numberL042301
Number of pages6
JournalPhysical Review E
Issue number4
Publication statusPublished - 31 Oct 2022

Bibliographical note

Copyright: - Non-exclusive license to distribute
The URI is used to record the fact that the submitter granted the following license to on submission of an article:

I grant a perpetual, non-exclusive license to distribute this article.
I certify that I have the right to grant this license.
I understand that submissions cannot be completely removed once accepted.
I understand that reserves the right to reclassify or reject any submission
Funding information:
B.L. and D.S. acknowledge support from the Leverhulme Trust (RPG-2018-092), European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 835913. B.L. acknowledges support from the startup funding from Harbin Institute of Technology, Shenzhen (Grant No. 20210134). D.S. acknowledges support from the EPSRC programme grant TRANSNET (EP/R035342/1). C.H.Y. is supported by the Research Grants Council of the Hong Kong Special Administrative Region, China (Projects No. EdUHK GRF 18304316, No. GRF 18301217, and No. GRF 18301119), the Dean's Research Fund of the Faculty of Liberal Arts and Social Sciences (Projects No. FLASS/DRF 04418, No. FLASS/ROP 04396, and No. FLASS/DRF 04624), and the Internal Research Grant (Projects No. RG67 2018-2019R R4015 and No. RG31 2020-2021R R4152), The Education University of Hong Kong, Hong Kong Special Administrative Region, China.


Dive into the research topics of 'Bilevel optimization in flow networks: A message-passing approach'. Together they form a unique fingerprint.

Cite this