論文の概要: How hard is learning to cut? Trade-offs and sample complexity

• arxiv url: http://arxiv.org/abs/2506.00252v1
• Date: Fri, 30 May 2025 21:41:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-05 01:42:09.168687
• Title: How hard is learning to cut? Trade-offs and sample complexity
• Title（参考訳）: カットの学習はどのくらい難しいか? トレードオフとサンプルの複雑さ
• Authors: Sammy Khalife, Andrea Lodi,
• Abstract要約: 両スコアに有効である新しいサンプル複雑性の低い境界を示す。 我々は、インスタンスをカットにマッピングする幅広いクラスの$mathcalF$に対して、それらのスコアを最小化するためにインスタンスの未知の分布を学習するには、同じクラス関数から学ぶのと同じくらい多くのサンプル(乗法定数まで)が必要であることを示す。 我々の結果は、制限されたカットセット、すなわちSimplex tableauから学習するケースにも及んでいる。
• 参考スコア（独自算出の注目度）: 9.721177829831316
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the recent years, branch-and-cut algorithms have been the target of data-driven approaches designed to enhance the decision making in different phases of the algorithm such as branching, or the choice of cutting planes (cuts). In particular, for cutting plane selection two score functions have been proposed in the literature to evaluate the quality of a cut: branch-and-cut tree size and gap closed. In this paper, we present new sample complexity lower bounds, valid for both scores. We show that for a wide family of classes $\mathcal{F}$ that maps an instance to a cut, learning over an unknown distribution of the instances to minimize those scores requires at least (up to multiplicative constants) as many samples as learning from the same class function $\mathcal{F}$ any generic target function (using square loss). Our results also extend to the case of learning from a restricted set of cuts, namely those from the Simplex tableau. To the best of our knowledge, these constitute the first lower bounds for the learning-to-cut framework. We compare our bounds to known upper bounds in the case of neural networks and show they are nearly tight. We illustrate our results with a graph neural network selection evaluated on set covering and facility location integer programming models and we empirically show that the gap closed score is an effective proxy to minimize the branch-and-cut tree size. Although the gap closed score has been extensively used in the integer programming literature, this is the first principled analysis discussing both scores at the same time both theoretically and computationally.
• Abstract（参考訳）: 近年、分岐や切断といったアルゴリズムの異なるフェーズにおける意思決定を強化するために設計されたデータ駆動型アプローチの標的となっている。 特に, 切削面選択において, 切削の質を評価するために2つのスコア関数が提案されている。 本稿では、両スコアに有効である新しいサンプル複雑性の低い境界について述べる。 インスタンスをカットにマッピングする幅広いクラスの$\mathcal{F}$に対して、それらのスコアを最小化するためにインスタンスの未知の分布を学習するには、同じクラス関数$\mathcal{F}$から学ぶのと同様に、少なくとも(乗法定数まで)多くのサンプルが必要である。 我々の結果は、制限されたカットセット、すなわちSimplex tableauから学習するケースにも及んでいる。 私たちの知る限りでは、これらはラーニング・トゥ・カット・フレームワークの最初の下位境界となっている。 ニューラルネットワークの場合、境界を既知の上限と比較し、ほぼ厳密であることを示す。 本研究の結果は,集合被覆および配置位置整数計画モデルに基づいて評価したグラフニューラルネットワークを用いて記述し,そのギャップ閉スコアが分岐木の大きさを最小化するための有効なプロキシであることを実証的に示す。 ギャップクローズドスコアは整数プログラミング言語の文献で広く使われているが、これは理論的にも計算的にも両スコアを同時に議論する最初の原理的分析である。

関連論文リスト

• Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut [1.4624458429745086]
  本研究は,最適な性能を持つ1つのアルゴリズムを選択するのではなく,インスタンスに基づいてアルゴリズムを選択することが可能となるような設定を考慮し,最近の研究を基礎にしている。 特に、代表的なインスタンスのサンプルが与えられた場合、問題のインスタンスをそのインスタンスの最も適切なアルゴリズムにマッピングするニューラルネットワークを学習する。 言い換えれば、ニューラルネットワークは混合整数最適化インスタンスを入力として取り、そのインスタンスの小さな分岐とカットツリーをもたらす決定を出力する。
  論文  参考訳（メタデータ） (2024-02-04T03:03:27Z)
• Lookback for Learning to Branch [77.32867454769936]
  Bipartite Graph Neural Networks (GNN) は、ディープラーニングに基づくMixed-Integer Linear Program (MILP) の重要コンポーネントであることが示されている。 近年の研究では、分岐とバウンド(B&B)の解法における分岐(可変選択)を置き換える上で、そのようなGNNの有効性が実証されている。
  論文  参考訳（メタデータ） (2022-06-30T02:33:32Z)
• A Unified Framework for Implicit Sinkhorn Differentiation [58.56866763433335]
  暗黙の微分によってシンクホーン層の解析勾配を求めるアルゴリズムを提案する。 特にGPUメモリなどのリソースが不足している場合には,計算効率が向上する。
  論文  参考訳（メタデータ） (2022-05-13T14:45:31Z)
• Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts [88.94020638263467]
  ブランチ・アンド・カット(ブランチ・アンド・カット)として知られる分岐・アンド・バウンドアルゴリズムにおける切断平面の組み入れは、現代の整数計画解法のバックボーンを形成する。 入力整数プログラムに付加される切断平面を定義するパラメータの変化により、アルゴリズムの各ステップがどのように影響を受けるかをピン留めする、分岐切断の新たな構造解析を行う。 この分析の主な応用は、機械学習を用いてブランチ・アンド・カット時にどの切断面を適用するかを決定するためのサンプルの複雑性保証を導出することである。
  論文  参考訳（メタデータ） (2022-04-15T03:32:40Z)
• Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond [98.92725321081994]
  最先端の解法は、根底にある木探索アルゴリズムを高速化するために、無数の切削平面技術を統合している。 本研究は,インスタンス分布に合わせて高い性能のカット選択ポリシーを学習するための最初の保証を証明した。
  論文  参考訳（メタデータ） (2021-06-08T00:57:59Z)
• Graph Partitioning and Sparse Matrix Ordering using Reinforcement Learning [0.13999481573773068]
  本稿では,強化学習とグラフ畳み込みニューラルネットワークに基づくグラフ分割手法を提案する。 提案手法はMETISやスコッチと同様の仕切り品質を実現する。 この方法は、あるクラスのグラフから別のグラフに一般化し、 suitesparse sparse matrix collectionの様々なグラフでうまく機能する。
  論文  参考訳（メタデータ） (2021-04-08T06:54:24Z)
• Learning by Minimizing the Sum of Ranked Range [58.24935359348289]
  本稿では,学習目標を定式化するための一般的なアプローチとして,ランキング範囲(SoRR)の和を紹介した。 ランク付き範囲は、実数の集合のソートされた値の連続的なシーケンスである。 我々は,SoRRフレームワークの最小化のための機械学習における2つの応用,すなわち,バイナリ分類のためのAoRR集約損失とマルチラベル/マルチクラス分類のためのTKML個人損失について検討する。
  論文  参考訳（メタデータ） (2020-10-05T01:58:32Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)

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

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