Fugu-MT 論文翻訳(概要): Learning to Schedule Heuristics in Branch-and-Bound

論文の概要: Learning to Schedule Heuristics in Branch-and-Bound

arxiv url: http://arxiv.org/abs/2103.10294v1
Date: Thu, 18 Mar 2021 14:49:52 GMT
ステータス: 処理完了
システム内更新日: 2021-03-19 13:49:10.626089
Title: Learning to Schedule Heuristics in Branch-and-Bound
Title（参考訳）: 分岐・境界におけるスケジュールヒューリスティックスへの学習
Authors: Antonia Chmiela, Elias B. Khalil, Ambros Gleixner, Andrea Lodi, Sebastian Pokutta
Abstract要約: 現実世界のアプリケーションは通常、迅速な意思決定を可能にするために、検索の早い段階で優れたソリューションを見つける必要があります。正確なMIPソルバにおけるスケジューリングのための最初のデータ駆動フレームワークを提案する。最先端の学術MIPソルバーのデフォルト設定と比較して、挑戦的なインスタンスのクラスで平均プライマリ積分を最大49%削減することができます。
参考スコア（独自算出の注目度）: 25.79025327341732
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Primal heuristics play a crucial role in exact solvers for Mixed Integer Programming (MIP). While solvers are guaranteed to find optimal solutions given sufficient time, real-world applications typically require finding good solutions early on in the search to enable fast decision-making. While much of MIP research focuses on designing effective heuristics, the question of how to manage multiple MIP heuristics in a solver has not received equal attention. Generally, solvers follow hard-coded rules derived from empirical testing on broad sets of instances. Since the performance of heuristics is instance-dependent, using these general rules for a particular problem might not yield the best performance. In this work, we propose the first data-driven framework for scheduling heuristics in an exact MIP solver. By learning from data describing the performance of primal heuristics, we obtain a problem-specific schedule of heuristics that collectively find many solutions at minimal cost. We provide a formal description of the problem and propose an efficient algorithm for computing such a schedule. Compared to the default settings of a state-of-the-art academic MIP solver, we are able to reduce the average primal integral by up to 49% on a class of challenging instances.
Abstract（参考訳）: 主ヒューリスティックは混合整数プログラミング(mip)の完全解法において重要な役割を果たす。解決者は十分な時間があれば最適な解を見つけることが保証されるが、現実世界のアプリケーションは通常、迅速な意思決定を可能にするために探索の早い段階で良い解を見つける必要がある。 MIP研究の多くは効果的なヒューリスティックスの設計に重点を置いているが、解法における複数のMIPヒューリスティックスをどのように管理するかという問題は、等しく注目されていない。一般に、解法は幅広いインスタンスに対する経験的テストから導かれるハードコードルールに従う。ヒューリスティックスのパフォーマンスはインスタンスに依存しているため、特定の問題に対してこれらの一般的なルールを使用することで、最高のパフォーマンスを得ることはできない。本研究では,正確なMIP解法におけるヒューリスティックススケジューリングのための,最初のデータ駆動型フレームワークを提案する。主ヒューリスティックスの性能を記述するデータから学習することにより、最小コストで多くの解を集合的に見つけるヒューリスティックスの問題固有のスケジュールを得る。この問題を形式的に記述し、そのようなスケジュールを計算するための効率的なアルゴリズムを提案する。最先端の学術的MIPソルバのデフォルト設定と比較して、挑戦的なインスタンスのクラスでは、平均原始積分を最大49%削減できる。

関連論文リスト

An Unsupervised Learning Framework Combined with Heuristics for the Maximum Minimal Cut Problem [5.092968949752308]
本研究は,MMCPの最大値と非教師なし学習フレームワークを提案する。重要な観察は、それぞれの溶液が少なくとも1本の枝木に対応することである。フレームワークを評価し、特定のアプリケーションを提供するために、広範な実験を行います。
論文参考訳（メタデータ） (2024-08-16T02:07:34Z)
An End-to-End Reinforcement Learning Approach for Job-Shop Scheduling Problems Based on Constraint Programming [5.070542698701157]
本稿では,CPと強化学習(Reinforcement Learning, RL)を用いてスケジューリング問題を解決する新しいエンドツーエンドアプローチを提案する。当社のアプローチでは,既存のCPソルバを活用して,プライオリティ・ディスパッチ・ルール(PDR)を学ぶエージェントをトレーニングする。
論文参考訳（メタデータ） (2023-06-09T08:24:56Z)
Online Learning for Scheduling MIP Heuristics [15.599296461516982]
そこで本稿では,問題の解決を手元にある単一インスタンスに適応させるオンライン学習手法を提案する。一般的に使われている静的ハンドリングを過去の観測を活かした適応フレームワークに置き換える。解決に少なくとも1000秒を要した難しいインスタンスに対しては、4%のスピードアップを観察する。
論文参考訳（メタデータ） (2023-04-04T14:55:15Z)
A Survey for Solving Mixed Integer Programming via Machine Learning [76.04988886859871]
本稿では、混合整数(MIP)問題を解くための機械学習の動向について調査する。本稿では、まず、MIPの定式化とプリミナリーと、MIPを解くための従来のアルゴリズムについて紹介する。そして、機械学習とMIPアルゴリズムの異なる統合をさらに促進することを提唱する。
論文参考訳（メタデータ） (2022-03-06T05:03:37Z)
Minimizing Entropy to Discover Good Solutions to Recurrent Mixed Integer Programs [0.0]
混合整数プログラミング(MIP)問題に対する現在の解法は、幅広い問題に対して良好に動作するように設計されている。近年の研究では、機械学習(ML)をMIPソルバと統合してドメイン知識を注入し、最適性ギャップを効率的に閉じることが示されている。本稿では、エントロピーの概念を用いて、最小限のトレーニングデータとチューニングで効率的にモデルを構築するオンラインソルバを提案する。
論文参考訳（メタデータ） (2022-02-07T18:52:56Z)
Learning Robust Scheduling with Search and Attention [6.217548079545464]
物理層リソースをチャネル品質、バッファサイズ、要求および制約に基づいてユーザに割り当てることは、無線リソースの管理における中心的な最適化問題の1つである。 MU-MIMOスケジューリングでは、スケジューラが複数のユーザを同じ時間周波数の物理リソースに割り当てることができる。本稿では,MU-MIMOスケジューリング問題を木構造問題として扱うとともに,AlphaGo Zeroの最近の成功から借用して,最高の実行ソリューションを探す可能性について検討する。
論文参考訳（メタデータ） (2021-11-15T20:46:26Z)
Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文参考訳（メタデータ） (2021-09-13T18:10:52Z)
A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
論文参考訳（メタデータ） (2021-03-10T03:16:12Z)
Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-01-07T08:00:02Z)
Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
論文参考訳（メタデータ） (2020-12-04T15:36:29Z)
Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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