論文の概要: Machine Learning-Augmented Optimization of Large Bilevel and Two-stage Stochastic Programs: Application to Cycling Network Design

• arxiv url: http://arxiv.org/abs/2209.09404v4
• Date: Wed, 05 Feb 2025 15:17:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-06 14:24:14.485112
• Title: Machine Learning-Augmented Optimization of Large Bilevel and Two-stage Stochastic Programs: Application to Cycling Network Design
• Title（参考訳）: 大規模2段階確率プログラムの機械学習による最適化:サイクリングネットワーク設計への応用
• Authors: Timothy C. Y. Chan, Bo Lin, Shoshanna Saxe,
• Abstract要約: 幅広い意思決定問題は、独立したフォロワーを持つ二段階プログラムとして定式化することができる。 これらの問題は、特に多くのフォロワーがいる場合、解決するのが非常に難しいことで知られている。 現実のサイクリングインフラ計画アプリケーションに動機付けられ,そのような問題を解決するための一般的なアプローチを提案する。
• 参考スコア（独自算出の注目度）: 4.092552518040045
• License:
• Abstract: 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.
• Abstract（参考訳）: 幅広い意思決定問題は、独立したフォロワーを持つ二段階のプログラムとして定式化することができ、特別なケースとして、2段階の確率的プログラムが含まれる。 これらの問題は、特に多くのフォロワーがいる場合、解決するのが非常に難しいことで知られている。 現実のサイクリングインフラ計画アプリケーションに動機付けられ,そのような問題を解決するための一般的なアプローチを提案する。 本研究では、フォロワーのサンプル部分集合を明示的に考慮し、機械学習モデルを用いてアンサンプされたフォロワーの客観的値を推定する最適化モデルを提案する。 本研究は,全従者集合を考慮した本来の目的関数によって測定された,生成したリーダ決定の最適性ギャップに関するバウンダリを実証する。 そこで我々は,組込み機械学習モデルへのインプットとして使用される従者探索アルゴリズムを開発し,境界を厳格化するとともに,従者特徴を学習するための表現学習手法を開発した。 数値解析により,本手法はベースラインよりも高い品質のリーダー決定を導出することを示す。 最後に、トロント市と共同で、トロントで現実世界のケーススタディを行い、100万人以上のフォロワーでサイクリングネットワークの設計問題を解決する。 現在の方法と比較すると、トロントの自転車のアクセシビリティは19.2%向上し、コスト削減のための1800万ドルに相当する。 私たちのアプローチはトロントのサイクリングインフラ計画に役立ち、現在のプラクティスを大きなマージンで上回ります。 これは、独立なフォロワーを持つ二段階プログラムとして定式化されるあらゆる決定問題に一般化することができる。

関連論文リスト

• Graph Reinforcement Learning for Network Control via Bi-Level Optimization [37.00510744883984]
  我々は、データ駆動戦略がこのプロセスを自動化し、最適性を損なうことなく効率的なアルゴリズムを学習できると主張している。 我々は、強化学習のレンズを通してネットワーク制御の問題を提示し、幅広い問題に対処するグラフネットワークベースのフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-05-16T03:20:22Z)
• A hybrid deep-learning-metaheuristic framework for bi-level network design problems [2.741266294612776]
  本研究では,道路ネットワーク設計問題(NDP)のための双方向アーキテクチャを用いたハイブリッドディープラーニング・メタヒューリスティックフレームワークを提案する。 我々は、ユーザ均衡(UE)トラフィック割り当て問題の解を近似するために、グラフニューラルネットワーク(GNN)を訓練する。 遺伝的アルゴリズム(GA)の適合度関数評価の計算にトレーニングモデルを用いて,NDPの解を近似する。
  論文  参考訳（メタデータ） (2023-03-10T16:23:56Z)
• Probabilistic Bilevel Coreset Selection [24.874967723659022]
  本稿では,各トレーニングサンプルの確率的重みを学習することにより,コアセット選択の連続確率的2レベル定式化を提案する。 暗黙的な微分の問題を伴わずに、偏りのない政策勾配を経由し、二段階最適化問題に対する効率的な解法を開発する。
  論文  参考訳（メタデータ） (2023-01-24T09:37:00Z)
• TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers [64.88759709443819]
  探索の効率を顕著に向上させると考えられる,インスタンス依存のプロキシを学習することを提案する。 私たちが最初に学ぶことを提案するプロキシは、補正係数、すなわち、インスタンスに依存しないコスト・ツー・ゴの見積もりと完璧な見積もりの比率である。 第2のプロキシはパス確率であり、グリッドセルが最も短いパスに横たわっている可能性を示している。
  論文  参考訳（メタデータ） (2022-12-22T14:26:11Z)
• CLUTR: Curriculum Learning via Unsupervised Task Representation Learning [130.79246770546413]
  CLUTRは、タスク表現とカリキュラム学習を2段階最適化に分離する、新しいカリキュラム学習アルゴリズムである。 CLUTRは、CarRacingとナビゲーション環境における一般化とサンプル効率の観点から、原則的かつ一般的なUED手法であるPAIREDよりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-10-19T01:45:29Z)
• Communication-Efficient Robust Federated Learning with Noisy Labels [144.31995882209932]
  フェデレーテッド・ラーニング(FL)は、分散した位置データの上で、将来性のあるプライバシ保護機械学習パラダイムである。 FLにおける雑音ラベルの効果を緩和する学習に基づく再重み付け手法を提案する。 提案手法は,複数の実世界のデータセットにおいて,各種ベースラインと比較して優れた性能を示した。
  論文  参考訳（メタデータ） (2022-06-11T16:21:17Z)
• Local Stochastic Bilevel Optimization with Momentum-Based Variance Reduction [104.41634756395545]
  具体的には、まず、決定論的勾配に基づくアルゴリズムであるFedBiOを提案する。 FedBiOの複雑性は$O(epsilon-1.5)$である。 本アルゴリズムは数値実験において,他のベースラインと比較して優れた性能を示す。
  論文  参考訳（メタデータ） (2022-05-03T16:40:22Z)
• Improved Bilevel Model: Fast and Optimal Algorithm with Theoretical Guarantee [110.16183719936629]
  本稿では,現行の定式化よりも高速に収束する2レベルモデルを提案する。 実験結果から,本モデルが現行のバイレベルモデルよりも大きなマージンで優れていたことが示唆された。
  論文  参考訳（メタデータ） (2020-09-01T20:52:57Z)
• Towards Model-Agnostic Post-Hoc Adjustment for Balancing Ranking Fairness and Algorithm Utility [54.179859639868646]
  Bipartiteランキングは、ラベル付きデータから正の個人よりも上位の個人をランク付けするスコアリング機能を学ぶことを目的としている。 学習したスコアリング機能が、異なる保護グループ間で体系的な格差を引き起こすのではないかという懸念が高まっている。 本稿では、二部構成のランキングシナリオにおいて、それらのバランスをとるためのモデル後処理フレームワークを提案する。
  論文  参考訳（メタデータ） (2020-06-15T10:08:39Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。