論文の概要: Predictive Dual Smoothing for Column Generation

• arxiv url: http://arxiv.org/abs/2609.34740v1
• Date: Mon, 28 Sep 2026 09:33:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 03:13:55.769453
• Title: Predictive Dual Smoothing for Column Generation
• Title（参考訳）: カラム生成のための予測的デュアル平滑化
• Abstract要約: 本稿では、現在の二重解と将来の二重解の学習予測を組み合わせた予測的双対平滑化を導入し、有用な新しい変数への価格設定を行う。 ストック切断と一般化された割当て問題の実験は、予測的二重平滑化が生成カラムと壁面時間を大幅に短縮することを示している。
• 参考スコア（独自算出の注目度）: 15.07216665649792
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Solving large-scale linear programs efficiently is an important challenge in many optimization settings. A key technique is column generation, which alternates between solving the master problem over a restricted subset of the variables, and using a pricing subproblem to identify new variables to add. The pricing subproblem is guided by the dual solution of the current restricted master problem, but oscillations in these dual solutions can substantially slow convergence. Dual stabilization methods address this issue. Dual smoothing is a common stabilization method, which guides the pricing subproblem using a combination of the current dual solution and duals from previous iterations. However, while past dual solutions can stabilize the dual trajectory, they do not necessarily guide pricing towards useful new variables. We therefore introduce predictive dual smoothing, which instead combines the current dual solution with a learned prediction of future duals to steer pricing towards variables that are more useful in subsequent iterations. The predictor is trained offline using supervision extracted from standard column generation trajectories and is used only to modify the pricing subproblem's objective function, while exact reduced-cost checks and fallback pricing with the unsmoothed duals preserve correctness. Experiments on cutting stock and generalized assignment problems show that predictive dual smoothing substantially reduces generated columns and wall-clock time relative to standard column generation and existing classical and learned stabilization methods. These gains extend to out-of-distribution instance sizes, and predictive smoothing provides further improvements when combined with strong classical stabilization.
• Abstract（参考訳）: 大規模線形プログラムを効率的に解くことは、多くの最適化設定において重要な課題である。 キーとなるテクニックは列生成であり、変数の制限されたサブセットでマスター問題を解くことと、新しい変数を追加するための価格サブプロブレムを使用することを交互に行う。 価格サブプロブレムは、現在の制限マスター問題の双対解によって導かれるが、これらの双対解の振動は実質的に収束を遅くすることができる。 二重安定化法はこの問題に対処する。 デュアルスムーシング(Dual smoothing)は、現在の双対解と双対解の組み合わせを用いて価格サブプロブレムを導出する一般的な安定化法である。 しかし、過去の双対解は双対軌道を安定化させることができるが、必ずしも有用な新しい変数への価格設定を導くとは限らない。 したがって、予測二重平滑化を導入し、その代わりに現在の双対解と将来の双対の学習予測を組み合わせることで、その後の反復においてより有用な変数に対する価格設定を行う。 予測器は標準カラム生成トラジェクトリから抽出したトラジェクトリを用いてオフラインでトレーニングされ、価格サブプロブレムの目的関数を変更するのにのみ使用される。 その結果, 予測二重平滑化は, 従来のカラム生成法や既存の古典的, 学習的安定化法と比較して, 生成カラムと壁面時間を大幅に短縮することがわかった。 これらのゲインはアウト・オブ・ディストリビューションのインスタンスサイズにまで拡張され、予測スムーシングは、強い古典的安定化と組み合わせることでさらなる改善をもたらす。

関連論文リスト

• Safe Inference-Time Alignment via Lagrangian Reward Augmentation [10.37343121248029]
  推論時アライメントは、補助的な報酬信号を用いた復号中にフリーズ言語モデルを操る。 安全制約下での一般的な推論時間アライメントフレームワークであるLagrangian Reward Augmentation (LARA)を提案する。 シーケンスレベルの推論時間アライメント法とトークンレベルの推論時間アライメント法の両方でLARAを評価し,LARAが有用性と無害性のトレードオフを改善することを発見した。
  論文  参考訳（メタデータ） (2026-07-02T21:27:59Z)
• Scalable Deep Unfolding of Conic Optimizers [16.022960827366067]
  Deep Openfolding (DU)は、学習可能なコンポーネントを導入し、未学習のイテレーションを通じてそれらをトレーニングすることで、反復を加速します。 COSMOのような完全更新された円錐解法をアンロールすると、学習した円錐解法に先立つ2つの障害が露呈する。 行列のない暗黙差分法で最初の障害に対処し、メモリを$O(n2)$から$O(n)$に減らし、直接分解がメモリを使い果たしたスケールでのバックプロパゲーションを可能にする。
  論文  参考訳（メタデータ） (2026-06-11T18:58:09Z)
• One-Shot Safety Alignment for Large Language Models via Optimal Dualization [64.52223677468861]
  本稿では,制約付きアライメントを等価な非制約アライメント問題に還元する双対化の観点を提案する。 我々は、閉形式を持つ滑らかで凸な双対函数を事前に最適化する。 我々の戦略は、モデルベースと嗜好ベースの設定における2つの実用的なアルゴリズムに導かれる。
  論文  参考訳（メタデータ） (2024-05-29T22:12:52Z)
• Adaptive Stabilization Based on Machine Learning for Column Generation [28.874307606632588]
  カラム生成(CG)は大規模線形プログラムの解法として確立された手法である。 本稿では,1)最適解の精度予測のための機械学習手法,2)精度予測を効果的に活用する適応安定化手法を提案する。 グラフカラー化問題では,従来の手法に比べてコンバージェンス率が大幅に向上していることが示されている。
  論文  参考訳（メタデータ） (2024-05-18T06:52:50Z)
• High-dimensional Linear Bandits with Knapsacks [7.8856737627153874]
  本研究では,スパース推定をオンラインで行うハードしきい値アルゴリズムのオンライン版を開発する。 以下の構造的仮定のいずれかが、よりシャープな後悔境界である$tildeO(s_0 sqrtT)$に対して十分であることを示す。 副産物として、クナップサック制約を伴わない高次元のコンテキスト帯域に我々のフレームワークを適用することで、データポーラとデータリッチレジームの両方において最適な後悔率を回復する。
  論文  参考訳（メタデータ） (2023-11-02T15:40:33Z)
• Primal Dual Continual Learning: Balancing Stability and Plasticity through Adaptive Memory Allocation [86.8475564814154]
  制約付き最適化問題を直接実行することは可能かつ有益であることを示す。 メモリベースのメソッドでは、以前のタスクからのサンプルの小さなサブセットをリプレイバッファに格納できる。 両変数は,制約摂動に対する連続学習問題の最適値の感度を示す。
  論文  参考訳（メタデータ） (2023-09-29T21:23:27Z)
• Expressing linear equality constraints in feedforward neural networks [9.918927210224165]
  制約が課される予測補助変数を持つ新しいサドル点ラグランジアンを導入する。 補助変数の除去は、線形制約を満たすために導入されたラグランジュ乗算器上の双対最小化問題につながる。 ラグランジュパラメータの驚くべき解釈は、制約から生じる固定重みを持つ無限層隠蔽単位として得られる。
  論文  参考訳（メタデータ） (2022-11-08T17:39:05Z)
• Scaling the Convex Barrier with Sparse Dual Algorithms [141.4085318878354]
  本稿では,ニューラルネットワークバウンダリングのための2つの新しい2重アルゴリズムを提案する。 どちらの方法も新しい緩和の強さを回復する: 厳密さと線形分離オラクル。 実行時間のほんの一部で、既製のソルバよりも優れた境界を得ることができます。
  論文  参考訳（メタデータ） (2021-01-14T19:45:17Z)
• Competitive Mirror Descent [67.31015611281225]
  制約のある競合最適化には、制約の対象となる競合する目的を最小化しようとする複数のエージェントが含まれる。 本稿では, 競合ミラー降下法(CMD)を提案する。 特別の場合として、正の円錐上の問題に対する新しい競合乗法重みアルゴリズムを得る。
  論文  参考訳（メタデータ） (2020-06-17T22:11:35Z)
• Multi-Objective Matrix Normalization for Fine-grained Visual Recognition [153.49014114484424]
  双線形プールは細粒度視覚認識(FGVC)において大きな成功を収める 近年,行列パワー正規化は双線形特徴量において2次情報を安定化させることができることが示されている。 両線形表現を同時に正規化できる効率的な多目的行列正規化法(MOMN)を提案する。
  論文  参考訳（メタデータ） (2020-03-30T08:40:35Z)

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

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