論文の概要: A machine learning based algorithm selection method to solve the minimum
cost flow problem
- arxiv url: http://arxiv.org/abs/2210.02195v1
- Date: Mon, 3 Oct 2022 16:06:24 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-06 15:11:19.411721
- Title: A machine learning based algorithm selection method to solve the minimum
cost flow problem
- Title（参考訳）: 最小コストフロー問題を解決するための機械学習に基づくアルゴリズム選択法
- Authors: Philipp Herrmann, Anna Meyer, Stefan Ruzika, Luca E. Sch\"afer and
Fabian von der Warth
- Abstract要約: 複数の機械学習分類器を訓練し、与えられた解の集合の中で最速の予測を行う。
木をベースとしたモデルでは,最小コストのフロー問題の関連構造を適応し,活用することが示されている。
- 参考スコア（独自算出の注目度）: 0.8399688944263843
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The minimum cost flow problem is one of the most studied network optimization
problems and appears in numerous applications. Some efficient algorithms exist
for this problem, which are freely available in the form of libraries or
software packages. It is noticeable that none of these solvers is better than
the other solution methods on all instances. Thus, the question arises whether
the fastest algorithm can be selected for a given instance based on the
characteristics of the instance. To this end, we train several machine learning
classifiers to predict the fastest among a given set of solvers. We accomplish
this by creating a representative data set of 81,000 instances and
characterizing each of these instances by a vector of relevant features. To
achieve better performance, we conduct a grid search to optimize the
hyperparameters of the classifiers. Finally, we evaluate the different
classifiers by means of accuracy. It is shown that tree-based models appear to
adapt and exploit the relevant structures of the minimum-cost flow problem
particularly well on a large number of instances, predicting the fastest solver
with an accuracy of more than 90%.
- Abstract（参考訳）: 最小コストフロー問題は最も研究されたネットワーク最適化問題の1つであり、多くのアプリケーションで見られる。
この問題にはライブラリやソフトウェアパッケージの形で自由に利用できる効率的なアルゴリズムがいくつか存在する。
いずれの解決者も、すべてのインスタンスの他のソリューションメソッドよりも優れているわけではないことは注目に値する。
したがって、インスタンスの特性に基づいて、与えられたインスタンスに対して最速のアルゴリズムを選択できるかどうかという問題が発生する。
この目的のために,複数の機械学習分類器を訓練し,与えられた解法セットの中で最速の予測を行う。
81,000のインスタンスからなる代表的データセットを作成し、それぞれのインスタンスを関連する特徴のベクターで特徴付けることで、これを実現する。
性能向上のために,分類器のハイパーパラメータを最適化するグリッド探索を行う。
最後に,異なる分類器を精度で評価する。
木をベースとしたモデルでは, 最小コストのフロー問題の関連構造を, 特に多数の事例においてよく適用し, 90%以上の精度で最も高速な解法を予測できることが示されている。
関連論文リスト
- Identifying Easy Instances to Improve Efficiency of ML Pipelines for Algorithm-Selection [0.20718016474717196]
本稿では,アルゴリズムの選択を必要とせず,ジェネリストソルバを用いて簡単に解決できる簡単なインスタンスを同定する手法を提案する。
これにより、機能計算に関連する計算予算が削減され、ASパイプライン内の他の場所で使用できるようになる。
論文 参考訳（メタデータ） (2024-06-24T12:25:04Z) - Frugal Algorithm Selection [1.079960007119637]
問題のすべてのインスタンスにうまく機能するアルゴリズムは存在しない。
本研究では、トレーニング対象のトレーニングインスタンスのサブセットを選択することで、このコストを削減する方法について検討する。
我々は,この問題を3つの方法でアプローチする: 能動的学習を用いて予測の不確実性に基づいて決定し, アルゴリズム予測器をタイムアウト予測器で拡張し, 徐々に増加するタイムアウトを用いてトレーニングデータを収集する。
論文 参考訳（メタデータ） (2024-05-17T19:23:30Z) - Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut [1.4624458429745086]
本研究は,最適な性能を持つ1つのアルゴリズムを選択するのではなく,インスタンスに基づいてアルゴリズムを選択することが可能となるような設定を考慮し,最近の研究を基礎にしている。
特に、代表的なインスタンスのサンプルが与えられた場合、問題のインスタンスをそのインスタンスの最も適切なアルゴリズムにマッピングするニューラルネットワークを学習する。
言い換えれば、ニューラルネットワークは混合整数最適化インスタンスを入力として取り、そのインスタンスの小さな分岐とカットツリーをもたらす決定を出力する。
論文 参考訳（メタデータ） (2024-02-04T03:03:27Z) - Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。
SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。
本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。
ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文 参考訳（メタデータ） (2021-09-13T18:10:52Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Run2Survive: A Decision-theoretic Approach to Algorithm Selection based
on Survival Analysis [75.64261155172856]
生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。
我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。
標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
論文 参考訳（メタデータ） (2020-07-06T15:20:17Z) - Approximate learning of high dimensional Bayesian network structures via
pruning of Candidate Parent Sets [6.85316573653194]
正確な学習は、適度または高い複雑性のネットワークには適用できないため、近似解が存在する。
いくつかの近似アルゴリズムは数千の変数を扱うように最適化されているが、それでもそのような高次元構造を学べないかもしれない。
本稿では,高次元問題を対象とした親集合のサイズ決定戦略について検討する。
論文 参考訳（メタデータ） (2020-06-08T17:09:18Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳（メタデータ） (2020-01-29T09:40:58Z) - Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。
最小クラスタ回復誤差率のアルゴリズムを考案する。
適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
論文 参考訳（メタデータ） (2019-10-14T09:18:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。