Bombarda2024b Bombarda, Andrea Gargantini, Angelo

On the Use of Multi-valued Decision Diagrams to Count Valid Configurations of Feature Models

in 28th ACM International Systems and Software Product Line Conference, ACM, SPLC ’24 (2024): 96--106

Abstract
This paper addresses the challenge of effi ciently counting valid configurations in Software Product Lines (SPLs). We propose a novel approach leveraging Multi-Valued Decision Diagrams (MDDs) for building the set of products. Building upon the MDD structure, we introduce several algorithmic optimizations to achieve a more compact and efficient representation of the product set compared to existing methods based on Binary Decision Diagrams. The eff ectiveness of our approach is evaluated through experimentation on two datasets: a set of synthetic benchmarks and large-scale industrial feature models. The results demonstrate significant improvements in scalability for models of medium complexity, particularly those rich in alternative groups. However, challenges remain for other model types, highlighting areas for future research.


[download the pdf file] [DOI]

My sw links