論文の概要: Rethinking Basis Path Testing: Mixed Integer Programming Approach for Test Path Set Generation

• arxiv url: http://arxiv.org/abs/2601.05463v1
• Date: Fri, 09 Jan 2026 01:36:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-12 17:41:49.806528
• Title: Rethinking Basis Path Testing: Mixed Integer Programming Approach for Test Path Set Generation
• Title（参考訳）: バスパステストの再考:テストパスセット生成のための混合整数プログラミングアプローチ
• Authors: Chao Wei, Xinyi Peng, Yawen Yan, Mao Luo, Ting Cai,
• Abstract要約: 本稿では,手続き探索タスクから宣言的最適化問題への基底経路生成を再構成する。 構造的単純性においてグローバルに最適な完全基底パスセットを生成するために設計された混合プログラミング(MIP)フレームワークを導入する。 我々のフレームワークには,理論上最適なパスセットを保証するホロスティックMIPモデルと,大規模かつ複雑なトポロジに対するスケーラブルなインクリメンタルMIP戦略の2つの補完戦略が含まれている。
• 参考スコア（独自算出の注目度）: 7.012302821190496
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Basis path testing is a cornerstone of structural testing, yet traditional automated methods, relying on greedy graph-traversal algorithms (e.g., DFS/BFS), often generate sub-optimal paths. This structural inferiority is not a trivial issue; it directly impedes downstream testing activities by complicating automated test data generation and increasing the cognitive load for human engineers. This paper reframes basis path generation from a procedural search task into a declarative optimization problem. We introduce a Mixed Integer Programming (MIP) framework designed to produce a complete basis path set that is globally optimal in its structural simplicity. Our framework includes two complementary strategies: a Holistic MIP model that guarantees a theoretically optimal path set, and a scalable Incremental MIP strategy for large, complex topologies. The incremental approach features a multi-objective function that prioritizes path simplicity and incorporates a novelty penalty to maximize the successful generation of linearly independent paths. Empirical evaluations on both real-code and large-scale synthetic Control Flow Graphs demonstrate that our Incremental MIP strategy achieves a 100\% success rate in generating complete basis sets, while remaining computationally efficient. Our work provides a foundational method for generating a high-quality structural "scaffold" that can enhance the efficiency and effectiveness of subsequent test generation efforts.
• Abstract（参考訳）: バスパステストは、構造的テストの基盤であるが、従来の自動化手法では、グレディなグラフトラバースアルゴリズム(例えば、DFS/BFS)に依存しており、しばしば準最適パスを生成する。 この構造的劣等性は、簡単な問題ではなく、自動テストデータ生成を複雑化し、人間のエンジニアの認知負荷を増大させることで、下流テスト活動を直接妨げます。 本稿では,手続き探索タスクから宣言的最適化問題への基底経路生成を再構成する。 構造的単純性においてグローバルに最適な完全基底パスセットを生成するために設計された混合整数プログラミング(MIP)フレームワークを導入する。 我々のフレームワークには,理論上最適なパスセットを保証するホロスティックMIPモデルと,大規模かつ複雑なトポロジに対するスケーラブルなインクリメンタルMIP戦略の2つの補完戦略が含まれている。 漸進的なアプローチは、経路の単純さを優先する多目的関数を特徴とし、線形独立経路の生成を最大化するために新しいペナルティを取り入れている。 実コードおよび大規模合成制御フローグラフの実証評価により,我々のインクリメンタルMIP戦略は,計算効率を保ちながら,完全基底集合の生成において100倍の成功率を達成することを示した。 本研究は,高品質な構造体"スキャフォールド"を生成するための基礎的手法を提供し,その後のテスト生成作業の効率性と有効性を向上させる。

関連論文リスト

• Dynamic Generation of Multi-LLM Agents Communication Topologies with Graph Diffusion Models [99.85131798240808]
  我々はtextitGuided Topology Diffusion (GTD) と呼ばれる新しい生成フレームワークを導入する。 条件付き離散グラフ拡散モデルにインスパイアされたGTD式は、反復的な構成過程としてトポロジー合成を行う。 各ステップで生成は、多目的報酬を予測する軽量プロキシモデルによって制御される。 実験により、GTDは高いタスク適応性、スパース、効率的な通信トポロジを生成できることが示されている。
  論文  参考訳（メタデータ） (2025-10-09T05:28:28Z)
• LLM Test Generation via Iterative Hybrid Program Analysis [3.511540973608371]
  Pantaは、コードを分析し、テストケースを構築する際に、人間が従う反復的なプロセスをエミュレートするテクニックである。 オープンソースプロジェクトのサイクロマティックな複雑性の高いクラスで実施した経験的評価は,Pantaが26%,ブランチカバレッジが23%向上したことを示す。
  論文  参考訳（メタデータ） (2025-03-17T16:10:38Z)
• Bridging Pattern-Aware Complexity with NP-Hard Optimization: A Unifying Framework and Empirical Study [0.0]
  本稿では,ドメイン間の効率的な計算複雑性を低減するための新しいパターン認識フレームワークを提案する。 厳密な定義、定理、メタ学習駆動型ソルバパイプラインによって、パターン利用効率(PUE)のようなメトリクスを導入し、最大で79%のソリューション品質向上を実現します。
  論文  参考訳（メタデータ） (2025-03-12T11:05:06Z)
• ProofAug: Efficient Neural Theorem Proving via Fine-grained Proof Structure Analysis [50.020850767257095]
  本稿では,LLMに様々な粒度で自動化手法を付加するProofAugを提案する。 本手法は,オープンソースのDeep-math-7bベースモデルとIsabelle証明アシスタントを用いて,MiniF2Fベンチマークで検証した。 また、ProofAugのLean 4バージョンを実装し、Kimina-Prover-seek-Distill-1.5Bのパス@1のパフォーマンスを44.3%から50.4%に改善します。
  論文  参考訳（メタデータ） (2025-01-30T12:37:06Z)
• Constrained Hybrid Metaheuristic Algorithm for Probabilistic Neural Networks Learning [0.3686808512438362]
  本研究では、確率論的ニューラルネットワーク(PNN)のトレーニングを強化するためのハイブリッドメタヒューリスティックアルゴリズムの可能性について検討する。 勾配に基づくアプローチのような伝統的な学習手法は、しばしば高次元で不確実な環境を最適化するのに苦労する。 本稿では,複数の個体群に基づく最適化手法を組み合わせた制約付きハイブリッドメタヒューリスティック(cHM)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-01-26T19:49:16Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。 既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。 提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
  論文  参考訳（メタデータ） (2023-07-08T15:41:48Z)
• Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Exploration [87.53543137162488]
  我々はtextttMEX というオンライン強化学習(オンラインRL)フレームワークを提案する。 textttMEXは、自動的に探索エクスプロイトのバランスをとりながら、見積もりと計画コンポーネントを統合する。 様々な MuJoCo 環境では,ベースラインを安定的なマージンで上回り,十分な報酬を得られる。
  論文  参考訳（メタデータ） (2023-05-29T17:25:26Z)
• Parameter Tuning Strategies for Metaheuristic Methods Applied to Discrete Optimization of Structural Design [0.0]
  本稿では, 鉄筋コンクリート(RC)構造物の設計最適化のためのメタヒューリスティック手法のパラメータを調整するためのいくつかの手法を提案する。 平均性能曲線の下での面積に基づいて, 実用性指標を提案する。
  論文  参考訳（メタデータ） (2021-10-12T17:34:39Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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