論文の概要: Improved Learning Bounds for Branch-and-Cut

• arxiv url: http://arxiv.org/abs/2111.11207v1
• Date: Thu, 18 Nov 2021 04:07:29 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-26 11:53:54.188055
• Title: Improved Learning Bounds for Branch-and-Cut
• Title（参考訳）: ブランチ・アンド・カットにおける学習境界の改善
• Authors: Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, Ellen Vitercik
• Abstract要約: 分岐とカットは整数プログラムの解法として最も広く使われているアルゴリズムである。 ますます人気のあるアプローチは、機械学習を使ってパラメータをチューニングすることだ。 本稿では,本手法のサンプル保証について述べる。
• 参考スコア（独自算出の注目度）: 98.92725321081994
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Branch-and-cut is the most widely used algorithm for solving integer programs, employed by commercial solvers like CPLEX and Gurobi. Branch-and-cut has a wide variety of tunable parameters that have a huge impact on the size of the search tree that it builds, but are challenging to tune by hand. An increasingly popular approach is to use machine learning to tune these parameters: using a training set of integer programs from the application domain at hand, the goal is to find a configuration with strong predicted performance on future, unseen integer programs from the same domain. If the training set is too small, a configuration may have good performance over the training set but poor performance on future integer programs. In this paper, we prove sample complexity guarantees for this procedure, which bound how large the training set should be to ensure that for any configuration, its average performance over the training set is close to its expected future performance. Our guarantees apply to parameters that control the most important aspects of branch-and-cut: node selection, branching constraint selection, and cutting plane selection, and are sharper and more general than those found in prior research.
• Abstract（参考訳）: ブランチ・アンド・カット(英: Branch-and-cut)は、CPLEX や Gurobi といった商用の解法を用いて、整数プログラムを解くアルゴリズムである。 ブランチ・アンド・カットは様々な変更可能なパラメータを持ち、それが構築する検索ツリーのサイズに大きな影響を与えるが、手動でチューニングすることは難しい。 マシンラーニングを使用してこれらのパラメータをチューニングするアプローチがますます普及している。アプリケーションドメインから手元にある整数プログラムのトレーニングセットを使用することで、将来予想されるパフォーマンスが、同じドメインから見当たらない整数プログラムの強い設定を見つけることが目標だ。 トレーニングセットが小さすぎる場合、構成はトレーニングセットよりも優れたパフォーマンスを持つが、将来の整数プログラムではパフォーマンスが劣る。 本稿では,任意の構成において,トレーニングセットに対する平均性能が将来期待される性能にほぼ近いことを保証するために,トレーニングセットがどの程度の大きさであるべきかを境界として,この手順のサンプル複雑性を保証する。 我々の保証は、ノードの選択、分岐制約の選択、平面の選択といった、分岐とカットの最も重要な側面を制御するパラメータに適用され、以前の研究よりも鋭く、より一般的なものである。

関連論文リスト

• Learning Cut Generating Functions for Integer Programming [1.1510009152620668]
  分岐とカットのアルゴリズムは、大規模な整数計画問題の解法である。 近年の進歩は、パラメータ化された族から最適な切断平面を選択するためのデータ駆動アプローチを採用している。 選択したCGFは,特定の分布に対するGMIカットよりも優れることを示す。
  論文  参考訳（メタデータ） (2024-05-22T20:56:34Z)
• Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning [39.40838358438744]
  線形プログラム(ILP)は、多数の最適化問題のモデリングと解決のための強力なツールである。 アルゴリズムとしてLarge Neighborhood Search (LNS)は、ブランチやバウンドよりも高速に、ILPの高品質なソリューションを見つけることができる。 本稿では,メトリクスによって測定された複数のILPベンチマークに対して,最先端のリアルタイム性能を実現する新しいアプローチCL-LNSを提案する。
  論文  参考訳（メタデータ） (2023-02-03T07:15:37Z)
• Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts [88.94020638263467]
  ブランチ・アンド・カット(ブランチ・アンド・カット)として知られる分岐・アンド・バウンドアルゴリズムにおける切断平面の組み入れは、現代の整数計画解法のバックボーンを形成する。 入力整数プログラムに付加される切断平面を定義するパラメータの変化により、アルゴリズムの各ステップがどのように影響を受けるかをピン留めする、分岐切断の新たな構造解析を行う。 この分析の主な応用は、機械学習を用いてブランチ・アンド・カット時にどの切断面を適用するかを決定するためのサンプルの複雑性保証を導出することである。
  論文  参考訳（メタデータ） (2022-04-15T03:32:40Z)
• AdaGrid: Adaptive Grid Search for Link Prediction Training Objective [58.79804082133998]
  トレーニングの目的は、モデルの性能と一般化能力に決定的に影響を及ぼす。 本稿では,訓練中にエッジメッセージの比率を動的に調整する適応グリッド探索(AdaGrid)を提案する。 AdaGridは、完全検索の9倍の時間効率を保ちながら、モデルの性能を1.9%まで向上させることができることを示す。
  論文  参考訳（メタデータ） (2022-03-30T09:24:17Z)
• Adaptive Cut Selection in Mixed-Integer Linear Programming [0.294944680995069]
  カットセレクション(英: cut selection)は、現代の全ての混合整数線形計画解法で用いられるサブルーチンである。 混合整数線形プログラムのファミリーを、無限に多くのファミリーワイド有効なカットと共に提示する。 特定のカット選択規則について、パラメータ空間の有限グリッド探索は常に全てのパラメータ値を見逃すことを示す。
  論文  参考訳（メタデータ） (2022-02-22T15:07:33Z)
• Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond [98.92725321081994]
  最先端の解法は、根底にある木探索アルゴリズムを高速化するために、無数の切削平面技術を統合している。 本研究は,インスタンス分布に合わせて高い性能のカット選択ポリシーを学習するための最初の保証を証明した。
  論文  参考訳（メタデータ） (2021-06-08T00:57:59Z)
• Learning to Select Cuts for Efficient Mixed-Integer Programming [46.60355046375608]
  複数インスタンス学習の設定において,データ駆動型で一般化可能なカット選択手法であるカットランキングを提案する。 カットランキングは、大規模MIPのための産業用解決器に展開されている。 解法の平均スピードアップ比は12.42%に達し、解の精度を損なうことなく製造された。
  論文  参考訳（メタデータ） (2021-05-28T07:48:34Z)
• Generalization in portfolio-based algorithm selection [97.74604695303285]
  ポートフォリオベースのアルゴリズム選択に関する最初の証明可能な保証を提供する。 ポートフォリオが大きければ、非常に単純なアルゴリズムセレクタであっても、過剰適合は避けられないことを示す。
  論文  参考訳（メタデータ） (2020-12-24T16:33:17Z)
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
  トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。 この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。 我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
  論文  参考訳（メタデータ） (2020-06-21T15:32:21Z)

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

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