論文の概要: Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut
- arxiv url: http://arxiv.org/abs/2402.02328v3
- Date: Tue, 4 Jun 2024 17:05:20 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-06 13:08:02.805371
- Title: Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut
- Title（参考訳）: ニューラルネットワークを用いたアルゴリズム選択のサンプル複雑度と分岐・カットへの応用
- Authors: Hongyu Cheng, Sammy Khalife, Barbara Fiedorowicz, Amitabh Basu,
- Abstract要約: 本研究は,最適な性能を持つ1つのアルゴリズムを選択するのではなく,インスタンスに基づいてアルゴリズムを選択することが可能となるような設定を考慮し,最近の研究を基礎にしている。
特に、代表的なインスタンスのサンプルが与えられた場合、問題のインスタンスをそのインスタンスの最も適切なアルゴリズムにマッピングするニューラルネットワークを学習する。
言い換えれば、ニューラルネットワークは混合整数最適化インスタンスを入力として取り、そのインスタンスの小さな分岐とカットツリーをもたらす決定を出力する。
- 参考スコア（独自算出の注目度）: 1.4624458429745086
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Data-driven algorithm design is a paradigm that uses statistical and machine learning techniques to select from a class of algorithms for a computational problem an algorithm that has the best expected performance with respect to some (unknown) distribution on the instances of the problem. We build upon recent work in this line of research by considering the setup where, instead of selecting a single algorithm that has the best performance, we allow the possibility of selecting an algorithm based on the instance to be solved, using neural networks. In particular, given a representative sample of instances, we learn a neural network that maps an instance of the problem to the most appropriate algorithm for that instance. We formalize this idea and derive rigorous sample complexity bounds for this learning problem, in the spirit of recent work in data-driven algorithm design. We then apply this approach to the problem of making good decisions in the branch-and-cut framework for mixed-integer optimization (e.g., which cut to add?). In other words, the neural network will take as input a mixed-integer optimization instance and output a decision that will result in a small branch-and-cut tree for that instance. Our computational results provide evidence that our particular way of using neural networks for cut selection can make a significant impact in reducing branch-and-cut tree sizes, compared to previous data-driven approaches.
- Abstract（参考訳）: データ駆動型アルゴリズム設計(Data-driven algorithm design)は、統計および機械学習技術を用いて、計算問題に対するアルゴリズムのクラスから選択するパラダイムである。
我々は、この一連の研究において、最高のパフォーマンスを持つ1つのアルゴリズムを選択する代わりに、ニューラルネットワークを用いて、解決すべきインスタンスに基づいてアルゴリズムを選択することが可能な設定を考慮し、最近の研究結果に基づいて構築する。
特に、代表的なインスタンスのサンプルが与えられた場合、問題のインスタンスをそのインスタンスの最も適切なアルゴリズムにマッピングするニューラルネットワークを学習する。
我々は、このアイデアを形式化し、データ駆動アルゴリズム設計における最近の研究の精神の中で、この学習問題に対する厳密なサンプル複雑性を導出する。
次に、このアプローチを、混合整数最適化のためのブランチ・アンド・カットのフレームワークで良い決定をする問題に適用する。
言い換えれば、ニューラルネットワークは混合整数最適化インスタンスを入力として取り、そのインスタンスの小さな分岐とカットツリーをもたらす決定を出力する。
我々の計算結果は、従来のデータ駆動型アプローチと比較して、ニューラルネットワークをカットセレクションに使用する場合、分岐とカットのツリーサイズを削減できることを示す。
関連論文リスト
- On Statistical Learning of Branch and Bound for Vehicle Routing
Optimization [3.6922704509753084]
我々は,計算コストの高いStrong Branching戦略の決定過程をエミュレートするためにニューラルネットワークを訓練する。
このアプローチは分岐とバウンドのアルゴリズムの性能にマッチするか、改善することができる。
論文 参考訳（メタデータ） (2023-10-15T23:59:57Z) - Neural Algorithmic Reasoning for Combinatorial Optimisation [20.36694807847833]
ニューラル推論の最近の進歩を活用して,CO問題の学習を改善することを提案する。
私たちは、COインスタンスでトレーニングする前に、関連するアルゴリズムでニューラルネットワークを事前トレーニングすることを提案します。
以上の結果から,この学習装置を用いることで,非アルゴリズム的情報深層学習モデルよりも優れた性能が得られることが示された。
論文 参考訳（メタデータ） (2023-05-18T13:59:02Z) - The Cascaded Forward Algorithm for Neural Network Training [61.06444586991505]
本稿では,ニューラルネットワークのための新しい学習フレームワークであるCascaded Forward(CaFo)アルゴリズムを提案する。
FFとは異なり、我々のフレームワークは各カスケードブロックのラベル分布を直接出力する。
我々のフレームワークでは、各ブロックは独立して訓練できるので、並列加速度システムに容易に展開できる。
論文 参考訳（メタデータ） (2023-03-17T02:01:11Z) - A machine learning based algorithm selection method to solve the minimum
cost flow problem [0.8399688944263843]
複数の機械学習分類器を訓練し、与えられた解の集合の中で最速の予測を行う。
木をベースとしたモデルでは,最小コストのフロー問題の関連構造を適応し,活用することが示されている。
論文 参考訳（メタデータ） (2022-10-03T16:06:24Z) - Learning with Differentiable Algorithms [6.47243430672461]
この論文は、古典的なアルゴリズムとニューラルネットワークのような機械学習システムを組み合わせることを探求している。
この論文はアルゴリズムの監督という概念を定式化し、ニューラルネットワークがアルゴリズムから、あるいは、アルゴリズムと連動して学ぶことを可能にする。
さらに、この論文では、微分可能なソートネットワーク、微分可能なソートゲート、微分可能な論理ゲートネットワークなど、微分可能なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-09-01T17:30:00Z) - Neural Combinatorial Optimization: a New Player in the Field [69.23334811890919]
本稿では,ニューラルネットワークに基づくアルゴリズムの古典的最適化フレームワークへの導入に関する批判的分析を行う。
性能, 転送可能性, 計算コスト, 大規模インスタンスなど, これらのアルゴリズムの基本的側面を分析するために, 総合的研究を行った。
論文 参考訳（メタデータ） (2022-05-03T07:54:56Z) - 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) - Benchmarking Simulation-Based Inference [5.3898004059026325]
確率的モデリングの最近の進歩は、確率の数値的評価を必要としないシミュレーションに基づく推論アルゴリズムを多数もたらした。
推論タスクと適切なパフォーマンス指標を備えたベンチマークを,アルゴリズムの初期選択とともに提供する。
性能指標の選択は重要であり、最先端のアルゴリズムでさえ改善の余地があり、逐次推定によりサンプリング効率が向上することがわかった。
論文 参考訳（メタデータ） (2021-01-12T18:31:22Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Channel Assignment in Uplink Wireless Communication using Machine
Learning Approach [54.012791474906514]
本稿では,アップリンク無線通信システムにおけるチャネル割り当て問題について検討する。
我々の目標は、整数チャネル割り当て制約を受ける全ユーザの総和率を最大化することです。
計算複雑性が高いため、機械学習アプローチは計算効率のよい解を得るために用いられる。
論文 参考訳（メタデータ） (2020-01-12T15:54:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。