論文の概要: A Comparative Analysis of Backbone Algorithms for Configurable Software Systems

• arxiv url: http://arxiv.org/abs/2603.15833v1
• Date: Mon, 16 Mar 2026 19:04:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-18 17:42:06.957289
• Title: A Comparative Analysis of Backbone Algorithms for Configurable Software Systems
• Title（参考訳）: 構成可能なソフトウェアシステムのためのバックボーンアルゴリズムの比較解析
• Authors: Luis Cambelo, Ruben Heradio, Jose-Miguel Horcas, Dictino Chaos, David Fernandez-Amoros,
• Abstract要約: 本研究は,実世界の変動性モデルから導出した公式の総合的な評価を行った最初のものである。 100変数から179節、186,059変数、527,240節までのシステムから、2,371式上の5つの最先端アルゴリズムの21の構成を分析する。 その結果, 変数モデル式は構造的に異なるが, 節密度は高く, 節の単純さも大きいことが示唆された。
• 参考スコア（独自算出の注目度）: 1.0678661063046846
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The backbone of a Boolean formula is the set of literals that must be true in every assignment that satisfies the formula. This concept is fundamental to key operations on variability models, including propagating user configuration decisions to identify implied feature selections, detecting dead features and dead code blocks, and preprocessing formulas to accelerate knowledge compilation into tractable representations such as binary decision diagrams. Despite its importance, previous empirical studies have evaluated backbone algorithms solely on SAT competition formulas (typically engineered to test the limits of SAT solvers), leading to inconsistent conclusions about their performance. This study provides the first comprehensive evaluation of formulas derived from real-world variability models, analyzing 21 configurations of 5 state-of-the-art algorithms on 2,371 formulas from configurable systems ranging from 100 variables and 179 clauses to 186,059 variables and 527,240 clauses. The results indicate that variability model formulas are structurally distinct, with higher clause density but greater clause simplicity. Our research provides clear algorithm selection guidelines: Algorithm 2/3 (iterative with solution filtering) is recommended for formulas with 1,000 or fewer variables, while Algorithm 5 (chunked core-based) with adaptive chunk size selection provides the best practical performance for larger formulas. Also, the results show that filtering heuristics have negligible or negative effects on performance for variability models. Finally, the study identifies a research gap: while Algorithm 5 with optimal chunk size can achieve runtime reductions exceeding 50\% compared to Algorithm 2/3 (the one that product line tools implement), the optimal chunk size varies unpredictably across formulas and cannot currently be estimated, opening directions for future research.
• Abstract（参考訳）: ブール公式のバックボーンは、式を満たす全ての代入において真でなければならないリテラルの集合である。 この概念は、インプリケートされた特徴の選択を識別するためのユーザ構成決定の伝搬、デッドフィーチャーとデッドコードブロックの検出、知識コンパイルをバイナリ決定図のような抽出可能な表現に加速するための前処理など、変数モデルに関する重要な操作に基礎を置いている。 その重要性にもかかわらず、以前の経験的研究はSAT競合公式(典型的にはSATソルバの限界をテストするために設計された)のみに基づくバックボーンアルゴリズムを評価し、それらの性能に関する矛盾した結論を導いた。 本研究は,100変数179節から186,059変数,527,240節までの構成可能なシステムから,2,371式上の5つの最先端アルゴリズムの21構成を解析し,実世界の変数モデルから導出した公式の総合的評価を行った。 その結果, 変数モデル式は構造的に異なるが, 句密度は高く, 節の単純さも大きいことが示唆された。 アルゴリズム2/3は1000以上の変数を持つ式に対して推奨され、アルゴリズム5(チャンクコアベース)は適応的なチャンクサイズ選択を行う。 また, フィルタヒューリスティックスは変動モデルの性能に無視的あるいは負の影響を及ぼすことを示した。 最適なチャンクサイズを持つアルゴリズム5は、アルゴリズム2/3(製品ラインツールが実装したもの)と比較して50倍以上のランタイム削減を達成することができるが、最適チャンクサイズは、式によって予測不可能に変化し、現在予測できないため、将来の研究の方向性が明らかになる。

関連論文リスト

• Direct Preference Optimization with Rating Information: Practical Algorithms and Provable Gains [67.71020482405343]
  評価ギャップの形で追加情報を活用するアルゴリズムを設計する方法について検討する。 精度の高いレーティングギャップ情報が存在する場合,DPOよりも高速な統計的レートを実現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-01-31T08:38:21Z)
• EquiBench: Benchmarking Large Language Models' Reasoning about Program Semantics via Equivalence Checking [58.15568681219339]
  大規模言語モデル(LLM)を評価するための新しいベンチマークであるEquiBenchを紹介する。 このタスクは、プログラムのセマンティクスについて推論するモデルの能力を直接テストする。 19の最先端LCMを評価し、最も難しいカテゴリでは、最高の精度は63.8%と76.2%であり、50%のランダムベースラインよりわずかに高い。
  論文  参考訳（メタデータ） (2025-02-18T02:54:25Z)
• Towards Fast Algorithms for the Preference Consistency Problem Based on Hierarchical Models [4.007697401483925]
  階層モデルに基づく選好文の一貫性問題の解法として,アルゴリズム的手法を構築し,比較する。 インスタンスが一貫すると、評価関数に階層的モデルが存在し、代替関数の順序関係を誘導する。 この問題を解決するための3つのアプローチを開発する。
  論文  参考訳（メタデータ） (2024-10-31T13:48:46Z)
• Prompt-Matcher: Leveraging Large Models to Reduce Uncertainty in Schema Matching Results [1.13107643869251]
  本稿では,大規模言語モデルの特定のプロンプトを用いた細粒度対応検証に基づく新しい手法を提案する。 本手法は,(1)対応選択アルゴリズム,(2)対応検証,(3)確率分布の更新の3つの主成分からなる反復ループである。 本稿では,計算効率においてブルートアルゴリズムを著しく上回る新しい$(1-1/e)$-approximationアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-08-24T16:54:08Z)
• Best-Subset Selection in Generalized Linear Models: A Fast and Consistent Algorithm via Splicing Technique [0.6338047104436422]
  ベストサブセットセクションは、このタイプの問題の聖杯として広く見なされている。 軽度条件下での最適部分集合回復のためのアルゴリズムを提案し,提案した。 我々の実装は、一般的な変数選択ツールキットと比較して約4倍のスピードアップを実現している。
  論文  参考訳（メタデータ） (2023-08-01T03:11:31Z)
• Efficient Convex Algorithms for Universal Kernel Learning [46.573275307034336]
  カーネルの理想的な集合: 線形パラメータ化(トラクタビリティ)を認める; すべてのカーネルの集合に密着する(正確性)。 従来のカーネル最適化アルゴリズムは分類に限られており、計算に複雑なセミデフィニティプログラミング(SDP)アルゴリズムに依存していた。 本稿では,従来のSDP手法と比較して計算量を大幅に削減するSVD-QCQPQPアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-15T04:57:37Z)
• Fast Feature Selection with Fairness Constraints [49.142308856826396]
  モデル構築における最適特徴の選択に関する基礎的問題について検討する。 この問題は、greedyアルゴリズムの変種を使用しても、大規模なデータセットで計算的に困難である。 適応クエリモデルは,最近提案された非モジュラー関数に対する直交整合探索のより高速なパラダイムに拡張する。 提案アルゴリズムは、適応型クエリモデルにおいて指数関数的に高速な並列実行を実現する。
  論文  参考訳（メタデータ） (2022-02-28T12:26:47Z)
• A Novel Surrogate-assisted Evolutionary Algorithm Applied to Partition-based Ensemble Learning [0.0]
  高価な最適化問題を解決するための新しいサロゲート支援アルゴリズムを提案する。 我々は,適応値推定に用いるサロゲートモデルと,進化的遺伝子-進化的最適混合アルゴリズムの最先端p3様変種を統合する。 提案したアルゴリズムをアンサンブル学習問題で検証する。
  論文  参考訳（メタデータ） (2021-04-16T11:51:18Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。 我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
  論文  参考訳（メタデータ） (2020-01-29T09:40:58Z)

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

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