論文の概要: SeqTG: Scalable Combinatorial Test Generation via Sequential Integer Linear Programming

• arxiv url: http://arxiv.org/abs/2603.13963v1
• Date: Sat, 14 Mar 2026 14:18:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-17 16:19:35.512574
• Title: SeqTG: Scalable Combinatorial Test Generation via Sequential Integer Linear Programming
• Title（参考訳）: SeqTG: 逐次整数線形プログラミングによるスケーラブルなコンビネーションテスト生成
• Authors: Sitong Yang, Wanying Bao, Yinyin Song, Yueting Cheng, Qian Li, Chao Wei,
• Abstract要約: 複雑な制約下での最小限のカバレッジ配列は、未解決のNPハードチャレンジのままである。 現在の強欲なアルゴリズムは、非常に欲求的だが、深刻なリターンの低下に苦しむ。それらは、初期相互作用を効率的にカバーするが、最後のいくつかの困難なペアをまとめるのに苦労するときに、肥大した冗長なテストスイートを生成する。 シークエンシャル線形プログラミング(ILP)に基づくスケーラブルなフレームワークであるSeqTGを紹介する。 本稿では,SeqTGが最新の肥大を効果的に根絶し,最先端のテストスイートのコンパクト性と厳密な制約順守を実現していることを示す。
• 参考スコア（独自算出の注目度）: 9.092621106269503
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Combinatorial Testing (CT) is essential for detecting interaction-triggered faults, yet generating minimal Covering Arrays under complex constraints remains an unresolved NP-hard challenge. Current greedy algorithms are highly scalable but suffer from severe ``diminishing returns'': they efficiently cover initial interactions but produce bloated, redundant test suites when struggling to pack the final few difficult pairs. While exact mathematical programming could theoretically address this inefficiency, it has historically been intractable due to combinatorial explosion. In this paper, we pioneer the application of exact mathematical modeling to CT by introducing SeqTG, a scalable framework based on Sequential Integer Linear Programming (ILP). To circumvent the scalability barrier, SeqTG employs a novel Warm-Start strategy: a rapid greedy initialization first clears the ``easy'' interactions, allowing the rigorous ILP solver to exclusively optimize the fragmented, difficult-to-cover remainder. The pipeline operates in three stages: (1) a Constraint-First phase grouping must-include requirements via graph partitioning; (2) an Incremental Optimization phase targeting the remaining interactions with sequential ILP; and (3) a Global Minimization phase eliminating redundancies via set-covering. Extensive evaluations across standard benchmarks and 200 large-scale configurations validate the framework's efficacy. The results demonstrate that SeqTG effectively eradicates late-stage bloat, achieving state-of-the-art test suite compactness and strict constraint adherence.
• Abstract（参考訳）: 組合せテスト(CT)は、相互作用トリガーされた障害を検出するのに不可欠であるが、複雑な制約の下で最小限のカバレッジアレイを生成することは、未解決のNPハードチャレンジのままである。 現在のgreedyアルゴリズムは、非常にスケーラブルだが、厳しい‘diminishing return’に悩まされている。それらは、初期インタラクションを効率的にカバーするが、最後のいくつかの難しいペアをまとめるのに苦労しているときに、肥大した冗長なテストスイートを生成する。 正確な数学的プログラミングはこの非効率性に理論的に対処できるが、歴史的には組合せ的爆発のために難解である。 本稿では,逐次整数線形計画法(ILP)に基づくスケーラブルなフレームワークであるSeqTGを導入することにより,CTへの正確な数学的モデリングの応用を開拓する。 SeqTGは、スケーラビリティの障壁を回避するために、新しいウォーム・スタート戦略を採用している: 迅速な欲求初期化は、まず 'easy'' の相互作用をクリアし、厳密な ILP ソルバが断片化され難解な残りを排他的に最適化できるようにする。 パイプラインは,(1) グラフ分割による制約第一位相グループ化,(2) 逐次ILPとの相互作用をターゲットとした漸進最適化,(3) 集合被覆による冗長性を排除したグローバル最小化の3段階からなる。 標準ベンチマークと200の大規模構成の広範な評価により、フレームワークの有効性が検証された。 その結果、SeqTGは後期肥大を効果的に根絶し、最先端のテストスイートのコンパクト性と厳密な制約順守を実現した。

関連論文リスト

• Explore-Execute Chain: Towards an Efficient Structured Reasoning Paradigm [8.405729585427226]
  Chain-of-Thought(CoT)とその変種は、大規模言語モデル(LLM)の推論能力を著しく向上させた。 E2C$(Explore-Execute Chain)は、推論を2つの異なるフェーズに分離する構造化推論フレームワークである。
  論文  参考訳（メタデータ） (2025-09-28T15:48:40Z)
• PT$^2$-LLM: Post-Training Ternarization for Large Language Models [52.4629647715623]
  大きな言語モデル(LLM)は、様々なタスクにまたがる印象的な機能を示しているが、その大きなメモリと計算能力は、デプロイメントを妨げている。 PT$2$-LLMを提案する。 その中核は2段精製パイプラインを備えた非対称3次量子化器である。
  論文  参考訳（メタデータ） (2025-09-27T03:01:48Z)
• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。 既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。 これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-21T17:15:48Z)
• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
  トークンの制約を評価するのは 違法にコストがかかる LCDは文字列上のグローバル分布を歪め、ローカル情報のみに基づいてトークンをサンプリングすることができる。 我々のアプローチは最先端のベースラインよりも優れていることを示す。
  論文  参考訳（メタデータ） (2025-04-07T18:30:18Z)
• Scalable First-order Method for Certifying Optimal k-Sparse GLMs [9.613635592922174]
  そこで本研究では,BnBフレームワークの視点緩和を解くために,一階近位勾配アルゴリズムを提案する。 提案手法は双有界計算を著しく高速化し,大規模問題に対する最適性証明の提供に極めて有効であることを示す。
  論文  参考訳（メタデータ） (2025-02-13T17:14:18Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)
• TEASER: Fast and Certifiable Point Cloud Registration [30.19476775410544]
  最初の高速かつ堅牢な3Dポイントの登録アルゴリズムは、大量の外れ値の存在下での3Dポイントの登録である。 TEASER++という名前の第二の高速で堅牢な認証翻訳は、大規模なサブプロブレムを解決するために、既成の非コンポーネントを使用する。
  論文  参考訳（メタデータ） (2020-01-21T18:56:00Z)

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

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