論文の概要: GNN-Guided Graph Coarsening and Adaptive QUBO Penalties for the Capacitated Vehicle Routing Problem with Time Windows on a Quantum Annealer
- arxiv url: http://arxiv.org/abs/2609.04593v2
- Date: Wed, 09 Sep 2026 17:23:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-10 15:10:00.988707
- Title: GNN-Guided Graph Coarsening and Adaptive QUBO Penalties for the Capacitated Vehicle Routing Problem with Time Windows on a Quantum Annealer
- Title（参考訳）: GNN-Guided Graph Coarsening and Adaptive QUBO Penalties for the Capacitated Vehicle Routing Problem with Time Windows on a Quantum Annealer (特集:情報ネットワーク)
- Authors: Youssef Kamel Rezk, Paweł Gora,
- Abstract要約: グラフの粗化は、大きな擬似非制約バイナリ最適化(QUBO)の定式化を減少させる。
Capacitated Vehicle Problem with Time Windows (CVRPTW) では、既存の粗大化は家族固有のチューニングを必要とし、ランダムなインスタンスでは信頼性が低い。
シミュレーションアニーリングとD-Wave Advantage2プロセッサを用いて,Solomonベンチマークのこれらの制限に対処する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Graph coarsening reduces the large Quadratic Unconstrained Binary Optimization (QUBO) formulations arising when vehicle-routing problems are solved by quantum annealing. Nearby customers with compatible time windows are merged into super-nodes, the reduced problem is solved, and the solution is expanded to the original graph. For the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW), existing coarsening heuristics require family-specific tuning and remain unreliable on random instances. We address these limitations on the Solomon benchmark using simulated annealing and a D-Wave Advantage2 processor. We first introduce adaptive penalty calibration. Uniform penalty scaling has little effect, whereas controlling the internal coefficient range substantially improves raw samples. Removing non-binding constraints, normalising binding ones, and scaling the remaining penalties reduces mean raw constraint violations from 33.0 to 0.06 at the same solver budget (p=3.7e-11, n=56). A variable-count-preserving control attributes this gain to conditioning rather than problem size. Second, we replace the hand-tuned merge score with a graph neural network (GNN) using one configuration across all families. At N=10, it achieves 100% feasibility across all Solomon families, including R-type (100% vs. 80% for the tuned heuristic). Across N=10,...,100, feasibility is 83% vs. 69%, with the GNN better or tied on 85/90 instance-size pairs. At N=80,100, the difference is significant (p=0.002; 25/25 pairs), while the QUBO remains approximately 5-6 times smaller. Finally, hardware experiments reproduce the conditioning effect at fixed logical variable count: feasible samples increase from 0.02% to 39% across 13 instances. Classical repair with local search remains a reference bound for end-to-end solution cost.
- Abstract（参考訳）: グラフの粗化は、量子アニーリングによって車両の走行問題を解く際に生じる大きな二次非拘束バイナリ最適化(QUBO)の定式化を減少させる。
互換性のある時間窓を持つ顧客をスーパーノードにマージし、削減された問題を解決し、ソリューションを元のグラフに拡張する。
Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) では、既存の粗いヒューリスティックは家族固有のチューニングを必要とし、ランダムなインスタンスでは信頼できない。
シミュレーションアニーリングとD-Wave Advantage2プロセッサを用いて,Solomonベンチマークのこれらの制限に対処する。
最初に適応的なペナルティ校正を導入する。
均一なペナルティスケーリングは効果がほとんどないが、内部係数範囲の制御はサンプルを著しく改善する。
非結合性制約の除去、バインディングの正規化、および残りの罰則のスケーリングは、同じ解決法予算(p=3.7e-11, n=56)において、平均的な生の制約違反を33.0から0.06に減少させる。
変数数保存制御はこの利得を問題のサイズではなく条件付けに帰着する。
第2に、手動のマージスコアをグラフニューラルネットワーク(GNN)に置き換える。
N=10では、R型を含む全てのソロモン族で100%実現可能である(チューニングされたヒューリスティックでは100%対80%)。
N=10,...,100の合計で、実現可能性は83%対69%で、GNNは85/90のインスタンスサイズのペアに縛られている。
N=80,100では差が大きく(p=0.002; 25/25ペア)、QUBOは5-6倍小さい。
最後に、ハードウェア実験は、固定論理変数数での条件付け効果を再現する: 実現可能なサンプルは13インスタンスで0.02%から39%に増加する。
局所探索による古典的な修復は、エンド・ツー・エンドのソリューションコストの基準となっている。
関連論文リスト
- Hybrid Quantum Neighborhood Selection: NISQ-Compatible Combinatorial Optimization via Stochastic Frontier Decomposition [0.0]
本研究は、Hybrid Quantum Neighborhood Selection (HQNS)を紹介する。
HQNSはステージ毎にFN活性変数のコンパクトフロンティアを選択し、残りを縮小QUBO係数に凍結する。
最大ダイバーシティ・サブセット選択問題(MDSSP)のHQNSを6つの尺度で最大1000まで評価した。
論文 参考訳（メタデータ） (2026-06-28T23:35:46Z) - Physics-Informed Residuals for Adaptive Mesh Refinement in Finite-Difference PDE Solvers [0.0]
本稿では,物理インフォームドニューラルネットワーク(PINN)を最終解法ではなく,適応メッシュ改良のためのオフグリッド残差プローブとして用いるハイブリッド戦略について検討する。
PINN残基はドメイン上でサンプリングされ、セルワイズインジケータに変換され、最終近似が有限差分ソルバによって計算される前に精製を誘導するために使用される。
論文 参考訳（メタデータ） (2026-06-01T16:47:21Z) - Quantum King-Ring Domination in Chess: A QAOA Approach [2.7474031534471384]
量子キングリング・ドミネーション(Quantum King-Ring Domination、QKRD)は、チェスの戦術的位置から派生したNISQスケールのベンチマークである。
我々はQAOA設計選択を体系的に評価し、制約保存ミキサーが標準ミキサーよりも約13ステップ早く収束していることを見出した。
内在的検証では、QAOAはグリーディを12.6%、ランダム選択を80.1%上回っている。
論文 参考訳（メタデータ） (2026-01-01T11:59:40Z) - INC: An Indirect Neural Corrector for Auto-Regressive Hybrid PDE Solvers [61.84396402100827]
本稿では,学習した補正を支配方程式に統合する間接ニューラルコレクタ(mathrmINC$)を提案する。
$mathrmINC$は、$t-1 + L$の順番でエラー増幅を減らし、$t$はタイムステップ、$L$はリプシッツ定数である。
大規模なベンチマークで$mathrmINC$をテストし、1Dカオスシステムから3D乱流まで、多くの異なる解法、神経バックボーン、テストケースをカバーした。
論文 参考訳（メタデータ） (2025-11-16T20:14:28Z) - Beyond Isotonization: Scalable Non-Crossing Quantile Estimation via Neural Networks for Student Growth Percentiles [0.0]
学生成長パーセンタイル(SGP)は、アメリカ合衆国の国家評価システムで広く採用されており、独立した量子レグレッションとポストホック補正が採用されている。
我々は、このアプローチが基本的な方法論上の矛盾を含んでいることを実証する: 独立に見積もられた、潜在的に交差する量子化の間には、単調性が必要である。
ニューラルネットワークを用いたマルチクエンタイル回帰(NNQR)を実用的な代替手段として提案する。
論文 参考訳（メタデータ） (2025-10-25T19:39:07Z) - RAYEN: Imposition of Hard Convex Constraints on Neural Networks [47.494620411594624]
RAYENは、ニューラルネットワークにハード凸制約を課すフレームワークである。
最先端のアルゴリズムの20倍から7468倍の高速化を実現している。
論文 参考訳（メタデータ） (2023-07-17T09:12:05Z) - Bounding the Width of Neural Networks via Coupled Initialization -- A
Worst Case Analysis [121.9821494461427]
2層ReLUネットワークに必要なニューロン数を著しく削減する方法を示す。
また、事前の作業を改善するための新しい下位境界を証明し、ある仮定の下では、最善を尽くすことができることを証明します。
論文 参考訳（メタデータ） (2022-06-26T06:51:31Z) - An Infinite-Feature Extension for Bayesian ReLU Nets That Fixes Their
Asymptotic Overconfidence [65.24701908364383]
ベイズ処理は、トレーニングデータを取り巻くReLUネットの過信を軽減することができる。
しかし、彼らから遠く離れたところでは、ReLUニューラルネットワーク(BNN)はいまだに不確実性を過小評価し過ぎている可能性がある。
事前学習した任意のReLU BNNに対して,低コストでemphpost-hocを適用可能であることを示す。
論文 参考訳（メタデータ） (2020-10-06T13:32:18Z) - AQD: Towards Accurate Fully-Quantized Object Detection [94.06347866374927]
本稿では,浮動小数点演算を除去するために,AQDと呼ばれる高精度な量子化オブジェクト検出ソリューションを提案する。
我々のAQDは、非常に低ビットのスキームの下での完全精度と比較して、同等またはそれ以上の性能を実現しています。
論文 参考訳（メタデータ） (2020-07-14T09:07:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。