論文の概要: 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の表現方法についても検討する。
関連論文リスト
- Reinforced In-Context Black-Box Optimization [67.02295929937829]
RIBBOは、オフラインデータからエンドツーエンドでBBOアルゴリズムを強化学習する手法である。
RIBBOは、複数の動作アルゴリズムとタスクによって生成された最適化履歴を学習するために、表現的なシーケンスモデルを使用している。
提案手法の中心となるのは,履歴の累積的後悔に基づくアルゴリズムの性能を表現するために,後悔から後悔へのトークンで最適化履歴を増大させることである。
論文 参考訳(メタデータ) (2024-02-27T11:32:14Z) - Scalable Mechanism Design for Multi-Agent Path Finding [90.68703851865585]
MAPF (Multi-Agent Path Finding) は、複数のエージェントが特定の目標地点に向かって共有領域を同時に移動するための経路を決定する。
最適解を見つけることは、しばしば計算不可能であり、近似アルゴリズムを用いることが不可欠である。
本稿では,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) - A Knowledge Representation Approach to Automated Mathematical Modelling [1.8907108368038215]
我々はMILPモデルオントロジーとMILP定式化の新しい制約型について提案する。
MILPは、リアルタイムスケジューリング、ルーティング、計画、リソース割り当て、タイムタブル最適化の問題をモデル化し、解くために一般的に用いられる数学的プログラミング手法である。
本研究の目的は,業務最適化問題の自然言語記述をMILP形式仕様にマッピングする,MILPの機械可読な知識表現を開発することである。
論文 参考訳(メタデータ) (2020-11-12T10:29:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。