論文の概要: Efficient Heuristics and Exact Methods for Pairwise Interaction Sampling

• arxiv url: http://arxiv.org/abs/2510.05955v1
• Date: Tue, 07 Oct 2025 14:11:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-08 17:57:08.282591
• Title: Efficient Heuristics and Exact Methods for Pairwise Interaction Sampling
• Title（参考訳）: ペアインタラクションサンプリングのための効率的なヒューリスティックスとエクササイズ手法
• Authors: Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, Michael Perk,
• Abstract要約: 現代ソフトウェアシステムにおけるテストの基本となる最適化問題について考察する。 発行されたベンチマークセットで最大のインスタンスを解決し、最適性を証明できます。
• 参考スコア（独自算出の注目度）: 0.8242194776558897
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a class of optimization problems that are fundamental to testing in modern configurable software systems, e.g., in automotive industries. In pairwise interaction sampling, we are given a (potentially very large) configuration space, in which each dimension corresponds to a possible Boolean feature of a software system; valid configurations are the satisfying assignments of a given propositional formula $\varphi$. The objective is to find a minimum-sized family of configurations, such that each pair of features is jointly tested at least once. Due to its relevance in Software Engineering, this problem has been studied extensively for over 20 years. In addition to new theoretical insights (we prove BH-hardness), we provide a broad spectrum of key contributions on the practical side that allow substantial progress for the practical performance. Remarkably, we are able to solve the largest instances we found in published benchmark sets (with about 500000000 feasible interactions) to provable optimality. Previous approaches were not even able to compute feasible solutions.
• Abstract（参考訳）: 本稿では,自動車産業において,現代の構成可能なソフトウェアシステムにおいて,テストの基本となる最適化問題について考察する。 ペアの相互作用サンプリングでは、各次元がソフトウェアシステムの可能なブール特徴に対応する(潜在的に非常に大きな)構成空間が与えられ、有効な構成は与えられた命題式$\varphi$の割り当てである。 目的は最小サイズの構成のファミリを見つけることであり、各機能のペアが少なくとも1回は共同でテストされる。 ソフトウェア工学の関連性から、この問題は20年以上にわたって広く研究されてきた。 新たな理論的洞察(BH-hardnessの証明)に加えて,実用面において重要な貢献を幅広く提供し,実用面の大幅な進歩を図っている。 注目すべきは、公開ベンチマークセットで見つかった最大のインスタンス(約50万の可能な相互作用)を、証明可能な最適性で解決できることです。 それまでのアプローチでは、実現可能なソリューションを計算できなかった。

関連論文リスト

• DaSAThco: Data-Aware SAT Heuristics Combinations Optimization via Large Language Models [2.9789407216680286]
  DaSAThcoは、インスタンス機能からカスタマイズされたアンサンブルへの一般化可能なマッピングを学習するフレームワークである。 我々のフレームワークは、体系的に定義された問題アーチタイプによってガイドされる大規模言語モデルを使用して、多様な特殊なアンサンブルのポートフォリオを生成し、その後、最終的なマッピングを形成するための適応的な選択メカニズムを学習する。
  論文  参考訳（メタデータ） (2025-09-16T02:58:50Z)
• How Low Can We Go? Minimizing Interaction Samples for Configurable Systems [2.569213261297365]
  提案手法は, 必要サンプルサイズに対して, ほぼ最適解と証明可能な下限を結合する枠組みである。 我々のアルゴリズムであるSampLNSは,85%のケースにおいて,従来手法よりも小型のサンプルを確実に見つけることができる。 これにより、研究者や実践者によるサンプルの最小化という面倒な作業を避けることができる。
  論文  参考訳（メタデータ） (2025-01-12T12:02:26Z)
• BEACON: A Bayesian Optimization Strategy for Novelty Search in Expensive Black-Box Systems [1.204357447396532]
  ノベルティサーチ(NS)は、シミュレーションや実験を通じて多様なシステムの振る舞いを明らかにすることを目指している。 NS法は一般に、入力空間の密度の高いサンプリングを必要とする進化戦略やその他のメタヒューリスティックに依存している。 サンプル効率のよいベイズ最適化に基づくNSのアプローチであるBEACONを導入し、入力-行動関係が不透明で、評価にコストがかかるような設定に最適化する。
  論文  参考訳（メタデータ） (2024-06-05T20:23:52Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。 ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。 本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
  論文  参考訳（メタデータ） (2023-06-21T17:03:22Z)
• BOtied: Multi-objective Bayesian optimization with tied multivariate ranks [33.414682601242006]
  本稿では,非支配解と結合累積分布関数の極端量子化との自然な関係を示す。 このリンクにより、我々はPareto対応CDFインジケータと関連する取得関数BOtiedを提案する。 種々の合成および実世界の問題に対する実験により,BOtied は最先端MOBO 取得関数より優れていることが示された。
  論文  参考訳（メタデータ） (2023-06-01T04:50:06Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Batched Data-Driven Evolutionary Multi-Objective Optimization Based on Manifold Interpolation [6.560512252982714]
  バッチ化されたデータ駆動型進化的多目的最適化を実現するためのフレームワークを提案する。 オフザシェルフ進化的多目的最適化アルゴリズムがプラグイン方式で適用できるのは、非常に一般的である。 提案するフレームワークは, より高速な収束と各種PF形状に対する強いレジリエンスを特徴とする。
  論文  参考訳（メタデータ） (2021-09-12T23:54:26Z)
• USCO-Solver: Solving Undetermined Stochastic Combinatorial Optimization Problems [9.015720257837575]
  入力-解対のサンプルから高品質な最適化解を推定することを目的として,空間間の回帰を考察する。 基礎学習にはPAC-Bayesianフレームワークを用いて学習エラー分析を行う。 我々は,合成データセットと実世界のデータセットの両方において,古典的な問題に対する高い励振実験結果を得た。
  論文  参考訳（メタデータ） (2021-07-15T17:59:08Z)
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
  トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。 この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。 我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
  論文  参考訳（メタデータ） (2020-06-21T15:32:21Z)

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

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