論文の概要: DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problems
- arxiv url: http://arxiv.org/abs/2406.19705v1
- Date: Fri, 28 Jun 2024 07:36:31 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-01 17:29:51.701619
- 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は、組合せ最適化問題の拡散解法である。
ソリューションの品質と推論速度の両面で優れています。
10000のノードを持ち、最大独立セットのベンチマークに挑戦する非常に大きなトラベリングセールスマン問題に対して、最先端の結果が得られます。
- 参考スコア（独自算出の注目度）: 37.205311971072405
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Combinatorial Optimization (CO) problems are fundamentally crucial in numerous practical applications across diverse industries, characterized by entailing enormous solution space and demanding time-sensitive response. Despite significant advancements made by recent neural solvers, their limited expressiveness does not conform well to the multi-modal nature of CO landscapes. While some research has pivoted towards diffusion models, they require simulating a Markov chain with many steps to produce a sample, which is time-consuming and does not meet the efficiency requirement of real applications, especially at scale. We propose DISCO, an efficient DIffusion Solver for Combinatorial Optimization problems that excels in both solution quality and inference speed. DISCO's efficacy is two-pronged: Firstly, it achieves rapid denoising of solutions through an analytically solvable form, allowing for direct sampling from the solution space with very few reverse-time steps, thereby drastically reducing inference time. Secondly, DISCO enhances solution quality by restricting the sampling space to a more constrained, meaningful domain guided by solution residues, while still preserving the inherent multi-modality of the output probabilistic distributions. DISCO achieves state-of-the-art results on very large Traveling Salesman Problems with 10000 nodes and challenging Maximal Independent Set benchmarks, with its per-instance denoising time up to 44.8 times faster. Through further combining a divide-and-conquer strategy, DISCO can be generalized to solve arbitrary-scale problem instances off the shelf, even outperforming models trained specifically on corresponding scales.
- Abstract（参考訳）: 組合せ最適化(CO)問題は、膨大なソリューション空間と時間に敏感な応答を必要とすることが特徴で、様々な産業にまたがる多くの実践的応用において、基本的に重要な問題である。
最近のニューラルソルバによる顕著な進歩にもかかわらず、その限定的な表現性はCOランドスケープのマルチモーダルな性質とよく一致しない。
拡散モデルに向かっている研究もあるが、サンプルを生成するには多くのステップでマルコフ連鎖をシミュレートする必要がある。
本稿では,解の質と推論速度の両面において優れる,解法最適化のための効率的な拡散解法であるdisCOを提案する。
DISCOの有効性は2つある: まず、分析的に解ける形で解を素早く分解し、非常に少ない逆時間ステップで解空間から直接サンプリングし、推論時間を劇的に短縮する。
第二に、 DisCO は、サンプリング空間を、解残基によって導かれるより制約された有意義な領域に制限し、出力確率分布の本質的にの多重モダリティを保ったまま、解の質を高める。
DISCOは10000のノードを持ち、最大独立セットのベンチマークに挑戦する非常に大きなトラベリングセールスマン問題に対する最先端の結果を達成し、そのインスタンスごとの遅延時間は44.8倍速くなった。
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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。