論文の概要: Learning to Branch in Combinatorial Optimization with Graph Pointer Networks

• arxiv url: http://arxiv.org/abs/2307.01434v1
• Date: Tue, 4 Jul 2023 01:56:07 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-06 18:37:11.789641
• Title: Learning to Branch in Combinatorial Optimization with Graph Pointer Networks
• Title（参考訳）: グラフポインタネットワークによる組合せ最適化の分岐学習
• Authors: Rui Wang, Zhiming Zhou, Tao Zhang, Ling Wang, Xin Xu, Xiangke Liao, Kaiwen Li
• Abstract要約: 本稿では,分岐境界における変数選択ポリシーを学習するためのグラフポインターネットワークモデルを提案する。 グラフニューラルネットワークとポインタ機構を組み合わせたモデルでは,解法状態から分岐変数決定への効果的マッピングが可能である。
• 参考スコア（独自算出の注目度）: 17.729352126574902
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Branch-and-bound is a typical way to solve combinatorial optimization problems. This paper proposes a graph pointer network model for learning the variable selection policy in the branch-and-bound. We extract the graph features, global features and historical features to represent the solver state. The proposed model, which combines the graph neural network and the pointer mechanism, can effectively map from the solver state to the branching variable decisions. The model is trained to imitate the classic strong branching expert rule by a designed top-k Kullback-Leibler divergence loss function. Experiments on a series of benchmark problems demonstrate that the proposed approach significantly outperforms the widely used expert-designed branching rules. Our approach also outperforms the state-of-the-art machine-learning-based branch-and-bound methods in terms of solving speed and search tree size on all the test instances. In addition, the model can generalize to unseen instances and scale to larger instances.
• Abstract（参考訳）: 分岐とバウンドは組合せ最適化問題を解決する典型的な方法である。 本稿では,分岐境界における変数選択ポリシーを学習するためのグラフポインターネットワークモデルを提案する。 解法状態を表すために,グラフの特徴,グローバル特徴,歴史的特徴を抽出する。 グラフニューラルネットワークとポインタ機構を組み合わせた提案モデルは, 解法状態から分岐変数決定へ効果的にマッピングすることができる。 このモデルは、設計されたトップkのKullback-Leibler分散損失関数によって古典的な強い分岐エキスパートルールを模倣するように訓練されている。 一連のベンチマーク問題に関する実験は、提案手法が広く使われている専門家設計の分岐規則よりも大幅に優れていることを示した。 また,本手法は,最先端の機械学習に基づくブランチ・アンド・バウンド手法よりも,すべてのテストインスタンスにおける高速化と木の大きさの探索に優れる。 さらに、モデルは見えないインスタンスに一般化し、より大きなインスタンスにスケールすることができる。

関連論文リスト

• A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimization [12.016449555335976]
  我々はNP-hard Maximum Cut問題に特化しているオープンソースのベンチマークスイートMaxCut-Benchを提案する。 我々は、このベンチマークを用いて、いくつかの一般的な学習ベースのアプローチの結果を体系的に相関づけたり、再現したりしようとする。 以上の結果から, 学習者の数人は, ナイーブな欲求アルゴリズムを上回り得ず, タブサーチを一貫して上回っているのはそのうちの1人だけであることが示唆された。
  論文  参考訳（メタデータ） (2024-06-14T19:44:23Z)
• Graph Convolutional Branch and Bound [1.8966938152549224]
  本稿では,最適化パイプラインにおけるディープラーニングモデルの有効性を示す。 この文脈では、ニューラルネットワークを利用して、価値ある情報を素早く取得することができる。
  論文  参考訳（メタデータ） (2024-06-05T09:42:43Z)
• Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
  グラフマッチングはコンピュータビジョンやパターン認識において一般的に用いられる技法である。 最近のデータ駆動型アプローチは、グラフマッチングの精度を著しく改善した。 データ駆動手法と従来の手法の利点を組み合わせたグラフニューラルネットワーク(GNN)に基づくアプローチを提案する。
  論文  参考訳（メタデータ） (2024-03-11T06:34:05Z)
• Optimizing Neural Networks with Gradient Lexicase Selection [7.554281369517276]
  機械学習で集約されたパフォーマンス測定を使用することの潜在的な欠点は、トレーニングケースのより高いエラーを、他のケースの低いエラーに対する妥協として受け入れることを学ぶことができることである。 本稿では、勾配降下と語彙選択を進化的に組み合わせた最適化フレームワークであるグラディエント・レキシケース選択を提案する。 実験により,提案手法は,広く使用されているディープニューラルネットワークアーキテクチャの一般化性能を向上することを示した。
  論文  参考訳（メタデータ） (2023-12-19T21:21:25Z)
• Discrete Graph Auto-Encoder [52.50288418639075]
  離散グラフオートエンコーダ(DGAE)という新しいフレームワークを導入する。 まず、置換同変オートエンコーダを用いてグラフを離散潜在ノード表現の集合に変換する。 2番目のステップでは、離散潜在表現の集合をソートし、特別に設計された自己回帰モデルを用いてそれらの分布を学習する。
  論文  参考訳（メタデータ） (2023-06-13T12:40:39Z)
• Learning Branching Heuristics from Graph Neural Networks [1.4660170768702356]
  まず,確率論的手法を用いて設計した新しいグラフニューラルネットワーク(GNN)モデルを提案する。 我々のアプローチは、AIで使用される古典的なバックトラッキングアルゴリズムの強化にGNNを適用する新しい方法を導入する。
  論文  参考訳（メタデータ） (2022-11-26T00:01:01Z)
• Equivariance with Learned Canonicalization Functions [77.32483958400282]
  正規化を行うために小さなニューラルネットワークを学習することは、事前定義を使用することよりも優れていることを示す。 実験の結果,正準化関数の学習は多くのタスクで同変関数を学習する既存の手法と競合することがわかった。
  論文  参考訳（メタデータ） (2022-11-11T21:58:15Z)
• Learning to Compare Nodes in Branch and Bound with Graph Neural Networks [5.08128537391027]
  整数プログラミングにおける分岐とバウンドのアプローチは、次の探索のために空間の一部を順序付けする必要がある。 本稿では,この問題に対処する新たなシアムグラフニューラルネットワークモデルを提案し,ノードを属性付き二部グラフとして表現する。 本手法は,ノードがランクに応じて探索される平易なフレームワークのインスタンスを解くことで評価する。
  論文  参考訳（メタデータ） (2022-10-30T19:38:23Z)
• Scaling Structured Inference with Randomization [64.18063627155128]
  本稿では、構造化されたモデルを数万の潜在状態に拡張するためにランダム化された動的プログラミング(RDP)のファミリを提案する。 我々の手法は古典的DPベースの推論に広く適用できる。 また、自動微分とも互換性があり、ニューラルネットワークとシームレスに統合できる。
  論文  参考訳（メタデータ） (2021-12-07T11:26:41Z)
• Temporal Graph Network Embedding with Causal Anonymous Walks Representations [54.05212871508062]
  本稿では,時間グラフネットワークに基づく動的ネットワーク表現学習のための新しいアプローチを提案する。 評価のために、時間的ネットワーク埋め込みの評価のためのベンチマークパイプラインを提供する。 欧州の大手銀行が提供した実世界のダウンストリームグラフ機械学習タスクにおいて、我々のモデルの適用性と優れた性能を示す。
  論文  参考訳（メタデータ） (2021-08-19T15:39:52Z)
• Gone Fishing: Neural Active Learning with Fisher Embeddings [55.08537975896764]
  ディープニューラルネットワークと互換性のあるアクティブな学習アルゴリズムの必要性が高まっている。 本稿では,ニューラルネットワークのための抽出可能かつ高性能な能動学習アルゴリズムBAITを紹介する。
  論文  参考訳（メタデータ） (2021-06-17T17:26:31Z)

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

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