論文の概要: Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming

• arxiv url: http://arxiv.org/abs/2402.05501v1
• Date: Thu, 8 Feb 2024 09:19:26 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-09 15:53:58.826950
• Title: Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming
• Title（参考訳）: 混合整数線形プログラミングのための機械学習強化分岐と境界
• Authors: Lara Scavuzzo and Karen Aardal and Andrea Lodi and Neil Yorke-Smith
• Abstract要約: Mixed Linear Programming (MILP)は、幅広いアプリケーションに対して強力なモデリング言語を提供する。 近年,ブランチ・アンド・バウンドアルゴリズムに関わる主要なタスクをすべて強化するための機械学習アルゴリズムの利用が爆発的な発展を遂げている。 特に、分岐とバウンドの効率の指標を自動的に最適化する機械学習アルゴリズムに注意を払っている。
• 参考スコア（独自算出の注目度）: 11.293025183996832
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Mixed Integer Linear Programming (MILP) is a pillar of mathematical optimization that offers a powerful modeling language for a wide range of applications. During the past decades, enormous algorithmic progress has been made in solving MILPs, and many commercial and academic software packages exist. Nevertheless, the availability of data, both from problem instances and from solvers, and the desire to solve new problems and larger (real-life) instances, trigger the need for continuing algorithmic development. MILP solvers use branch and bound as their main component. In recent years, there has been an explosive development in the use of machine learning algorithms for enhancing all main tasks involved in the branch-and-bound algorithm, such as primal heuristics, branching, cutting planes, node selection and solver configuration decisions. This paper presents a survey of such approaches, addressing the vision of integration of machine learning and mathematical optimization as complementary technologies, and how this integration can benefit MILP solving. In particular, we give detailed attention to machine learning algorithms that automatically optimize some metric of branch-and-bound efficiency. We also address how to represent MILPs in the context of applying learning algorithms, MILP benchmarks and software.
• Abstract（参考訳）: Mixed Integer Linear Programming (MILP)は、幅広いアプリケーションに強力なモデリング言語を提供する数学的最適化の柱である。 過去数十年間、MILPの解決には膨大なアルゴリズムの進歩が見られ、多くの商用および学術ソフトウェアパッケージが存在する。 それでも、問題インスタンスとソルバの両方からのデータの提供と、新しい問題とより大きな(現実の)インスタンスを解決したいという願望は、アルゴリズム開発を継続する必要性を引き起こしている。 MILPソルバはブランチとバインドをメインコンポーネントとして使用する。 近年, 分岐ヒューリスティックス, 分岐, 切断面, ノード選択, ソルバ構成決定など, 分岐とバウンドのアルゴリズムに関わる主要なタスクをすべて強化するための機械学習アルゴリズムの利用が爆発的な発展を遂げている。 本稿では、機械学習の統合と数学的最適化を補完する技術として捉えるビジョンと、この統合がmilp解決にどのように役立つかを論じた。 特に、分岐とバウンドの効率の指標を自動的に最適化する機械学習アルゴリズムに注意を払っている。 また、学習アルゴリズム、MILPベンチマーク、ソフトウェアの適用状況におけるMILPの表現方法についても検討する。

関連論文リスト

• Meta-Learning from Learning Curves for Budget-Limited Algorithm Selection [11.409496019407067]
  予算制限のシナリオでは、アルゴリズム候補を慎重に選択し、それを訓練するための予算を割り当てることが不可欠である。 本稿では,エージェントが十分に訓練されるまで待たずに,最も有望なアルゴリズムを学習する過程において,エージェントが選択しなければならない新しい枠組みを提案する。
  論文  参考訳（メタデータ） (2024-10-10T08:09:58Z)
• Reinforced In-Context Black-Box Optimization [64.25546325063272]
  RIBBOは、オフラインデータからエンドツーエンドでBBOアルゴリズムを強化学習する手法である。 RIBBOは、複数の動作アルゴリズムとタスクによって生成される最適化履歴を学習するために、表現的なシーケンスモデルを使用している。 提案手法の中心となるのは,テキストレグレット・ツー・ゴートークンによる最適化履歴の増大である。
  論文  参考訳（メタデータ） (2024-02-27T11:32:14Z)
• Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
  MAPF (Multi-Agent Path Finding) は、複数のエージェントが同時に移動し、与えられた目標地点に向かって共有領域を通って衝突しない経路を決定する。 最適解を見つけることは、しばしば計算不可能であり、近似的な準最適アルゴリズムを用いることが不可欠である。 本稿では、MAPFのスケーラブルな機構設計の問題を紹介し、MAPFアルゴリズムを近似した3つの戦略防御機構を提案する。
  論文  参考訳（メタデータ） (2024-01-30T14:26:04Z)
• Machine Learning Insides OptVerse AI Solver: Design Principles and Applications [74.67495900436728]
  本稿では,Huawei CloudのOpsVerse AIソルバに機械学習(ML)技術を統合するための総合的研究について述べる。 本稿では,実世界の多面構造を反映した生成モデルを用いて,複雑なSATインスタンスとMILPインスタンスを生成する手法を紹介する。 本稿では,解解器性能を著しく向上させる,最先端パラメータチューニングアルゴリズムの導入について詳述する。
  論文  参考訳（メタデータ） (2024-01-11T15:02:15Z)
• A Survey From Distributed Machine Learning to Distributed Deep Learning [0.356008609689971]
  データとアルゴリズムを複数のマシンに分散する分散機械学習が提案されている。 これらのアルゴリズムを分類とクラスタリング(従来の機械学習)、深層学習、深層強化学習グループに分割する。 上記のアルゴリズムの調査に基づいて、今後の研究で対処すべき限界を強調した。
  論文  参考訳（メタデータ） (2023-07-11T13:06:42Z)
• On a class of geodesically convex optimization problems solved via Euclidean MM methods [50.428784381385164]
  ユークリッド凸化関数の違いは、統計学と機械学習の異なるタイプの問題の違いとして記述できることを示す。 最終的に、より広い範囲、より広い範囲の作業を支援するのです。
  論文  参考訳（メタデータ） (2022-06-22T23:57:40Z)
• Algorithmic Foundations of Empirical X-risk Minimization [51.58884973792057]
  この原稿は、機械学習とAIの新しい最適化フレームワーク、bf empirical X-risk baseline (EXM)を紹介している。 Xリスク(X-risk)は、構成測度または目的の族を表すために導入された用語である。
  論文  参考訳（メタデータ） (2022-06-01T12:22:56Z)
• A Survey for Solving Mixed Integer Programming via Machine Learning [76.04988886859871]
  本稿では、混合整数(MIP)問題を解くための機械学習の動向について調査する。 本稿では、まず、MIPの定式化とプリミナリーと、MIPを解くための従来のアルゴリズムについて紹介する。 そして、機械学習とMIPアルゴリズムの異なる統合をさらに促進することを提唱する。
  論文  参考訳（メタデータ） (2022-03-06T05:03:37Z)
• Knowledge engineering mixed-integer linear programming: constraint typology [2.4002205752931625]
  混合整数線形プログラムMILPの制約型について検討する。 milpは、実生活のスケジューリング、ルーティング、計画、リソース割り当て、時間的最適化問題のモデリングと解決によく使われる数学的プログラミング手法である。
  論文  参考訳（メタデータ） (2021-02-20T20:07:24Z)
• Parallel Scheduling Self-attention Mechanism: Generalization and Optimization [0.76146285961466]
  本稿では,SAT(Satisfiability check)ソルバによって解決された小インスタンスの最適スケジューリングから導いた一般スケジューリングアルゴリズムを提案する。 余剰計算をスキップする際のさらなる最適化戦略も推進され、元の計算の約25%と50%の削減が達成される。 提案アルゴリズムは、入力ベクトルの数がアーキテクチャで利用可能な演算ユニットの数に割り切れる限り、問題のサイズにかかわらず適用可能である。
  論文  参考訳（メタデータ） (2020-12-02T12:04:16Z)

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

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