論文の概要: Efficient Construction of Feasible Solutions in Column Generation using Quantum Annealing

• arxiv url: http://arxiv.org/abs/2503.24107v2
• Date: Tue, 19 Aug 2025 10:26:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-20 15:36:31.437301
• Title: Efficient Construction of Feasible Solutions in Column Generation using Quantum Annealing
• Title（参考訳）: 量子アニーリングによるカラム生成における有効解の効率的な構築
• Authors: Taisei Takabayashi, Naoki Maruyama, Takuma Yoshihara, Renichiro Haba, Masayuki Ohzeki,
• Abstract要約: カラム生成(CG)は制約付き0-1次計画問題の解法として用いられている。 本稿では,CG による連続緩和から実現可能な 0-1 ソリューションを構築するための後処理手法を提案する。
• 参考スコア（独自算出の注目度）: 0.4194295877935868
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Column generation (CG) has been used to solve constrained 0-1 quadratic programming problems. The pricing problem, which is iteratively solved in CG, can be reduced to an unconstrained 0-1 quadratic programming problem, allowing for the efficient application of quantum annealing (QA). The solutions obtained by CG are continuous relaxations, which cannot be practically used as feasible 0-1 solutions. In this paper, we propose a postprocessing method for constructing feasible 0-1 solutions from the continuous relaxations obtained through CG. The proposed technique consists of two phases: (i) mapping the continuous CG solution to a feasible 0-1 solution and (ii) applying a constraint-aware local search to improve that solution's quality. Numerical experiments on randomly generated problems demonstrate that CG with the proposed postprocessing yields solutions comparable to commercial solvers with significantly reduced computation time. Consequently, the postprocessing enables CG with QA to obtain high-quality approximate solutions faster.
• Abstract（参考訳）: カラム生成(CG)は制約付き0-1次計画問題の解法として用いられている。 CGで反復的に解かれる価格問題は、制約のない0-1二次計画問題に還元され、量子アニール(QA)の効率的な適用が可能となる。 CG で得られる解は連続緩和であり、現実的には 0-1 の解として利用できない。 本稿では,CGによる連続緩和から実現可能な0-1ソリューションを構築するための後処理手法を提案する。 提案手法は2段階からなる。 (i)連続CG解を実現可能な0-1解にマッピングし、 二 制約対応局所探索を適用して、その解の質を向上させること。 乱数生成問題に対する数値実験により,提案した後処理によるCGは,計算時間を大幅に短縮した商用解法に匹敵する解が得られることを示した。 その結果、後処理により、QAを用いたCGにより、高品質な近似解を高速に得ることができる。

関連論文リスト

• The Differentiable Feasibility Pump [49.55771920271201]
  本稿では,従来の実現可能性ポンプとその追随点の多くを,特定のパラメータを持つ勾配差アルゴリズムとみなすことができることを示す。 この再解釈の中心的な側面は、伝統的なアルゴリズムがそのコストに関して線形緩和の解を区別することを観察することである。
  論文  参考訳（メタデータ） (2024-11-05T22:26:51Z)
• Quantum Algorithms for Drone Mission Planning [0.0]
  ミッションプランニングはしばしば、一連のミッション目標を達成するためにISR(Intelligence, Surveillance and Reconnaissance)資産の使用を最適化する。 このような解を見つけることはNP-Hard問題であり、古典的なコンピュータでは効率的に解けないことが多い。 我々は、現在の古典的手法に対してスピードアップを提供する可能性のある、短期量子アルゴリズムについて検討する。
  論文  参考訳（メタデータ） (2024-09-27T10:58:25Z)
• OTClean: Data Cleaning for Conditional Independence Violations using Optimal Transport [51.6416022358349]
  sysは、条件付き独立性(CI)制約下でのデータ修復に最適な輸送理論を利用するフレームワークである。 我々はSinkhornの行列スケーリングアルゴリズムにインスパイアされた反復アルゴリズムを開発し、高次元および大規模データを効率的に処理する。
  論文  参考訳（メタデータ） (2024-03-04T18:23:55Z)
• A quantum algorithm for solving 0-1 Knapsack problems [0.0]
  与えられたインスタンスのすべての実現可能なソリューションを重ね合わせに生成するアプローチである"Quantum Tree Generator"を導入する。 新しい実行時計算手法を導入することで、既存のプラットフォームやシミュレータの範囲を超えて、メソッドのランタイムを予測できます。
  論文  参考訳（メタデータ） (2023-10-10T13:40:30Z)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。 新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。 導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
  論文  参考訳（メタデータ） (2023-06-10T08:25:16Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• Parabolic Relaxation for Quadratically-constrained Quadratic Programming -- Part II: Theoretical & Computational Results [6.355764634492975]
  我々は,2次制約付き二次プログラムに対する凸緩和と,ほぼ実現可能な解に対するペナル化放物緩和を導入する。 我々は, ある条件を満たす逐次点対点解から, ペナル化放物緩和収束は, カルーシュ・クーン最適正則性問題を満たすことを示した。
  論文  参考訳（メタデータ） (2022-08-07T02:58:04Z)
• Fast Convex Optimization for Two-Layer ReLU Networks: Equivalent Model Classes and Cone Decompositions [41.337814204665364]
  ReLUアクティベーション機能を持つ2層ニューラルネットワークの凸最適化アルゴリズムを開発した。 凸ゲート型ReLUモデルでは,ReLUトレーニング問題に対するデータ依存の近似バウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2022-02-02T23:50:53Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。 我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
  論文  参考訳（メタデータ） (2021-08-18T09:26:17Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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