Efficient Heuristics and Exact Methods for Pairwise Interaction Sampling
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912633244876800 |
|---|---|
| author | Fekete, Sándor P. Keldenich, Phillip Krupke, Dominik Perk, Michael |
| author_facet | Fekete, Sándor P. Keldenich, Phillip Krupke, Dominik Perk, Michael |
| contents | 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 $φ$. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_05955 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient Heuristics and Exact Methods for Pairwise Interaction Sampling Fekete, Sándor P. Keldenich, Phillip Krupke, Dominik Perk, Michael Data Structures and Algorithms Computational Complexity Software Engineering 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 $φ$. 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. |
| title | Efficient Heuristics and Exact Methods for Pairwise Interaction Sampling |
| topic | Data Structures and Algorithms Computational Complexity Software Engineering |
| url | https://arxiv.org/abs/2510.05955 |