論文の概要: Formulating Multistage Cutting Stock Problems as QUBO

• arxiv url: http://arxiv.org/abs/2609.14070v1
• Date: Sat, 12 Sep 2026 17:38:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-16 07:15:05.650611
• Title: Formulating Multistage Cutting Stock Problems as QUBO
• Title（参考訳）: QUBOとしての多段切削ストック問題
• Abstract要約: ギロチンカットを用いた多段切削ストック問題の制限版に対する線形計画式を提案する。 使用可能な残余で問題をモデル化する上で、可能なメリットがあることが示されています。
• 参考スコア（独自算出の注目度）: 3.736283816064367
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Cutting stock problems are of large relevance to a variety of industry branches. Here, we present a linear programming formulation for a restricted version of the multistage 2D cutting stock problem with Guillotine cuts and test it on published benchmark instances. After this, we derive a non-exact reformulation in quadratic unconstrained binary optimization (QUBO) form via unbalanced penalization, which we show to have possible benefits in modeling the problem with usable leftovers. This work mainly considers the restricted formulation, in which the dimensions of each cut are determined by those of a single required piece. We further discuss how the approach can be extended to the unrestricted problem, which allows more general cutting patterns involving cuts with dimensions of multiple required pieces and naturally gives rise to quadratic terms in the inequalities of the problem formulation. We showcase solutions via a Simulated Annealing solver for the restricted problem class, where we mainly study the performance of the iterative augmented Lagrangian method. We also discuss possible applications of Quantum Annealing in this setting, as a strong motivation to research QUBO formulations.
• Abstract（参考訳）: 株式の問題は様々な産業分野に大きく関係している。 ここでは,ギロチンカットを用いた多段切削ストック問題の限定バージョンに対する線形プログラミングの定式化と,それを公開ベンチマークインスタンス上で検証する。 その後、不均衡なペナル化による2次非制約バイナリ最適化(QUBO)の非コンパクトな修正が導出され、使用可能な残余で問題をモデル化する上での利点が示される。 この研究は、主に制限された定式化を考慮し、各カットの寸法は1つの必要なピースによって決定される。 さらに、この手法が制限のない問題にどのように拡張できるかについても論じる。これにより、複数の必要部分の次元を持つ切断を含むより一般的な切断パターンが可能となり、問題定式化の不等式において自然に二次項が生じる。 制限された問題クラスに対するシミュレートされたアニーリング解法による解を示し、主に反復的なラグランジアン法の性能について研究する。 我々はまた、QUBOの定式化の研究の強い動機として、この設定における量子アニールの応用の可能性についても論じる。

関連論文リスト

• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。 既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。 これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-21T17:15:48Z)
• Pushing the Limits of Large Language Model Quantization via the Linearity Theorem [71.3332971315821]
  本稿では,階層的$ell$再構成誤差と量子化によるモデルパープレキシティ増加との直接的な関係を確立する「線形定理」を提案する。 この知見は,(1)アダマール回転とHIGGSと呼ばれるMSE最適格子を用いた単純なデータフリーLCM量子化法,(2)非一様層ごとの量子化レベルを求める問題に対する最適解の2つの新しい応用を可能にする。
  論文  参考訳（メタデータ） (2024-11-26T15:35:44Z)
• Solving the Product Breakdown Structure Problem with constrained QAOA [0.0]
  本稿では,産業関連製品ブレークダウン構造問題の解法を提案する。 我々の解は制約付きQAOAに基づいており、これは構成上、問題制約によって禁止される解を表すヒルベルト空間の一部を探ることはない。 実験により,本手法はスケーリング行動に非常に有利なだけでなく,バレン高原の負の効果も抑制できることが示された。
  論文  参考訳（メタデータ） (2024-06-21T15:15:02Z)
• Optimized QUBO formulation methods for quantum computing [0.4999814847776097]
  実世界の金融シナリオにインスパイアされたNPハード最適化問題に対して,我々の手法を適用する方法について述べる。 2つのD波量子異方体にこの問題の事例を提出し、これらのシナリオで使用される標準手法と新しい手法の性能を比較した。
  論文  参考訳（メタデータ） (2024-06-11T19:59:05Z)
• 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)
• Deriving Compact QUBO Models via Multilevel Constraint Transformation [0.8192907805418583]
  そこで本稿では,QUBOモデルに基づくMLCTS(Multilevel Constraint Transformation Scheme)を提案する。 概念実証では、後者の問題に対する2つのQUBOモデルの性能を、汎用ソフトウェアベースソルバとハードウェアベースのQUBOソルバで比較する。 MLCTS由来のモデルは、ハードウェアベースのアプローチで最大7倍のインスタンスを解くことで、両方のソルバのパフォーマンスを著しく向上させる。
  論文  参考訳（メタデータ） (2024-04-04T17:34:08Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  断片的な離散化は既存の離散化問題と矛盾しないことを示す。 この理論を2つの画像のマッチング問題に適用する。
  論文  参考訳（メタデータ） (2021-07-13T12:31:06Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Competitive Mirror Descent [67.31015611281225]
  制約のある競合最適化には、制約の対象となる競合する目的を最小化しようとする複数のエージェントが含まれる。 本稿では, 競合ミラー降下法(CMD)を提案する。 特別の場合として、正の円錐上の問題に対する新しい競合乗法重みアルゴリズムを得る。
  論文  参考訳（メタデータ） (2020-06-17T22:11:35Z)

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

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