論文の概要: DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problems

• arxiv url: http://arxiv.org/abs/2406.19705v4
• Date: Tue, 08 Oct 2024 15:59:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-10 14:28:03.101641
• Title: DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problems
• Title（参考訳）: DISCO: 大規模組合せ最適化問題に対する効率的な拡散解法
• Authors: Kexiong Yu, Hang Zhao, Yuhang Huang, Renjiao Yi, Kai Xu, Chenyang Zhu,
• Abstract要約: DISCOは、大規模な組合せ最適化問題に対する効率的な拡散解法である。 サンプリング空間は、解残基によって導かれるより有意義な領域に制約され、出力分布のマルチモーダルな性質は保たれる。 大規模なトラベリングセールスマン問題や最大独立セットのベンチマークに挑戦し、他の拡散手段よりも最大5.28倍の速度で推論を行う。
• 参考スコア（独自算出の注目度）: 37.205311971072405
• License:
• Abstract: Combinatorial Optimization (CO) problems are fundamentally important in numerous real-world applications across diverse industries, characterized by entailing enormous solution space and demanding time-sensitive response. Despite recent advancements in neural solvers, their limited expressiveness struggles to capture the multi-modal nature of CO landscapes. While some research has shifted towards diffusion models, these models still sample solutions indiscriminately from the entire NP-complete solution space with time-consuming denoising processes, which limit their practicality for large problem scales. We propose DISCO, an efficient DIffusion Solver for large-scale Combinatorial Optimization problems that excels in both solution quality and inference speed. DISCO's efficacy is twofold: First, it enhances solution quality by constraining the sampling space to a more meaningful domain guided by solution residues, while preserving the multi-modal properties of the output distributions. Second, it accelerates the denoising process through an analytically solvable approach, enabling solution sampling with minimal reverse-time steps and significantly reducing inference time. DISCO delivers strong performance on large-scale Traveling Salesman Problems and challenging Maximal Independent Set benchmarks, with inference time up to 5.28 times faster than other diffusion alternatives. By incorporating a divide-and-conquer strategy, DISCO can well generalize to solve unseen-scale problem instances, even surpassing models specifically trained for those scales.
• Abstract（参考訳）: 組合せ最適化(CO)の問題は、様々な産業にまたがる多くの実世界のアプリケーションにおいて本質的に重要である。 ニューラルソルバの最近の進歩にもかかわらず、その限られた表現力はCOランドスケープのマルチモーダルな性質を捉えるのに苦労している。 拡散モデルに移行した研究もあるが、これらのモデルはNP完全解空間全体から無差別にサンプリングし、時間を要するデノナイジングプロセスにより、大規模な問題スケールでの実用性を制限している。 本研究では,解の質と推論速度の両面で優れている大規模組合せ最適化問題に対して,効率的な拡散解法であるdisCOを提案する。 第一に、サンプリング空間を溶液残基によって導かれるより有意義な領域に制限し、出力分布のマルチモーダル特性を保ち、溶液品質を高める。 第二に、分析的に解決可能なアプローチによってデノナイズプロセスを加速し、最小のリバースタイムステップで解をサンプリングし、推論時間を著しく短縮する。 DISCOは大規模トラベリングセールスマン問題と最大独立セットのベンチマークに挑戦し、推論時間は他の拡散手段よりも5.28倍高速である。 DISCOは分割/分散戦略を取り入れることで、目に見えないスケールの問題を解くためにうまく一般化することができ、そのスケールのために特別に訓練されたモデルを超えます。

関連論文リスト

• Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling [0.0]
  本研究では、連続緩和による勾配に基づく更新と準量子アナリング(QQA)を組み合わせた別のアプローチを提案する。 数値実験により,本手法はiSCOと学習型解法に匹敵する性能を有する汎用解法であることが示された。
  論文  参考訳（メタデータ） (2024-09-02T12:55:27Z)
• DiffSG: A Generative Solver for Network Optimization with Diffusion Model [75.27274046562806]
  拡散生成モデルはより広い範囲の解を考えることができ、学習パラメータによるより強力な一般化を示す。 拡散生成モデルの本質的な分布学習を利用して高品質な解を学習する新しいフレームワークを提案する。
  論文  参考訳（メタデータ） (2024-08-13T07:56:21Z)
• DiffuSolve: Diffusion-based Solver for Non-convex Trajectory Optimization [9.28162057044835]
  最適軌道局所は非線形および高次元力学系において計算コストが高い。 本稿では,非次元オプティマ問題に対するDiffuに基づく一般モデルを提案する。 また,新たな制約付き拡散モデルであるDiff+を提案する。
  論文  参考訳（メタデータ） (2024-02-22T03:52:17Z)
• Continuous Tensor Relaxation for Finding Diverse Solutions in Combinatorial Optimization Problems [0.6906005491572401]
  本研究では、教師なし学習(UL)に基づくCOソルバのための連続的アン緩和(CTRA)を提案する。 CTRAは、単一のトレーニング実行で多様なソリューションを見つけるための計算効率のよいフレームワークである。 数値実験により、CTRAにより、ULベースの解法は、既存の解法を繰り返すよりもはるかに高速にこれらの多様な解を見つけることができることが示された。
  論文  参考訳（メタデータ） (2024-02-03T15:31:05Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  置換フローショップスケジューリング(PFSS)は製造業で広く使われている。 我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。 我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
  論文  参考訳（メタデータ） (2022-10-31T09:46:26Z)
• DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems [41.57773395100222]
  深部強化学習(DRL)モデルはNP-hard Combinatorial Optimization問題を解決する上で有望な結果を示している。 本稿では,DIMESという新しいアプローチを提案することによって,大規模最適化におけるスケーラビリティの課題に対処する。 コストのかかる自己回帰的復号法や離散解の反復的洗練に苦しむ従来のDRL法とは異なり、DIMESは候補解の基底分布をパラメータ化するためのコンパクトな連続空間を導入する。 DIMESは、トラベリングセールスマン問題や最大独立セット問題のための大規模なベンチマークデータセットにおいて、最近のDRLベースの手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-10-08T23:24:37Z)
• Neural Stochastic Dual Dynamic Programming [99.80617899593526]
  我々は、問題インスタンスを断片的線形値関数にマッピングすることを学ぶトレーニング可能なニューラルモデルを導入する。 $nu$-SDDPは、ソリューションの品質を犠牲にすることなく、問題解決コストを大幅に削減できる。
  論文  参考訳（メタデータ） (2021-12-01T22:55:23Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Learning What to Defer for Maximum Independent Sets [84.00112106334655]
  本稿では,各段階における解の要素的決定を学習することにより,エージェントが適応的に段階数を縮小あるいは拡張する,新たなDRL方式を提案する。 提案手法を最大独立集合(MIS)問題に適用し、現状のDRL方式よりも大幅に改善したことを示す。
  論文  参考訳（メタデータ） (2020-06-17T02:19:31Z)

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

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