Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-22T20:49:43.113Z Has data issue: false hasContentIssue false
  • English
  • Français

Reasoning about conditional constraint specification problems and feature models

Published online by Cambridge University Press:  20 April 2011

Raphael Finkel  and
Barry O'Sullivan
Raphael Finkel
Affiliation:
Department of Computer Science, University of Kentucky, Lexington, Kentucky, USA
Barry O'Sullivan
Affiliation:
Cork Constraint Computation Centre, University College Cork, Cork, Ireland
Get access Rights & Permissions [Opens in a new window]

Abstract

Product configuration is a major industrial application domain for constraint satisfaction techniques. Conditional constraint satisfaction problems (CCSPs) and feature models (FMs) have been developed to represent configuration problems in a natural way. CCSPs are like constraint satisfaction problems (CSPs), but they also include potential variables, which might or might not exist in any given solution, as well as classical variables, which are required to take a value in every solution. CCSPs model, for example, options on a car, for which the style of sunroof (a variable) only makes sense if the car has a sunroof at all. FMs are directed acyclic graphs of features with constraints on edges. FMs model, for example, cell phone features, where utility functions are required, but the particular utility function “games” is optional, but requires Java support. We show that existing techniques from formal methods and answer set programming can be used to naturally model CCSPs and FMs. We demonstrate configurators in both approaches. An advantage of these approaches is that the model builder does not have to reformulate the CCSP or FM into a classic CSP, converting potential variables into classical variables by adding a “does not exist” value and modifying the problem constraints. Our configurators automatically reason about the model itself, enumerating all solutions and discovering several kinds of model flaws.

Keywords

AlloyAnswer-Set ProgrammingConfigurationConstraint SatisfactionFlaw Detection
Type
Special Issue Articles
Information
AI EDAM , Volume 25 , Issue 2: Configuration , May 2011 , pp. 163 - 174
Copyright
Copyright © Cambridge University Press 2011

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

Benavides, D., Ruiz-Cortés, A., & Trinidad, P. (2005). Automated reasoning on feature models. Proc. 17th Int. Conf. Advanced Information Systems Engineering, CAiSE 2005 (Pastor, O., & Cunha, J.F., Eds.), LNCS, Vol. 3520, pp. 491–503. New York: Springer.Google Scholar
Bowen, J., & Bahler, D. (1991). Conditional existence of variables in generalised constraint networks. Proc. AAAI, pp. 215–220.Google Scholar
Czarnecki, K., & Eisenecker, U. (2000). Generative Programming: Methods, Tools, and Applications. Reading, MA: Addison–Wesley Professional.Google Scholar
Finkel, R.A., & O'Sullivan, B. (2009). Reasoning about conditional constraint specifications. Proc. ICTAI, IEEE Computer Society, pp. 349–353.Google Scholar
Gebser, M., Kaufmann, B., Neumann, A., & Schaub, T. (2007). Clasp: a conflict-driven answer set solver. Proc. LPNMR, pp. 260–265.Google Scholar
Gelle, E., & Faltings, B. (2003). Solving mixed and conditional constraint satisfaction problems. Constraints 8(2), 107–141.CrossRefGoogle Scholar
Giunchiglia, E., Yu, L., & Maratea, M. (2004). Cmodels-2: SAT-based answer set programming. Proc. AAAI.Google Scholar
Hinchey, M., Jackson, M., Cousot, P., Cook, B., Bowen, J.P., & Margaria, T. (2008). Software engineering and formal methods. Communications of the ACM 51(9), 54–59.Google Scholar
Jackson, D. (2002). Alloy: a lightweight object modelling notation. ACM Transactions on Software Engineering and Methodology 11(2), 256–290.CrossRefGoogle Scholar
Junker, U. (2006). Configuration. In Handbook of Constraint Programming, Foundations of Artificial Intelligence (Rossi, F., van Beek, P., Walsh, T., Eds.), pp. 837–873. New York: Elsevier.CrossRefGoogle Scholar
Mailharro, D. (1998). A classification and constraint-based framework for configuration. Artificial Intelligence for Engineering, Design, Analysis and Manufacturing 12, 383–397.CrossRefGoogle Scholar
Mittal, S., & Falkenhainer, B. (1990). Dynamic constraint satisfaction problems. Proc. AAAI-90, pp. 25–32.Google Scholar
Niemelä, I., & Simons, P. (1997). Smodels—an implementation of the stable model and well-founded semantics for normal logic programs. In Logic Programming and Nonmonotonic Reasoning (Dix, J., Furbach, U., & Nerode, A., Eds.), LNCS, Vol. 1265, pp. 420–429. New York: Springer.CrossRefGoogle Scholar
Sabin, D., & Freuder, E.C. (1996). Configuration as composite constraint satisfaction. Proc. Artificial Intelligence and Manufacturing. Research Planning Workshop (Luger, G.F., Ed.), pp. 153–161. Menlo Park, CA: AAAI Press.Google Scholar
Sabin, D., & Weigel, R. (1998). Product configuration frameworks—a survey. IEEE Intelligent Systems 13(4), 42–49.Google Scholar
Sabin, M., & Freuder, E.C. (1998). Detecting and resolving inconsistency and redundancy in conditional constraint satisfaction problems. Proc. CP98 Workshop on Constraint Problem Reformulation.Google Scholar
Sabin, M., & Gelle, E. (2006). Evaluation of solving models for conditional constraint satisfaction problems. Proc. AAAI. New York: AAAI Press.Google Scholar
Segura, S. (2008). Automated analysis of feature models using atomic sets. Proc. 1st Workshop on Analyses of Software Product Lines (ASPL 2008), SPLC'08, pp. 201–207, Limerick, Ireland.Google Scholar
Stumptner, M., Friedrich, G.E., & Haselböck, A. (1998). Generative constraint-based configuration of large technical systems. Artificial Intelligence for Engineering, Design, Analysis and Manufacturing 12, 307–320.Google Scholar
Torlak, E., Chang, F.S.-H., & Jackson, D. (2008). Finding minimal unsatisfiable cores of declarative specifications. In FM (Cuellar, J., Maibaum, T.S.E., & Sere, K., Eds.), LNCS, Vol. 5014, pp. 326–341. New York: Springer.Google Scholar