論文の概要: Search Strategy Generation for Branch and Bound Using Genetic Programming

• arxiv url: http://arxiv.org/abs/2412.09444v2
• Date: Tue, 17 Dec 2024 13:24:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-18 13:57:57.636931
• Title: Search Strategy Generation for Branch and Bound Using Genetic Programming
• Title（参考訳）: 遺伝的プログラミングを用いた分岐境界探索戦略生成
• Authors: Gwen Maudet, Grégoire Danoy,
• Abstract要約: GP2S(Genetic Programming for Search Strategy)は,B&B検索戦略を自動生成する機械学習手法である。 我々は、SCIPソルバの標準手法、最近のグラフニューラルネットワークに基づく手法、手工芸品との比較を行った。 我々の手法は最良基準よりも2%遅く、SCIPを一貫して上回り、平均速度は11.3%に達する。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Branch-and-Bound (B\&B) is an exact method in integer programming that recursively divides the search space into a tree. During the resolution process, determining the next subproblem to explore within the tree-known as the search strategy-is crucial. Hand-crafted heuristics are commonly used, but none are effective over all problem classes. Recent approaches utilizing neural networks claim to make more intelligent decisions but are computationally expensive. In this paper, we introduce GP2S (Genetic Programming for Search Strategy), a novel machine learning approach that automatically generates a B\&B search strategy heuristic, aiming to make intelligent decisions while being computationally lightweight. We define a policy as a function that evaluates the quality of a B\&B node by combining features from the node and the problem; the search strategy policy is then defined by a best-first search based on this node ranking. The policy space is explored using a genetic programming algorithm, and the policy that achieves the best performance on a training set is selected. We compare our approach with the standard method of the SCIP solver, a recent graph neural network-based method, and handcrafted heuristics. Our first evaluation includes three types of primal hard problems, tested on instances similar to the training set and on larger instances. Our method is at most 2\% slower than the best baseline and consistently outperforms SCIP, achieving an average speedup of 11.3\%. Additionally, GP2S is tested on the MIPLIB 2017 dataset, generating multiple heuristics from different subsets of instances. It exceeds SCIP's average performance in 7 out of 10 cases across 15 times more instances and under a time limit 15 times longer, with some GP2S methods leading on most experiments in terms of the number of feasible solutions or optimality gap.
• Abstract（参考訳）: ブランチ・アンド・バウンド(ブランチ・アンド・バウンド、英: Branch-and-Bound、B\&B)は、探索空間を木に再帰的に分割する整数計画法である。 解決の過程では、探索戦略として知られる木の中で探索する次のサブプロブレムを決定することが不可欠である。 手作りのヒューリスティックは一般的に使われているが、すべての問題クラスに対して有効ではない。 ニューラルネットワークを利用した最近のアプローチは、よりインテリジェントな決定をするが、計算コストが高いと主張している。 本稿では,B&B検索戦略をヒューリスティックに自動生成する新しい機械学習手法であるGP2S(Genetic Programming for Search Strategy)を紹介する。 本稿では,B\&Bノードの品質を評価する関数として,B\&Bノードの特徴と問題を組み合わせ,このノードのランク付けに基づく最良検索によって検索戦略ポリシーを定義する。 遺伝的プログラミングアルゴリズムを用いてポリシー空間を探索し、トレーニングセット上で最高のパフォーマンスを達成するポリシーを選択する。 我々は、SCIPソルバの標準的な手法、最近のグラフニューラルネットワークに基づく手法、手作りヒューリスティックスと比較した。 最初の評価では、トレーニングセットと同様のインスタンスでテストし、より大きなインスタンスでテストする3種類の原始的難しい問題が含まれています。 提案手法は, 最良ベースラインよりも少なくとも2\%遅く, SCIPより一貫して優れ, 平均速度は11.3\%である。 さらに、GP2SはMIPLIB 2017データセットでテストされており、インスタンスの異なるサブセットから複数のヒューリスティックを生成する。 SCIPの平均性能は15倍のインスタンスに対して10ケース中7ケースで、タイムリミットでは15倍、GP2Sメソッドでは実現可能な解数や最適性ギャップの点でほとんどの実験に導かれる。

関連論文リスト

• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• Leveraging Experience in Lazy Search [37.75223642505171]
  遅延グラフ探索アルゴリズムは、エッジ評価が計算ボトルネックとなる動き計画問題の解法において効率的である。 我々は,この問題を探索問題の状態に関するマルコフ決定過程 (MDP) として定式化する。 我々は,訓練中にMDPを解くことができる分子セレクタを計算可能であることを示す。
  論文  参考訳（メタデータ） (2021-10-10T00:46:44Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Exploiting Learned Policies in Focal Search [0.49723239539321284]
  政策学習を有界-準最適探索アルゴリズムに統合する方法を示す。 提案手法は3つのベンチマーク領域を対象とし,15-puzzleでは150万のサンプルを用いて学習したニューラルネットワークを用いて解析を行った。 本稿では,emphDiscrepancy Focal Searchにおいて,対応する経路が最適経路の接頭辞である確率の近似を最大化するノードを拡大し,実行時および解の質の観点から最もよい結果が得られることを示す。
  論文  参考訳（メタデータ） (2021-04-21T13:50:40Z)
• 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)
• A Study of Learning Search Approximation in Mixed Integer Branch and Bound: Node Selection in SCIP [2.528056693920671]
  このようなポリシーを2つの設定で学習するオフライン手法を提案する。 1つの設定は、プリンギング中に子供のセレクタに対応し、もう1つはダイビングに似ている。 5つのMIPデータセットの実証結果は、我々のノード選択ポリシーが、文献における最先端の先例よりもはるかに高速な解決につながることを示している。
  論文  参考訳（メタデータ） (2020-07-08T08:12:44Z)
• Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
  生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。 我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。 標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
  論文  参考訳（メタデータ） (2020-07-06T15:20:17Z)
• Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
  基本アルゴリズムを選択できるメタアルゴリズムを開発した。 基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
  論文  参考訳（メタデータ） (2020-03-03T18:46:34Z)

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

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