Bilevel optimization in flow networks: A message-passing approach

Bo Li, David Saad, Chi Ho Yeung

Research output: Contribution to journalLetter, comment or opinionpeer-review

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

Bibliographical note

Copyright: arXiv.org - Non-exclusive license to distribute
The URI http://arxiv.org/licenses/nonexclusive-distrib/1.0/ is used to record the fact that the submitter granted the following license to arXiv.org on submission of an article:

I grant arXiv.org 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 arXiv.org 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.

Fingerprint

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

Cite this