論文の概要: Enumeration algorithms for combinatorial problems using Ising machines
- arxiv url: http://arxiv.org/abs/2412.00284v1
- Date: Fri, 29 Nov 2024 23:33:26 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-04 15:42:16.700317
- Title: Enumeration algorithms for combinatorial problems using Ising machines
- Title（参考訳）: イジングマシンを用いた組合せ問題列挙アルゴリズム
- Authors: Yuta Mizuno, Mohammad Ali, Tamiki Komatsuzaki,
- Abstract要約: 最適化や制約満足度問題といった組合せ問題は意思決定に現れる。
本稿では,Ising マシンを用いた列挙アルゴリズムを提案する。
提案アルゴリズムは,従来の分岐結合アルゴリズムよりも高速に,高密度グラフの最大傾きを列挙する。
- 参考スコア（独自算出の注目度）: 0.40964539027092917
- License:
- Abstract: Combinatorial problems such as combinatorial optimization and constraint satisfaction problems arise in decision-making across various fields of science and technology. In real-world applications, when multiple optimal or constraint-satisfying solutions exist, enumerating all these solutions -- rather than finding just one -- is often desirable, as it provides flexibility in decision-making. However, combinatorial problems and their enumeration versions pose significant computational challenges due to combinatorial explosion. To address these challenges, we propose enumeration algorithms for combinatorial optimization and constraint satisfaction problems using Ising machines. Ising machines are specialized devices designed to efficiently solve combinatorial problems. Typically, they sample low-cost solutions in a stochastic manner. Our enumeration algorithms repeatedly sample solutions to collect all desirable solutions. The crux of the proposed algorithms is their stopping criteria for sampling, which are derived based on probability theory. In particular, the proposed algorithms have theoretical guarantees that the failure probability of enumeration is bounded above by a user-specified value, provided that lower-cost solutions are sampled more frequently and equal-cost solutions are sampled with equal probability. Many physics-based Ising machines are expected to (approximately) satisfy these conditions. As a demonstration, we applied our algorithm using simulated annealing to maximum clique enumeration on random graphs. We found that our algorithm enumerates all maximum cliques in large dense graphs faster than a conventional branch-and-bound algorithm specially designed for maximum clique enumeration. This demonstrates the promising potential of our proposed approach.
- Abstract（参考訳）: 組合せ最適化や制約満足度問題といった組合せ問題は、科学と技術の様々な分野における意思決定において生じる。
現実のアプリケーションでは、複数の最適あるいは制約を満たすソリューションが存在する場合、意思決定の柔軟性を提供するため、これらすべてのソリューションを列挙することが望ましい。
しかし、組合せ問題とその列挙バージョンは組合せ爆発による計算上の問題を引き起こす。
これらの課題に対処するため,Ising マシンを用いた組合せ最適化と制約満足度問題に対する列挙アルゴリズムを提案する。
イジングマシンは、組合せ問題を効率的に解くように設計された特殊な装置である。
通常、彼らは確率的な方法で低コストのソリューションをサンプリングする。
我々の列挙アルゴリズムは、全ての望ましい解を収集するために繰り返し解をサンプリングする。
提案アルゴリズムの要点はサンプリングの停止基準であり、確率論に基づいて導出される。
特に, 提案アルゴリズムは, 利用者指定値によって列挙の失敗確率が上述の値に制限されることを理論的に保証し, 低コストの解がより頻繁にサンプリングされ, 等コストの解が等確率でサンプリングされることを仮定する。
多くの物理学ベースのイジングマシンは(ほぼ)これらの条件を満たすことが期待されている。
実演として,ランダムグラフ上での最大斜め列挙に擬似アニールを用いたアルゴリズムを適用した。
提案アルゴリズムは,最大傾き列挙のために特別に設計された従来の分岐境界アルゴリズムよりも高速に,高密度グラフ内の最大傾きを列挙する。
これは我々の提案したアプローチの有望な可能性を示している。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - A Sequential Deep Learning Algorithm for Sampled Mixed-integer
Optimisation Problems [0.3867363075280544]
混合整数最適化問題に対する2つの効率的なアルゴリズムを導入,解析する。
両アルゴリズムが最適解に対して有限時間収束を示すことを示す。
3つの数値実験により,これらのアルゴリズムの有効性を定量的に確立する。
論文 参考訳（メタデータ） (2023-01-25T17:10:52Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - Ising formulation of integer optimization problems for utilizing quantum
annealing in iterative improvement strategy [1.14219428942199]
繰り返し改善戦略において量子アニーリングを利用するために,整数最適化問題のイジング定式化を提案する。
基底状態と候補解との重なりがしきい値を超えた場合, 完全に連結されたフェロポッツモデルに対して一階相転移を回避できることを解析的に示す。
論文 参考訳（メタデータ） (2022-11-08T02:12:49Z) - Optimization of Robot Trajectory Planning with Nature-Inspired and
Hybrid Quantum Algorithms [0.0]
産業規模でロボット軌道計画問題を解く。
我々のエンドツーエンドソリューションは、高度に多目的なランダムキーアルゴリズムとモデル積み重ねとアンサンブル技術を統合している。
我々は、後者が我々のより大きなパイプラインにどのように統合され、問題に対する量子対応ハイブリッドソリューションを提供するかを示す。
論文 参考訳（メタデータ） (2022-06-08T02:38:32Z) - Dynamic programming by polymorphic semiring algebraic shortcut fusion [1.9405875431318445]
動的プログラミング(動的プログラミング、英: Dynamic Programming、DP)は、難解問題の効率的かつ正確な解法のためのアルゴリズム設計パラダイムである。
本稿では,セミリングに基づくDPアルゴリズムを体系的に導出するための厳密な代数形式について述べる。
論文 参考訳（メタデータ） (2021-07-05T00:51:02Z) - A Hybrid Quantum-Classical Heuristic to solve large-scale Integer Linear
Programs [0.4925222726301578]
本稿では、整数線形プログラムの解を見つけることができる任意の量子アルゴリズムをブランチ・アンド・プライス・アルゴリズムに統合する手法を提案する。
量子アルゴリズムの役割は、ブランチ・アンド・プライスに現れるサブプロブレムに対する整数解を見つけることである。
論文 参考訳（メタデータ） (2021-03-29T08:59:26Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳（メタデータ） (2020-01-29T09:40:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。