論文の概要: DualCert: A Solver for the Traveling Salesman Problem with Constraint-Coupled Learning
- arxiv url: http://arxiv.org/abs/2608.09042v1
- Date: Mon, 10 Aug 2026 02:48:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-11 19:16:37.045142
- Title: DualCert: A Solver for the Traveling Salesman Problem with Constraint-Coupled Learning
- Title（参考訳）: DualCert: 制約結合学習によるトラベリングセールスマン問題の解法
- Abstract要約: 大規模走行セールスマン問題 (TSP) では、出力の妥当性を保ちながら限られた計算を割り当てることが求められる。
DualCertは、Emphconstraint-coupled learningを導入し、現在の等級方程式と動的に分離されたサブチュール除去制約がそれぞれの学習遷移を定義する。
1000の保持されたTSP1000インスタンス上で、DualCertは、Lin--Kernighan--Helsgaunバージョン3(LKH-3)からの平均的なツアーコストギャップ(0.0573%)をインスタンス当たり9.55秒のバッチ修正秒で達成した。
- 参考スコア（独自算出の注目度）: 4.941039246565574
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Large traveling salesman problem (TSP) instances require a solver to allocate limited computation while preserving the validity of its outputs. Existing neural--operations-research (OR) hybrids predict guidance without requiring learned transitions to satisfy constraints discovered during search. DualCert introduces \emph{constraint-coupled learning}, in which current degree equations and dynamically separated subtour-elimination constraints (SECs) define each learned transition. At each refinement, the degree equations and selected, strictly satisfied SEC equations, with positive slacks, define an iterate-dependent primal-slack Karush--Kuhn--Tucker (KKT) manifold. Repaired dual variables and violated SEC rows define a local cost field. An exact constrained mirror-descent step maps each finite state to a positive state on the same manifold. Where selected rows and deterministic ties remain fixed, implicit differentiation maps parameter perturbations into the manifold tangent space and reuses the forward constraint operator for the local-cost-field derivative. The terminal edge state allocates computation across Held--Karp ascent, candidate-graph edge tests, and tour construction under a fixed budget. Deterministic verification recomputes original costs and accepts only verified candidate-graph lower bounds and edge decisions. On 1,000 held-out TSP1000 instances, DualCert attains a mean tour-cost gap of \(0.0573\%\) from Lin--Kernighan--Helsgaun version 3 (LKH-3) reference tours in \(9.55\) batch-amortized seconds per instance. It returns a verified candidate-graph lower bound for every instance and achieves \(81.46\%\) edge-decision coverage. The mean gap is \(67.1\%\) smaller than the reported NeuroLKH mean gap. Thus, optimization constraints govern learning, while deterministic verification preserves output validity.
- Abstract（参考訳）: 大規模走行セールスマン問題 (TSP) では、出力の妥当性を保ちながら限られた計算を割り当てることが求められる。
既存のニューラル・オペレーション・リサーチ(OR)ハイブリッドは、探索中に発見された制約を満たすために学習した遷移を必要とせずにガイダンスを予測する。
DualCert は \emph{constraint-coupled learning} を導入している。
各洗練度において、厳密に満たされたSEC方程式と正のスラックスを持つ次数方程式は、イテレート依存の原始スラックカルーシュ-クーン-タッカー多様体(KKT)を定義する。
二重変数の修復とSECの行の違反は、局所的なコストフィールドを定義する。
厳密な制約付きミラー・ディフレッシュステップは、各有限状態を同じ多様体上の正の状態に写す。
選択された行と決定論的関係が固定されている場合、暗黙の微分写像は、多様体接空間への摂動をパラメータとし、局所コスト場微分に対するフォワード制約作用素を再利用する。
端末エッジ状態は、Held--Karp上昇、候補グラフエッジテスト、およびツアー構築を固定予算で割り当てる。
決定論的検証は、元のコストを再計算し、検証された候補グラフの下限とエッジ決定のみを受け入れる。
1000の保持されたTSP1000インスタンスでは、DualCertはLin--Kernighan--Helsgaunバージョン3(LKH-3)から1インスタンスあたり9.55\のバッチアモテート秒で、平均的なツアーコストギャップ(0.0573\%\)を達成している。
検証済みの候補グラフの下限を各インスタンスに対して返し、(81.46\%\)エッジ決定カバレッジを達成する。
平均ギャップは、報告されたNeuroLKH平均ギャップよりも小さい(67.1\%\)。
したがって、最適化制約は学習を制御し、決定論的検証は出力の妥当性を保持する。
関連論文リスト
- Statistical Symmetry Release for Equivariant Quantum Learning [12.042012916861829]
ハード対称性の制約はモデルの複雑さを減少させるが、ラベル情報を消去することもできる。
統計的対称性の解放は、有限データと量子測度がそのような制約を緩和することを正当化する場合を決定する。
論文 参考訳（メタデータ） (2026-09-10T12:38:27Z) - Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。
スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
論文 参考訳（メタデータ） (2026-09-07T01:38:41Z) - The Cost of Adaptivity: Matching Lower Bounds Across Learning Problems [1.0742675209112622]
我々はスライス正規化ミニマックス比を用いてニュアンス適応を定式化する。
また、事前発表された1つのガウスクエリから任意のポストホックインスペクションへ拡張するコストを定義する。
論文 参考訳（メタデータ） (2026-08-09T17:19:11Z) - PAC-Bayesian Certificates for Quadratic Closed-Loop Control [0.0]
PAC-ベイズ境界は、データ依存予測器に対する有限サンプル保証を提供する。
学習に基づく制御にそれらを適用することは、自然な目的が二次的な軌道コストであるため困難である。
PAC-Bayes-Chernoff 証明書の集合を,実現可能な閉ループ応答に対する後部分布として提供する。
論文 参考訳（メタデータ） (2026-06-26T17:24:21Z) - A Barrier-Metric First-Order Method for Linearly Constrained Bilevel Optimization [1.4323566945483492]
固定された多面体下実現可能性集合を用いた双レベル最適化について検討した。
アクティブセットの変更は、上位の目的を非滑らかにすることができる。
既存の過次法は、典型的には低いヘッセン逆数や等価線型解を必要とする。
論文 参考訳（メタデータ） (2026-05-12T03:44:08Z) - The Extrapolation Cliff in On-Policy Distillation of Near-Deterministic Structured Outputs [52.709361620508595]
ListOPDは、パラメータの5分の1で8B-SFTベースラインで、学生をドメイン内に持ち込む。
Amazon Fashionでは、3つの事前登録テスト — 細粒度崖間隔テスト、小さなクリップのクロス予測 — がロックされた予測ウィンドウ内に落下し、グリッド解像度以下のクローズドフォーム予測に一致する小さなクリップ値が設定されている。
論文 参考訳（メタデータ） (2026-05-09T06:48:00Z) - Adaptive Test-Time Compute Allocation for Reasoning LLMs via Constrained Policy Optimization [18.737087162461563]
テストタイムの計算スケーリングは、大規模言語モデルのパフォーマンスを向上させるための強力なレバーとなっている。
しかし、これらのテクニックを有限の推論予算の下で展開するには、現在のシステムがほとんど無視する決定が必要である。
我々はこれを制約付き最適化問題(平均計算予算の予測精度を最大化する)として定式化し、2段階のソルベ・テン・ラーンパイプラインで解いた。
論文 参考訳（メタデータ） (2026-04-16T10:39:22Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - Fully Stochastic Trust-Region Sequential Quadratic Programming for
Equality-Constrained Optimization Problems [62.83783246648714]
目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。
アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
論文 参考訳（メタデータ） (2022-11-29T05:52:17Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - Regret and Cumulative Constraint Violation Analysis for Online Convex
Optimization with Long Term Constraints [24.97580261894342]
本稿では,長期的制約を伴うオンライン凸最適化について考察する。
新たなアルゴリズムが最初に提案され、静的後悔のために$mathcalO(Tmaxc,1-c)$bound、累積制約違反のために$mathcalO(T(1-c)/2)$boundを達成する。
論文 参考訳（メタデータ） (2021-06-09T15:18:06Z) - Upper Confidence Primal-Dual Reinforcement Learning for CMDP with
Adversarial Loss [145.54544979467872]
マルコフ決定過程(CMDP)に対するオンライン学習の検討
本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。
我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
論文 参考訳（メタデータ） (2020-03-02T05:02:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。