論文の概要: Imperfect Is Perfect: Learned Column Prefilling for Branch-Price-and-Cut

• arxiv url: http://arxiv.org/abs/2610.21001v1
• Date: Wed, 14 Oct 2026 22:38:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-16 19:13:16.100386
• Title: Imperfect Is Perfect: Learned Column Prefilling for Branch-Price-and-Cut
• Title（参考訳）: ブランチ・プライス・アンド・カットのためのコラム・プレフィルは完璧ではない
• Abstract要約: カラムが正しい方法で不完全な場合、その逆を示す。 マスターの外にある任意の最適解に属さない通常のルートのプールは、ルートを高速化する。 列が最適である必要はないので、列を生成することは学習課題になる。
• 参考スコア（独自算出の注目度）: 13.887538587894355
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Column generation folklore warns that initial columns hurt: a warm start may bias the dual and slow the root of branch-price-and-cut. We show the opposite once the columns are imperfect in the right way. Preloading the support of the optimal root LP, the best columns one could know in advance, fails to finish on half of our hardest instances; a pool of ordinary routes that need not belong to any optimal solution, held outside the master and priced at the current smoothed dual, speeds the root up. Because the columns need not be optimal, producing them becomes a learning task: a neural edge scorer guides a constructive generator that builds the pool in seconds. A second network predicts the initial center of Wentges smoothing from the instance file, and with it the direction of the smoothed pricing queries; the solver's own updates run unchanged. With prefill and center in place, exact pricing dominates root pricing time, so we rebuild bucket-graph labeling around its dominance test for the GPU and certify on the CPU. Inside RouteOpt, the state-of-the-art exact solver for capacitated vehicle routing, the pipeline reaches the same certified root bound in 13.2% of vanilla RouteOpt's root pricing time over 95 instances with 300 to 1000 customers, prefill alone in 26.1%, and 17.5 times faster in the best case. In an exact branch-price-and-cut solver for unrelated parallel machine scheduling, prefill with smoothing and the learned center certifies all 25 benchmark instances, 12 times faster than the solver's own column generation, which certifies 20 of them.
• Abstract（参考訳）: カラム生成のフォークロアは、初期カラムが傷つくと警告する: 温かいスタートは、二倍に偏り、分岐価格とカットの根元を遅くする可能性がある。 カラムが正しい方法で不完全な場合、その逆を示す。 最適なルートLPのサポートをプレロードすると、前もって知ることのできる最高の列が、最も難しいインスタンスの半分で終了する。 ニューラルネットワークのエッジスコアラは、プールを数秒で構築する建設的なジェネレータをガイドします。 第2のネットワークは、インスタンスファイルからスムーズなWentgesの初期中心を予測し、スムーズな価格クエリの方向を予測します。 プリフィルとセンターの配置により、正確な価格設定がルート価格時間を支配しているため、GPUの優位性テストを中心にバケットグラフラベリングを再構築し、CPU上で認証します。 RouteOptの内部では、静電容量化された車両ルーティングのための最先端の正確な解法であり、バニラ・ルートオプトのルート価格の13.2%で、300から1000人の顧客が95インスタンス以上、26.1%で単独でプリフィルし、ベストケースでは17.5倍の速さで、同じ認定されたルートに達する。 非関連並列マシンスケジューリングのための正確なブランチ・プライス・アンド・カット・ソルバでは、スムーズなプリフィルと学習センタが25のベンチマークインスタンス全てを認証し、20の認証を行う。

関連論文リスト

• Learning Warm Starts for the Simplex Method from Measured Solver Cost [0.06363400715351394]
  強い教師付き基底予測器は、二重単純体の反復の3分の2を除去するが、その時間の3分の1しか除去しない。 良いスタートによって取り除かれたイテレーションは安価になりがちで、最適なベースへの近さはコストによってランク付けされません。 そこで,CostStartを紹介した。これは教師付き予測をベースとして,測定した命令数に基づいて小さなポリシーを訓練する。
  論文  参考訳（メタデータ） (2026-10-14T20:19:58Z)
• Calibrated $α$-Barycenters for Multiobjective $f$-Divergence Optimization [9.096942663106747]
  CAL-$-MODMは非線形予測器を1つのバリセンターに集約する。 CAL-p2はL-BFGSより3.15タイム、Direct-TRより1.10タイムという中央値のペアアップを実現している。
  論文  参考訳（メタデータ） (2026-10-12T14:02:15Z)
• SquidAgent: Parallelize Wisely, Coordinate Efficiently [66.64544354706031]
  LLMベースのエージェントは複雑なマルチステップタスクを解決するが、シーケンシャルな実行にはかなりの遅延が発生する。 クリティカルパスコストに加えて、再探索とアライメントオーバーヘッドが対応するシリアルコストよりも低い場合にのみ、レイヤを並列化すべきである。 SquidAgentは平均スループット2.2$times$、平均スループット2.6$times$、最強のマルチエージェントベースラインよりも2.0$times$のスループット改善を実現している。
  論文  参考訳（メタデータ） (2026-10-06T16:35:28Z)
• HEAT: Faster Fully Homomorphic Inference via Approximations-Weights Co-Adaptation [56.14416807766864]
  同型暗号化により、サーバは暗号化されたユーザープロンプト上で言語モデルを直接実行することができる。 既存のアプローチでは、各サイトのエラー許容度を調整するのではなく、モデル全体のイテレーションカウントを均一に修正する。 非線形反復回数を学習可能にする微調整法であるHAT(Hymomorphic Encryption-Aware Training)を導入する。
  論文  参考訳（メタデータ） (2026-09-01T18:02:02Z)
• Fast LapSum: Exact Differentiable Top-k at Million Scale [10.106073328854459]
  Fast LapSumは、GPUソルバがソート後に線形時間で実行される、正確な予算のソフトトップ$k$プリミティブである。 我々はFast LapSumを、トレーニングループ内で数百万の座標を操作する要求のある2つのアプリケーション上でデモした。
  論文  参考訳（メタデータ） (2026-08-07T07:44:35Z)
• GridProbe: Posterior-Probing for Adaptive Test-Time Compute in Long-Video VLMs [3.9266376632068485]
  GridProbeは、効率的なトレーニング不要な後処理推論パラダイムである。 解答空間における証拠は、凍結したVLM自身の推論を用いて得られる。 疑似関連フレームを適応的に選択し、精度の損失が少なくて、準四分法的な注意コストをもたらす。
  論文  参考訳（メタデータ） (2026-05-11T15:57:46Z)
• SVG-EAR: Parameter-Free Linear Compensation for Sparse Video Generation via Error-aware Routing [77.91660464664615]
  Diffusion Transformers (DiTs) はビデオ生成において主要なバックボーンとなっているが、その二次的注意コストは依然として大きなボトルネックとなっている。 本稿では,不足しているコントリビューションをトレーニングなしで回収できることを示す。 パラメータフリーな線形補償分岐であるSVG-EARを導入する。
  論文  参考訳（メタデータ） (2026-03-09T22:15:31Z)
• Finding Transformer Circuits with Edge Pruning [71.12127707678961]
  自動回路発見の効率的かつスケーラブルなソリューションとしてエッジプルーニングを提案する。 本手法は,従来の手法に比べてエッジ数の半分未満のGPT-2の回路を探索する。 その効率のおかげで、Edge PruningをCodeLlama-13Bにスケールしました。
  論文  参考訳（メタデータ） (2024-06-24T16:40:54Z)
• Genetic column generation: Fast computation of high-dimensional multi-marginal optimal transport problems [0.0]
  CG内の二重状態が「逆」の役割を果たすMMOT用に作られた遺伝的学習法を使用します。 最大120のグリッドポイントと最大30のマージンを持つベンチマーク問題に対して,本手法は常に精度を見出した。
  論文  参考訳（メタデータ） (2021-03-23T15:24:50Z)

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

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