論文の概要: Beyond Local Selection: Global Cut Selection for Enhanced Mixed-Integer Programming

• arxiv url: http://arxiv.org/abs/2503.15847v1
• Date: Thu, 20 Mar 2025 04:59:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-21 16:34:30.076169
• Title: Beyond Local Selection: Global Cut Selection for Enhanced Mixed-Integer Programming
• Title（参考訳）: ローカル選択を超えて - 混合整数プログラミングの強化のためのグローバルカット選択
• Authors: Shuli Zeng, Sijia Zhang, Shaoang Li, Feng Wu, Xiang-Yang Li,
• Abstract要約: 混合整数計画法(MIP)では、分枝・分枝・分枝(B&C)アルゴリズムには切断平面が不可欠である。 本稿では,二部グラフを用いて探索木を表現し,グラフニューラルネットワークと強化学習を組み合わせてカット選択戦略を開発するGCSを提案する。 実験により、GCSは従来の学習手法と比較して、合成および大規模現実世界のMIPの解法効率を著しく改善することが示された。
• 参考スコア（独自算出の注目度）: 35.5099165939453
• License:
• Abstract: In mixed-integer programming (MIP) solvers, cutting planes are essential for Branch-and-Cut (B&C) algorithms as they reduce the search space and accelerate the solving process. Traditional methods rely on hard-coded heuristics for cut plane selection but fail to leverage problem-specific structural features. Recent machine learning approaches use neural networks for cut selection but focus narrowly on the efficiency of single-node within the B&C algorithm, without considering the broader contextual information. To address this, we propose Global Cut Selection (GCS), which uses a bipartite graph to represent the search tree and combines graph neural networks with reinforcement learning to develop cut selection strategies. Unlike prior methods, GCS applies cutting planes across all nodes, incorporating richer contextual information. Experiments show GCS significantly improves solving efficiency for synthetic and large-scale real-world MIPs compared to traditional and learning-based methods.
• Abstract（参考訳）: 混合整数計画法(MIP)では、探索空間を減らし、解法を高速化するため、分岐とカット(B&C)アルゴリズムには切断平面が不可欠である。 伝統的な手法は、平面選択のためにハードコードされたヒューリスティックに頼っているが、問題固有の構造的特徴を活用できない。 最近の機械学習アプローチでは、ニューラルネットワークをカットセレクションに使用しているが、より広い文脈情報を考慮せずに、B&Cアルゴリズム内の単一ノードの効率を狭く重視している。 そこで我々は,二部グラフを用いて探索木を表現し,グラフニューラルネットワークと強化学習を組み合わせてカット選択戦略を開発するGCSを提案する。 従来の方法とは異なり、GCSはよりリッチなコンテキスト情報を導入して、すべてのノードにカットプレーンを適用している。 実験により、GCSは従来の学習手法と比較して、合成および大規模現実世界のMIPの解法効率を著しく改善することが示された。

関連論文リスト

• Scalable Neural Network Verification with Branch-and-bound Inferred Cutting Planes [9.061956085975519]
  我々はCOntraint Strengthening (BICCOS) を用いた分枝・分枝型推論切削を開発する。 BICCOSは、VNN-COMP 2024の勝者である$alpha,beta$-CROWNの検証ツールの一部である。
  論文  参考訳（メタデータ） (2024-12-31T00:43:11Z)
• Brain-inspired Chaotic Graph Backpropagation for Large-scale Combinatorial Optimization [3.97492577026225]
  教師なし学習を伴うグラフニューラルネットワーク(GNN)は、効率的な時間複雑性で大規模最適化問題(COP)を解決することができる。 しかし、現在の主流のバックプロパゲーションベースのトレーニングアルゴリズムは、ローカルなミニマに陥りがちである。 カオスグラフバックプロパゲーション(CGBP)というカオス学習アルゴリズムを導入し,カオスだけではなく,高い効率でトレーニングを行う。
  論文  参考訳（メタデータ） (2024-12-13T05:00:57Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。 GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。 我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
  論文  参考訳（メタデータ） (2024-06-05T22:52:27Z)
• Learning Cut Generating Functions for Integer Programming [1.1510009152620668]
  分岐とカットのアルゴリズムは、大規模な整数計画問題の解法である。 近年の進歩は、パラメータ化された族から最適な切断平面を選択するためのデータ駆動アプローチを採用している。 選択したCGFは,特定の分布に対するGMIカットよりも優れることを示す。
  論文  参考訳（メタデータ） (2024-05-22T20:56:34Z)
• Online Network Source Optimization with Graph-Kernel MAB [62.6067511147939]
  大規模ネットワークにおける最適なソース配置をオンラインで学習するためのグラフカーネルマルチアームバンディットアルゴリズムであるGrab-UCBを提案する。 適応グラフ辞書モデルを用いて,ネットワークプロセスを記述する。 我々は、ネットワークパラメータに依存する性能保証を導出し、シーケンシャルな意思決定戦略の学習曲線にさらに影響を及ぼす。
  論文  参考訳（メタデータ） (2023-07-07T15:03:42Z)
• A Comprehensively Improved Hybrid Algorithm for Learning Bayesian Networks: Multiple Compound Memory Erasing [0.0]
  本稿では、新しいハイブリッドアルゴリズムMCME(multiple compound memory erasing)を提案する。 MCMEは、最初の2つの手法の利点を維持し、上記のCIテストの欠点を解消し、方向判別段階におけるスコアリング機能に革新をもたらす。 多くの実験により、MCMEは既存のアルゴリズムよりも優れた、あるいは類似した性能を示している。
  論文  参考訳（メタデータ） (2022-12-05T12:52:07Z)
• Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning [80.45697245527019]
  我々は、最良限の改善をもたらすカットを明示的に目指している欲求選択規則が、カット選択に対して強い決定を下すことを示す。 本研究では,頭頂部の専門家を対象とした模擬学習のための新しいニューラルアーキテクチャ(NeuralCut)を提案する。
  論文  参考訳（メタデータ） (2022-06-27T16:07:27Z)
• Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts [88.94020638263467]
  ブランチ・アンド・カット(ブランチ・アンド・カット)として知られる分岐・アンド・バウンドアルゴリズムにおける切断平面の組み入れは、現代の整数計画解法のバックボーンを形成する。 入力整数プログラムに付加される切断平面を定義するパラメータの変化により、アルゴリズムの各ステップがどのように影響を受けるかをピン留めする、分岐切断の新たな構造解析を行う。 この分析の主な応用は、機械学習を用いてブランチ・アンド・カット時にどの切断面を適用するかを決定するためのサンプルの複雑性保証を導出することである。
  論文  参考訳（メタデータ） (2022-04-15T03:32:40Z)
• Attentive CutMix: An Enhanced Data Augmentation Approach for Deep Learning Based Image Classification [58.20132466198622]
  そこで我々は,CutMixに基づく自然拡張拡張戦略であるAttentive CutMixを提案する。 各トレーニングイテレーションにおいて、特徴抽出器から中間注意マップに基づいて最も記述性の高い領域を選択する。 提案手法は単純かつ有効であり,実装が容易であり,ベースラインを大幅に向上させることができる。
  論文  参考訳（メタデータ） (2020-03-29T15:01:05Z)

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

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