論文の概要: SAG-Sep: Sparse Augmented Graphs and Onion-Guided Search for Rounded Capacity Cut Separation

• arxiv url: http://arxiv.org/abs/2610.37952v1
• Date: Tue, 27 Oct 2026 20:37:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-31 05:25:12.331354
• Title: SAG-Sep: Sparse Augmented Graphs and Onion-Guided Search for Rounded Capacity Cut Separation
• Title（参考訳）: SAG-Sep: Sparse Augmented Graphs and Onion-Guided Search for Rounded Capacity Cut separation (特集:SAG-Sep)
• Abstract要約: SAG-SepはRCC誘導サブセットのノードメンバシップを1つのフォワードパスで分数LPソリューションからスコアするセパレータである。 高い値の正確なRCCはネストされ、タマネギのようなサブセットファミリーに編成され、SAG-Sepのノードはネストの深さを追跡する。 以上の結果から, LP-aware sparse エンコーディングと高値切断のネスト構造は, 神経分離に有効な構造パターンであることが示唆された。
• 参考スコア（独自算出の注目度）: 14.395686798094808
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Rounded capacity cuts (RCCs) are among the most effective cuts for capacitated vehicle-routing relaxations, but exact separation is computationally prohibitive at scale. Existing heuristic and neural separators can be fast, but often fail to produce sufficiently many effective cuts within practical separation budgets. We introduce SAG-Sep, a separator that scores node membership in RCC-inducing subsets across vehicle-count levels from a fractional LP solution in a single encoder forward pass, avoiding the iterative predict-and-coarsen inference used by NeuralSEP-style separators. SAG-Sep encodes the LP solution as a Sparse Augmented Graph (SAG), adding flow-informed multi-hop edges that expose long-range routing structure without densifying attention. Beyond LP-aware sparse encoding, we observe that high-value exact RCCs are typically nested, organizing into onion-like subset families, and SAG-Sep's node scores track subset nesting depth. This motivates Onion-Sweep (OS), a training-free decoder that ranks customers by their scores, evaluates the RCC violation of every prefix of the ranking in one vectorized pass, and emits the most violated prefix of each replica together with a cross-replica family of nested proposals, converting independent node scores into structurally coordinated RCC candidates without a tuned threshold or probing band. On the NeuralSEP benchmark with N=1000 customer instances, SAG-Sep with OS reduces the average root gap by 17.7% relative to the strongest NeuralSEP baseline, while the single-pass SAG-Sep separator achieves a roughly 30-fold per-iteration neural separation speedup. Our findings suggest that LP-aware sparse encoding and the nested structure of high-value cuts are structural patterns worth leveraging in neural separation more broadly.
• Abstract（参考訳）: 丸みを帯びたキャパシティカット(RCC)は、静電容量の緩衝に最も効果的なカットであるが、正確な分離は大規模に計算的に禁止されている。 既存のヒューリスティックとニューラルセパレータは高速であるが、実際的な分離予算の中で十分な数の効果的な切断を達成できない場合が多い。 SAG-Sepは、1エンコーダフォワードパスにおける分数LPソリューションから車数レベルにまたがるRCC誘導サブセットのノードメンバシップをスコアするセパレータであり、NeuralSEPスタイルセパレータで使用される反復予測と相関推論を回避する。 SAG-Sep は LP ソリューションを Sparse Augmented Graph (SAG) としてエンコードし、フローインフォームされたマルチホップエッジを追加し、注意を増すことなく長距離ルーティング構造を公開する。 LPを意識したスパース符号化以外にも、高い値の正確なRCCはネストされ、タマネギのようなサブセットファミリーに編成され、SAG-Sepのノードはネスト深度を追跡する。 これは、顧客をスコアでランク付けするトレーニングフリーデコーダであるオニオン・スウィープ(OS)をモチベーションし、1つのベクトル化されたパスにおけるランキングのすべてのプレフィックスのRCC違反を評価し、各レプリカの最も違反したプレフィックスをネストされた提案のクロスレプリカファミリと共に出力し、独立ノードスコアを調整しきい値やプローブバンドなしで構造的に調整されたRCC候補に変換する。 N=1000の顧客インスタンスによるNeuralSEPベンチマークでは、OSによるSAG-Sepは、最強のNeuralSEPベースラインと比較して平均ルートギャップを17.7%削減し、シングルパスのSAG-Sepセパレータは、約30倍のニューラルネットワーク分離スピードアップを達成する。 以上の結果から, LP-aware sparse エンコーディングと高値切片のネスト構造は, より広範に神経分離に活用する価値のある構造パターンであることが示唆された。

関連論文リスト

• DISTA-Net++: Rethinking Infrared Small Target Unmixing Beyond Sub-Pixel Separation [50.40058918817059]
  長距離赤外線画像は、回折制限されたシグネチャが1つの識別不能なブロブに融合する密度の高いターゲットクラスタに対向する。 DisTA-Net++は2つの相乗的なメカニズムで動的に展開するバックボーンをアンカーする。 DisTA-Net++は、CSO-mAPが16.15%、62.96%の精度で、計算の6分の1に過ぎない。
  論文  参考訳（メタデータ） (2026-09-16T14:57:11Z)
• No More K-means: Single-Stage Sparse Coding for Efficient Multi-Vector Retrieval [51.43543998583709]
  SSR(Single-stage Sparse Retrieval)は、高価なクラスタリングを効率的なスパースコーディングに置き換えるパラダイムシフトである。 ColBERTv2と比較してインデックス処理時間を15倍短縮し、検索レイテンシを半減させ、同時に検索性能を向上させる。
  論文  参考訳（メタデータ） (2026-05-28T15:53:34Z)
• Factorizers for Distributed Sparse Block Codes [45.29870215671697]
  分散ブロック符号(SBC)を高速かつ高精度に分解する手法を提案する。 我々の反復分解器は、しきい値に基づく非線形活性化、条件付きランダムサンプリング、および $ell_infty$-based similarity metricを導入している。 CIFAR-100, ImageNet-1K, RAVENデータセット上での4つの深層CNNアーキテクチャの実現可能性を示す。
  論文  参考訳（メタデータ） (2023-03-24T12:31:48Z)
• COPS: Controlled Pruning Before Training Starts [68.8204255655161]
  最先端のディープニューラルネットワーク(DNN)プルーニング技術は、トレーニング開始前にワンショットで適用され、プルーニングスコアと呼ばれる単一の基準の助けを借りてスパースアーキテクチャを評価する。 この作業では、単一プルーニング基準に集中するのではなく、任意のGASを組み合わせてより強力なプルーニング戦略を構築するためのフレームワークを提供します。
  論文  参考訳（メタデータ） (2021-07-27T08:48:01Z)
• Towards Optimal Branching of Linear and Semidefinite Relaxations for Neural Network Robustness Certification [10.349616734896522]
  本研究では,ReLUニューラルネットワークの逆入力摂動に対する堅牢性を検証する。 入力不確実性集合を分割し,各部分の緩和を個別に解くために,分岐とバウンドのアプローチをとる。 提案手法は緩和誤差を低減し,ReLUアクティベーションの性質を活かしたパーティションを用いてLP緩和を行うことによって完全に誤差を除去することを示す。
  論文  参考訳（メタデータ） (2021-01-22T19:36:40Z)

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

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