論文の概要: Fast Continuous and Integer L-shaped Heuristics Through Supervised Learning

• arxiv url: http://arxiv.org/abs/2205.00897v1
• Date: Mon, 2 May 2022 13:15:32 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-03 16:35:14.721700
• Title: Fast Continuous and Integer L-shaped Heuristics Through Supervised Learning
• Title（参考訳）: 教師付き学習による高速連続・整数L字ヒューリスティックス
• Authors: Eric Larsen, Emma Frejinger, Bernard Gendron and Andrea Lodi
• Abstract要約: 混合整数線形二段階プログラムの解を高速化する手法を提案する。 我々は,第2段階の要求の高い問題を解決することを目的としている。 私たちの中核となる考え方は、オンラインソリューションの時間を大幅に削減し、第一段階ソリューションの精度を小さくすることです。
• 参考スコア（独自算出の注目度）: 4.521119623956821
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We propose a methodology at the nexus of operations research and machine learning (ML) leveraging generic approximators available from ML to accelerate the solution of mixed-integer linear two-stage stochastic programs. We aim at solving problems where the second stage is highly demanding. Our core idea is to gain large reductions in online solution time while incurring small reductions in first-stage solution accuracy by substituting the exact second-stage solutions with fast, yet accurate supervised ML predictions. This upfront investment in ML would be justified when similar problems are solved repeatedly over time, for example, in transport planning related to fleet management, routing and container yard management. Our numerical results focus on the problem class seminally addressed with the integer and continuous L-shaped cuts. Our extensive empirical analysis is grounded in standardized families of problems derived from stochastic server location (SSLP) and stochastic multi knapsack (SMKP) problems available in the literature. The proposed method can solve the hardest instances of SSLP in less than 9% of the time it takes the state-of-the-art exact method, and in the case of SMKP the same figure is 20%. Average optimality gaps are in most cases less than 0.1%.
• Abstract（参考訳）: そこで本研究では, ml から利用可能な汎用近似器を応用した nexus of operations research and machine learning (ml) において, 混合整数線形2段階確率プログラムの解を高速化する手法を提案する。 我々は,第2段階が高度に要求される問題を解決することを目指している。 我々の中核となる考え方は、高速かつ高精度に教師付きML予測をすることで、第1ステージソリューションの精度を低下させながら、オンラインソリューションの時間を大幅に短縮することである。 このMLへの事前投資は、例えば、艦隊管理、ルーティング、コンテナヤード管理に関連する輸送計画において、同様の問題が繰り返し解決された場合に正当化される。 数値計算の結果は、整数と連続L字切断を半々的に扱う問題クラスに焦点をあてる。 文献で利用可能な確率的サーバ位置(SSLP)と確率的マルチクナップサック(SMKP)問題から導かれる問題の標準化されたファミリに、我々の広範な経験分析を基礎としている。 提案手法は,最先端の正解法に要する時間の9%以下でSSLPの最も難しいインスタンスを解くことができ,SMKPの場合,同じ数値が20%である。 平均最適ギャップは、ほとんどの場合0.1%未満である。

関連論文リスト

• A Stochastic Approach to Bi-Level Optimization for Hyperparameter Optimization and Meta Learning [74.80956524812714]
  我々は,現代のディープラーニングにおいて広く普及している一般的なメタ学習問題に対処する。 これらの問題は、しばしばBi-Level Optimizations (BLO)として定式化される。 我々は,与えられたBLO問題を,内部損失関数が滑らかな分布となり,外損失が内部分布に対する期待損失となるようなii最適化に変換することにより,新たな視点を導入する。
  論文  参考訳（メタデータ） (2024-10-14T12:10:06Z)
• Sample-Efficient Multi-Agent RL: An Optimization Perspective [103.35353196535544]
  一般関数近似に基づく汎用マルコフゲーム(MG)のためのマルチエージェント強化学習(MARL)について検討した。 汎用MGに対するマルチエージェントデカップリング係数(MADC)と呼ばれる新しい複雑性尺度を導入する。 我々のアルゴリズムは既存の研究に匹敵するサブリニアな後悔を与えることを示す。
  論文  参考訳（メタデータ） (2023-10-10T01:39:04Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  置換フローショップスケジューリング(PFSS)は製造業で広く使われている。 我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。 我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
  論文  参考訳（メタデータ） (2022-10-31T09:46:26Z)
• Learning Optimal Solutions via an LSTM-Optimization Framework [0.0]
  動的混合整数プログラムに取り組むためのディープラーニング最適化フレームワークを提案する。 我々は,情報を前後に処理できる双方向長短期記憶(LSTM)フレームワークを開発した。 本研究は, 単体容量化ロットサイズ問題に対する最適決定の予測におけるアプローチを実証する。
  論文  参考訳（メタデータ） (2022-07-06T19:38:01Z)
• Minimizing Entropy to Discover Good Solutions to Recurrent Mixed Integer Programs [0.0]
  混合整数プログラミング(MIP)問題に対する現在の解法は、幅広い問題に対して良好に動作するように設計されている。 近年の研究では、機械学習(ML)をMIPソルバと統合してドメイン知識を注入し、最適性ギャップを効率的に閉じることが示されている。 本稿では、エントロピーの概念を用いて、最小限のトレーニングデータとチューニングで効率的にモデルを構築するオンラインソルバを提案する。
  論文  参考訳（メタデータ） (2022-02-07T18:52:56Z)
• MILP for the Multi-objective VM Reassignment Problem [1.3649494534428743]
  多目的機械再割り当て問題は制約と混合整数プログラミングのアプローチにおいて難しい問題である。 我々は,IBM ILOG CPLEXのような混合整数最適化問題を多目的マシン再割り当て問題に利用できることを示す。 本研究では,小・中規模のデータセンタに対してのみ有用であり,最適公差や検索空間での探索方向の制限など,いくつかの緩和効果があることを示す。
  論文  参考訳（メタデータ） (2021-03-18T17:46:57Z)
• Learning to Schedule Heuristics in Branch-and-Bound [25.79025327341732]
  現実世界のアプリケーションは通常、迅速な意思決定を可能にするために、検索の早い段階で優れたソリューションを見つける必要があります。 正確なMIPソルバにおけるスケジューリングのための最初のデータ駆動フレームワークを提案する。 最先端の学術MIPソルバーのデフォルト設定と比較して、挑戦的なインスタンスのクラスで平均プライマリ積分を最大49%削減することができます。
  論文  参考訳（メタデータ） (2021-03-18T14:49:52Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。 リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。 このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
  論文  参考訳（メタデータ） (2021-02-27T19:28:39Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)

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

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