論文の概要: Solving Combinatorial Optimization Problems on Fujitsu Digital Annealer
- arxiv url: http://arxiv.org/abs/2311.05196v1
- Date: Thu, 9 Nov 2023 08:20:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-10 15:54:55.227364
- Title: Solving Combinatorial Optimization Problems on Fujitsu Digital Annealer
- Title（参考訳）: 富士通デジタルアニーラーにおける組合せ最適化問題の解法
- Authors: Yu-Ting Kao, Jia-Le Liao, Hsiu-Chuan Hsu
- Abstract要約: ディジタルアニール (DA) は、制約のないバイナリ最適化 (QUBO) を用いた最適化問題を解くために開発された。
DAはIEEE 33-busとIEEE 118-busネットワークのコミュニティ構造を効果的に特定した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Combinatorial optimization problems are ubiquitous in various disciplines and
applications. Many heuristic algorithms have been devoted to solve these types
of problems. In order to increase the efficiency for finding the optimal
solutions, an application-specific hardware, called digital annealer (DA) has
been developed for solving combinatorial optimization problems using quadratic
unconstrained binary optimization (QUBO) formulations. In this study, we
formulated the number partitioning problem and the graph partitioning problem
into QUBO forms and solved such problems with the DA developed by Fujitsu Ltd.
The QUBO formulation of the number partitioning problem is fully connected. The
DA found the overall runtime for the optimal solution to be less than 30
seconds for 6500 binary variables. For the graph partitioning problem, we
adopted modularity as the metric for determining the quality of the partitions.
For Zachary's Karate Club graph, the modularity obtained was 0.445, a 6%
increase against D-wave Quantum Annealer and Simulated Annealing. Moreover, to
explore the DA's potential applications to real-world problems, we used the
search for communities or virtual microgrids in a power distribution network as
an example. The problem was formulated into graph partitioning. It is shown
that the DA effectively identified community structures in the IEEE 33-bus and
IEEE 118-bus network.
- Abstract（参考訳）: 組合せ最適化問題は様々な分野や応用においてユビキタスである。
この種の問題を解決するために多くのヒューリスティックアルゴリズムが費やされている。
最適解を見つけるための効率を高めるために,2次非制約二元最適化(QUBO)を用いた組合せ最適化問題を解くために,DA(Digital Annealer)と呼ばれるアプリケーション固有のハードウェアを開発した。
本研究では,数分割問題とグラフ分割問題をQUBO形式に定式化し,富士通製DAを用いてこの問題を解いた。
数分割問題のqubo定式化は完全連結である。
DAは6500のバイナリ変数に対して、最適なソリューション全体のランタイムが30秒未満であることを発見した。
グラフ分割問題に対して,我々は分割の品質を決定する指標としてモジュール性を採用した。
Zachary の Karate Club グラフでは、モジュラリティは 0.445 であり、D-wave Quantum Annealer と Simulated Annealing に対して6%増加した。
さらに,実世界の問題に対するdaの潜在的な応用を探求するために,電力流通ネットワークにおけるコミュニティや仮想マイクログリッドの探索を例として用いた。
問題はグラフ分割に定式化された。
その結果,DAはIEEE 33-busとIEEE 118-busネットワークのコミュニティ構造を効果的に同定した。
関連論文リスト
- A Random-Key Optimizer for Combinatorial Optimization [0.0]
Random-Key Hubs (RKO) は最適化問題に適した汎用的で効率的な局所探索手法である。
ランダムキーの概念を用いて、RKOは解をランダムキーのベクトルとしてエンコードし、後に問題固有のデコーダを介して実現可能な解へとデコードする。
RKOフレームワークは古典的メタヒューリスティクスの多元体を組み合わせ、それぞれが独立して、あるいは並列に動作可能であり、エリートソリューションプールを通じてソリューション共有が促進される。
論文 参考訳（メタデータ） (2024-11-06T22:23:29Z) - Evaluating Quantum Optimization for Dynamic Self-Reliant Community Detection [3.6021182997326022]
量子計算カラーブルーを用いて解くのに適した二次非拘束バイナリ最適化(QUBO)問題を定式化する。
この定式化は、最大自己充足力とそれらの間を流れる最小限のパワーを持つコミュニティを見つけることを目的としている。
D-Waveのハイブリッド量子古典解法、古典解法、分枝結合解法などである。
論文 参考訳（メタデータ） (2024-07-09T11:44:58Z) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-11T04:40:05Z) - Graph Partitioning with Fujitsu Digital Annealer [0.0]
本研究は,富士通デジタルアナーラーの性能と走行時間を評価する。
DAはケース1354ペガゼの電力グリッドネットワークを45のサブグループに分割し、60,930のバイナリ変数を要求した。
その結果,Fujitsu DAはグラフ分割の高速かつ効率的な最適化に有効であることが示唆された。
論文 参考訳（メタデータ） (2023-11-28T06:59:01Z) - 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) - Let the Flows Tell: Solving Graph Combinatorial Optimization Problems
with GFlowNets [86.43523688236077]
組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。
GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。
本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
論文 参考訳（メタデータ） (2023-05-26T15:13:09Z) - Discrete quadratic model QUBO solution landscapes [0.0]
本稿では,QUBO DQMソリューションランドスケープの構造に及ぼす符号化とペナルティ強度の選択の影響について検討する。
本研究は、ワンホットおよびドメインウォールエンコーディングに特化している。
論文 参考訳（メタデータ） (2023-04-30T20:19:46Z) - DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization [51.517956081644186]
グラフベースの拡散フレームワークであるDIFUSCOを導入する。
本フレームワークは, NPC問題を離散0, 1ベクトル最適化問題とみなす。
MIS問題に対して、DIFUSCOは、挑戦的なSATLIBベンチマークにおいて、以前の最先端のニューラルソルバよりも優れている。
論文 参考訳（メタデータ） (2023-02-16T11:13:36Z) - Learning To Dive In Branch And Bound [95.13209326119153]
グラフニューラルネットワークを用いて特定の潜水構造を学習するためのL2Diveを提案する。
我々は、変数の割り当てを予測するために生成モデルを訓練し、線形プログラムの双対性を利用して潜水決定を行う。
論文 参考訳（メタデータ） (2023-01-24T12:01:45Z) - Bayesian Algorithm Execution: Estimating Computable Properties of
Black-box Functions Using Mutual Information [78.78486761923855]
多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。
本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。
これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
論文 参考訳（メタデータ） (2021-04-19T17:22:11Z) - Consistent Second-Order Conic Integer Programming for Learning Bayesian
Networks [2.7473982588529653]
連続観測データからBNのスパースDAG構造を学習する問題について検討する。
この数学的プログラムの最適解は、ある条件下では望ましい統計的性質を持つことが知られている。
ほぼ最適解を得るために, 分岐・結合プロセスの終了に向け, 早期停止条件を提案する。
論文 参考訳（メタデータ） (2020-05-29T00:13:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。