論文の概要: Geometric Characteristics of Subproblems in Ising-Machine-Assisted Large Neighborhood Search
- arxiv url: http://arxiv.org/abs/2607.05014v1
- Date: Mon, 06 Jul 2026 12:56:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-07 22:26:30.154278
- Title: Geometric Characteristics of Subproblems in Ising-Machine-Assisted Large Neighborhood Search
- Title（参考訳）: Ising-Machine-Assisted Large Neborhood Searchにおけるサブプロブレムの幾何学的特徴
- Abstract要約: 大規模な2次非制約バイナリ最適化問題は、しばしば現在のIsingマシンの入力サイズ制限を超えている。
大近傍探索(LNS)は、制限されたサブプロブレムを逐次最適化することで、この困難を緩和する。
- 参考スコア（独自算出の注目度）: 0.7519872646378835
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Large-scale quadratic unconstrained binary optimization (QUBO) formulations of constrained combinatorial optimization problems often exceed the input-size limit of present Ising machines or suffer from degraded solution quality as the number of binary variables increases. Large neighborhood search (LNS) mitigates this difficulty by sequentially optimizing restricted subproblems, but the structural factors that distinguish subproblems beyond the number of binary variables remain insufficiently characterized. In this study, we examine vehicle routing problems and compare a construction based on the vehicle routes of the current solution, denoted by LNS-K, with a construction based on QUBO variables and constraint relations, denoted by LNS-Q, while controlling the number of binary variables in the subproblems. Under the tested conditions, LNS-K obtained shorter total distances than LNS-Q in the matched-size comparisons, and the position variance, a measure of the spatial spread of the selected customers, decreased during the iterations in LNS-K. These observations suggest that subproblem design for sequential optimization with Ising machines should consider not only subproblem size but also semantic and geometric structures inherited from the current solution.
- Abstract（参考訳）: 制約付き組合せ最適化問題の2次非制約バイナリ最適化(QUBO)の大規模定式化は、現在のIsingマシンの入力サイズ制限を超えたり、バイナリ変数の数が増えるにつれて解の質が低下することがある。
大近傍探索(LNS)は、制限されたサブプロブレムを逐次最適化することで、この困難を緩和するが、サブプロブレムを二進変数の数を超えて区別する構造的要因は依然として不十分である。
本研究では,車両経路問題を調査し,LNS-Kで表される現在のソリューションの車両経路に基づく構成と,LNS-Qで表されるQUBO変数と制約関係に基づく構成とを比較し,サブプロブレム内のバイナリ変数数を制御した。
実験条件下では,LNS-Kはマッチングサイズ比較においてLNS-Qよりも短い全距離を得た。
これらの観察から,Isingマシンを用いた逐次最適化のためのサブプロブレム設計は,サブプロブレムのサイズだけでなく,現在の解から受け継いだ意味的・幾何学的構造も考慮すべきであることが示唆された。
関連論文リスト
- Regularized Large Neighborhood Search [11.54620327711825]
大規模地域探索(LNS)を用いたNP難問の運用研究実践者
正規化LSS(RLNS)によりこのギャップを埋める。
アンダートロピック正規化では、RLNSが正確なブロックギブスサンプリングを行う。
論文 参考訳（メタデータ） (2026-06-01T14:16:18Z) - EQE-QAOA: An Equivalence-Preserving Qubit Efficient Framework for Combinatorial Optimization [54.05451096499336]
既存の技術は情報損失のコストで量子ビットの削減に依存しており、計算性能は劣化している。
等価保存量子ビット効率QAOAを提案し、性能を劣化させることなく必要なキュービット数を著しく削減する。
完全独立変数を持つ非制約問題を除いて,大規模最適化問題に広く適用可能であることを示す。
論文 参考訳（メタデータ） (2026-04-20T13:57:49Z) - Encoding Matters: Benchmarking Binary and D-ary Representations for Quantum Combinatorial Optimization [1.3824488054100907]
本研究では,D-ary Optimization (QUDO) を,高次元ヒルベルト空間において決定変数を直接符号化する代替の定式化として検討する。
本研究では,QUDOがトラベリングセールスマン問題,グラフカラー化,ジョブスケジューリング,Max-K-Cutなど,広範なペナルティ構築を必要とせずに,様々な問題クラスにおいて構造的制約を自然に捉えていることを示す。
本研究は、量子最適化のためのスケーラブルで表現力のある表現としてQUDOを強調し、近似比を一貫して改善し、等価回路深さでの計算オーバーヘッドを大幅に削減することを示した。
論文 参考訳（メタデータ） (2026-02-07T04:37:32Z) - Improving QAOA to find approximate QUBO solutions in O(1) shots [0.0]
本稿では,目標近似比(AR)を達成する確率を,正確な最適化を必要とせず考慮した修正fpQAOA方式を提案する。
この組み合わせは、問題の大きさが大きくなるにつれて、近似解を得るために必要なショットの中央値の減少につながることを実証する。
論文 参考訳（メタデータ） (2025-09-23T14:07:55Z) - A Gradient Meta-Learning Joint Optimization for Beamforming and Antenna Position in Pinching-Antenna Systems [63.213207442368294]
マルチ導波路ピンチアンテナシステムの新しい最適化設計について検討する。
提案したGML-JOアルゴリズムは,既存の最適化手法と比較して,様々な選択や性能に頑健である。
論文 参考訳（メタデータ） (2025-06-14T17:35:27Z) - Multi-level Neural Networks for high-dimensional parametric obstacle problems [0.0]
挑戦的(ランダムな)パラメトリック障害物問題の解法を開発し,解析した。
障害物問題の高次元解は、特別に構築された畳み込みニューラルネットワーク(CNN)によって近似される
数値実験は、この挑戦的な問題に対する最先端のパフォーマンスを示している。
論文 参考訳（メタデータ） (2025-04-07T12:50:56Z) - WANCO: Weak Adversarial Networks for Constrained Optimization problems [5.257895611010853]
まず、拡張ラグランジアン法を用いてミニマックス問題をミニマックス問題に変換する。
次に、それぞれ原始変数と双対変数を表すために、2つの(または複数の)ディープニューラルネットワークを使用します。
ニューラルネットワークのパラメータは、敵のプロセスによって訓練される。
論文 参考訳（メタデータ） (2024-07-04T05:37:48Z) - A DeepLearning Framework for Dynamic Estimation of Origin-Destination
Sequence [63.70447384033326]
本稿では,ODシーケンスの構造を推論する深層学習手法と,従来の数値最適化を導く構造制約を用いた統合手法を提案する。
実験の結果,ニューラルネットワークはODシーケンスの構造を効果的に推論し,数値最適化のための実用的な制約を提供することで,より良い結果が得られることがわかった。
論文 参考訳（メタデータ） (2023-07-11T04:58:45Z) - Qubit efficient quantum algorithms for the vehicle routing problem on
NISQ processors [48.68474702382697]
時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。
そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
論文 参考訳（メタデータ） (2023-06-14T13:44:35Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep
Unrolling [86.85697555068168]
2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。
特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。
PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
論文 参考訳（メタデータ） (2021-05-05T03:36:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。