論文の概要: Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networks

• arxiv url: http://arxiv.org/abs/2409.04495v1
• Date: Fri, 6 Sep 2024 14:58:31 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-10 22:31:08.704139
• Title: Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networks
• Title（参考訳）: 非自己回帰型ニューラルネットワークによる正線形制約下での組合せ最適化の学習
• Authors: Runzhong Wang, Yang Li, Junchi Yan, Xiaokang Yang,
• Abstract要約: 組合せ最適化(英: Combinatorial Optimization、CO)は、計算機科学、応用数学などにおける基本的な問題である。 本稿では, 正線形制約下でのCO問題の解法として, 非自己回帰ニューラルネットワーク群を設計する。 本研究では,施設位置,最大被覆率,旅行セールスマン問題を含む代表的CO問題の解決において,この枠組みの有効性を検証する。
• 参考スコア（独自算出の注目度）: 103.78912399195005
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Combinatorial optimization (CO) is the fundamental problem at the intersection of computer science, applied mathematics, etc. The inherent hardness in CO problems brings up challenge for solving CO exactly, making deep-neural-network-based solvers a research frontier. In this paper, we design a family of non-autoregressive neural networks to solve CO problems under positive linear constraints with the following merits. First, the positive linear constraint covers a wide range of CO problems, indicating that our approach breaks the generality bottleneck of existing non-autoregressive networks. Second, compared to existing autoregressive neural network solvers, our non-autoregressive networks have the advantages of higher efficiency and preserving permutation invariance. Third, our offline unsupervised learning has lower demand on high-quality labels, getting rid of the demand of optimal labels in supervised learning. Fourth, our online differentiable search method significantly improves the generalizability of our neural network solver to unseen problems. We validate the effectiveness of this framework in solving representative CO problems including facility location, max-set covering, and traveling salesman problem. Our non-autoregressive neural solvers are competitive to and can be even superior to state-of-the-art solvers such as SCIP and Gurobi, especially when both efficiency and efficacy are considered. Code is available at https://github.com/Thinklab-SJTU/NAR-CO-Solver
• Abstract（参考訳）: 組合せ最適化(英: Combinatorial Optimization、CO)は、計算機科学、応用数学などにおける基本的な問題である。 CO問題の固有の硬さは、COを正確に解くことの難しさを生じさせ、ディープ・ニューラル・ネットワークベースの解法を研究フロンティアにする。 本稿では,CO問題の正の線形制約下での解法として,非自己回帰ニューラルネットワーク群を設計する。 第一に、正線形制約はCOの幅広い問題をカバーしており、我々のアプローチが既存の非自己回帰的ネットワークの一般性ボトルネックを突破することを示している。 第二に、既存の自己回帰型ニューラルネットワークソルバと比較して、我々の非自己回帰型ネットワークは高い効率と置換不変性を保存するという利点がある。 第三に、オフラインの教師なし学習は高品質なラベルに対する需要を減らし、教師なし学習における最適なラベルの需要をなくした。 第4に、我々のオンライン微分可能探索法は、ニューラルネットワークソルバの一般化可能性を大幅に改善し、未確認の問題に対処する。 本研究では,施設位置,最大被覆率,旅行セールスマン問題を含む代表的CO問題の解決における,この枠組みの有効性を検証する。 我々の非自己回帰型ニューラルソルバは競争力があり、特に効率性と有効性を考慮した場合、SCIPやGurobiのような最先端のニューラルソルバよりも優れている。 コードはhttps://github.com/Thinklab-SJTU/NAR-CO-Solverで入手できる。

関連論文リスト

• LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
  本稿では,ニューラルネットワークに人気の高い正の線形満足度を導入する方法について検討する。 本稿では,古典的なシンクホーンアルゴリズムを拡張し,複数の辺分布の集合を共同で符号化する,最初の微分可能満足層を提案する。
  論文  参考訳（メタデータ） (2024-07-18T22:05:21Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。 GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。 我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
  論文  参考訳（メタデータ） (2024-06-05T22:52:27Z)
• Network Interdiction Goes Neural [26.308933674471895]
  ネットワーク断面積問題は、2人のプレイヤーが関与する最適化問題である。 1つは、ネットワーク上の最適化問題を解決することを目的としており、もう1つは、最初のプレイヤーの目的を阻止するためにネットワークを変更することを目的としている。
  論文  参考訳（メタデータ） (2024-05-26T02:34:26Z)
• Neural Algorithmic Reasoning for Combinatorial Optimisation [20.36694807847833]
  ニューラル推論の最近の進歩を活用して,CO問題の学習を改善することを提案する。 私たちは、COインスタンスでトレーニングする前に、関連するアルゴリズムでニューラルネットワークを事前トレーニングすることを提案します。 以上の結果から,この学習装置を用いることで,非アルゴリズム的情報深層学習モデルよりも優れた性能が得られることが示された。
  論文  参考訳（メタデータ） (2023-05-18T13:59:02Z)
• Globally Optimal Training of Neural Networks with Threshold Activation Functions [63.03759813952481]
  しきい値アクティベートを伴うディープニューラルネットワークの重み劣化正規化学習問題について検討した。 ネットワークの特定の層でデータセットを破砕できる場合に、簡易な凸最適化の定式化を導出する。
  論文  参考訳（メタデータ） (2023-03-06T18:59:13Z)
• Unsupervised Optimal Power Flow Using Graph Neural Networks [172.33624307594158]
  グラフニューラルネットワークを用いて、要求された電力と対応するアロケーションとの間の非線形パラメトリゼーションを学習する。 シミュレーションを通して、この教師なし学習コンテキストにおけるGNNの使用は、標準解法に匹敵するソリューションにつながることを示す。
  論文  参考訳（メタデータ） (2022-10-17T17:30:09Z)
• Optimization-Informed Neural Networks [0.6853165736531939]
  制約付き非線形最適化問題を解くために最適化インフォームドニューラルネットワーク(OINN)を提案する。 簡単に言うと、OINNはCNLPをニューラルネットワークトレーニング問題に変換する。 提案手法の有効性は古典的な問題の収集を通じて実証される。
  論文  参考訳（メタデータ） (2022-10-05T09:28:55Z)
• Edge Rewiring Goes Neural: Boosting Network Resilience via Policy Gradient [62.660451283548724]
  ResiNetは、さまざまな災害や攻撃に対する回復力のあるネットワークトポロジを発見するための強化学習フレームワークである。 ResiNetは複数のグラフに対してほぼ最適のレジリエンス向上を実現し,ユーティリティのバランスを保ちながら,既存のアプローチに比べて大きなマージンを持つことを示す。
  論文  参考訳（メタデータ） (2021-10-18T06:14:28Z)

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

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