論文の概要: Quantum Annealing for Minimum Bisection Problem: A Machine Learning-based Approach for Penalty Parameter Tuning

• arxiv url: http://arxiv.org/abs/2509.19005v1
• Date: Tue, 23 Sep 2025 13:49:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-24 20:41:27.869027
• Title: Quantum Annealing for Minimum Bisection Problem: A Machine Learning-based Approach for Penalty Parameter Tuning
• Title（参考訳）: 最小二分法問題に対する量子アニーリング:ペナルティパラメータチューニングのための機械学習に基づくアプローチ
• Authors: Renáta Rusnáková, Martin Chovanec, Juraj Gazda,
• Abstract要約: ペナルティパラメータの適応的チューニングのための機械学習に基づく新しいアプローチを提案する。 我々は、最大4,000ノードのランダムに生成されたErdHos-R'enyiグラフの大規模なデータセット上で、我々のアプローチをテストする。
• 参考スコア（独自算出の注目度）: 0.39325957466009204
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Minimum Bisection Problem is a well-known NP-hard problem in combinatorial optimization, with practical applications in areas such as parallel computing, network design, and machine learning. In this paper, we examine the potential of using D-Wave Systems' quantum annealing solvers to solve the Minimum Bisection Problem, which we formulate as a Quadratic Unconstrained Binary Optimization model. A key challenge in this formulation lies in choosing an appropriate penalty parameter, as it plays a crucial role in ensuring both the quality of the solution and the satisfaction of the problem's constraints. To address this, we introduce a novel machine learning-based approach for adaptive tuning of the penalty parameter. Specifically, we use a Gradient Boosting Regressor model trained to predict suitable penalty parameter values based on structural properties of the input graph, the number of nodes and the graph's density. This method enables the penalty parameter to be adjusted dynamically for each specific problem instance, improving the solver's ability to balance the competing goals of minimizing the cut size and maintaining equally sized partitions. We test our approach on a large dataset of randomly generated Erd\H{o}s-R\'enyi graphs with up to 4,000 nodes, and we compare the results with classical partitioning algorithms, Metis and Kernighan-Lin. Experimental findings demonstrate that our adaptive tuning strategy significantly improves the performance of the quantum annealing hybrid solver and consistently outperforms the classical methods used, indicating its potential as an alternative for the graph partitioning problem.
• Abstract（参考訳）: 最小二項問題(Minimum Bisection Problem)は、並列コンピューティング、ネットワーク設計、機械学習といった分野の実践的な応用で、組合せ最適化においてよく知られたNPハード問題である。 本稿では、D-Wave Systemsの量子アニール解法を用いて、二次非拘束二項最適化モデルとして定式化した最小二項問題の解法について検討する。 この定式化における重要な課題は、ソリューションの品質と問題の制約の満足度の両方を保証する上で重要な役割を果たすため、適切なペナルティパラメータを選択することである。 そこで本稿では,ペナルティパラメータの適応的チューニングのための機械学習に基づく新しいアプローチを提案する。 具体的には、入力グラフの構造特性、ノード数、グラフ密度に基づいて適切なペナルティパラメータ値を予測するために訓練されたグラディエントブースティング回帰モデルを用いる。 この方法では、特定の問題インスタンス毎にペナルティパラメータを動的に調整し、カットサイズを最小化し、等サイズのパーティションを維持することで競合する目標をバランスさせる能力を向上させる。 我々は、最大4,000ノードのランダムに生成されたErd\H{o}s-R\enyiグラフの大規模なデータセット上で、我々のアプローチを検証し、その結果を古典的なパーティショニングアルゴリズムであるMetisとKernighan-Linと比較する。 実験結果から,我々の適応的チューニング戦略は量子アニールハイブリッドソルバの性能を著しく向上させ,従来手法よりも一貫して優れており,グラフ分割問題の代替としての可能性を示している。

関連論文リスト

• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。 既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。 これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-21T17:15:48Z)
• Evaluating Quantum Optimization for Dynamic Self-Reliant Community Detection [3.6021182997326022]
  量子計算カラーブルーを用いて解くのに適した二次非拘束バイナリ最適化(QUBO)問題を定式化する。 この定式化は、最大自己充足力とそれらの間を流れる最小限のパワーを持つコミュニティを見つけることを目的としている。 D-Waveのハイブリッド量子古典解法、古典解法、分枝結合解法などである。
  論文  参考訳（メタデータ） (2024-07-09T11:44:58Z)
• Feature selection in linear SVMs via a hard cardinality constraint: a scalable SDP decomposition approach [3.7876216422538485]
  本稿では, 線形支援ベクトルマシン(SVM)において, 濃度制約が適用された場合の組込み特徴選択問題について検討する。 この問題は、元の線形SVMが時間内に解決可能な問題に等しいにもかかわらず、濃度制約が存在するためNPハードである。 この問題に対処するために、まず2つの混合整数式を導入し、新しい半定緩和法を提案する。
  論文  参考訳（メタデータ） (2024-04-15T19:15:32Z)
• 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)
• A Deep Unrolling Model with Hybrid Optimization Structure for Hyperspectral Image Deconvolution [50.13564338607482]
  本稿では,DeepMixと呼ばれるハイパースペクトルデコンボリューション問題に対する新しい最適化フレームワークを提案する。 これは3つの異なるモジュール、すなわちデータ一貫性モジュール、手作りの正規化器の効果を強制するモジュール、および装飾モジュールで構成されている。 本研究は,他のモジュールの協調作業によって達成される進歩を維持するために設計された,文脈を考慮した認知型モジュールを提案する。
  論文  参考訳（メタデータ） (2023-06-10T08:25:16Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。 ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
  論文  参考訳（メタデータ） (2023-05-28T06:33:37Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。 レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
  論文  参考訳（メタデータ） (2022-03-01T19:47:16Z)
• Numerical Solution of Stiff Ordinary Differential Equations with Random Projection Neural Networks [0.0]
  正規微分方程式(ODE)の解に対する乱射影ニューラルネットワーク(RPNN)に基づく数値スキームを提案する。 提案手法は剛性の影響を受けずに高い数値近似精度を示し,textttode45 と textttode15s の関数よりも優れていた。
  論文  参考訳（メタデータ） (2021-08-03T15:49:17Z)

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

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