論文の概要: Learning-based Directed Graph Abstraction of Combinatorial Spaces for Order-Preserving Search in Mixed-Combinatorial Nonlinear Optimization

• arxiv url: http://arxiv.org/abs/2606.01425v1
• Date: Sun, 31 May 2026 19:54:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-02 21:34:29.696182
• Title: Learning-based Directed Graph Abstraction of Combinatorial Spaces for Order-Preserving Search in Mixed-Combinatorial Nonlinear Optimization
• Title（参考訳）: 混合組合せ非線形最適化における順序保存探索のための組合せ空間の学習によるグラフ抽象化
• Authors: Gishnu Madhu, Feng Liu, Souma Chowdhury,
• Abstract要約: 混合組合せ非線形プログラミング(MCNLP)の問題は、多くのエンジニアリング設計と計画アプリケーションで発生する。 本稿では,グラフニューラルネットワーク(GNN)を用いた空間上の探索経路学習を目的としたロボット計画領域の開発について述べる。 より具体的には、結合の非直交完全連結グラフから写像を学習することにより、空間の第一種構造的抽象化について述べる。
• 参考スコア（独自算出の注目度）: 7.921235364449131
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Mixed-combinatorial nonlinear programming (MCNLP) problems arise in many engineering design and planning applications, e.g., due to categorical, component, and geometric design choices, as well as joint task and motion planning. Traditional representations of combinatorial spaces, such as integer or binary encoding, often introduce spurious relations, increase dimensionality, and require additional compatibility constraints. Instead, this paper draws on recent developments in robot planning and vehicle/network routing domains that aim to learn search heuristics over combinatorial spaces using graph neural networks (GNNs). More specifically, this paper presents a first-of-its-kind structured abstraction of the combinatorial space by learning a mapping from an undirected fully connected graph of combinations to a directed graph indicating improvement directions using an Edge Field Graph Network (EFGN). To demonstrate the utility of this new way of abstracting the combinatorial space in solving MCNLPs, we adopt a recent optimization framework that purely searches over the non-combinatorial (e.g., continuous) variables and retrieves the best-suited combination for each candidate design by using the abstraction model, akin to a recommender system. The presented direction-aware abstraction model provides a potentially more scalable and interpretable retrieval of combinations compared to the original recommendation system in that framework. For evaluation, the proposed method is integrated with a well-known particle swarm optimization and genetic algorithm solvers on three benchmark nonlinear problems with varying numbers of combinations and variables. Compared to baseline solvers using indexified combinations, the GNN-based recommender consistently achieves better mean optimum values and robustness across multiple runs.
• Abstract（参考訳）: 混合組合せ非線形プログラミング(MCNLP)問題は多くの工学設計や計画アプリケーションで発生し、例えば、分類的、成分的、幾何学的設計の選択や、共同作業や運動計画が原因である。 整数やバイナリエンコーディングのような伝統的な組合せ空間の表現は、しばしば急激な関係を導入し、次元性を高め、追加の互換性の制約を必要とする。 そこで本研究では,グラフニューラルネットワーク(GNN)を用いた組合せ空間における探索ヒューリスティックス学習を目的とした,ロボット計画と車両/ネットワークルーティング領域の最近の発展について述べる。 具体的には、エッジフィールドグラフネットワーク(EFGN)を用いて、組合せの非方向の完全連結グラフから、改善方向を示す有向グラフへの写像を学習することにより、組合せ空間の第一種構造的抽象化を提案する。 MCNLPを解く上での組合せ空間を抽象化するこの新しい手法の有用性を実証するために,非組合せ変数(例えば連続変数)を純粋に探索し,抽象モデルを用いて各候補設計に最適な組合せを検索する,最近の最適化フレームワークを採用する。 提案された方向対応抽象化モデルは、そのフレームワークのオリジナルのレコメンデーションシステムと比較して、潜在的にスケーラブルで解釈可能な組み合わせの検索を提供する。 評価のために,提案手法はよく知られた粒子群最適化と遺伝的アルゴリズムの3つのベンチマーク非線形問題に対する遺伝的アルゴリズムの解法と組み合わせた。 インデックス化された組み合わせを使用するベースラインソルバと比較して、GNNベースのレコメンデータは、複数の実行において最適な平均値とロバスト性を一貫して達成する。

関連論文リスト

• Designing Active Tether-Net Systems for Space Debris Capture with Graph-Learning-Aided Mixed-Combinatorial Optimization [8.22669567374754]
  本稿では,テザネットシステムの複雑で制約付き非線形最適化問題について検討する。 グラフニューラルネットワーク(GNN)は、グラフ内のノードとして表される(上記の)候補の組み合わせと、入力として与えられる候補の連続変数ベクトル部分とをスコアするために訓練される。 その結果、MCNLP最適化はNLPに還元され、標準解法を用いて解ける。
  論文  参考訳（メタデータ） (2026-05-27T19:19:42Z)
• Bootstrap Learning for Combinatorial Graph Alignment with Sequential GNNs [8.49454123392354]
  グラフニューラルネットワーク(GNN)は、ニューラルネットワークの従来の最適化手法よりも優れており、その実践的影響を制限している。 本稿では,構造情報のみを用いて,グラフアライメント問題に対する新しい連鎖手法を提案する。 提案手法は,従来のネットワークが生成した類似度行列を反復的に洗練することを学ぶ,一連のGNNを訓練する。 各GNNは、以前のイテレーションからノードアライメントの品質に関する個別のランキング情報を組み込むことで、部分的なソリューションを改善する。
  論文  参考訳（メタデータ） (2025-10-03T15:17:00Z)
• Preference-Based Gradient Estimation for ML-Guided Approximate Combinatorial Optimization [15.102119312523696]
  組合せ最適化(CO)の問題は、医学、物流、製造など幅広い領域で発生する。 本研究では,CO の非学習近似アルゴリズムを学習ベースで拡張する手法を提案する。 本手法は,近似アルゴリズムをブラックボックスとして扱う新しい勾配推定法を用いて,自己教師付き方式でエンドツーエンドに学習する。
  論文  参考訳（メタデータ） (2025-02-26T18:23:07Z)
• 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)
• Random Aggregate Beamforming for Over-the-Air Federated Learning in Large-Scale Networks [66.18765335695414]
  本稿では,アグリゲーションエラーを最小限に抑え,選択したデバイス数を最大化する目的で,共同装置の選択とアグリゲーションビームフォーミング設計について検討する。 コスト効率のよい方法でこの問題に取り組むために,ランダムな集合ビームフォーミング方式を提案する。 また, 得られた集計誤差と, デバイス数が大きい場合に選択したデバイス数についても解析を行った。
  論文  参考訳（メタデータ） (2024-02-20T23:59:45Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  木アンサンブルはアルゴリズムチューニングやニューラルアーキテクチャ検索といったブラックボックス最適化タスクに適している。 ブラックボックス最適化にツリーアンサンブルを使うことの2つのよく知られた課題は、探索のためのモデル不確実性を効果的に定量化し、また、 (ii) ピースワイドな定値取得関数を最適化することである。 我々のフレームワークは、連続/離散的機能に対する非拘束ブラックボックス最適化のための最先端の手法と同様に、混合変数の特徴空間と既知の入力制約を組み合わせた問題の競合する手法よりも優れている。
  論文  参考訳（メタデータ） (2022-07-02T16:59:37Z)
• Neural Improvement Heuristics for Graph Combinatorial Optimization Problems [49.85111302670361]
  本稿では,ノード,エッジ,あるいはその両方に情報をエンコードするグラフベースの問題を扱う新しいニューラル改善(NI)モデルを提案する。 提案モデルは,各地区の操作の選択を誘導する丘登頂に基づくアルゴリズムの基本的な構成要素として機能する。
  論文  参考訳（メタデータ） (2022-06-01T10:35:29Z)
• Neural Combinatorial Optimization: a New Player in the Field [69.23334811890919]
  本稿では,ニューラルネットワークに基づくアルゴリズムの古典的最適化フレームワークへの導入に関する批判的分析を行う。 性能, 転送可能性, 計算コスト, 大規模インスタンスなど, これらのアルゴリズムの基本的側面を分析するために, 総合的研究を行った。
  論文  参考訳（メタデータ） (2022-05-03T07:54:56Z)
• A Differentiable Approach to Combinatorial Optimization using Dataless Neural Networks [20.170140039052455]
  我々は、ソリューションを生成するニューラルネットワークのトレーニングにデータを必要としないという、根本的に異なるアプローチを提案する。 特に、最適化問題をニューラルネットワークに還元し、データレストレーニングスキームを用いて、それらのパラメータが関心の構造をもたらすように、ネットワークのパラメータを洗練する。
  論文  参考訳（メタデータ） (2022-03-15T19:21:31Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)

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

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