論文の概要: Geometric Algorithms for Neural Combinatorial Optimization with Constraints

• arxiv url: http://arxiv.org/abs/2510.24039v1
• Date: Tue, 28 Oct 2025 03:49:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-29 15:35:36.746619
• Title: Geometric Algorithms for Neural Combinatorial Optimization with Constraints
• Title（参考訳）: 制約付きニューラルコンビネーション最適化のための幾何学的アルゴリズム
• Authors: Nikolaos Karalias, Akbar Rafiey, Yifei Xu, Zhishang Luo, Behrooz Tahmasebi, Connie Jiang, Stefanie Jegelka,
• Abstract要約: Self-Supervised Learning for Combinatorial Optimization (CO)は、ニューラルネットワークを使って問題を解決するための新しいパラダイムである。 ニューラルネットワークによる離散的な制約付き最適化問題の解決を可能にする、エンドツーエンドの微分可能なフレームワークを設計する。
• 参考スコア（独自算出の注目度）: 46.17172939797694
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Self-Supervised Learning (SSL) for Combinatorial Optimization (CO) is an emerging paradigm for solving combinatorial problems using neural networks. In this paper, we address a central challenge of SSL for CO: solving problems with discrete constraints. We design an end-to-end differentiable framework that enables us to solve discrete constrained optimization problems with neural networks. Concretely, we leverage algorithmic techniques from the literature on convex geometry and Carath\'eodory's theorem to decompose neural network outputs into convex combinations of polytope corners that correspond to feasible sets. This decomposition-based approach enables self-supervised training but also ensures efficient quality-preserving rounding of the neural net output into feasible solutions. Extensive experiments in cardinality-constrained optimization show that our approach can consistently outperform neural baselines. We further provide worked-out examples of how our method can be applied beyond cardinality-constrained problems to a diverse set of combinatorial optimization tasks, including finding independent sets in graphs, and solving matroid-constrained problems.
• Abstract（参考訳）: Self-Supervised Learning (SSL) for Combinatorial Optimization (CO)は、ニューラルネットワークを用いて組合せ問題を解くための新興パラダイムである。 本稿では,COにおけるSSLの主な課題である,離散制約による問題解決について述べる。 ニューラルネットワークによる離散的な制約付き最適化問題の解決を可能にする、エンドツーエンドの微分可能なフレームワークを設計する。 具体的には、凸幾何学とCarath\'eodoryの定理に関する文献のアルゴリズム技術を利用して、ニューラルネットワークの出力を、実現可能な集合に対応するポリトープコーナーの凸結合に分解する。 この分解に基づくアプローチは、自己教師付きトレーニングを可能にすると同時に、ニューラルネットワーク出力の効率的な品質保存ラウンドリングを実現可能なソリューションに保証する。 濃度制約最適化における広範囲な実験は、我々のアプローチが神経ベースラインを一貫して上回ることを示す。 さらに,グラフ内の独立集合の探索やマトロイド制約問題の解法を含む,多種多様な組合せ最適化タスクに対して,濃度制約問題を超えて我々の手法をどのように適用できるかを示す。

関連論文リスト

• Learning based convex approximation for constrained parametric optimization [11.379408842026981]
  本稿では、制約付き最適化問題を解決するために、入力ニューラルネットワーク(ICNN)に基づく自己教師付き学習フレームワークを提案する。 厳密な収束解析を行い、このフレームワークが元の問題のKKT近似点に収束することを示す。 提案手法は精度,実現可能性,計算効率の両立を実現している。
  論文  参考訳（メタデータ） (2025-05-07T00:33:14Z)
• A neural network approach for solving the Monge-Ampère equation with transport boundary condition [0.0]
  本稿では,輸送境界条件でモンジュ・アンペア方程式を解くためのニューラルネットワークに基づく新しい手法を提案する。 我々は、方程式の残差、境界条件、凸性制約を含む損失関数を最小化することにより、多層パーセプトロンネットワークを利用して近似解を学習する。
  論文  参考訳（メタデータ） (2024-10-25T11:54:00Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• Are Graph Neural Networks Optimal Approximation Algorithms? [26.5364112420121]
  最適化問題のクラスに対して最適な近似アルゴリズムをキャプチャするグラフニューラルネットワークアーキテクチャを設計する。 我々は、OptGNNの学習した埋め込みから最適解のバウンダリを生成するアルゴリズムを設計するために、凸緩和を捕捉するOptGNNの能力を利用する。
  論文  参考訳（メタデータ） (2023-10-01T00:12:31Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Neural Combinatorial Optimization: a New Player in the Field [69.23334811890919]
  本稿では,ニューラルネットワークに基づくアルゴリズムの古典的最適化フレームワークへの導入に関する批判的分析を行う。 性能, 転送可能性, 計算コスト, 大規模インスタンスなど, これらのアルゴリズムの基本的側面を分析するために, 総合的研究を行った。
  論文  参考訳（メタデータ） (2022-05-03T07:54:56Z)
• Constrained Combinatorial Optimization with Reinforcement Learning [0.30938904602244344]
  本稿では,RL(Deep Reinforcement Learning)を用いた制約付き最適化問題に対処する枠組みを提案する。 我々は、その定式化における制約に対処するために、Neural Combinatorial Optimization(NCO)理論を拡張した。 その文脈では、ソリューションは環境との相互作用に基づいて反復的に構築されます。
  論文  参考訳（メタデータ） (2020-06-22T03:13:07Z)
• The Hidden Convex Optimization Landscape of Two-Layer ReLU Neural Networks: an Exact Characterization of the Optimal Solutions [51.60996023961886]
  コーン制約のある凸最適化プログラムを解くことにより,グローバルな2層ReLUニューラルネットワークの探索が可能であることを示す。 我々の分析は新しく、全ての最適解を特徴づけ、最近、ニューラルネットワークのトレーニングを凸空間に持ち上げるために使われた双対性に基づく分析を活用できない。
  論文  参考訳（メタデータ） (2020-06-10T15:38:30Z)

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

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