論文の概要: Branch and Bound in Mixed Integer Linear Programming Problems: A Survey of Techniques and Trends

• arxiv url: http://arxiv.org/abs/2111.06257v1
• Date: Fri, 5 Nov 2021 10:18:21 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-14 15:27:24.969828
• Title: Branch and Bound in Mixed Integer Linear Programming Problems: A Survey of Techniques and Trends
• Title（参考訳）: 混合整数線形プログラミング問題における分岐と境界:技術と動向の調査
• Authors: Lingying Huang, Xiaomeng Chen, Wei Huo, Jiazheng Wang, Fan Zhang, Bo Bai, Ling Shi
• Abstract要約: 一般分岐および有界(B&B)アルゴリズムにおける4つの臨界成分に対する異なるアプローチとアルゴリズムについて検討する。 近年,B&Bアルゴリズムの高速化のために,このアルゴリズムに学習技術が導入されている。
• 参考スコア（独自算出の注目度）: 7.432176855020725
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we surveyed the existing literature studying different approaches and algorithms for the four critical components in the general branch and bound (B&B) algorithm, namely, branching variable selection, node selection, node pruning, and cutting-plane selection. However, the complexity of the B&B algorithm always grows exponentially with respect to the increase of the decision variable dimensions. In order to improve the speed of B&B algorithms, learning techniques have been introduced in this algorithm recently. We further surveyed how machine learning can be used to improve the four critical components in B&B algorithms. In general, a supervised learning method helps to generate a policy that mimics an expert but significantly improves the speed. An unsupervised learning method helps choose different methods based on the features. In addition, models trained with reinforcement learning can beat the expert policy, given enough training and a supervised initialization. Detailed comparisons between different algorithms have been summarized in our survey. Finally, we discussed some future research directions to accelerate and improve the algorithms further in the literature.
• Abstract（参考訳）: 本稿では, 分岐変数選択, ノード選択, ノードプルーニング, 切削平面選択という, 一般分岐境界(B&B)アルゴリズムにおける4つの臨界成分に対する異なるアプローチとアルゴリズムについて検討した。 しかし、B&Bアルゴリズムの複雑さは常に決定変数次元の増加に関して指数関数的に増大する。 近年,B&Bアルゴリズムの高速化のために,このアルゴリズムに学習技術が導入されている。 さらに、B&Bアルゴリズムの4つの重要なコンポーネントを改善するために機械学習をどのように利用できるかを調査した。 一般に、教師付き学習法は、専門家を模倣するが、速度を大幅に改善するポリシーを生成するのに役立つ。 教師なし学習法は、特徴に基づいて異なる方法を選択するのに役立つ。 さらに、強化学習で訓練されたモデルは、十分なトレーニングと教師付き初期化によって専門家の方針を破ることができる。 異なるアルゴリズム間の詳細な比較が調査にまとめられている。 最後に,論文におけるアルゴリズムのさらなる高速化と改良に向けた今後の研究の方向性について論じる。

関連論文リスト

• Meta-Learning from Learning Curves for Budget-Limited Algorithm Selection [11.409496019407067]
  予算制限のシナリオでは、アルゴリズム候補を慎重に選択し、それを訓練するための予算を割り当てることが不可欠である。 本稿では,エージェントが十分に訓練されるまで待たずに,最も有望なアルゴリズムを学習する過程において,エージェントが選択しなければならない新しい枠組みを提案する。
  論文  参考訳（メタデータ） (2024-10-10T08:09:58Z)
• Tree-Based Adaptive Model Learning [62.997667081978825]
  我々はKearns-Vazirani学習アルゴリズムを拡張し、時間とともに変化するシステムを扱う。 本稿では,学習前の動作を再利用し,更新し,LearnerLibライブラリに実装し,大規模な実例で評価する学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-31T21:24:22Z)
• The CLRS Algorithmic Reasoning Benchmark [28.789225199559834]
  アルゴリズムの学習表現は機械学習の新たな領域であり、ニューラルネットワークから古典的なアルゴリズムで概念をブリッジしようとしている。 本稿では,従来のアルゴリズムを包括するCLRS Algorithmic Reasoning Benchmarkを提案する。 我々のベンチマークは、ソート、探索、動的プログラミング、グラフアルゴリズム、文字列アルゴリズム、幾何アルゴリズムなど、様々なアルゴリズムの推論手順にまたがっている。
  論文  参考訳（メタデータ） (2022-05-31T09:56:44Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Algorithm Selection on a Meta Level [58.720142291102135]
  本稿では,与えられたアルゴリズムセレクタの組み合わせに最適な方法を求めるメタアルゴリズム選択の問題を紹介する。 本稿では,メタアルゴリズム選択のための一般的な方法論フレームワークと,このフレームワークのインスタンス化として具体的な学習手法を提案する。
  論文  参考訳（メタデータ） (2021-07-20T11:23:21Z)
• Safe Learning and Optimization Techniques: Towards a Survey of the State of the Art [3.6954802719347413]
  安全な学習と最適化は、できるだけ安全でない入力ポイントの評価を避ける学習と最適化の問題に対処します。 安全強化学習アルゴリズムに関する包括的な調査は2015年に発表されたが、アクティブラーニングと最適化に関する関連研究は考慮されなかった。 本稿では,強化学習,ガウス過程の回帰と分類,進化的アルゴリズム,アクティブラーニングなど,様々な分野のアルゴリズムについて概説する。
  論文  参考訳（メタデータ） (2021-01-23T13:58:09Z)
• Evolving Reinforcement Learning Algorithms [186.62294652057062]
  メタラーニング強化学習アルゴリズムの手法を提案する。 学習アルゴリズムはドメインに依存しないため、トレーニング中に見えない新しい環境に一般化することができる。 従来の制御タスク、gridworld型タスク、atariゲームよりも優れた一般化性能を得る2つの学習アルゴリズムに注目した。
  論文  参考訳（メタデータ） (2021-01-08T18:55:07Z)
• Mastering Rate based Curriculum Learning [78.45222238426246]
  学習の進行という概念には、学習者のサンプル効率の低下につながるいくつかの欠点があると主張する。 本稿では,習得率の概念に基づく新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-08-14T16:34:01Z)
• Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
  生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。 我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。 標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
  論文  参考訳（メタデータ） (2020-07-06T15:20:17Z)

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

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