Reasoning about conditional constraint specification problems and feature models

Raphael Finkel, Barry O'Sullivan

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


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.

Original languageEnglish
Pages (from-to)163-174
Number of pages12
JournalArtificial Intelligence for Engineering Design, Analysis and Manufacturing: AIEDAM
Issue number2
StatePublished - May 2011

Bibliographical note

Funding Information:
Raphael Finkel’s work was partially supported by the US National Science Foundation (Grant IIS-0325063). Barry O’Sullivan is funded by the Science Foundation Ireland (Grant 05/IN/I886). Any opinions, findings, conclusions, or recommendations expressed in this material are those of the authors and do not necessarily reflect


  • Alloy
  • Answer-Set Programming
  • Configuration
  • Constraint Satisfaction
  • Flaw Detection

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering
  • Artificial Intelligence


Dive into the research topics of 'Reasoning about conditional constraint specification problems and feature models'. Together they form a unique fingerprint.

Cite this