論文の概要: Online Learning for Scheduling MIP Heuristics

• arxiv url: http://arxiv.org/abs/2304.03755v1
• Date: Tue, 4 Apr 2023 14:55:15 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-16 22:35:28.339920
• Title: Online Learning for Scheduling MIP Heuristics
• Title（参考訳）: MIPヒューリスティックススケジューリングのためのオンライン学習
• Authors: Antonia Chmiela, Ambros Gleixner, Pawel Lichocki, Sebastian Pokutta
• Abstract要約: そこで本稿では,問題の解決を手元にある単一インスタンスに適応させるオンライン学習手法を提案する。 一般的に使われている静的ハンドリングを過去の観測を活かした適応フレームワークに置き換える。 解決に少なくとも1000秒を要した難しいインスタンスに対しては、4%のスピードアップを観察する。
• 参考スコア（独自算出の注目度）: 15.599296461516982
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Mixed Integer Programming (MIP) is NP-hard, and yet modern solvers often solve large real-world problems within minutes. This success can partially be attributed to heuristics. Since their behavior is highly instance-dependent, relying on hard-coded rules derived from empirical testing on a large heterogeneous corpora of benchmark instances might lead to sub-optimal performance. In this work, we propose an online learning approach that adapts the application of heuristics towards the single instance at hand. We replace the commonly used static heuristic handling with an adaptive framework exploiting past observations about the heuristic's behavior to make future decisions. In particular, we model the problem of controlling Large Neighborhood Search and Diving - two broad and complex classes of heuristics - as a multi-armed bandit problem. Going beyond existing work in the literature, we control two different classes of heuristics simultaneously by a single learning agent. We verify our approach numerically and show consistent node reductions over the MIPLIB 2017 Benchmark set. For harder instances that take at least 1000 seconds to solve, we observe a speedup of 4%.
• Abstract（参考訳）: MIP(Mixed Integer Programming)はNPハードであるが、現代の解法はしばしば数分で大きな現実世界の問題を解く。 この成功の一部はヒューリスティックスによるものである。 それらの振る舞いは、非常にインスタンスに依存しているため、大規模なベンチマークインスタンスの不均一なコーパスに対する経験的テストに由来するハードコードされたルールに依存すると、準最適性能につながる可能性がある。 本稿では,経験則の適用を手元にある単一インスタンスに適用するオンライン学習手法を提案する。 我々は、一般的に使用される静的ヒューリスティックハンドリングを、ヒューリスティックの振る舞いに関する過去の観察を利用して将来の決定を行う適応フレームワークに置き換える。 特に,多武装バンディット問題である広範で複雑なヒューリスティックスの2つのクラスであるLarge Neborhood Search and Divingの制御問題をモデル化する。 文学における既存の作業を超えて、我々は1つの学習エージェントによって2つの異なるヒューリスティックのクラスを同時に制御する。 提案手法を数値的に検証し,MIPLIB 2017ベンチマークセット上で一貫したノード削減を示す。 解決に少なくとも1000秒を要する難しいインスタンスに対しては、4%のスピードアップを観察します。

関連論文リスト

• An Unsupervised Learning Framework Combined with Heuristics for the Maximum Minimal Cut Problem [5.092968949752308]
  本研究は,MMCPの最大値と非教師なし学習フレームワークを提案する。 重要な観察は、それぞれの溶液が少なくとも1本の枝木に対応することである。 フレームワークを評価し、特定のアプリケーションを提供するために、広範な実験を行います。
  論文  参考訳（メタデータ） (2024-08-16T02:07:34Z)
• Deciphering Movement: Unified Trajectory Generation Model for Multi-Agent [53.637837706712794]
  任意の軌道をマスク入力として処理する統一軌道生成モデルUniTrajを提案する。 具体的には,空間特徴抽出のためのトランスフォーマーエンコーダ内に埋め込まれたゴースト空間マスキング(GSM)モジュールを導入する。 バスケットボール-U,サッカー-U,サッカー-Uの3つの実用的なスポーツゲームデータセットをベンチマークして評価を行った。
  論文  参考訳（メタデータ） (2024-05-27T22:15:23Z)
• Planning for Sample Efficient Imitation Learning [52.44953015011569]
  現在の模倣アルゴリズムは、高い性能と高環境サンプル効率を同時に達成するのに苦労している。 本研究では,環境内サンプルの効率と性能を同時に達成できる計画型模倣学習手法であるEfficientImitateを提案する。 実験結果から,EIは性能と試料効率の両立を図った。
  論文  参考訳（メタデータ） (2022-10-18T05:19:26Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  機械学習は分岐のための有望なパラダイムとして登場した。 分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。 我々は現在最先端のRL分岐アルゴリズムを3～5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
  論文  参考訳（メタデータ） (2022-05-28T06:08:07Z)
• Minimizing Entropy to Discover Good Solutions to Recurrent Mixed Integer Programs [0.0]
  混合整数プログラミング(MIP)問題に対する現在の解法は、幅広い問題に対して良好に動作するように設計されている。 近年の研究では、機械学習(ML)をMIPソルバと統合してドメイン知識を注入し、最適性ギャップを効率的に閉じることが示されている。 本稿では、エントロピーの概念を用いて、最小限のトレーニングデータとチューニングで効率的にモデルを構築するオンラインソルバを提案する。
  論文  参考訳（メタデータ） (2022-02-07T18:52:56Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents [1.3812010983144802]
  ジョブショップスケジューリング問題(JSSP)に対する深層強化学習手法を提案する。 目的は、ジョブやマシンの数によって異なるJSSPインスタンスのディストリビューションについて学べるgreedyのようなものを構築することである。 予想通り、モデルはある程度は、トレーニングで使用されるものと異なる分布から生じるより大きな問題やインスタンスに一般化することができる。
  論文  参考訳（メタデータ） (2021-10-18T07:55:39Z)
• Softmax with Regularization: Better Value Estimation in Multi-Agent Reinforcement Learning [72.28520951105207]
  q$-learningの過大評価は、シングルエージェント強化学習で広く研究されている重要な問題である。 ベースラインから逸脱する大きな関節動作値をペナライズする,新たな正規化ベースの更新方式を提案する。 本手法は,StarCraft IIマイクロマネジメントの課題に対して,一貫した性能向上を実現する。
  論文  参考訳（メタデータ） (2021-03-22T14:18:39Z)
• Learning to Schedule Heuristics in Branch-and-Bound [25.79025327341732]
  現実世界のアプリケーションは通常、迅速な意思決定を可能にするために、検索の早い段階で優れたソリューションを見つける必要があります。 正確なMIPソルバにおけるスケジューリングのための最初のデータ駆動フレームワークを提案する。 最先端の学術MIPソルバーのデフォルト設定と比較して、挑戦的なインスタンスのクラスで平均プライマリ積分を最大49%削減することができます。
  論文  参考訳（メタデータ） (2021-03-18T14:49:52Z)
• Resource Allocation in Multi-armed Bandit Exploration: Overcoming Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
  腕の引っ張りに様々な量の資源を割り当てることができる分割可能な資源にアクセス可能な場合,マルチアームの帯状地における探索について検討する。 特に、分散コンピューティングリソースの割り当てに重点を置いており、プル毎により多くのリソースを割り当てることで、結果をより早く得ることができます。
  論文  参考訳（メタデータ） (2020-10-31T18:19:29Z)

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

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