Machine Learning–Augmented Optimization of Large Bilevel and Two-Stage Stochastic Programs: Application to Cycling Network Design

双层优化 计算机科学 代表(政治) 利用 网络规划与设计 功能(生物学) 数学优化 运筹学 工作(物理) 随机规划 质量(理念) 决策问题 航程(航空) 自行车 结果(博弈论) 最优化问题 离散选择 线性规划 业务规划 理论(学习稳定性) 随机优化 贝尔曼方程 采样(信号处理) 流量网络 影响图 交通规划 工业工程 最优决策
作者
Timothy C. Y. Chan,Bo Lin,Shoshanna Saxe
出处
期刊:Manufacturing & Service Operations Management [Institute for Operations Research and the Management Sciences]
卷期号:27 (6): 1851-1868 被引量:2
标识
DOI:10.1287/msom.2024.1317
摘要

Problem definition: A wide range of decision problems can be formulated as bilevel programs with independent followers, which, as a special case, include two-stage stochastic programs. These problems are notoriously difficult to solve, especially when a large number of followers are present. Motivated by a real-world cycling infrastructure planning application, we present a general approach to solving such problems. Methodology/results: We propose an optimization model that explicitly considers a sampled subset of followers and exploits a machine learning model to estimate the objective values of unsampled followers. We prove bounds on the optimality gap of the generated leader decision as measured by the original objective function that considers the full follower set. We then develop follower sampling algorithms to tighten the bounds and a representation learning approach to learn follower features, which are used as inputs to the embedded machine learning model. Through numerical studies, we show that our approach generates leader decisions of higher quality compared with baselines. Finally, in collaboration with the City of Toronto, we perform a real-world case study in Toronto, where we solve a cycling network design problem with over one million followers. Compared with the current practice, our approach improves Toronto’s cycling accessibility by 19.2%, equivalent to $18 million in potential cost savings. Managerial implications: Our approach is being used to inform the cycling infrastructure planning in Toronto and can be generalized to any decision problems that are formulated as bilevel programs with independent followers. Funding: This work was supported by City of Toronto Transportation Services and the Natural Sciences and Engineering Research Council of Canada [NSERC Alliance Grant ALLRP 561212-20]. Supplemental Material: The electronic companion is available at https://doi.org/10.1287/msom.2024.1317 .
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
CipherSage的应助被errui采纳,获得10
刚刚
1秒前
南先生完成签到,获得积分10
1秒前
云中觅星河完成签到,获得积分10
1秒前
翔翔超人完成签到,获得积分10
3秒前
阳光的迎海完成签到,获得积分10
4秒前
可爱的函函的应助被勤恳浩然采纳,获得10
5秒前
5秒前
6秒前
6秒前
6秒前
科研通AI6.2的应助被酷酷的鸿采纳,获得10
6秒前
ssc发布了新的文献求助10
6秒前
7秒前
xiao礼完成签到,获得积分10
7秒前
ppistachio完成签到 ,获得积分10
9秒前
科研通AI6.3的应助被qq采纳,获得10
9秒前
AeAeAe完成签到,获得积分10
10秒前
jifas完成签到,获得积分10
10秒前
stop here完成签到,获得积分10
10秒前
梁凯华完成签到 ,获得积分10
10秒前
张哈哈发布了新的文献求助10
10秒前
11秒前
陈1完成签到 ,获得积分10
11秒前
errui发布了新的文献求助10
11秒前
11秒前
廿一雨完成签到,获得积分10
12秒前
学习永动机完成签到,获得积分10
12秒前
Danger完成签到 ,获得积分10
12秒前
科科完成签到,获得积分10
13秒前
molihuakai的应助被不错吧采纳,获得10
13秒前
zzx123发布了新的文献求助10
14秒前
15秒前
小蘑菇的应助被胖三斤采纳,获得10
15秒前
流苏发布了新的文献求助10
15秒前
凉水完成签到,获得积分10
15秒前
16秒前
迅速河马完成签到,获得积分20
16秒前
16秒前
李健的应助被阳光的半雪采纳,获得10
17秒前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
拉伸高分子熔体中缠结行为的模拟和小角中子散射研究 1700
The World Atlas of Wine 9th edition 1000
奈特基础组织学:配套组织病理学(第4版)(Netter's Essential Histology With Correlated Histopathology) 800
八旗制度の研究 600
Boundaries and Bodhisattvas 500
高分子基功能界面水蒸发材料与应用研究 500
热门求助领域 (近24小时)
化学 材料科学 医学 生物 纳米技术 计算机科学 工程类 有机化学 化学工程 生物化学 物理 复合材料 内科学 催化作用 光电子学 人工智能 细胞生物学 无机化学 物理化学 数学
热门帖子
关注 科研通微信公众号,转发送积分 8182102
求助须知:如何正确求助?哪些是违规求助? 9571775
关于积分的说明 21819723
捐赠科研通 7778500
什么是DOI,文献DOI怎么找? 3433617
关于科研通互助平台的介绍 2557786
邀请新用户注册赠送积分活动 2479651