論文の概要: Learned Pairwise Deep Dual-Optimal Inequalities for Stabilizing Column Generation
- arxiv url: http://arxiv.org/abs/2607.13373v1
- Date: Wed, 15 Jul 2026 01:35:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-16 16:39:12.620293
- Title: Learned Pairwise Deep Dual-Optimal Inequalities for Stabilizing Column Generation
- Title（参考訳）: カラム生成の安定化のためのPairwise Deep Dual-Optimal不等式
- Abstract要約: L-PDDOIs(Learled pairwise Deep-optimal inequality)は、二変数間のペアワイズ順序を予測し、主問題に直接組み込む学習フレームワークである。
予測された関係間の競合や冗長性はパフォーマンスを損なう可能性があるため、グラフベースの後処理フィルタはデプロイ前に設定された候補を圧縮する。
静電容量化車両ルーティング問題と時間窓による車両ルーティング問題の主なテストセットでは、L-PDDOIの直接展開により、それぞれ平均ルートCG時間を89.7%、93.9%削減する。
- 参考スコア（独自算出の注目度）: 14.46729903150912
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Column generation (CG) is central to many large-scale optimization algorithms, including branch-price-and-cut methods for vehicle routing problems, but unstable dual solutions can substantially slow its convergence. Existing deep dual-optimal inequalities can reduce this instability by restricting the dual space. Their construction, however, typically relies on problem-specific exchange arguments that are difficult to establish for routing problems with capacity limits, time windows, and other resource constraints. We introduce learned pairwise deep dual-optimal inequalities (L-PDDOIs), a learning framework that predicts pairwise orderings between dual variables and incorporates their primal counterparts directly into the master problem. To construct training labels, the framework samples optimal dual solutions and selects pairwise order relations that hold simultaneously on a sufficiently large common subset of the samples. A classifier then assigns a score to each candidate relation. Because conflicts and redundancies among the predicted relations can impair performance, graph-based postprocessing filters and compresses the candidate set before deployment. We further introduce a recovery procedure that selectively relaxes learned inequalities and provides a certificate when the baseline CG bound has been restored. On the main test sets for the capacitated vehicle routing problem and the vehicle routing problem with time windows, direct deployment of L-PDDOIs reduces the geometric mean root CG time by 89.7% and 93.9%, respectively, while incurring mean bound losses of only 1.3% and 0.5%. The recovery procedure retains corresponding time reductions of 54.8% and 83.1%, respectively, while guaranteeing no loss in the CG bound.
- Abstract（参考訳）: カラム生成(CG)は、車両ルーティング問題に対する分岐価格とカット法を含む多くの大規模最適化アルゴリズムの中心であるが、不安定な双対解はその収束を著しく遅らせる可能性がある。
既存の双対最適不等式は、双対空間を制限することによってこの不安定性を減少させることができる。
しかし、それらの構成は典型的には、容量制限や時間窓、その他のリソース制約のあるルーティング問題を確立するのが難しい問題固有の交換引数に依存している。
L-PDDOIs(Learled pairwise Deep-optimal inequality)は、二変数間のペアワイズ順序を予測し、主問題に直接組み込む学習フレームワークである。
トレーニングラベルを構築するために、フレームワークは最適な双対解をサンプリングし、サンプルの十分な大きな共通部分集合に同時に保持するペアの順序関係を選択する。
次に、分類器が各候補関係にスコアを割り当てる。
予測された関係間の競合や冗長性はパフォーマンスを損なう可能性があるため、グラフベースの後処理フィルタはデプロイ前に設定された候補を圧縮する。
さらに、学習した不等式を選択的に緩和する回復手順を導入し、ベースラインCG境界が復元されたときに証明書を提供する。
容量化車両ルーティング問題と時間窓による車両ルーティング問題の主なテストセットでは、L-PDDOIの直接展開により、幾何学的平均CG時間をそれぞれ89.7%と93.9%削減し、平均境界損失は1.3%と0.5%に留まる。
回復手順は、それぞれ54.8%と83.1%の時間短縮を保持し、CGバウンドの損失は保証されない。
関連論文リスト
- RecGPT-Mobile-V2 Technical Report [22.10290138930905]
RecGPT-Mobile-V2は、意図的品質と実行効率をステージド設計の目的として扱うエンドツーエンドフレームワークである。
このフレームワークは異種間相互作用をエビデンス保存軌道に変換し、ドメイン適応と教師付きアライメントを通じてレコメンデーションネイティブ基盤を確立する。
オンライン検索分析では、クエリリコールチャネルは、確立されたリコールチャネルによってサーフェスされたインベントリに補完されるインベントリを検索することを示している。
論文 参考訳（メタデータ） (2026-08-25T09:23:17Z) - Closed-Form Spectral Regularization for Multi-Task Model Merging [96.82449201305234]
モデルマージは、個別に調整された複数の専門家をトレーニングデータなしで単一のマルチタスクモデルに結合する。
State-of-the-art merging method formulate merging as a layer-wise interference problem。
本稿では,逐次降下の勾配-流路に一致するソフト指数フィルタを組み合わせた閉形式手法SWUDIを提案する。
論文 参考訳（メタデータ） (2026-06-05T14:00:47Z) - Improving Search Agent with One Line of Code [68.58667107354253]
ツールベースのエージェント強化学習(TARL)は,検索エージェントが外部ツールと対話できるようにトレーニングするための,有望なパラダイムとして登場した。
textbfSearch textbfAgent textbfPolicy textbfOptimization (textbfSAPO)を提案する。
論文 参考訳（メタデータ） (2026-03-10T04:07:39Z) - GPU-friendly and Linearly Convergent First-order Methods for Certifying Optimal $k$-sparse GLMs [7.079949618914198]
ブランチ・アンド・バウンド(BnB)フレームワークは、パースペクティブ・リラクゼーションを使って最適性を証明できる。
これらの緩和を解く既存の手法は計算集約的であり、スケーラビリティを制限している。
我々は線形収束性と計算効率の両立した近位フレームワークを開発する。
論文 参考訳（メタデータ） (2026-03-01T22:26:09Z) - RaCoT: Plug-and-Play Contrastive Example Generation Mechanism for Enhanced LLM Reasoning Reliability [12.67288560758937]
本稿では,RaCoT(Retrieval-aware Contrastive-of-Thought)を提案する。
RaCoTは、解答の発散を決定する重要な詳細に積極的に焦点を合わせるようモデルに誘導する。
論文 参考訳（メタデータ） (2025-10-26T15:06:44Z) - Scalable First-order Method for Certifying Optimal k-Sparse GLMs [9.613635592922174]
そこで本研究では,BnBフレームワークの視点緩和を解くために,一階近位勾配アルゴリズムを提案する。
提案手法は双有界計算を著しく高速化し,大規模問題に対する最適性証明の提供に極めて有効であることを示す。
論文 参考訳（メタデータ） (2025-02-13T17:14:18Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳（メタデータ） (2023-10-20T12:45:12Z) - Enhancing Column Generation by Reinforcement Learning-Based
Hyper-Heuristic for Vehicle Routing and Scheduling Problems [9.203492057735074]
カラム生成(CG)は変数を動的に生成することで大規模問題を解決する重要な手法である。
CGの性能を高めるために,RLHHと呼ばれる強化学習に基づく超ヒューリスティックフレームワークを提案する。
論文 参考訳（メタデータ） (2023-10-15T00:05:50Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality [131.45028999325797]
ディスカウント型MDPのための2倍堅牢なオフポリチックAC(DR-Off-PAC)を開発した。
DR-Off-PACは、俳優と批評家の両方が一定のステップで同時に更新される単一のタイムスケール構造を採用しています。
有限時間収束速度を研究し, dr-off-pac のサンプル複雑性を特徴とし, $epsilon$-accurate optimal policy を得る。
論文 参考訳（メタデータ） (2021-02-23T18:56:13Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。