論文の概要: A Bi-Level Framework for Learning to Solve Combinatorial Optimization on
Graphs
- arxiv url: http://arxiv.org/abs/2106.04927v1
- Date: Wed, 9 Jun 2021 09:18:18 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-10 14:57:13.457831
- Title: A Bi-Level Framework for Learning to Solve Combinatorial Optimization on
Graphs
- Title(参考訳): グラフの組合せ最適化を解くための二段階学習フレームワーク
- Authors: Runzhong Wang, Zhigang Hua, Gan Liu, Jiayi Zhang, Junchi Yan, Feng Qi,
Shuang Yang, Jun Zhou, Xiaokang Yang
- Abstract要約: 本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。
このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
- 参考スコア(独自算出の注目度): 91.07247251502564
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Combinatorial Optimization (CO) has been a long-standing challenging research
topic featured by its NP-hard nature. Traditionally such problems are
approximately solved with heuristic algorithms which are usually fast but may
sacrifice the solution quality. Currently, machine learning for combinatorial
optimization (MLCO) has become a trending research topic, but most existing
MLCO methods treat CO as a single-level optimization by directly learning the
end-to-end solutions, which are hard to scale up and mostly limited by the
capacity of ML models given the high complexity of CO. In this paper, we
propose a hybrid approach to combine the best of the two worlds, in which a
bi-level framework is developed with an upper-level learning method to optimize
the graph (e.g. add, delete or modify edges in a graph), fused with a
lower-level heuristic algorithm solving on the optimized graph. Such a bi-level
approach simplifies the learning on the original hard CO and can effectively
mitigate the demand for model capacity. The experiments and results on several
popular CO problems like Directed Acyclic Graph scheduling, Graph Edit Distance
and Hamiltonian Cycle Problem show its effectiveness over manually designed
heuristics and single-level learning methods.
- Abstract(参考訳): Combinatorial Optimization(CO)は、NPハードな性質を特徴とする長年にわたる挑戦的な研究トピックである。
伝統的にそのような問題は、通常高速だが解の質を犠牲にするヒューリスティックなアルゴリズムでほぼ解決される。
現在、組合せ最適化のための機械学習(MLCO)がトレンドとなっているが、ほとんどの既存のMLCOメソッドは、COの複雑さが高いMLモデルの容量によってほとんど制限される、エンドツーエンドのソリューションを直接学習することで、COを単一レベルの最適化として扱う。
本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。
グラフのエッジの追加、削除、あるいは変更)は、最適化されたグラフ上で解く低レベルのヒューリスティックアルゴリズムと融合する。
このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデル容量の需要を効果的に軽減することができる。
Directed Acyclic Graph scheduling, Graph Edit Distance, Hamiltonian Cycle ProblemなどのCO問題に対する実験と結果は、手作業で設計したヒューリスティックスやシングルレベルの学習方法に対する効果を示している。
関連論文リスト
- Learning Constrained Optimization with Deep Augmented Lagrangian Methods [60.94111369773497]
機械学習(ML)モデルは、制約付き最適化ソルバをエミュレートするために訓練される。
本稿では,MLモデルを用いて2つの解推定を直接予測する手法を提案する。
これにより、双対目的が損失関数であるエンドツーエンドのトレーニングスキームと、双対上昇法をエミュレートした原始的実現可能性への解推定を可能にする。
論文 参考訳(メタデータ) (2024-03-06T04:43:22Z) - Contextual Stochastic Bilevel Optimization [50.36775806399861]
文脈情報と上層変数の期待を最小化する2レベル最適化フレームワークCSBOを導入する。
メタラーニング、パーソナライズドラーニング、エンド・ツー・エンドラーニング、Wassersteinはサイド情報(WDRO-SI)を分散的に最適化している。
論文 参考訳(メタデータ) (2023-10-27T23:24:37Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳(メタデータ) (2023-02-24T18:41:48Z) - Solving Dynamic Graph Problems with Multi-Attention Deep Reinforcement
Learning [1.3534683694551497]
近年,NP-hardグラフ問題に対する解を見つけるためのディープラーニング技術が注目されている。
本稿では,グラフに基づく動的最適化問題の解法を学ぶために,GTA-RL (Graph Temporal Attention with Reinforcement Learning) という新しいアーキテクチャを提案する。
論文 参考訳(メタデータ) (2022-01-13T11:36:05Z) - Effective and efficient structure learning with pruning and model
averaging strategies [9.023722579074734]
本稿では,2つの新しい手法と丘登り探索を組み合わせたBN構造学習アルゴリズムについて述べる。
アルゴリズムは探索空間グラフをプルーニングすることから始まり、プルーニング戦略をプルーニング戦略のアグレッシブバージョンと見なすことができる。
そして、ヒルクライミング探索プロセスで平均化を行い、目的関数を最大化する近隣グラフに移動する。
論文 参考訳(メタデータ) (2021-12-01T10:35:34Z) - Learning Primal Heuristics for Mixed Integer Programs [5.766851255770718]
本研究は,機械学習を用いて効果的な霊長類を自動学習できるかどうかを考察する。
本稿では,最適化問題をグラフとして表現するための新しい手法を提案する。
可変解の予測はB&B法の新たな構成であるProbabilistic Branching with guided Depth-first Searchによって行われる。
論文 参考訳(メタデータ) (2021-07-02T06:46:23Z) - Cogradient Descent for Dependable Learning [64.02052988844301]
双線形最適化問題に対処するために,CoGDアルゴリズムに基づく信頼度の高い学習法を提案する。
CoGDは、ある変数がスパーシティ制約を持つ場合の双線形問題を解くために導入された。
また、特徴と重みの関連を分解するためにも使用できるため、畳み込みニューラルネットワーク(CNN)をより良く訓練するための我々の手法をさらに一般化することができる。
論文 参考訳(メタデータ) (2021-06-20T04:28:20Z) - Cogradient Descent for Bilinear Optimization [124.45816011848096]
双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。
一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。
本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
論文 参考訳(メタデータ) (2020-06-16T13:41:54Z) - Gumbel-softmax-based Optimization: A Simple General Framework for
Optimization Problems on Graphs [5.486093983007419]
本稿では,ディープラーニングフレームワークによって強化された高度な自動微分技術に基づく,シンプルで高速で汎用的なアルゴリズムフレームワークを提案する。
高品質なソリューションは、従来のアプローチに比べてはるかに少ない時間で得られる。
論文 参考訳(メタデータ) (2020-04-14T14:11:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。