Abstract
Conflict detection is used in various scenarios ranging from interactive decision making (e.g., knowledge-based configuration) to the diagnosis of potentially faulty models (e.g., using knowledge base analysis operations). Conflicts can be regarded as sets of restrictions (constraints) causing an inconsistency. Junker’s QuickXPlain is a divide-and-conquer based algorithm for the detection of preferred minimal conflicts. In this article, we present a novel approach to the detection of such conflicts which is based on speculative programming. We introduce a parallelization of QuickXPlain and empirically evaluate this approach on the basis of synthesized knowledge bases representing feature models. The results of this evaluation show significant performance improvements in the parallelized QuickXPlain version.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
Note that this representation can be easily translated into a specific solver representation – see, for example, choco-solver.org.
References
Acher, M., Collet, P., Lahire, P., & France, R. (2013). Familiar: A domain-specific language for large scale management of feature models. Science of Computer Programming, 78(6), 657–681.
Alférez, M., Acher, M., Galindo, J.A., Baudry, B., & Benavides, D. (2019). Modeling variability in the video domain Language and experience report. Software Quality Journal, 27(1), 307–347.
Bakker, R., & Dikker, F. (1993). Diagnosing and Solving Over-determined Constraint Satisfaction Problems. In 13Th intl. Joint conference on artificial intelligence (IJCAI’93) (pp. 276–281). France: Chambéry.
Batory, D. (2005). Feature models, grammars, and propositional formulas. In Intl. conference on software product lines (pp. 7–20). Springer.
Benavides, D., Ruiz-Cortés, A., & Trinidad, P. (2005). Automated reasoning on feature models. In LNCS Advanced information systems engineering: 17th Intl, Conference, CAiSE 2005, (Vol. 3520 pp. 491–503).
Benavides, D., Segura, S., & Ruiz-Cortes, A. (2010). Automated analysis of feature models 20 years later A literature review. Information Systems, 35, 615–636.
Bordeaux, L., Hamadi, Y., & Samulowitz, H. (2009). Experiments with Massively Parallel Constraint Solving. In 21St Intl. Joint conference on artifical intelligence (pp. 443–448). USA: Morgan Kaufmann Publishers.
Burton, F. (1985). Speculative computation, parallelism, and functional programming. IEEE Transactions on Computers, C-34(12), 1190–1193.
de Kleer, J., & Williams, B. (1987). Diagnosing multiple faults. Artificial Intelligence, 32(1), 97–130.
Díaz, J., Pérez, J., & Garbajosa, J. (2014). Agile product-line architecting in practice: A case study in smart grids. Information and Software Technology, 56(7), 727–748.
Doux, G., Albert, P., Barbier, G., Cabot, J., Del Fabro, M., & Lee, S. (2011). An mde-based approach for solving configuration problems An application to the eclipse platform. In European conference on modelling foundations and applications (pp. 160–171). Springer.
Felfernig, A. (2021). AI techniques for software requirements prioritization. In M. Kalech, R. Abreu, & M. Last (Eds.) Artificial intelligence methods for software engineering (pp. 29–47). World Scientific.
Felfernig, A., Benavides, D., Galindo, J., & Reinfrank, F. (2013). Towards anomaly explanation in feature models. In 15Th intl. configuration workshop (pp. 117–124).
Felfernig, A., Boratto, L, Stettinger, M., & Tkalcic, M. (2018). Group Recommender Systems – An Introduction. Berlin: Springer.
Felfernig, A., & Systems, R. Burke. (2008). Constraint-based Recommender Technologies and Research Issues. In ACM intl. conference on electronic commerce (ICEC’08) (pp. 17–26). Austria: Innsbruck.
Felfernig, A., Friedrich, G., Jannach, D., & Stumptner, M. (2004). Consistency-based Diagnosis of Configuration Knowledge Bases. Artificial Intelligence, 152(2), 213–234.
Felfernig, A., Friedrich, G., Jannach, D., & Zanker, M. (2006). An integrated environment for the development of knowledge-based recommender applications. Intelligence Journal of Electronic Commerce (IJEC), 11(2), 11–34.
Felfernig, A., Hotz, L., Bagley, C., & Tiihonen, J. (2014). Knowledge-based Configuration - From Research to Business Cases. Burlington: Morgan Kaufmann.
Felfernig, A., Polat-Erdeniz, S., Uran, C., Reiterer, S., Atas, M., Tran, T., Azzoni, P., Kiraly, C., & Dolui, K. (2019). An overview of recommender systems in the internet of things. Journal of Intelligent Information Systems, 52 (2), 285–309.
Felfernig, A., Schubert, M., & Zehentner, C. (2012). An Efficient Diagnosis Algorithm for Inconsistent Constraint Sets. Artificial Intelligence for Engineering Design, Analysis and Manufacturing, 26(1), 53–62.
Felfernig, A., Walter, R., Galindo, J., Benavides, D., Erdeniz, S., Atas, M., & Reiterer, S. (2018). Anytime Diagnosis for Reconfiguration. Journal of Intelligent Information Systems, 51(1), 161–182.
Fleischanderl, G. (2002). Suggestions from the software engineering practice for applying Consistency-Based diagnosis to configuration knowledge bases. In 13Th Intl. workshop on principles of diagnosis (DX-02) (pp. 33–35). Austria: Semmering.
Friedrich, G., Stumptner, M., & Wotawa, F. (1999). Model-based Diagnosis of Hardware Designs. Artificial Intelligence, 111(1–2), 3–39.
Galindo, J., & Benavides, D. (2019). Towards a new repository for feature model exchange. In C. Cetina, O. Díaz, L. Duchien, M. Huchard, R. Rabiser, C. Salinesi, C. Seidl, X. Tërnava, L. Teixeira, T. Thüm, & T. Zadi (Eds.) 23rd intl. systems and software product line conference, SPLC Volume b, Paris, France, September 9-13, 2019 (p. 2019). ACM.
Galindo, J., Benavides, D., Trinidad, P., Gutiérrez-Fernández, A., & Ruiz-Cortés, A. (2019). Automated analysis of feature models Quo vadis? Computing, 101(5), 387–433.
Gent, I., Miguel, I., Nightingale, P., McCreesh, C., Prosser, P., Nooore, N., & Unsworth, C. (2018). A review of literature on parallel constraint solving. Theory and Practice of Logic Programming, 18(5–6), 725–758.
Hamadi, Y., & Sais, L. (2018). Handbook of Parallel Constraint Reasoning. Berlin: Springer.
Horcas, J., Pinto, M., & Fuentes, L. (2018). Variability models for generating efficient configurations of functional quality attributes. Information and Software Technology, 95, 147–164.
Jannach, D., Schmitz, T., & Shchekotykhin, K. (2015). Parallelized hitting set computation for model-based diagnosis. In 29th AAAI conference on artificial intelligence (pp. 1503–1510). Texas: AAAI Press.
Jannach, D., Schmitz, T., & Shchekotykhin, K. (2016). Parallel Model-Based diagnosis on Multi-Core computers. Journal of Artificial Intelligence Research, 55, 835–887.
Junker, U. (2004). quickXPlain: Preferred Explanations and Relaxations for Over-constrained Problems. In 19th national conference on artifical intelligence (pp. 167–172 ). San Jose: AAAI Press.
Kastner, C., Thum, T., Saake, G., Feigenspan, J., Leich, T., Wielgorz, F., & Apel, S. (2009). Featureide: A tool framework for feature-oriented software development. In 31St IEEE intl. conference on software engineering (pp. 611–614). IEEE.
Le, V.M., Felfernig, A., Uta, M., Benavides, D., Galindo, J., & Tran, T.N.T. (2021). DirectDebug: Automated testing and debugging of feature models. In 43Rd IEEE/ACM intl. conference on software engineering: New ideas and emerging results (pp. 81–85). IEEE/ACM.
Le Berre, D., & Parrain, A. (2010). The Sat4j Library, Release 2.2. Journal on Satisfiability. Boolean Modeling and Computation, 7(2-3), 59–64.
Marques-Silva, J., Heras, F., Janota, M., Previti, A., & Belov, A. (2013). On computing minimal correction subsets. In 23Rd intl. joint conference on artificial intelligence. Beijing, China (pp. 615–622).
O’Sullivan, B., Nanopulos, A., Faltings, B., & Pu, P. (2007). Representative explanations for Over-Constrained problems. In 22Nd AAAI conference on artificial intelligence (pp. 323–328). Canada: Vancouver.
Reiter, R. (1987). A theory of diagnosis from first principles. Artificial Intelligence, 23(1), 57–95.
Ricci, F., Rokach, L., Shapira, B., & Kantor, P. (2011). Recommender Systems Handbook, Springer, Berlin.
Rossi, F., Venable, K., & Walsh, T. (2011). A Short Introduction to Preferences: Between Artificial Intelligence and Social Choice. California: Morgan & Claypool Publishers.
Schmitz, T., & Jannach, D. (2017). An AI-based interactive tool for spreadsheet debugging. In IEEE symposium on visual languages and human-centric computing (VL/HCC’17) (pp. 333–334). USA: IEEE.
Stumptner, M. (1997). An Overview of Knowledge-based Configuration. Ai Communications, 10(2), 111–125.
Thum, T., Batory, D., & Kastner, C. (2009). Reasoning about edits to feature models. In 31St IEEE intl. conference on software engineering (pp. 254–264). Piscataway: IEEE.
Tran, T.N.T., Felfernig, A., & Tintarev, N. (2021). Humanized Recommender Systems: State-of-the-art and Research Issues. ACM Transactions on Interactive Intelligent Systems, 11(2), 1–41.
Tsang, E. (1993). Foundations of Constraint Satisfaction. Cambridge: Academic Press.
Varela-Vaca, A., Galindo, J.A., Ramos-Gutiérrez, B., Gómez-López, M., & Benavides, D. (2019). Process mining to unleash variability management: discovering configuration workflows using logs. In Proceedings of the 23rd intl. systems and software product line conference, (Vol. A pp. 265–276).
Vecchio, M., Azzoni, P., Menychtas, A., Maglogiannis, I., & Felfernig, A. (2021). A fully open-source approach to intelligent edge computing: the AGILE’s lesson. Sensors, 21(4), 1309.
Vidal, C., Felfernig, A., Galindo, J., Atas, M., & Benavides, D. (2020). A Parallelized Variant of Junker’s quickXPlain Algorithm. In 25Th intl. symp. on methodologies for intell. Syst., volume 12117 of springer lecture notes in computer science (pp. 457–468). Springer.
Walsh, T. (2007). Representing and reasoning with preferences. AI Magazine, 28(4), 59–70.
White, J., Benavides, D., Schmidt, D.C., Trinidad, P., Dougherty, B., & Ruiz-Cortes, A. (2010). Automated diagnosis of feature model configurations. J. Syst Softw., 83(7), 1094–1107.
Wotawa, F. (2001). A variant of reiter’s Hitting-Set algorithm. Information Processing Letters, 79(1), 45–51.
Acknowledgements
This work has been partially funded by the EU FEDER program, the ParXCel project (880657) funded by the Austrian Research Promotion Agency, the MINECO project OPHELIA (RTI2018-101204-B-C22), the TASOVA network (MCIU-AEI TIN2017-90644-REDT), and the Junta de Andalucia METAMORFOSIS project. We want to thank Jesús Giráldez from the University of Granada as well as Rafael Corchuelo and Mayte Gómez–López from the University of Sevilla for providing feedback in early stages of this research.
Author information
Authors and Affiliations
Corresponding author
Additional information
Material
The software, material and results used during the runtime analysis can be accessed through https://doi.org/10.5281/zenodo.3825090
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Vidal, C., Felfernig, A., Galindo, J. et al. Explanations for over-constrained problems using QuickXPlain with speculative executions. J Intell Inf Syst 57, 491–508 (2021). https://doi.org/10.1007/s10844-021-00675-4
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10844-021-00675-4