論文の概要: A Study of Learning Search Approximation in Mixed Integer Branch and Bound: Node Selection in SCIP

• arxiv url: http://arxiv.org/abs/2007.03948v2
• Date: Mon, 3 Jan 2022 21:04:30 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-12 13:04:55.342978
• Title: A Study of Learning Search Approximation in Mixed Integer Branch and Bound: Node Selection in SCIP
• Title（参考訳）: scipにおける混合整数分岐とバウンドノード選択における学習探索近似に関する研究
• Authors: Kaan Yilmaz and Neil Yorke-Smith
• Abstract要約: このようなポリシーを2つの設定で学習するオフライン手法を提案する。 1つの設定は、プリンギング中に子供のセレクタに対応し、もう1つはダイビングに似ている。 5つのMIPデータセットの実証結果は、我々のノード選択ポリシーが、文献における最先端の先例よりもはるかに高速な解決につながることを示している。
• 参考スコア（独自算出の注目度）: 2.528056693920671
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In line with the growing trend of using machine learning to help solve combinatorial optimisation problems, one promising idea is to improve node selection within a mixed integer programming (MIP) branch-and-bound tree by using a learned policy. Previous work using imitation learning indicates the feasibility of acquiring a node selection policy, by learning an adaptive node searching order. In contrast, our imitation learning policy is focused solely on learning which of a node's children to select. We present an offline method to learn such a policy in two settings: one that comprises a heuristic by committing to pruning of nodes; one that is exact and backtracks from a leaf to guarantee finding the optimal integer solution. The former setting corresponds to a child selector during plunging, while the latter is akin to a diving heuristic. We apply the policy within the popular open-source solver SCIP, in both heuristic and exact settings. Empirical results on five MIP datasets indicate that our node selection policy leads to solutions significantly more quickly than the state-of-the-art precedent in the literature. While we do not beat the highly-optimised SCIP state-of-practice baseline node selector in terms of solving time on exact solutions, our heuristic policies have a consistently better optimality gap than all baselines, if the accuracy of the predictive model is sufficient. Further, the results also indicate that, when a time limit is applied, our heuristic method finds better solutions than all baselines in the majority of problems tested. We explain the results by showing that the learned policies have imitated the SCIP baseline, but without the latter's early plunge abort. Our recommendation is that, despite the clear improvements over the literature, this kind of MIP child selector is better seen in a broader approach using learning in MIP branch-and-bound tree decisions.
• Abstract（参考訳）: 組合せ最適化問題の解決に機械学習を用いる傾向の高まりに合わせて、学習ポリシーを用いることで、混合整数プログラミング(MIP)の分岐木におけるノード選択を改善することが期待されている。 模倣学習を用いた先行研究は、適応ノード探索順序を学習することにより、ノード選択ポリシーを取得する可能性を示す。 対照的に、我々の模倣学習政策は、どのノードの子どもを選ぶかを学ぶことに集中している。 本稿では,ノードの刈り込みにコミットしてヒューリスティックを構成するもの,葉からバックトラックして最適整数解を求めるもの,という2つの設定で学習するオフライン手法を提案する。 前者のセッティングはプリンギング中に子供のセレクターに対応し、後者はダイビングヒューリスティックに似ている。 我々は,このポリシーを一般のオープンソースソルバSCIPに,ヒューリスティックかつ正確な設定で適用する。 5つのMIPデータセットの実証結果は、我々のノード選択ポリシーが、文献における最先端の先例よりもはるかに高速な解決につながることを示している。 我々は、厳密な解の解法の観点から、高度に最適化されたSCIPベースラインノードセレクタを破ることはできないが、予測モデルの精度が十分であれば、我々のヒューリスティックポリシーは、全てのベースラインよりも一貫して優れた最適性ギャップを有する。 さらに,本研究の結果は,時間制限を適用した場合には,テストされた問題の大部分において,すべてのベースラインよりも優れた解を求めることを示す。 我々は,学習したポリシがscipベースラインを模倣したことを示すことにより,結果を説明する。 我々の推奨は、文献よりも明らかに改善されているにもかかわらず、この種のMIP子選別器は、MIP分岐木決定における学習を用いてより広いアプローチでよりよく見られることである。

関連論文リスト

• Reinforcement Learning for Node Selection in Branch-and-Bound [52.2648997215667]
  現在の最先端セレクタは手作りのアンサンブルを使用して、ナイーブなサブノードセレクタと、個々のノードデータに依存する学習ノードセレクタを自動的に切り替える。 孤立ノードではなく木の状態全体を考慮しながら強化学習(RL)を用いる新しいシミュレーション手法を提案する。
  論文  参考訳（メタデータ） (2023-09-29T19:55:56Z)
• Realistic Unsupervised CLIP Fine-tuning with Universal Entropy Optimization [101.08992036691673]
  本稿では,未知のクラスにおける配布外サンプルの存在を考慮し,教師なしの微調整シナリオについて考察する。 特に,分布外検出と既知のクラスに関連するインスタンスの認識を同時に強化することに注力する。 我々はUniversal Entropy Optimization(UEO)と呼ばれるシンプルで効率的で効果的なアプローチを提案する。
  論文  参考訳（メタデータ） (2023-08-24T16:47:17Z)
• Optimal Decision Tree Policies for Markov Decision Processes [7.995360025953931]
  マルコフ決定過程(MPD)におけるサイズ制限決定木の最適化について検討する。 これは、模倣学習の固有の欠点、すなわち、複雑なポリシーが、サイズ制限木を使って表現できないことによるものである。 一般的に、機械学習モデルの性能と解釈可能性の間にはトレードオフがあるが、OMDTは3の深さに制限され、しばしば最適限に近い性能を示す。
  論文  参考訳（メタデータ） (2023-01-30T18:51:02Z)
• Sample-Efficient Multi-Objective Learning via Generalized Policy Improvement Prioritization [8.836422771217084]
  マルチオブジェクト強化学習(MORL)アルゴリズムは、エージェントが異なる好みを持つ可能性のあるシーケンシャルな決定問題に対処する。 本稿では、一般化政策改善(GPI)を用いて、原則的、正式に派生した優先順位付けスキームを定義する新しいアルゴリズムを提案する。 実験により,本手法は多目的タスクの挑戦において,最先端のMORLアルゴリズムよりも優れていることを示す。
  論文  参考訳（メタデータ） (2023-01-18T20:54:40Z)
• Policy learning "without" overlap: Pessimism and generalized empirical Bernstein's inequality [94.89246810243053]
  本論文は,事前収集した観測値を利用して最適な個別化決定規則を学習するオフライン政策学習について検討する。 既存の政策学習法は、一様重なりの仮定、すなわち、全ての個々の特性に対する全ての作用を探索する正当性は、境界を低くしなければならない。 我々は,点推定の代わりに低信頼度境界(LCB)を最適化する新しいアルゴリズムであるPPLを提案する。
  論文  参考訳（メタデータ） (2022-12-19T22:43:08Z)
• Branch Ranking for Efficient Mixed-Integer Programming via Offline Ranking-based Policy Learning [45.1011106869493]
  オフライン強化学習(RL)問題として分岐学習を定式化する。 オフラインポリシー学習を通じてブランチランキングと呼ばれるブランチモデルをトレーニングします。 合成MIPベンチマークと実世界のタスクの実験は、ブランチランクがより効率的で堅牢であることを示している。
  論文  参考訳（メタデータ） (2022-07-26T15:34:10Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs [6.084888301899142]
  混合整数プログラム(MIP)に対する学習型LSSアプローチの検討 ニューラル・ディバイディング・モデルを用いて代入よりも確率分布を表現し、既製のMIPソルバとともに初期代入を生成する。 そこで我々はニューラル近隣選択ポリシーを訓練し,各ステップで探索地区を選択する。
  論文  参考訳（メタデータ） (2021-07-21T16:43:46Z)
• Exploiting Learned Policies in Focal Search [0.49723239539321284]
  政策学習を有界-準最適探索アルゴリズムに統合する方法を示す。 提案手法は3つのベンチマーク領域を対象とし,15-puzzleでは150万のサンプルを用いて学習したニューラルネットワークを用いて解析を行った。 本稿では,emphDiscrepancy Focal Searchにおいて,対応する経路が最適経路の接頭辞である確率の近似を最大化するノードを拡大し,実行時および解の質の観点から最もよい結果が得られることを示す。
  論文  参考訳（メタデータ） (2021-04-21T13:50:40Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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