Machine Learning-Augmented Optimization of Large Bilevel and Two-stage Stochastic Programs: Application to Cycling Network Design
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 present. Motivated by a real-world cycling infrastructure planning application, we present a general approach to solving such problems. 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 to 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 to the current practice, our approach improves Toronto's cycling accessibility by 19.2%, equivalent to $18M in potential cost savings. Our approach is being used to inform the cycling infrastructure planning in Toronto and outperforms the current practice by a large margin. It can be generalized to any decision problems that are formulated as bilevel programs with independent followers.
Code (0)
등록된 구현이 없습니다.
Tasks
Representation LearningSimilar Papers 제목 키워드 기반
Effective Bilevel Optimization via Minimax Reformulation
Bilevel optimization has found successful applications in various machine learning problems, including hyper-parameter optimization, data cleaning, and meta-learning. However, its huge computational cost presents a signi…
Bilevel OptimizationMeta-LearningA Gradient-based Bilevel Optimization Approach for Tuning Hyperparameters in Machine Learning
Hyperparameter tuning is an active area of research in machine learning, where the aim is to identify the optimal hyperparameters that provide the best performance on the validation set. Hyperparameter tuning is often ac…
Bayesian OptimizationBIG-bench Machine LearningBilevel OptimizationHyperparameter OptimizationBilevel Optimization for Machine Learning: Algorithm Design and Convergence Analysis
Bilevel optimization has become a powerful framework in various machine learning applications including meta-learning, hyperparameter optimization, and network architecture search. There are generally two classes of bile…
BIG-bench Machine LearningBilevel OptimizationHyperparameter OptimizationMeta-LearningImplicit Bilevel Optimization: Differentiating through Bilevel Optimization Programming
Bilevel Optimization Programming is used to model complex and conflicting interactions between agents, for example in Robust AI or Privacy-preserving AI. Integrating bilevel mathematical programming within deep learning …
Bilevel OptimizationPrivacy PreservingA Globally Convergent Gradient-based Bilevel Hyperparameter Optimization Method
Hyperparameter optimization in machine learning is often achieved using naive techniques that only lead to an approximate set of hyperparameters. Although techniques such as Bayesian optimization perform an intelligent s…
Bayesian OptimizationBilevel OptimizationHyperparameter Optimization