論文の概要: Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond

• arxiv url: http://arxiv.org/abs/2106.04033v1
• Date: Tue, 8 Jun 2021 00:57:59 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-09 16:17:13.239015
• Title: Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond
• Title（参考訳）: 木探索構成のサンプル複雑性:切削面とその周辺
• Authors: Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, Ellen Vitercik
• Abstract要約: 最先端の解法は、根底にある木探索アルゴリズムを高速化するために、無数の切削平面技術を統合している。 本研究は,インスタンス分布に合わせて高い性能のカット選択ポリシーを学習するための最初の保証を証明した。
• 参考スコア（独自算出の注目度）: 98.92725321081994
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Cutting-plane methods have enabled remarkable successes in integer programming over the last few decades. State-of-the-art solvers integrate a myriad of cutting-plane techniques to speed up the underlying tree-search algorithm used to find optimal solutions. In this paper we prove the first guarantees for learning high-performing cut-selection policies tailored to the instance distribution at hand using samples. We first bound the sample complexity of learning cutting planes from the canonical family of Chv\'atal-Gomory cuts. Our bounds handle any number of waves of any number of cuts and are fine tuned to the magnitudes of the constraint coefficients. Next, we prove sample complexity bounds for more sophisticated cut selection policies that use a combination of scoring rules to choose from a family of cuts. Finally, beyond the realm of cutting planes for integer programming, we develop a general abstraction of tree search that captures key components such as node selection and variable selection. For this abstraction, we bound the sample complexity of learning a good policy for building the search tree.
• Abstract（参考訳）: 切断平面法は、過去数十年間、整数計画において顕著な成功をもたらしてきた。 最先端の解法は、多くの切断平面技術を統合し、最適解を見つけるために使用される木探索アルゴリズムを高速化する。 本稿では,手元のインスタンス分布に合わせた高パフォーマンスなカット選択ポリシーを学習するための最初の保証を,サンプルを用いて証明する。 まず, chv\'atal-gomory 切断の正準族から切削面を学習するサンプルの複雑さを限定した。 我々の境界は、任意の数のカットの任意の数の波動を扱い、制約係数の大きさに微調整される。 次に、より洗練されたカット選択ポリシーのためのサンプル複雑性境界を証明し、スコアリングルールを組み合わせてカットのファミリーから選択する。 最後に、整数計画のための切断平面の領域を超えて、ノード選択や変数選択といったキーコンポーネントをキャプチャする木探索の一般的な抽象化を開発する。 この抽象化のために、探索木を構築するための良いポリシーを学ぶためのサンプルの複雑さを束縛する。

関連論文リスト

• Learning Cut Generating Functions for Integer Programming [1.1510009152620668]
  分岐とカットのアルゴリズムは、大規模な整数計画問題の解法である。 近年の進歩は、パラメータ化された族から最適な切断平面を選択するためのデータ駆動アプローチを採用している。 選択したCGFは,特定の分布に対するGMIカットよりも優れることを示す。
  論文  参考訳（メタデータ） (2024-05-22T20:56:34Z)
• Learning bounded-degree polytrees with known skeleton [15.137372516678143]
  有界次数ポリツリーの効率的な適切な学習のための有限サンプル保証を確立する。 基礎となる無向グラフが知られているとき、d$-polytreesを時間で学習し、任意の有界$d$のサンプル複雑性を学習する効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2023-10-10T06:03:51Z)
• TreeDQN: Learning to minimize Branch-and-Bound tree [78.52895577861327]
  Branch-and-Boundは、Mixed Linear Programsという形で最適化タスクを解決するための便利なアプローチである。 解法の効率は、分割する変数を選択するのに使用される分岐に依存する。 分岐を効率的に学習できる強化学習法を提案する。
  論文  参考訳（メタデータ） (2023-06-09T14:01:26Z)
• Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts [88.94020638263467]
  ブランチ・アンド・カット(ブランチ・アンド・カット)として知られる分岐・アンド・バウンドアルゴリズムにおける切断平面の組み入れは、現代の整数計画解法のバックボーンを形成する。 入力整数プログラムに付加される切断平面を定義するパラメータの変化により、アルゴリズムの各ステップがどのように影響を受けるかをピン留めする、分岐切断の新たな構造解析を行う。 この分析の主な応用は、機械学習を用いてブランチ・アンド・カット時にどの切断面を適用するかを決定するためのサンプルの複雑性保証を導出することである。
  論文  参考訳（メタデータ） (2022-04-15T03:32:40Z)
• Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks [61.2383572324176]
  本稿では,データマイニングにおける頻繁なアイテムセットマイニングの概念をよく知られたメメティック検索フレームワークに統合する,頻繁なアイテムセット駆動探索手法を提案する。 頻繁なアイテムセット組換え演算子を反復的に使用して、高品質なソリューションで頻繁に発生するアイテムセットに基づいた有望な子孫ソリューションを生成する。 特に、29個の新しい上界を発見し、以前の18個の最もよく知られた境界と一致する。
  論文  参考訳（メタデータ） (2022-01-18T11:16:40Z)
• Improved Learning Bounds for Branch-and-Cut [98.92725321081994]
  分岐とカットは整数プログラムの解法として最も広く使われているアルゴリズムである。 ますます人気のあるアプローチは、機械学習を使ってパラメータをチューニングすることだ。 本稿では,本手法のサンプル保証について述べる。
  論文  参考訳（メタデータ） (2021-11-18T04:07:29Z)
• Learning to Select Cuts for Efficient Mixed-Integer Programming [46.60355046375608]
  複数インスタンス学習の設定において,データ駆動型で一般化可能なカット選択手法であるカットランキングを提案する。 カットランキングは、大規模MIPのための産業用解決器に展開されている。 解法の平均スピードアップ比は12.42%に達し、解の精度を損なうことなく製造された。
  論文  参考訳（メタデータ） (2021-05-28T07:48:34Z)

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

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