Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-26T05:10:34.140Z Has data issue: false hasContentIssue false
  • English
  • Français

Formulating constraint satisfaction problems for the inspection of configuration rules

Published online by Cambridge University Press:  02 September 2015

Anna Tidstam ,
Johan Malmqvist ,
Alexey Voronov ,
Knut Åkesson  and
Martin Fabian
Anna Tidstam*
Affiliation:
Department of Product and Production Development, Chalmers University of Technology, Gothenburg, Sweden
Johan Malmqvist
Affiliation:
Department of Product and Production Development, Chalmers University of Technology, Gothenburg, Sweden
Alexey Voronov
Affiliation:
Department of Signals and Systems, Chalmers University of Technology, Gothenburg, Sweden
Knut Åkesson
Affiliation:
Department of Signals and Systems, Chalmers University of Technology, Gothenburg, Sweden
Martin Fabian
Affiliation:
Department of Signals and Systems, Chalmers University of Technology, Gothenburg, Sweden
*
Reprint requests to: Anna Tidstam, Hörsalsvägen 7A, Göteborg 412 58, Sweden. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Product configuration is when an artifact from a product family is assembled from a set of predefined components that can only be combined in certain ways. These ways are defined by configuration rules. The product developers inspect the configuration rules when they develop new configuration rules or modify the configuration rules set. The inspection of configuration rules is thereby an important activity to avoid errors in the configuration rules set. Several formulations of constraint satisfaction problems (CSPs) are proposed that facilitate the inspection of configuration rules in propositional logic (IF-THEN, AND, NOT, OR, etc.). Many of the configuration rules are so called production rules; that is, a configuration rule is an IF-THEN expression that fires when the IF condition is met. Several configuration rules build chains that fire during the product configuration. It is therefore important not only to inspect single configuration rules but also to analyze the effect of multiple configuration rules. Formulating the tasks as variations of the CSP can support the inspection activity. More specifically, we address the reformulation of configuration rules, testing of feature variant combinations, and counting of item quantities from an item set. The suggested CSPs are tested on industrial vehicle configuration rules for computational performance. The results show that the time for achieving results from the solving of the CSP is within seconds. Our future work will be to implement the various CSPs into a demonstrator that could be tested by product developers.

Keywords

Configuration RulesConstraint Satisfaction ProblemProduct ConfigurationPropositional Logic
Type
Regular Articles
Information
AI EDAM , Volume 30 , Special Issue 3: System Architecture Design , August 2016 , pp. 313 - 328
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Alves, V., Gheyi, R., Massoni, T., Kulesza, U., Borba, P., & Lucena, C. (2006). Refactoring product lines. Proc. Int. Conf. Generative Programming and Component Engineering, GPCE ’06. New York: ACM Press.Google Scholar
Amilhastre, J., Fargier, H., & Marquis, P. (2002). Consistency restoration and explanations in dynamic CSPs—application to configuration. Artificial Intelligence 135(1–2), 199–234.CrossRefGoogle Scholar
Aspvall, B., & Plass, M. (1979). A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Information Processing Letters 8(3), 121–123.CrossRefGoogle Scholar
Astesana, J.-M., Bossu, Y., Cosserat, L., & Fargier, H. (2010 a). Constraint-based modeling and exploitation of a vehicle range at Renault's: requirement analysis and complexity study. Proc. Workshop on Configuration, ECAI 2010. Amsterdam: IOS Press BV.Google Scholar
Astesana, J.-M., Cosserat, L., & Fargier, H. (2010 b). Constraint-based vehicle configuration: a case Study. Proc. Int. Conf. Tools With Artificial Intelligence, ICTAI 2010. New York: IEEE.Google Scholar
Batory, D.S., Benavides, D., & Ruiz-Cortés, A. (2006). Automated analysis of feature models: challenges ahead. Communications of the ACM 49(12), 45.CrossRefGoogle Scholar
Baumeister, J., & Freiberg, M. (2010). Knowledge visualization for evaluation tasks. Knowledge and Information Systems 29(2), 349–378.CrossRefGoogle Scholar
Baumeister, J., Puppe, F., & Seipel, D. (2004). Refactoring methods for knowledge bases. Engineering Knowledge in the Age of the Semantic Web. Berlin: Springer–Verlag.Google Scholar
Bertin, J. (1983). Semiology of Graphics: Diagrams, Networks, Maps. Madison, WI: University of Wisconsin Press.Google Scholar
Bucki, J. (2015). Bill of Materials. Accessed at http://operationstech.about.com/od/glossary/g/BillMaterials.htm on May 1, 2015.Google Scholar
Büning, H.K., & Kullmann, O. (2009). Minimal unsatisfiability and autarkies. In Handbook of Satisfiability (Biere, A., Heule, M., van Maaren, H., & Walsh, T., Eds.), pp. 339–402.Amsterdam: IOS Press.Google Scholar
Chakraborty, R. (2010). Knowledge Representations. Accessed at http://www.myreaders.info/03-Knowledge_Representations.pdf on May 1, 2015.Google Scholar
Cook, S.A. (1971). The complexity of theorem-proving procedures. Proc. ACM Symp. New York: ACM Press.Google Scholar
Dowling, W.F., & Gallier, J.H. (1984). Linear-time algorithms for testing the satisfiability of propositional Horn formulae. Journal of Logic Programming 1(3), 267–284.CrossRefGoogle Scholar
Een, N., & Sörensson, N. (2003). Temporal induction by incremental SAT solving. Electronic Notes in Theoretical Computer Science 89(4), 543–560.CrossRefGoogle Scholar
Een, N., & Sörensson, N. (2004). An extensible SAT-solver. Theory and Applications of Satisfiability Testing 2919, 502–518.CrossRefGoogle Scholar
Felfernig, A., Friedrich, G., Jannach, D., & Stumptner, M. (2004). Consistency-based diagnosis of configuration knowledge bases. Artificial Intelligence 152(2), 213–234.CrossRefGoogle Scholar
Fowler, M., Beck, K., Brant, J., Opdyke, W., & Roberts, D. (1999). Refactoring: Improving the Design of Existing Code. Boston: Addison–Wesley Professional.Google Scholar
Hertli, T., Moser, R.A., & Scheder, D. (2011). Improving ppsz for 3-sat using critical variables. Proc. Int. Symp. Theoretical Aspects of Computer Science, STACS 2011. Leibniz, Germany: Schloss Dagstuhl.Google Scholar
Junker, U. (2006). Configuration. In Handbook of Constraint Programming (Rossi, F., van Beek, P., & Walsh, T., Eds.), pp. 837–874. New York: Elsevier Science.CrossRefGoogle Scholar
Krebs, T., Wolter, K., & Hotz, L. (2004). Mass customization for evolving product families. Proc. Int. Conf. Economic, Technical and Organizational Aspects of Product Configuration Systems, Copenhagen, June 28–29.Google Scholar
Kübler, A., Zengler, C., & Küchlin, W. (2010). Model counting in product configuration. Proc. Workshop on Logics for Component Configuration, LoCoCo, 2010. Sydney: EPTCS.Google Scholar
Le Berre, D., & Parrain, A. (2010). The Sat4j library, release 2.2 system description. Journal on Satisfiability, Boolean Modeling and Computation 7, 59–64.CrossRefGoogle Scholar
Liffiton, M.H. (2009). Analyzing infeasible constraint systems. PhD Thesis. University of Michigan.Google Scholar
Mittal, S., & Falkenhainer, B. (1990). Dynamic constraint satisfaction problems. National Conf. Artificial Intelligence, AAAI-90. Boston: AAAI Press.Google Scholar
Object Management Group. (2009). Production Rule Representation (PRR), International Standard (IEC) 61131-3. Needham: Object Management Group.Google Scholar
Russell, S.J., & Norvig, P. (2003). Artificial Intelligence: A Modern Approach. Upper Saddle River, NJ: Pearson Education.Google Scholar
Shortliffe, E. (1976). Computer-Based Medical Consultations, MYCIN. Amsterdam: Elsevier.Google Scholar
Sinz, C., Kaiser, A., & Küchlin, W. (2003). Formal methods for the validation of automotive product configuration data. Artificial Intelligence for Engineering Design, Analysis and Manufacturing 17(1), 75–97.CrossRefGoogle Scholar
Soininen, T., Tiihonen, J., Männistö, T., & Sulonen, R. (1998). Towards a general ontology of configuration. Artificial Intelligence for Engineering Design, Analysis and Manufacturing 12, 357–372.CrossRefGoogle Scholar
Thüm, T., Batory, D.S., & Kastner, C. (2009). Reasoning about edits to feature models. Int. Conf. Software Engineering, pp. 254–264. Los Alamitos, CA: IEEE.Google Scholar
Tidstam, A., Bligård, L.-O., Ekstedt, F., Voronov, A., Åkesson, K., & Malmqvist, J. (2012). Development of industrial visualization tools for validation of vehicle configuration rules. Proc. Int. Symp. Tools and Methods of Competitive Engineering, TMCE'12. Voorschoten: Emerald Eye.Google Scholar
Tsang, E.P. (1993). Foundations of Constraint Satisfaction. London: Academic Press.Google Scholar
van Maaren, H. (2000). A short note on some tractable cases of the satisfiability problem. Information and Computation 158(2), 125–130.CrossRefGoogle Scholar
Voronov, A. (2013). On formal methods for large-scale product configuration. PhD Thesis. Chalmers University of Technology.Google Scholar
Wehle, H.-D. (2011). Cloud Billing Service. Accessed at http://www.ibm.com/developerworks/cloud/library/cl-devcloudmodule/ on May 1, 2015.Google Scholar