論文の概要: Learn2Aggregate: Supervised Generation of Chvátal-Gomory Cuts Using Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2409.06559v1
• Date: Tue, 10 Sep 2024 14:41:46 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-11 17:11:30.002140
• Title: Learn2Aggregate: Supervised Generation of Chvátal-Gomory Cuts Using Graph Neural Networks
• Title（参考訳）: Learn2Aggregate: グラフニューラルネットワークを用いたChvátal-Gomoryカットの生成の監視
• Authors: Arnaud Deza, Elias B. Khalil, Zhenan Fan, Zirui Zhou, Yong Zhang,
• Abstract要約: 混合整数線形プログラミング(MILP)におけるChv'atal-Gomory(CG)カットの生成を最適化するための機械学習フレームワークを提案する。 このフレームワークは、CGカット生成におけるアグリゲーションに有用な制約を分類するために、グラフニューラルネットワークを訓練する。 本手法は,標準CG法と同程度の積分性ギャップを約$textittwice$で埋めると同時に,40$%高速に動作させる。
• 参考スコア（独自算出の注目度）: 24.126826148945586
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present $\textit{Learn2Aggregate}$, a machine learning (ML) framework for optimizing the generation of Chv\'atal-Gomory (CG) cuts in mixed integer linear programming (MILP). The framework trains a graph neural network to classify useful constraints for aggregation in CG cut generation. The ML-driven CG separator selectively focuses on a small set of impactful constraints, improving runtimes without compromising the strength of the generated cuts. Key to our approach is the formulation of a constraint classification task which favours sparse aggregation of constraints, consistent with empirical findings. This, in conjunction with a careful constraint labeling scheme and a hybrid of deep learning and feature engineering, results in enhanced CG cut generation across five diverse MILP benchmarks. On the largest test sets, our method closes roughly $\textit{twice}$ as much of the integrality gap as the standard CG method while running 40$% faster. This performance improvement is due to our method eliminating 75% of the constraints prior to aggregation.
• Abstract（参考訳）: 混合整数線形プログラミング(MILP)におけるChv\'atal-Gomory(CG)カットの生成を最適化するための機械学習(ML)フレームワークである$\textit{Learn2Aggregate}$を提示する。 このフレームワークは、CGカット生成におけるアグリゲーションに有用な制約を分類するために、グラフニューラルネットワークを訓練する。 ML駆動のCGセパレータは、小さな影響のある制約セットに選択的にフォーカスし、生成されたカットの強度を損なうことなくランタイムを改善する。 提案手法の鍵となるのは,制約のスパースアグリゲーションを好む制約分類タスクの定式化である。 これにより、5つのMILPベンチマークでCGカット生成が向上する。 最も大きなテストセットでは、40$%高速に実行しながら、標準CGメソッドと同じくらいの積分ギャップを約$\textit{twice}$で閉じます。 この性能改善は,アグリゲーション前の制約の75%を除去する手法が原因である。

関連論文リスト

• Graph Sparsification via Mixture of Graphs [67.40204130771967]
  そこで我々はMixture-of-Graphs (MoG)を導入し、各ノードに対して動的に調整されたプルーニングソリューションを選択する。 MoGには複数のスパシファイアの専門家が組み込まれており、それぞれが独自のスパーシリティレベルとプルーニング基準によって特徴付けられ、各ノードに対して適切な専門家を選択する。 5つのGNNを備えた4つの大規模OGBデータセットと2つのスーパーピクセルデータセットの実験により、MoGはより高い空間レベルのサブグラフを識別することを示した。
  論文  参考訳（メタデータ） (2024-05-23T07:40:21Z)
• Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partition [56.26113670151363]
  グラフ凝縮(Graph condensation)は、大きなグラフを小さいが情報的な凝縮グラフに置き換えるための、データ中心のソリューションである。 既存のGCメソッドは複雑な最適化プロセスに悩まされており、過剰な計算資源を必要とする。 我々は、CGC(Class-partitioned Graph Condensation)と呼ばれるトレーニング不要なGCフレームワークを提案する。 CGCはより効率的な凝縮プロセスで最先端の性能を達成する。
  論文  参考訳（メタデータ） (2024-05-22T14:57:09Z)
• Solving a Class of Cut-Generating Linear Programs via Machine Learning [0.0]
  カット生成線形プログラム(CGLP)は分離オラクルとして重要な役割を担い、混合整数プログラムの可能な領域に対して有効な不等式を生成する。 分岐木と分岐木のノードでデュアルPを実行するのは、ノード候補の数と、ノードが有用な切断平面を許容する事前知識がないため、計算的に煩雑である。 本稿では,分岐木ノードで切断面を生成できるかどうかを判定する,マシンPクラスの最適値を近似する学習に基づく新しいフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-10-30T18:31:52Z)
• CARL-G: Clustering-Accelerated Representation Learning on Graphs [18.763104937800215]
  本稿では,クラスタ検証指標(CVI)にインスパイアされた損失を利用したグラフ表現学習のための新しいクラスタリングベースのフレームワークを提案する。 CARL-Gはクラスタリング法やCVIに適応し,クラスタリング法とCVIの適切な選択により,CARL-Gは4/5データセットのノード分類ベースラインを最大79倍のトレーニングスピードアップで上回ることを示す。
  論文  参考訳（メタデータ） (2023-06-12T08:14:42Z)
• General Cutting Planes for Bound-Propagation-Based Neural Network Verification [144.7290035694459]
  任意の切削平面制約を加えることができるような境界伝搬手順を一般化する。 MIPソルバは、境界プロパゲーションベースの検証器を強化するために高品質な切削面を生成することができる。 本手法は,oval20ベンチマークを完全解き,oval21ベンチマークの2倍のインスタンスを検証できる最初の検証器である。
  論文  参考訳（メタデータ） (2022-08-11T10:31:28Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  本稿では,CGPと呼ばれるグラフの段階的プルーニングフレームワークを動的にGNNに提案する。 LTHに基づく手法とは異なり、提案手法では再学習を必要とせず、計算コストを大幅に削減する。 提案手法は,既存の手法の精度を一致させたり,あるいは超えたりしながら,トレーニングと推論の効率を大幅に向上させる。
  論文  参考訳（メタデータ） (2022-07-18T14:23:31Z)
• A Deep Reinforcement Learning Framework For Column Generation [13.767526395378638]
  カラム生成(CG)は、非常に多数の変数(カラム)を持つ線形プログラムを解くための反復アルゴリズムである。 CGのための最初の強化学習(RL)手法であるRCCGを提案する。 各繰り返しの局所情報に基づいて列をミオプティックに選択する典型的な列選択規則とは異なり、CGを逐次決定問題として扱う。
  論文  参考訳（メタデータ） (2022-06-03T03:58:54Z)
• MGAE: Masked Autoencoders for Self-Supervised Learning on Graphs [55.66953093401889]
  Masked Graph Autoencoder (MGAE) フレームワークは、グラフ構造データの効果的な学習を行う。 自己指導型学習から洞察を得て、私たちはランダムに大量のエッジを隠蔽し、トレーニング中に欠落したエッジを再構築しようとします。
  論文  参考訳（メタデータ） (2022-01-07T16:48:07Z)
• Enhancing Column Generation by a Machine-Learning-Based Pricing Heuristic for Graph Coloring [5.278929511653199]
  カラム生成(CG)は,大規模最適化問題の解決に有効な手法である。 本稿では,高品質な列を効率的に生成できる機械学習価格ヒューリスティックを提案する。
  論文  参考訳（メタデータ） (2021-12-08T03:58:25Z)
• Meta Clustering Learning for Large-scale Unsupervised Person Re-identification [124.54749810371986]
  メタクラスタリング学習(MCL)と呼ばれる「大規模タスクのための小さなデータ」パラダイムを提案する。 MCLは、第1フェーズのトレーニングのためにコンピューティングを節約するためにクラスタリングを介して、未ラベルデータのサブセットを擬似ラベル付けするのみである。 提案手法は計算コストを大幅に削減すると同時に,従来よりも優れた性能を実現している。
  論文  参考訳（メタデータ） (2021-11-19T04:10:18Z)

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

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