=Paper=
{{Paper
|id=Vol-3193/paper2ASPOCP
|storemode=property
|title=Conflict Handling in Product Configuration using Answer Set Programming
|pdfUrl=https://ceur-ws.org/Vol-3193/paper2ASPOCP.pdf
|volume=Vol-3193
|authors=Konstantin Herud,Joachim Baumeister,Orkunt Sabuncu,Torsten Schaub
|dblpUrl=https://dblp.org/rec/conf/iclp/HerudBSS22
}}
==Conflict Handling in Product Configuration using Answer Set Programming==
https://ceur-ws.org/Vol-3193/paper2ASPOCP.pdf
Conflict Handling in Product Configuration using
Answer Set Programming
Konstantin Herud1 , Joachim Baumeister1,2 , Orkunt Sabuncu3,4 and Torsten Schaub4,5
1
denkbares GmbH, Germany
2
University of Würzburg, Germany
3
TED University, Turkey
4
Potassco Solutions, Germany
5
University of Potsdam, Germany
Abstract
Product configuration is one of the most important industrial applications of artificial intelligence. In
order to enable customers to individualize complex products, usually logical configuration models are
necessary. One challenge that exists here is the communication of product knowledge to the customer.
This work deals with the situation of invalid customer requirements under given logical constraints. The
goal is to explain why configurations are invalid and how they can be minimally changed to become
valid again. This involves computing all minimal subsets of both constraints and requirements that make
the configuration unsatisfiable. For this, we present a novel approach based on the declarative paradigm
of Answer Set Programming. We empirically demonstrate its suitability for real-time configurators with
thousands of features and constraints. The approach thus fills the gap of an easy-to-implement as well
as high-performing conflict resolution component.
Keywords
Product Configuration, Conflict Explanation, Conflict Resolution, Answer Set Programming, Minimally
Unsatisfiable Subsets
1. Introduction
Product configuration deals with the commercial interest of making an offering more attractive
by allowing it to be personalized by customers. As a result, products or services are more
likely to be purchased. Instead of offering a predefined set of cars, for example, customers can
instead assemble the exact car they want from components such as different wheels, colors,
and assistants. Many products are also often too complex that there is no other option than to
configure them specifically for each customer. This typically happens with non-standardizable
parameters, such as the dimensions and quantity of window blinds. Similar to software devel-
opment, product configuration has thus accompanied many companies for a long time. It is
therefore considered one of the most successful applications of artificial intelligence. Product
configuration is not only used for simple products, but for a variety of diverse problems [1].
Examples include railway interlocking systems [2], cement plants [3], mobile phone networks
Federated Logic Conference: ICLP Workshops, July 31 – August 12, 2022, Haifa, Israel
Envelope-Open konstantin.herud@denkbares.com (K. Herud); joachim.baumeister@denkbares.com (J. Baumeister);
orkunt.sabuncu@tedu.edu.tr (O. Sabuncu); torsten@cs.uni-potsdam.de (T. Schaub)
© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). Editors: Joaquin Arias,
Roberta Calegari, Luke Dickens, Gopal Gupta, Markus Hecher, Daniela Inclezan, Emily LeBlanc, Elmer Salazar, Jessica Zangari
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)
[4], offers, contracts, user manuals, or technical documentation [5], and services like elevator
maintenance [6]. Despite its long history and profitability, there are still several issues that make
implementing product configuration a challenge. Here, there are two sides: On the one hand,
the business side, where the main challenge is collaboratively developing and continuously
maintaining a knowledge base about a product. On the other hand, the customer side, which is
concerned with intuitively communicating the knowledge. Both sides divide into numerous
sub-challenges. This paper addresses one challenge, namely resolving conflicts interactively
with the customer during the configuration process. A conflict here denotes an unsatisfiable set
of user selected feature requirements which result in a configuration that cannot be manufac-
tured or sold. While this notion will be defined in more detail, we pursue two goals based on it
in this work:
1. Explanation: It should be explained how the user requirements violate the constraints
of the configuration model.
2. Resolution: Recommendations should be made to the user as to which requirements
they should change to resolve the conflict.
To avoid overwhelming the user with unnecessary information, minimal subsets have to be
calculated in both cases. For Goal 1 these are the subsets of unsatisfied constraints. For Goal 2
they are the subsets of feature selections that make the configuration unsatisfiable. Although
various solutions for computing minimal subsets exist, e. g., QuickXPlain [7], these encounter
several problems. First, it is costly and error-prone to implement these solutions by oneself.
QuickXPlain is one of the most popular approaches, yet there is no reference implementation.
Second, regarding performance, there are both qualitative and quantitative challenges. Since
configurators are mostly interactive, response times must be in real time and scalable to a
large number of customers. To address all of these challenges, we present a novel approach
based on Answer Set Programming (ASP), a declarative problem solving paradigm [8, 9]. The
contribution of this work therefore is threefold:
• We present a general and extensible framework for modeling product configuration using
ASP.
• We present an easy-to-implement approach for explaining and resolving conflicts during
product configuration.
• We demonstrate the high performance of the approach, which makes it well suited for
real-time applications.
For this, in Section 2, we first define product configuration and in particular the explanation as
well as the resolution of conflicts. Based on this definition of the problem, we show the related
literature in Section 3. Here, we first discuss the broader context, then specifically ASP and the
algorithm needed for our implementation. Subsequently, we present this implementation in
Section 4 and show an evaluation of our approach in Section 5. Finally, we conclude this work
in Section 6.
2. Definition
Product configuration is a well researched area and there are several efforts for a general
ontology [10, 11, 12]. However, we keep the definition of product configuration in Section 2.1
as simple as possible for the scope of this work. The ideas presented are nevertheless easily
extendable to more complex ontologies. Moreover, the approaches can also be applied to the
superset of configuration problems in general. Section 2.2 will therefore formally define and
illustrate the problem of explaining conflicts during (product) configuration. Section 2.3 follows
equivalently with the resolution of conflicts.
2.1. Product Configuration
Product configuration involves the feature-based personalization of a product, which is as-
sembled from various components. A simple example of this is the configuration of a car.
Customizable features here include the type of steering wheel and the color of the casing. The
lowest common denominator of general ontologies are therefore features and their type in the
knowledge modeling, i. e., variable characteristics of the product and their domains.
Definition 1 (Feature). The properties of a product are specified by 1 ≤ 𝑖 ≤ 𝑘 features. A
feature 𝑓𝑖 is a variable defined by its feature type. The type domain (𝑓𝑖 ) of a feature determines
its discrete, finite, and non-empty domain.
We use typewriter font for concrete examples and write features with a capital initial letter.
Domain values are completely capitalized. For example, the color of a car could be described by
a feature Color , where domain (Color ) = {BLACK , WHITE , RED }. Features define the structural
knowledge about configurable aspects in a product. But a large part of the knowledge is
behavioral, i. e., the constraints on the interaction between features. The set of all possible
configurations results from the cross product of the domains of all features. However, usually
only a fraction of them form valid configurations, i. e., combinations of feature values that can
be manufactured. To capture this set of valid solutions in the space of all possible solutions,
constraints are defined.
Definition 2 (Constraint). A constraint 𝑐 restricts the solution space of possible configurations.
It is defined as a relation that maps a configuration 𝑋 to a boolean truth value, i. e.,
𝑐 ∶ 𝑋 → {⊤, ⊥} . (1)
While the configuration will be defined in more detail shortly, the combination of features
and constraints of a product forms a knowledge base.
Definition 3 (Configuration Knowledge Base). A configuration knowledge base is a triple
(𝐹 , 𝐷, 𝐶), where 𝐹 is the set of all features, 𝐷 is the set of all feature types, and 𝐶 is a set of
constraints over 𝐹.
Although here we bypass the dynamic nature of product configuration, where features
become active depending on the configuration, our approach can be easily extended to do so.
This requires introducing cardinalities for features, e. g., to define optional features. Regardless,
the knowledge base can be used to offer individual configurations to customers.
Definition 4 (Configuration). A configuration 𝑋 binds values 𝑥 to features 𝑓𝑖 ∈ 𝐹 in a knowledge
base (𝐹 , 𝐷, 𝐶).
𝑋 = {𝑓𝑖 = 𝑥 ∣ 𝑓𝑖 ∈ 𝐹 ∧ 𝑥 ∈ domain (𝑓𝑖 )} . (2)
𝑋 is complete, if (3) holds, and valid if (4) holds.
complete (𝑋) ∶ ∀𝑓𝑖 ∈ 𝐹 ∶ 𝑓𝑖 ∈ 𝑋 (3)
valid (𝑋) ∶ ∀𝑐 ∈ 𝐶 ∶ 𝑐 (𝑋) = ⊤ (4)
A configuration is therefore merely the finished process of feature binding where exactly one
value exists for each feature. The user requirements 𝑈 are a partial configuration, where each
feature assignment 𝑓𝑖 = 𝑥 is explicitly given by the user. Neither complete (𝑈) nor valid (𝑈) have
to be true. If valid (𝑈) holds, the configuration task consists of completing 𝑈 to a configuration
𝑋 such that complete (𝑋) and valid (𝑋) holds. Note that multiple configurations may be possible
for completing a configuration task. The amount of options is upper bounded by the cross
product of the domains of all features. There is not always a solution to a configuration problem,
though, namely when valid (𝑈) does not hold. In this paper we are interested in exactly this
case, which we refer to as conflict. To sell a configuration despite invalid requirements, the
conflict must be explained and resolved interactively with the customer.
2.2. Explaining Conflicts
Explaining conflicts requires two steps:
1. An analysis of the set of violated constraints
2. A description of the violated constraints in natural language
Even if the general definition 2 of constraints as arbitrary relations is restricted to, for example,
first order logic, it is very difficult to automatically generate natural language explanations.
While it is easy to assemble explanations from blocks of text for each logical operator, the
result is typically hard to parse and not helpful to the user. In most cases, it is also not in a
company’s best interest to disclose the exact constraints of the knowledge base to the public.
Instead, to concisely explain the higher purpose of violated constraints and in particular the
interaction of multiple constraints, usually external knowledge is required. We therefore argue
that explanations have to be manufactured in natural language as part of knowledge modeling.
One solution to this may be the use of modern language modeling and its ability for zero shot
learning [13]. This involves solving problems at test time that did not occur during training.
Here, for example, the models are able to summarize error messages from long log files into
natural language explanations. However, we leave this research question open as future work.
Instead, this paper focuses on Step 1 — the analysis of violated constraints. These are especially
important for debugging during the development of the knowledge base. Although it is easy to
output which constraint was violated during the reasoning process, two challenges arise:
1. A conflict only arises through the interaction of several constraints. Each individual
constraint would not yield an unsatisfiable configuration.
2. Only the minimal set of constraints yielding an unsatisfiable configuration has to be
determined. Note that there may be several independent sets.
As an example, we look again at the car configuration problem. Here, among others, four
constraints exist, for example, as a consequence of a larger table of allowed values.
• 𝑐0 ∶ Body = OFF_ROAD → Drive = ALL_WHEEL
• 𝑐1 ∶ Drive = ALL_WHEEL → Transmission = AUTOMATIC
• 𝑐2 ∶ Transmission = AUTOMATIC → CruiseControl = TRUE
• 𝑐3 ∶ ((Leather = TRUE ) ∧ (Color = BLACK ∨ Color = WHITE )) ∨ …
Note that this example formally hurts the definition of a constraint as a relation, but
it is purely for intuition. Body determines the type of car, e. g., sport, cabriolet, or
SUV, and Color its finish. A customer now wants to buy a black off-road vehicle,
i. e., 𝑈0 = {Body = OFF_ROAD , Color = BLACK }. Since they want to save money, they
choose faux leather and deactivate the cruise control assistant resulting in 𝑈1 = 𝑈0 ∪
{Leather = FAUX , CruiseControl = FALSE }. The example is tailored to intuitively see that
the user requirements are thereby unsatisfiable. In addition, both Challenges 1 and 2 are
illustrated.
1. There is a chain of constraints which only together yield unsatisfiability, namely 𝑐0 , 𝑐1 ,
and 𝑐2 together with requirements for CruiseControl and Body .
2. Two independent conflicts occur. First, the conflict chain of the previous point. Second,
the choice of color Color which is incompatible with the faux leather Leather by 𝑐3 .
Based on this, we define the goal of analysing conflicts in Equation 5. It consists of determining
the set 𝐶 − of all ⊆-minimal sets of constraints which alone lead to the unsatisfiability of user
requirements 𝑈.
𝐶 − = {𝐶𝑖− ⊆ 𝐶 ∣ ¬valid (𝑈) given (𝐹 , 𝐷, 𝐶 ∩ 𝐶𝑖− )}
(5)
such that ∀𝐶𝑖 , 𝐶𝑗 ∈ 𝐶 − ∶ 𝐶𝑖 ⊈ 𝐶𝑗 .
2.3. Resolving Conflicts
In practice, a suggestion should be offered to the user on how to change the set of unsatisfiable
requirements 𝑈 to resolve all conflicts. For this, a subset of 𝑈 needs to be found, whose removal
makes it possible to complete 𝑈 into a valid configuration 𝑋 again. Again, there are two
challenges:
1. There can be different ways to resolve a conflict. For example, with a constraint on a
combination of multiple features, each individual feature can be reset on its own.
2. Each way to resolve a conflict should be minimal, i. e., no subset of any possibility also
leads back to satisfiability.
Given Challenge 1, we are interested in computing all ⊆-minimal candidates for resolving the
conflict. These can be subsequently ranked by a recommender system to maximize user or
company interest. We again examine the car example from Section 2.2. To resolve the two
conflicts under the given four constrains and the requirements
{Body = OffRoad , Color = Black , Leather = Faux , CruiseControl = False }
there are four optimal possibilities for removing requirements.
1. {CruiseControl , Color } 3. {Body , Color }
2. {CruiseControl , Leather } 4. {Body , Leather }
Similarly to explaining conflicts the task of resolving conflicts defines itself by calculating
⊆-minimal answers. Instead of the constraints, however, all sets 𝑈 − of the user requirements
are to be computed, by whose exclusion the configuration becomes valid again.
𝑈 − = {𝑈𝑖− ⊆ 𝑈 ∣ valid (𝑈 ⧵ 𝑈𝑖− ) given (𝐹 , 𝐷, 𝐶)}
(6)
such that ∀𝑈𝑖 , 𝑈𝑗 ∈ 𝑈 − ∶ 𝑈𝑖 ⊈ 𝑈𝑗 .
Note that every single set 𝑈𝑖− ∈ 𝑈 − must contain at least one value for all 𝐶𝑖− ∈ 𝐶 − , that gives
rise to the respective conflict, i. e., |𝑈𝑖 | ≥ |𝐶 − |. For this reason, each of the four conflict resolution
options consists of two features, one for each of the conflicts.
3. Background
Based on the preceding problem definition, we now contextualize our work in the literature in
Section 3.1 and present the background of Answer Set Programming in Section 3.2.
3.1. Related Work
The explanation of unsatisfiable constraint systems has a large background [14, 15, 16, 17, 18,
19, 20, 21, 22, 23]. The vast majority of these approaches are based on the notion of a Minimally
Unsatisfiable Subset (MUS) [24]. Given a set of constraints 𝐶, a subset 𝐶̂ ⊆ 𝐶 is a MUS if 𝐶̂
is unsatisfiable and for each 𝐶̂𝑖 ⊂ 𝐶̂ is satisfiable. Note that our goal of explaining conflicts
corresponds to the computation of all MUSs. These are computed over the set of constraints
in the knowledge base. The set of user requirements 𝑈 corresponds to hard, non-relaxable
constraints. Besides MUSs, another important concept is Minimal Correction Subsets (MCS) [24].
Given a set of constraints 𝐶, a subset 𝐶̂ ⊆ 𝐶 is a MCS if 𝐶 ⧵ 𝐶̂ is satisfiable and for each 𝐶̂𝑖 ⊂ 𝐶̂ is
unsatisfiable. Similarly, our goal of conflict resolution corresponds to the computation of MCSs.
This time U is a set of relaxable soft constraints and the knowledge base constraints are hard.
Finally, there is an important relation between MUS and MCS [24]. Let 𝑋 be a finite collection
of sets. A hitting set 𝐻 𝑆 (𝑋) is defined as ∀𝑋𝑖 ∈ 𝑋 ∶ 𝐻 𝑆 (𝑋) ∩ 𝑋𝑖 ≠ ∅. It is minimal if there is no
proper subset of it that is also a hitting set of 𝑋. The MUS/MCS duality states that any MCS of a
problem instance is a hitting set of all MUSs of that instance and, correspondingly, any MUS is
a hitting set of all MCSs. Similar to many other methods, we make use of this relationship.
A recent survey classifies methods along four dimensions [25]: First, whether the solution is
solver-specific or solver-agnostic. Solver-agnostic methods typically use a-posteriori analyses
to generate explanations. In this respect, our approach is specific to Conflict Driven Nogood
Learning [26], though agnostic to the specific implementation. The second dimension is user or
solver focused. Our explanations are directed at users rather than to support the search process
of a solver. The third dimension is about various quality metrics, e. g., to prefer the smallest
possible explanation size. Since our methods potentially find all unsatisfiable constraint and user
requirement sets, any kind of ranking metrics can be easily implemented. This also provides
an answer to the last dimension, namely whether all or only a subset of the declarations are
computed. It is relevant here to mention that our conflict analysis is only partially any-time
capable, but our conflict resolution works completely any-time, which is explained in more
detail in Section 4.
While there is a lot of literature on general approaches for constraint satisfaction problems,
the literature specific to product configuration is much sparser [7, 27]. Lastly, there is a small
amount that deals with product configuration using ASP, however we are not aware of any
approaches that perform conflict analysis during product configuration using ASP. Our work
thus fills this gap of an easy-to-implement conflict resolution component.
3.2. Answer Set Programming
A logic program in Answer Set Programming consists of rules of the form
a 1 ; … ; a 𝑚 :- a 𝑚+1 , … , a 𝑛 , not a 𝑛+1 , … , not a 𝑜 .
where each a 𝑖 is an atom of form p(t 1 ,...,t 𝑘 ) and all t 𝑖 are terms, composed of function
symbols and variables. For 1 ≤ 𝑚 ≤ 𝑛 ≤ 𝑜, atoms a 1 to a 𝑚 are often called head atoms, while
a 𝑚+1 to a 𝑛 and not a 𝑛+1 to not a 𝑜 are also referred to as positive and negative body literals,
respectively. An expression is said to be ground, if it contains no variables. As usual, not denotes
(default) negation. A rule is called a fact if 𝑚 = 𝑛 = 𝑜 = 1, normal if 𝑚 = 1, and an integrity
constraint if 𝑚 = 0. In this work, we deal with normal logic programs only. Semantically, a logic
program induces a set of stable models, being distinguished models of the program determined
by the stable models semantics [28].
To ease the use of ASP in practice, several extensions have been developed. First of all,
rules with variables are viewed as shorthands for the set of their ground instances. Further
language constructs include conditional literals and cardinality constraints [29]. The former
are of the form a:b 1 ,...,b 𝑚 , the latter can be written as s {d 1 ;...;d 𝑛 } t , where a and b 𝑖 are
possibly negated (regular) literals and each d 𝑗 is a conditional literal; s and t provide optional
lower and upper bounds on the number of satisfied literals in the cardinality constraint. We
refer to b 1 ,...,b 𝑚 as a condition. The practical value of both constructs becomes apparent
when used with variables. For instance, a conditional literal like a(X):b(X) in a rule’s body
expands to the conjunction of all instances of a(X) for which the corresponding instance of
b(X) holds. Similarly, 2 {a(X):b(X)} 4 is true whenever at least two and at most four instances
of a(X) (subject to b(X) ) are true. Note that we name a normal rule with a cardinality constraint
construct as the head a choice rule.
Next, let us consider a system directive particular to clingo. Clingo offers means for manipu-
lating the solver’s decision heuristics. We rely on this capacity to compute answer sets that are
subset minimal with respect to the choices of the solver. Such heuristic directives are of form
#heuristic a:b 1 ,...,b 𝑚 . [w,m]
where a:b 1 ,...,b 𝑚 is a conditional literal; w is a numeral term and m a heuristic modifier,
indicating how the solver’s heuristic treatment of a should be changed whenever b 1 ,...,b 𝑚
holds. The modifier false , for instance, not only assigns w as the level of a given that clingo
decides first upon atoms of the highest level, but also enforces that a becomes false whenever it
is chosen by the solver.
Finally, Algorithm 1 for finding ⊆-minimal answers involves two ideas [30].
1. First, all atoms 𝑇 that are to be ⊆-minimized are set to false using heuristic directives
before deciding on the truth values of other atoms. This ensures that the first answer 𝑆
found is ⊆-minimal with respect to 𝑇.
2. To enumerate all ⊆-minimal responses, the solver adds a nogood over the true atoms in
𝑆 ⊆ 𝑇 after each call. This constraint ensures that no superset of the ⊆-minimal answer is
found, which ultimately leads to enumerating all ⊆-minimal answers.
The loop of solving and adding nogoods is iterated until the program is no longer satisfiable
and thus all answers have been found.
Input: Program 𝑃 and atoms 𝑇 to subset minimize
foreach 𝑥 ∈ 𝑇 do
SetSign(𝑥, 𝑓 𝑎𝑙𝑠𝑒, 1);
while satisfiable do
S←Solve(P);
P←AddConstraint(⊥ ← 𝑎0 , … , 𝑎𝑛 for {𝑎0 , … , 𝑎𝑛 } = 𝑇 ∩ 𝑆);
Output(𝑆);
Algorithm 1: Algorithm used for finding minimal subsets [30]
4. Implementation
This section shows how to make use of ASP for the problem definition of Section 2. For that, we
first define the product configuration knowledge base in ASP syntax. Then, both conflict analysis
and resolution are presented. Note that ASP generally restricts the definition of constraints
as arbitrary relations. However, clingooffers with so-called theories capabilities to introduce
foreign solving techniques and thus to remove this restriction [31]. For the scope of this paper,
we nevertheless limit the expressive power of constraints to the capabilities of ASP.
4.1. Problem Modelling
In ASP, problem instances are specified as facts. For this, we first formulate the structural and
behavioral knowledge. We then describe the solution path of the search problem, known as
encoding.
4.1.1. Structural Knowledge
The main predicate of the hierarchy is feature/2 with arguments TYPE , and NAME . Note that by
convention capitalized symbols define variables. Here for feature 𝑓𝑖 , TYPE refers to domain (𝑓𝑖 )
and NAME is the unique feature name. These are specified as facts in the program, i. e., the
variables are replaced with specific values. The domain of concrete features is defined using
domain/2 to specify a value VALUE for domain TYPE . Lastly, value/2 exists to bind values VALUE
to features FEATURE . This predicate is used during inference and to specify user requirements.
4.1.2. Behavioral Knowledge
Since constraints are part of a specific problem instance, we reify them into facts from which
respective rules are instantiated [31]. For this purpose, we formulate a simplified meta-encoding
to instantiate equations, disjunctions, conjunctions, and negations from facts. The facts contain
literal identifiers, e. g. variables X, L, R, O , or A as arguments, which are abstract symbols.
holds(X) :- eq(X, L, R), value(L, VL), value(R, VR), VL = VR.
holds(X) :- or(X), #count{ O : or(X, O), holds(O)} > 0.
holds(X) :- and(X), #count{ A : and(X, A), not holds(A)} = 0.
holds(X) :- neg(X, N), not holds(N).
Thus, arbitrarily complex syntax trees of logical statements can be created. Note that this
encoding can be easily extended, e.g. to formulate inequalities or arithmetic expressions.
Wherever we use predicates with the same name but different arity, e. g. or/1 and or/2 , the
shorter predicates just omit the last arguments.
4.1.3. Generate and Test
We define the encoding of the problem according to the “generate and test” ASP convention.
First, a choice rule describes a set of all possible solutions, i. e., a simple superset of the set of
solutions to the given search problem.
1 {value(F, V) : domain(T, V)} 1 :- feature(T, F).
Second, it is followed by an integrity check, which eliminates all solutions that lead to an invalid
configuration, i. e.,
:- constraint(C), not holds(C).
Here C points to the root literal of the syntax tree for any constraint.
4.2. Explaining Conflicts
Conflict analysis requires finding the set of all ⊆-minimal constraint sets of a knowledge
base (𝐹 , 𝐷, 𝐶) that alone yield unsatisfiability. Instead of directly calculating these minimally
unsatisfiable subsets (MUSs) it is easier to calculate minimal correction sets (MCSs). This requires
only an additional predicate mcs/1 , which takes as argument the literal C of a constraint/1
atom. The solver decides about the truth value of mcs/1 to deactivate constraints as desired. To
then determine all MCSs, the solver initially assigns all mcs/1 -atoms to false, as presented in
Section 3.2, and learns nogoods about all included mcs/1 -atoms after each answer. This requires
a modification of the previous integrity check: it cannot be that a constraint does not hold and
is not part of a MCS.
{mcs(C) : constraint(C)}.
:- constraint(C), not holds(C), not mcs(C).
#heuristic mcs(C) : constraint(C). [1,false]
It is then easy to use the MUS/MCS duality from subsection 3.1 to compute the corresponding
MUSs, i. e., the hitting sets of the MCSs. A pure solution in ASP without further implementation
requires for example the encoding below.
{mus(C) : mcs(I, C)}.
:- mcs(I), #count{ C : mus(C), mcs(I, C)} != 1.
Here mcs/2 is the I -th MCS with constraint C and mus/1 is a MUS with constraint C (the index
is implicitly given by the answer set). Note that this happens in a separate step. However, the
complexity is much less than computing the MCSs and thus negligible. For the car example in
Section 2.2 three MCSs result:
1. {𝑐0 , 𝑐3 } 2. {𝑐1 , 𝑐3 } 3. {𝑐2 , 𝑐3 }
From which the following MUSs are calculated:
1. {𝑐0 , 𝑐1 , 𝑐2 } 2. {𝑐3 }
Besides simplicity, a major advantage is the loose description of constraints. The approach
is thus agnostic about their concrete implementation. E. g., theory atoms [32] can be easily
implemented to simplify numerical calculations [33].
4.3. Resolving Conflicts
For conflict resolution, we need to find the ⊆-minimal set of user requirements 𝑈 to change.
Similar to the previous section, we introduce two predicates mcs/2 and assumption/2 . Both
take as arguments a FEATURE and VALUE . Note that this formulation is a simplification and can
easily be generalized to arbitrary arguments. We then formulate an encoding around the original
choice rule for selecting values out of feature domains. Again, we let the solver decide on the
truth value of the mcs/2 atom. If it chooses false, the passed assumption is true, i. e., the original
user requirement. Otherwise, the solver can make a free choice for the feature. To determine the
⊆-minimal required changes, the solver again uses the algorithm from Section 3.2 and initially
assigns all mcs/2 -atoms to false. The following listing shows the required modification of the
ASP encoding, with the first line giving an example of assumption/2 .
assumption(color, black).
{mcs(F, V)} :- assumption(F, V).
value(F, V) :- assumption(F, V), not mcs(F, V).
#heuristic mcs(F, V) : assumption(F, V). [1,false]
5. Evaluation
Finally, we demonstrate the high performance of our approach in Section 5.2. For legal reasons,
we do not publish real knowledge bases, but generate synthetic knowledge bases utilizing real
ones in Section 5.1.
5.1. Dataset
To evaluate the performance of our approach, we probabilistically generate synthetic knowl-
edge bases (𝐹 , 𝐷, 𝐶) for publication. Here, the parameters of the probabilistic distributions are
extracted from real knowledge bases of industrial partners. First, 𝐹 and 𝐷 are generated. The
Table 1
The results of our experiments. Each value is the average of 100 problem instances. Size refers to the
amount of both features and constraints in a knowledge base. Choices refers to the amount of decisions
the solver made about choice rules. All experiments were performed with a single CPU core.
(a) Explanation (b) Resolution
Size Grounding Solving Choices Size Grounding Solving Choices
10 1.1 ms 0.24 ms 7 10 1.4 ms 0.4 ms 29
100 12.8 ms 2.4 ms 94 100 18.6 ms 8.0 ms 2,123
1,000 97.4 ms 23.4 ms 954 1,000 135.4 ms 124.8 ms 54,009
10,000 3.1 s 1.0 s 27,885 10,000 4.2 s 2.7 s 1,080,180
number of options of each feature follows a log-normal distribution. Second, a predetermined
number of constraints are generated according to the scheme conditions → consequences. The
conditions are a binomially distributed conjunction of 𝑓𝑖 = 𝑥 or 𝑓𝑖 ≠ 𝑥 pairs. Here, for each
constituent of the conjunction, an 𝑓𝑖 ∈ 𝐹 is drawn at random without replacement, and cor-
respondingly an 𝑥 ∈ domain (𝑓𝑖 ). An empty set of conditions is allowed. The consequences
represent a set of allowed feature combinations, which is the most common constraint type in
our real knowledge bases. We first randomly draw a binomially distributed set of more than one
feature. This set represents the columns of the combination table. Then, the number of allowed
feature-value combinations, i. e., the rows of the table, is generated log-normally distributed.
Each combination here consists of a conjunction over a range of values for each feature. Each
constituent of the conjunction, i.e., a cell of the table, in turn describes as a disjunction a set of
allowed or disallowed values. We ensure that each generated knowledge base allows at least
min (1, 000, 000, |𝐹 |2 ) valid configurations.
Finally, we generate problem instances, i. e., 𝑈 ∶ ¬valid (𝑈). For this we draw a log-normally
distributed percentage 𝑝 of constraints to be violated and slightly modify the integrity check of
our encoding:
:- #count{ C : constraint(C), not holds(C) } != n.
Here 𝑛 = round (𝑝 ∗ |𝐶|). We then let the solver decide randomly during search to generate
diverse instances. Our data is publicly available. 1
5.2. Results
The results of the experiments are shown in Table 1. We evaluate problem instances with
10, 100, 1000 and 10,000 both features as well as constraints. For each size, we create 100
problem instances and report the mean. On average, the programs have relative to their size 890,
10,625, 95,617, and 2,739,913 atoms, and a similar albeit slightly higher number of rules. Note
that grounding may typically be performed only once per knowledge base as a preprocessing
step. Subsequently, for example, assumptions or multishot capabilities can be used to solve all
problem instances [31].
1
https://github.com/kherud/product-configuration-synthetic-data
6. Conclusion
The explanation of conflicts in unsatisfiable constraint systems has historically been of great
interest. Although a variety of approaches exist, they are often purely of academic relevance.
Since there are rarely reference implementations, own implementations require profound
scientific knowledge. These problems make conflict analysis a major challenge in practice.
Product configuration is one of the most important practical areas of artificial intelligence.
Yet, comparatively little literature exists that addresses its application in practice. Answer Set
Programming (ASP) is the right tool due to its declarative abstraction of the problem description
from the solution path. Thus, we first developed a general and extensible framework for
modeling product configuration in ASP. We then showed how both the explanation of conflicts
and their resolution can be solved in under ten lines of declarative ASP syntax. Finally, our
empirical evaluation showed that the technique is well suited for the high performance demands
of real-world applications. A major scientific challenge that remains open is communicating
the identified conflicts to non-expert users in natural language.
References
[1] A. Felfernig, L. Hotz, C. Bagley, J. Tiihonen, Knowledge-based Configuration: From Re-
search to Business Cases, Morgan Kaufmann, Amsterdam, 2014.
[2] A. Falkner, H. Schreiner, Siemens: Configuration and reconfiguration in industry,
Knowledge-Based Configuration: From Research to Business Cases (2014) 199–210.
doi:10.1016/B978- 0- 12- 415817- 7.00016- 5 .
[3] K. Orsvärna, M. H. Bennick, Tacton: Use of tacton configurator at flsmidth, in: Knowledge-
Based Configuration, Morgan Kaufmann, 2014.
[4] I. Nica, F. Wotawa, R. Ochenbauer, C. Schober, H. F. Hofbauer, S. Boltek, Kapsch: Re-
configuration of mobile phone networks, in: Knowledge-Based Configuration, Morgan
Kaufmann, 2014.
[5] R. Rabiser, M. Vierhauser, M. Lehofer, P. Günbacher, T. Männistö, Configuring and
generating technical documents, in: Knowledge-Based Configuration, Morgan Kaufmann,
2014.
[6] J. Tiihonen, W. Mayer, M. Stumptner, M. Heiskala, Configuring services and processes, in:
Knowledge-Based Configuration, Morgan Kaufmann, 2014.
[7] U. Junker, QUICKXPLAIN: preferred explanations and relaxations for over-constrained
problems, in: D. L. McGuinness, G. Ferguson (Eds.), Proceedings of the Nineteenth National
Conference on Artificial Intelligence, Sixteenth Conference on Innovative Applications of
Artificial Intelligence, July 25-29, 2004, San Jose, California, USA, AAAI Press / The MIT
Press, 2004, pp. 167–172. URL: http://www.aaai.org/Library/AAAI/2004/aaai04-027.php.
[8] M. Gebser, R. Kaminski, B. Kaufmann, T. Schaub, Answer Set Solving in Practice, Synthe-
sis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool Pub-
lishers, 2012. URL: https://doi.org/10.2200/S00457ED1V01Y201211AIM019. doi:10.2200/
S00457ED1V01Y201211AIM019 .
[9] V. Lifschitz, Answer Set Programming, Springer, 2019. URL: https://doi.org/10.1007/
978-3-030-24658-7. doi:10.1007/978- 3- 030- 24658- 7 .
[10] S. Mittal, F. Frayman, Towards a generic model of configuraton tasks, in: Proceedings
of the 11th International Joint Conference on Artificial Intelligence - Volume 2, IJCAI’89,
Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1989, p. 1395–1401.
[11] T. Soininen, J. Tiihonen, T. Männistö, R. Sulonen, Towards a general ontology of con-
figuration, Artif. Intell. Eng. Des. Anal. Manuf. 12 (1998) 357–372. URL: http://journals.
cambridge.org/action/displayAbstract?aid=38651.
[12] U. Junker, Configuration, in: F. Rossi, P. van Beek, T. Walsh (Eds.), Handbook of
Constraint Programming, volume 2 of Foundations of Artificial Intelligence, Elsevier,
2006, pp. 837–873. URL: https://doi.org/10.1016/S1574-6526(06)80028-3. doi:10.1016/
S1574- 6526(06)80028- 3 .
[13] T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan,
P. Shyam, G. Sastry, A. Askell, S. Agarwal, A. Herbert-Voss, G. Krueger, T. Henighan,
R. Child, A. Ramesh, D. M. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler,
M. Litwin, S. Gray, B. Chess, J. Clark, C. Berner, S. McCandlish, A. Radford, I. Sutskever,
D. Amodei, Language models are few-shot learners, in: H. Larochelle, M. Ranzato,
R. Hadsell, M. Balcan, H. Lin (Eds.), Advances in Neural Information Processing Systems
33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020,
December 6-12, 2020, virtual, 2020. URL: https://proceedings.neurips.cc/paper/2020/hash/
1457c0d6bfcb4967418bfb8ac142f64a-Abstract.html.
[14] R. Bruni, On exact selection of minimally unsatisfiable subformulae, Ann. Math. Ar-
tif. Intell. 43 (2005) 35–50. URL: https://doi.org/10.1007/s10472-005-0418-4. doi:10.1007/
s10472- 005- 0418- 4 .
[15] J. Huang, MUP: a minimal unsatisfiability prover, in: T. Tang (Ed.), Proceedings of the
2005 Conference on Asia South Pacific Design Automation, ASP-DAC 2005, Shanghai,
China, January 18-21, 2005, ACM Press, 2005, pp. 432–437. URL: https://doi.org/10.1145/
1120725.1120907. doi:10.1145/1120725.1120907 .
[16] F. Hemery, C. Lecoutre, L. Sais, F. Boussemart, Extracting mucs from constraint networks,
in: G. Brewka, S. Coradeschi, A. Perini, P. Traverso (Eds.), ECAI 2006, 17th European
Conference on Artificial Intelligence, August 29 - September 1, 2006, Riva del Garda, Italy,
Including Prestigious Applications of Intelligent Systems (PAIS 2006), Proceedings, volume
141 of Frontiers in Artificial Intelligence and Applications, IOS Press, 2006, pp. 113–117. URL:
http://www.booksonline.iospress.nl/Content/View.aspx?piid=1657.
[17] É. Grégoire, B. Mazure, C. Piette, Extracting muses, in: G. Brewka, S. Coradeschi, A. Perini,
P. Traverso (Eds.), ECAI 2006, 17th European Conference on Artificial Intelligence, August
29 - September 1, 2006, Riva del Garda, Italy, Including Prestigious Applications of Intelli-
gent Systems (PAIS 2006), Proceedings, volume 141 of Frontiers in Artificial Intelligence
and Applications, IOS Press, 2006, pp. 387–391.
[18] H. van Maaren, S. Wieringa, Finding guaranteed muses fast, in: H. K. Büning, X. Zhao
(Eds.), Theory and Applications of Satisfiability Testing - SAT 2008, 11th International
Conference, SAT 2008, Guangzhou, China, May 12-15, 2008. Proceedings, volume 4996
of Lecture Notes in Computer Science, Springer, 2008, pp. 291–304. URL: https://doi.org/10.
1007/978-3-540-79719-7_27. doi:10.1007/978- 3- 540- 79719- 7\_27 .
[19] C. Desrosiers, P. Galinier, A. Hertz, S. Paroz, Using heuristics to find minimal unsatisfiable
subformulas in satisfiability problems, J. Comb. Optim. 18 (2009) 124–150. URL: https:
//doi.org/10.1007/s10878-008-9142-4. doi:10.1007/s10878- 008- 9142- 4 .
[20] J. P. M. Silva, Minimal unsatisfiability: Models, algorithms and applications (invited
paper), in: 40th IEEE International Symposium on Multiple-Valued Logic, ISMVL 2010,
Barcelona, Spain, 26-28 May 2010, IEEE Computer Society, 2010, pp. 9–14. URL: https:
//doi.org/10.1109/ISMVL.2010.11. doi:10.1109/ISMVL.2010.11 .
[21] A. Nadel, Boosting minimal unsatisfiable core extraction, in: R. Bloem, N. Sharygina (Eds.),
Proceedings of 10th International Conference on Formal Methods in Computer-Aided
Design, FMCAD 2010, Lugano, Switzerland, October 20-23, IEEE, 2010, pp. 221–229. URL:
https://ieeexplore.ieee.org/document/5770953/.
[22] V. Ryvchin, O. Strichman, Faster extraction of high-level minimal unsatisfiable cores, in:
K. A. Sakallah, L. Simon (Eds.), Theory and Applications of Satisfiability Testing - SAT
2011 - 14th International Conference, SAT 2011, Ann Arbor, MI, USA, June 19-22, 2011.
Proceedings, volume 6695 of Lecture Notes in Computer Science, Springer, 2011, pp. 174–187.
URL: https://doi.org/10.1007/978-3-642-21581-0_15. doi:10.1007/978- 3- 642- 21581- 0\
_15 .
[23] A. Belov, J. Marques-Silva, Accelerating MUS extraction with recursive model rotation, in:
P. Bjesse, A. Slobodová (Eds.), International Conference on Formal Methods in Computer-
Aided Design, FMCAD ’11, Austin, TX, USA, October 30 - November 02, 2011, FMCAD
Inc., 2011, pp. 37–40. URL: http://dl.acm.org/citation.cfm?id=2157663.
[24] M. H. Liffiton, K. A. Sakallah, Algorithms for computing minimal unsatisfiable sub-
sets of constraints, J. Autom. Reason. 40 (2008) 1–33. URL: https://doi.org/10.1007/
s10817-007-9084-z. doi:10.1007/s10817- 007- 9084- z .
[25] S. D. Gupta, B. Genc, B. O’Sullivan, Explanation in constraint satisfaction: A survey, in:
Z. Zhou (Ed.), Proceedings of the Thirtieth International Joint Conference on Artificial
Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021, ijcai.org,
2021, pp. 4400–4407. URL: https://doi.org/10.24963/ijcai.2021/601. doi:10.24963/ijcai.
2021/601 .
[26] M. Gebser, B. Kaufmann, T. Schaub, Conflict-driven answer set solving: From theory to
practice, Artif. Intell. 187 (2012) 52–89. URL: https://doi.org/10.1016/j.artint.2012.04.001.
doi:10.1016/j.artint.2012.04.001 .
[27] A. Felfernig, M. Schubert, C. Zehentner, An efficient diagnosis algorithm for inconsistent
constraint sets, Artif. Intell. Eng. Des. Anal. Manuf. 26 (2012) 53–62. URL: https://doi.org/
10.1017/S0890060411000011. doi:10.1017/S0890060411000011 .
[28] M. Gelfond, V. Lifschitz, Logic programs with classical negation, in: D. Warren, P. Sz-
eredi (Eds.), Proceedings of the Seventh International Conference on Logic Programming
(ICLP’90), MIT Press, 1990, pp. 579–597.
[29] P. Simons, I. Niemelä, T. Soininen, Extending and implementing the stable model semantics,
Artificial Intelligence 138 (2002) 181–234.
[30] M. Razzaq, R. Kaminski, J. Romero, T. Schaub, J. Bourdon, C. Guziolowski, Computing di-
verse boolean networks from phosphoproteomic time series data, in: M. Češka, D. Šafránek
(Eds.), Computational Methods in Systems Biology, Springer International Publishing,
Cham, 2018, pp. 59–74.
[31] R. Kaminski, J. Romero, T. Schaub, P. Wanko, How to build your own asp-based system?!,
CoRR abs/2008.06692 (2020). URL: https://arxiv.org/abs/2008.06692. arXiv:2008.06692 .
[32] M. Gebser, R. Kaminski, B. Kaufmann, M. Ostrowski, T. Schaub, P. Wanko, Theory solving
made easy with clingo 5, in: M. Carro, A. King, N. Saeedloei, M. D. Vos (Eds.), Technical
Communications of the 32nd International Conference on Logic Programming, ICLP 2016
TCs, October 16-21, 2016, New York City, USA, volume 52 of OASIcs, Schloss Dagstuhl -
Leibniz-Zentrum für Informatik, 2016, pp. 2:1–2:15. URL: https://doi.org/10.4230/OASIcs.
ICLP.2016.2. doi:10.4230/OASIcs.ICLP.2016.2 .
[33] M. Banbara, B. Kaufmann, M. Ostrowski, T. Schaub, Clingcon: The next generation, Theory
Pract. Log. Program. 17 (2017) 408–461. URL: https://doi.org/10.1017/S1471068417000138.
doi:10.1017/S1471068417000138 .