<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Archiving and Interchange DTD v1.0 20120330//EN" "JATS-archivearticle1.dtd">
<article xmlns:xlink="http://www.w3.org/1999/xlink">
  <front>
    <journal-meta>
      <journal-title-group>
        <journal-title>August</journal-title>
      </journal-title-group>
    </journal-meta>
    <article-meta>
      <title-group>
        <article-title>Conflict Handling in Product Configuration using Answer Set Program ming</article-title>
      </title-group>
      <contrib-group>
        <contrib contrib-type="author">
          <string-name>Konstantin Herud</string-name>
          <email>konstantin.herud@denkbares.com</email>
          <xref ref-type="aff" rid="aff1">1</xref>
          <xref ref-type="aff" rid="aff2">2</xref>
          <xref ref-type="aff" rid="aff6">6</xref>
        </contrib>
        <contrib contrib-type="author">
          <string-name>Joachim Baumeister</string-name>
          <email>joachim.baumeister@denkbares.com</email>
          <xref ref-type="aff" rid="aff1">1</xref>
          <xref ref-type="aff" rid="aff2">2</xref>
          <xref ref-type="aff" rid="aff5">5</xref>
          <xref ref-type="aff" rid="aff6">6</xref>
        </contrib>
        <contrib contrib-type="author">
          <string-name>Orkunt Sabuncu</string-name>
          <email>orkunt.sabuncu@tedu.edu.tr</email>
          <xref ref-type="aff" rid="aff0">0</xref>
          <xref ref-type="aff" rid="aff1">1</xref>
          <xref ref-type="aff" rid="aff2">2</xref>
          <xref ref-type="aff" rid="aff3">3</xref>
        </contrib>
        <contrib contrib-type="author">
          <string-name>Torsten Schaub</string-name>
          <email>torsten@cs.uni-potsdam.de</email>
          <xref ref-type="aff" rid="aff0">0</xref>
          <xref ref-type="aff" rid="aff1">1</xref>
          <xref ref-type="aff" rid="aff2">2</xref>
          <xref ref-type="aff" rid="aff4">4</xref>
        </contrib>
        <aff id="aff0">
          <label>0</label>
          <institution>Potassco Solutions</institution>
          ,
          <country country="DE">Germany</country>
        </aff>
        <aff id="aff1">
          <label>1</label>
          <institution>Product Configuration</institution>
          ,
          <addr-line>Conflict Explanation, Conflict Resolution, Answer Set Programming, Minimally</addr-line>
        </aff>
        <aff id="aff2">
          <label>2</label>
          <institution>Roberta Calegari</institution>
          ,
          <addr-line>Luke Dickens, Gopal Gupta, Markus Hecher, Daniela Inclezan, Emily LeBlanc, Elmer Salazar, Jessica Zangari</addr-line>
        </aff>
        <aff id="aff3">
          <label>3</label>
          <institution>TED University</institution>
          ,
          <country country="TR">Turkey</country>
        </aff>
        <aff id="aff4">
          <label>4</label>
          <institution>University of Potsdam</institution>
          ,
          <country country="DE">Germany</country>
        </aff>
        <aff id="aff5">
          <label>5</label>
          <institution>University of Würzburg</institution>
          ,
          <country country="DE">Germany</country>
        </aff>
        <aff id="aff6">
          <label>6</label>
          <institution>denkbares GmbH</institution>
          ,
          <country country="DE">Germany</country>
        </aff>
      </contrib-group>
      <pub-date>
        <year>2022</year>
      </pub-date>
      <volume>12</volume>
      <issue>2022</issue>
      <abstract>
        <p>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.</p>
      </abstract>
    </article-meta>
  </front>
  <body>
    <sec id="sec-1">
      <title>1. Introduction</title>
      <p>
        Product configuration deals with the commercial interest of making an ofering more attractive
by allowing it to be personalized by customers. As a result, products or services are more
likely to be purchased. Instead of ofering a predefined set of cars, for example, customers can
instead assemble the exact car they want from components such as diferent 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
development, 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 [
        <xref ref-type="bibr" rid="ref1">1</xref>
        ].
Examples include railway interlocking systems [
        <xref ref-type="bibr" rid="ref2">2</xref>
        ], cement plants [
        <xref ref-type="bibr" rid="ref3">3</xref>
        ], mobile phone networks
[
        <xref ref-type="bibr" rid="ref4">4</xref>
        ], ofers, contracts, user manuals, or technical documentation [
        <xref ref-type="bibr" rid="ref5">5</xref>
        ], and services like elevator
maintenance [
        <xref ref-type="bibr" rid="ref6">6</xref>
        ]. 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
manufactured 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.
      </p>
      <p>
        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 [
        <xref ref-type="bibr" rid="ref7">7</xref>
        ], 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 [
        <xref ref-type="bibr" rid="ref8 ref9">8, 9</xref>
        ]. The
contribution of this work therefore is threefold:
• We present a general and extensible framework for modeling product configuration using
      </p>
      <p>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.</p>
      <p>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.</p>
    </sec>
    <sec id="sec-2">
      <title>2. Definition</title>
      <p>
        Product configuration is a well researched area and there are several eforts for a general
ontology [
        <xref ref-type="bibr" rid="ref10 ref11 ref12">10, 11, 12</xref>
        ]. 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.
      </p>
      <sec id="sec-2-1">
        <title>2.1. Product Configuration</title>
        <p>Product configuration involves the feature-based personalization of a product, which is
assembled 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.</p>
        <p>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.</p>
        <p>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.,
 ∶  →
{⊤, ⊥} .</p>
        <p>(1)</p>
        <p>While the configuration will be defined in more detail shortly, the combination of features
and constraints of a product forms a knowledge base.</p>
        <p>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  .</p>
        <p>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 ofer individual configurations to customers.
Definition 4 (Configuration) . A configuration  binds values  to features   ∈  in a knowledge
base ( , ,  ).</p>
        <p>= {  =  ∣   ∈  ∧  ∈
domain (  )} .
 is complete, if (3) holds, and valid if (4) holds.
(2)
(3)
(4)
complete ( ) ∶ ∀  ∈  ∶   ∈ 
valid ( ) ∶ ∀ ∈  ∶ 
( ) = ⊤</p>
        <p>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.</p>
      </sec>
      <sec id="sec-2-2">
        <title>2.2. Explaining Conflicts</title>
        <sec id="sec-2-2-1">
          <title>Explaining conflicts requires two steps:</title>
        </sec>
        <sec id="sec-2-2-2">
          <title>1. An analysis of the set of violated constraints</title>
          <p>
            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,
ifrst order logic, it is very dificult 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 [
            <xref ref-type="bibr" rid="ref13">13</xref>
            ]. 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.
          </p>
          <p>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.</p>
          <p>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 of-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.</p>
          <p>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  .</p>
          <p>− = { − ⊆  ∣ ¬ valid ( ) given ( , ,  ∩</p>
          <p>−)}
such that ∀  ,   ∈  − ∶   ⊈   .
(5)</p>
        </sec>
      </sec>
      <sec id="sec-2-3">
        <title>2.3. Resolving Conflicts</title>
        <p>In practice, a suggestion should be ofered 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 diferent 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.</p>
        <p>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</p>
        <p>{Body = OffRoad, Color = Black, Leather = Faux, CruiseControl = False}
there are four optimal possibilities for removing requirements.</p>
        <p>1. {CruiseControl, Color}
2. {CruiseControl, Leather}
3. {Body, Color}
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 ( , ,</p>
        <p>)}
such that ∀  ,   ∈  − ∶   ⊈   .
(6)
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.</p>
      </sec>
    </sec>
    <sec id="sec-3">
      <title>3. Background</title>
      <sec id="sec-3-1">
        <title>3.1. Related Work</title>
        <p>
          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.
The explanation of unsatisfiable constraint systems has a large background [
          <xref ref-type="bibr" rid="ref14 ref15 ref16 ref17 ref18">14, 15, 16, 17, 18,
19, 20, 21, 22, 23</xref>
          ]. 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.
        </p>
        <p>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.</p>
        <p>
          While there is a lot of literature on general approaches for constraint satisfaction problems,
the literature specific to product configuration is much sparser [
          <xref ref-type="bibr" rid="ref7">7, 27</xref>
          ]. 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.
        </p>
      </sec>
      <sec id="sec-3-2">
        <title>3.2. Answer Set Programming</title>
        <p>A logic program in Answer Set Programming consists of rules of the form
a1 ; … ; a :- a+1</p>
        <p>, … , a , not a+1 , … , not a .
where each a is an atom of form p(t1,...,t ) and all t are terms, composed of function
symbols and variables. For 1 ≤  ≤  ≤  , atoms a1 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].</p>
        <p>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:b1,...,b , the latter can be written as s {d1;...;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 b1,...,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.</p>
        <p>Next, let us consider a system directive particular to clingo. Clingo ofers means for
manipulating 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:b1,...,b . [w,m]
where a:b1,...,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 b1,...,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.</p>
        <p>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.</p>
        <p>The loop of solving and adding nogoods is iterated until the program is no longer satisfiable
and thus all answers have been found.</p>
        <sec id="sec-3-2-1">
          <title>Input: Program  and atoms  to subset minimize</title>
          <p>foreach  ∈  do</p>
          <p>SetSign(,  , 1 );
while satisfiable do</p>
          <p>S←Solve(P);
P←AddConstraint(⊥ ←  0, … ,   for { 0, … ,   } =  ∩  );
Output( );</p>
          <p>Algorithm 1: Algorithm used for finding minimal subsets [ 30]</p>
        </sec>
      </sec>
    </sec>
    <sec id="sec-4">
      <title>4. Implementation</title>
      <p>This section shows how to make use of ASP for the problem definition of Section 2. For that, we
ifrst 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, clingoofers 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.</p>
      <sec id="sec-4-1">
        <title>4.1. Problem Modelling</title>
        <p>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)} &gt; 0.
holds(X) :- and(X), #count{ A : and(X, A), not holds(A)} = 0.
holds(X) :- neg(X, N), not holds(N).</p>
        <p>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 diferent 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).</p>
        <p>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).</p>
        <p>Here C points to the root literal of the syntax tree for any constraint.</p>
      </sec>
      <sec id="sec-4-2">
        <title>4.2. Explaining Conflicts</title>
        <p>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.</p>
        <p>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}</p>
        <p>2. { 1,  3}</p>
        <sec id="sec-4-2-1">
          <title>From which the following MUSs are calculated:</title>
          <p>1. { 0,  1,  2}
2. { 3}
3. { 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].</p>
        </sec>
      </sec>
      <sec id="sec-4-3">
        <title>4.3. Resolving Conflicts</title>
        <p>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]</p>
      </sec>
    </sec>
    <sec id="sec-5">
      <title>5. Evaluation</title>
      <sec id="sec-5-1">
        <title>5.1. Dataset</title>
        <p>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.</p>
        <p>To evaluate the performance of our approach, we probabilistically generate synthetic
knowledge bases ( , ,  ) for publication. Here, the parameters of the probabilistic distributions are
extracted from real knowledge bases of industrial partners. First,  and  are generated. The
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
correspondingly 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.</p>
        <p>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.</p>
        <p>Here  = round ( ∗ || ). We then let the solver decide randomly during search to generate
diverse instances. Our data is publicly available. 1</p>
      </sec>
      <sec id="sec-5-2">
        <title>5.2. Results</title>
        <p>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].
1https://github.com/kherud/product-configuration-synthetic-data</p>
      </sec>
    </sec>
    <sec id="sec-6">
      <title>6. Conclusion</title>
      <p>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.
[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
ComputerAided 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. Lifiton, K. A. Sakallah, Algorithms for computing minimal unsatisfiable
subsets 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 eficient 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.
Szeredi (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,</p>
      <p>Artificial Intelligence 138 (2002) 181–234.
[30] M. Razzaq, R. Kaminski, J. Romero, T. Schaub, J. Bourdon, C. Guziolowski, Computing
diverse 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?!,</p>
      <p>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.</p>
      <p>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.</p>
    </sec>
  </body>
  <back>
    <ref-list>
      <ref id="ref1">
        <mixed-citation>
          [1]
          <string-name>
            <given-names>A.</given-names>
            <surname>Felfernig</surname>
          </string-name>
          ,
          <string-name>
            <given-names>L.</given-names>
            <surname>Hotz</surname>
          </string-name>
          ,
          <string-name>
            <given-names>C.</given-names>
            <surname>Bagley</surname>
          </string-name>
          ,
          <string-name>
            <given-names>J.</given-names>
            <surname>Tiihonen</surname>
          </string-name>
          ,
          <article-title>Knowledge-based Configuration: From Research to Business Cases</article-title>
          , Morgan Kaufmann, Amsterdam,
          <year>2014</year>
          .
        </mixed-citation>
      </ref>
      <ref id="ref2">
        <mixed-citation>
          [2]
          <string-name>
            <given-names>A.</given-names>
            <surname>Falkner</surname>
          </string-name>
          ,
          <string-name>
            <given-names>H.</given-names>
            <surname>Schreiner</surname>
          </string-name>
          ,
          <article-title>Siemens: Configuration and reconfiguration in industry, Knowledge-Based Configuration: From Research to Business Cases (</article-title>
          <year>2014</year>
          )
          <fpage>199</fpage>
          -
          <lpage>210</lpage>
          . doi:
          <volume>10</volume>
          .1016/B978- 0
          <source>- 12- 415817- 7</source>
          .
          <fpage>00016</fpage>
          -
          <lpage>5</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref3">
        <mixed-citation>
          [3]
          <string-name>
            <given-names>K.</given-names>
            <surname>Orsvärna</surname>
          </string-name>
          ,
          <string-name>
            <given-names>M. H.</given-names>
            <surname>Bennick</surname>
          </string-name>
          , Tacton:
          <article-title>Use of tacton configurator at flsmidth</article-title>
          , in: KnowledgeBased Configuration, Morgan Kaufmann,
          <year>2014</year>
          .
        </mixed-citation>
      </ref>
      <ref id="ref4">
        <mixed-citation>
          [4]
          <string-name>
            <given-names>I.</given-names>
            <surname>Nica</surname>
          </string-name>
          ,
          <string-name>
            <given-names>F.</given-names>
            <surname>Wotawa</surname>
          </string-name>
          ,
          <string-name>
            <given-names>R.</given-names>
            <surname>Ochenbauer</surname>
          </string-name>
          ,
          <string-name>
            <given-names>C.</given-names>
            <surname>Schober</surname>
          </string-name>
          ,
          <string-name>
            <given-names>H. F.</given-names>
            <surname>Hofbauer</surname>
          </string-name>
          ,
          <string-name>
            <given-names>S.</given-names>
            <surname>Boltek</surname>
          </string-name>
          ,
          <article-title>Kapsch: Reconfiguration of mobile phone networks, in: Knowledge-Based Configuration</article-title>
          , Morgan Kaufmann,
          <year>2014</year>
          .
        </mixed-citation>
      </ref>
      <ref id="ref5">
        <mixed-citation>
          [5]
          <string-name>
            <given-names>R.</given-names>
            <surname>Rabiser</surname>
          </string-name>
          ,
          <string-name>
            <given-names>M.</given-names>
            <surname>Vierhauser</surname>
          </string-name>
          ,
          <string-name>
            <given-names>M.</given-names>
            <surname>Lehofer</surname>
          </string-name>
          ,
          <string-name>
            <given-names>P.</given-names>
            <surname>Günbacher</surname>
          </string-name>
          , T. Männistö,
          <article-title>Configuring and generating technical documents, in: Knowledge-Based Configuration</article-title>
          , Morgan Kaufmann,
          <year>2014</year>
          .
        </mixed-citation>
      </ref>
      <ref id="ref6">
        <mixed-citation>
          [6]
          <string-name>
            <given-names>J.</given-names>
            <surname>Tiihonen</surname>
          </string-name>
          ,
          <string-name>
            <given-names>W.</given-names>
            <surname>Mayer</surname>
          </string-name>
          ,
          <string-name>
            <given-names>M.</given-names>
            <surname>Stumptner</surname>
          </string-name>
          ,
          <string-name>
            <given-names>M.</given-names>
            <surname>Heiskala</surname>
          </string-name>
          ,
          <article-title>Configuring services and processes, in: Knowledge-Based Configuration</article-title>
          , Morgan Kaufmann,
          <year>2014</year>
          .
        </mixed-citation>
      </ref>
      <ref id="ref7">
        <mixed-citation>
          [7]
          <string-name>
            <given-names>U.</given-names>
            <surname>Junker</surname>
          </string-name>
          ,
          <article-title>QUICKXPLAIN: preferred explanations and relaxations for over-constrained problems</article-title>
          , in: D. L.
          <string-name>
            <surname>McGuinness</surname>
            ,
            <given-names>G.</given-names>
          </string-name>
          Ferguson (Eds.),
          <source>Proceedings of the Nineteenth National Conference on Artificial Intelligence, Sixteenth Conference on Innovative Applications of Artificial Intelligence, July 25-29</source>
          ,
          <year>2004</year>
          , San Jose, California, USA, AAAI Press / The MIT Press,
          <year>2004</year>
          , pp.
          <fpage>167</fpage>
          -
          <lpage>172</lpage>
          . URL: http://www.aaai.org/Library/AAAI/
          <year>2004</year>
          /aaai04-
          <fpage>027</fpage>
          .php.
        </mixed-citation>
      </ref>
      <ref id="ref8">
        <mixed-citation>
          [8]
          <string-name>
            <given-names>M.</given-names>
            <surname>Gebser</surname>
          </string-name>
          ,
          <string-name>
            <given-names>R.</given-names>
            <surname>Kaminski</surname>
          </string-name>
          , B. Kaufmann, T. Schaub, Answer Set Solving in Practice,
          <source>Synthesis Lectures on Artificial Intelligence and Machine Learning</source>
          , Morgan &amp; Claypool Publishers,
          <year>2012</year>
          . URL: https://doi.org/10.2200/S00457ED1V01Y201211AIM019. doi:
          <volume>10</volume>
          .2200/ S00457ED1V01Y201211AIM019.
        </mixed-citation>
      </ref>
      <ref id="ref9">
        <mixed-citation>
          [9]
          <string-name>
            <given-names>V.</given-names>
            <surname>Lifschitz</surname>
          </string-name>
          , Answer Set Programming, Springer,
          <year>2019</year>
          . URL: https://doi.org/10.1007/ 978-3-
          <fpage>030</fpage>
          -24658-7. doi:
          <volume>10</volume>
          .1007/978-3-
          <fpage>030</fpage>
          -24658-7.
        </mixed-citation>
      </ref>
      <ref id="ref10">
        <mixed-citation>
          [10]
          <string-name>
            <given-names>S.</given-names>
            <surname>Mittal</surname>
          </string-name>
          ,
          <string-name>
            <given-names>F.</given-names>
            <surname>Frayman</surname>
          </string-name>
          ,
          <article-title>Towards a generic model of configuraton tasks</article-title>
          ,
          <source>in: Proceedings of the 11th International Joint Conference on Artificial Intelligence -</source>
          Volume
          <volume>2</volume>
          , IJCAI'
          <fpage>89</fpage>
          , Morgan Kaufmann Publishers Inc., San Francisco, CA, USA,
          <year>1989</year>
          , p.
          <fpage>1395</fpage>
          -
          <lpage>1401</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref11">
        <mixed-citation>
          [11]
          <string-name>
            <given-names>T.</given-names>
            <surname>Soininen</surname>
          </string-name>
          ,
          <string-name>
            <given-names>J.</given-names>
            <surname>Tiihonen</surname>
          </string-name>
          ,
          <string-name>
            <given-names>T.</given-names>
            <surname>Männistö</surname>
          </string-name>
          ,
          <string-name>
            <given-names>R.</given-names>
            <surname>Sulonen</surname>
          </string-name>
          ,
          <article-title>Towards a general ontology of conifguration</article-title>
          ,
          <source>Artif. Intell. Eng. Des. Anal. Manuf</source>
          .
          <volume>12</volume>
          (
          <year>1998</year>
          )
          <fpage>357</fpage>
          -
          <lpage>372</lpage>
          . URL: http://journals. cambridge.org/action/displayAbstract?aid=
          <fpage>38651</fpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref12">
        <mixed-citation>
          [12]
          <string-name>
            <given-names>U.</given-names>
            <surname>Junker</surname>
          </string-name>
          , Configuration, in: F. Rossi, P. van Beek, T. Walsh (Eds.),
          <source>Handbook of Constraint Programming, volume 2 of Foundations of Artificial Intelligence , Elsevier</source>
          ,
          <year>2006</year>
          , pp.
          <fpage>837</fpage>
          -
          <lpage>873</lpage>
          . URL: https://doi.org/10.1016/S1574-
          <volume>6526</volume>
          (
          <issue>06</issue>
          )
          <fpage>80028</fpage>
          -
          <lpage>3</lpage>
          . doi:
          <volume>10</volume>
          .1016/ S1574-
          <volume>6526</volume>
          (
          <issue>06</issue>
          )
          <fpage>80028</fpage>
          -
          <lpage>3</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref13">
        <mixed-citation>
          [13]
          <string-name>
            <surname>T. B. Brown</surname>
            ,
            <given-names>B.</given-names>
          </string-name>
          <string-name>
            <surname>Mann</surname>
            ,
            <given-names>N.</given-names>
          </string-name>
          <string-name>
            <surname>Ryder</surname>
            ,
            <given-names>M.</given-names>
          </string-name>
          <string-name>
            <surname>Subbiah</surname>
            ,
            <given-names>J.</given-names>
          </string-name>
          <string-name>
            <surname>Kaplan</surname>
            ,
            <given-names>P.</given-names>
          </string-name>
          <string-name>
            <surname>Dhariwal</surname>
            ,
            <given-names>A.</given-names>
          </string-name>
          <string-name>
            <surname>Neelakantan</surname>
            ,
            <given-names>P.</given-names>
          </string-name>
          <string-name>
            <surname>Shyam</surname>
            ,
            <given-names>G.</given-names>
          </string-name>
          <string-name>
            <surname>Sastry</surname>
            ,
            <given-names>A.</given-names>
          </string-name>
          <string-name>
            <surname>Askell</surname>
            ,
            <given-names>S.</given-names>
          </string-name>
          <string-name>
            <surname>Agarwal</surname>
            ,
            <given-names>A.</given-names>
          </string-name>
          <string-name>
            <surname>Herbert-Voss</surname>
            , G. Krueger,
            <given-names>T.</given-names>
          </string-name>
          <string-name>
            <surname>Henighan</surname>
            ,
            <given-names>R.</given-names>
          </string-name>
          <string-name>
            <surname>Child</surname>
            ,
            <given-names>A.</given-names>
          </string-name>
          <string-name>
            <surname>Ramesh</surname>
            ,
            <given-names>D. M.</given-names>
          </string-name>
          <string-name>
            <surname>Ziegler</surname>
            ,
            <given-names>J.</given-names>
          </string-name>
          <string-name>
            <surname>Wu</surname>
            ,
            <given-names>C.</given-names>
          </string-name>
          <string-name>
            <surname>Winter</surname>
            ,
            <given-names>C.</given-names>
          </string-name>
          <string-name>
            <surname>Hesse</surname>
            ,
            <given-names>M.</given-names>
          </string-name>
          <string-name>
            <surname>Chen</surname>
            , E. Sigler,
            <given-names>M.</given-names>
          </string-name>
          <string-name>
            <surname>Litwin</surname>
            ,
            <given-names>S.</given-names>
          </string-name>
          <string-name>
            <surname>Gray</surname>
            ,
            <given-names>B.</given-names>
          </string-name>
          <string-name>
            <surname>Chess</surname>
            ,
            <given-names>J.</given-names>
          </string-name>
          <string-name>
            <surname>Clark</surname>
            ,
            <given-names>C.</given-names>
          </string-name>
          <string-name>
            <surname>Berner</surname>
            ,
            <given-names>S.</given-names>
          </string-name>
          <string-name>
            <surname>McCandlish</surname>
            ,
            <given-names>A.</given-names>
          </string-name>
          <string-name>
            <surname>Radford</surname>
            ,
            <given-names>I.</given-names>
          </string-name>
          <string-name>
            <surname>Sutskever</surname>
            ,
            <given-names>D.</given-names>
          </string-name>
          <string-name>
            <surname>Amodei</surname>
          </string-name>
          ,
          <article-title>Language models are few-shot learners</article-title>
          , in: H.
          <string-name>
            <surname>Larochelle</surname>
            ,
            <given-names>M.</given-names>
          </string-name>
          <string-name>
            <surname>Ranzato</surname>
            ,
            <given-names>R.</given-names>
          </string-name>
          <string-name>
            <surname>Hadsell</surname>
            ,
            <given-names>M.</given-names>
          </string-name>
          <string-name>
            <surname>Balcan</surname>
          </string-name>
          , H. Lin (Eds.),
          <source>Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems</source>
          <year>2020</year>
          ,
          <article-title>NeurIPS 2020</article-title>
          , December 6-
          <issue>12</issue>
          ,
          <year>2020</year>
          , virtual,
          <year>2020</year>
          . URL: https://proceedings.neurips.cc/paper/2020/hash/ 1457c0d6bfcb4967418bfb8ac142f64a-Abstract.html.
        </mixed-citation>
      </ref>
      <ref id="ref14">
        <mixed-citation>
          [14]
          <string-name>
            <given-names>R.</given-names>
            <surname>Bruni</surname>
          </string-name>
          ,
          <article-title>On exact selection of minimally unsatisfiable subformulae</article-title>
          , Ann. Math. Artif. Intell.
          <volume>43</volume>
          (
          <year>2005</year>
          )
          <fpage>35</fpage>
          -
          <lpage>50</lpage>
          . URL: https://doi.org/10.1007/s10472-005-0418-4. doi:
          <volume>10</volume>
          .1007/ s10472-005-0418-4.
        </mixed-citation>
      </ref>
      <ref id="ref15">
        <mixed-citation>
          [15]
          <string-name>
            <given-names>J.</given-names>
            <surname>Huang</surname>
          </string-name>
          ,
          <article-title>MUP: a minimal unsatisfiability prover</article-title>
          , in: T. Tang (Ed.),
          <source>Proceedings of the 2005 Conference on Asia South Pacific Design Automation, ASP-DAC</source>
          <year>2005</year>
          , Shanghai, China, January
          <volume>18</volume>
          -
          <issue>21</issue>
          ,
          <year>2005</year>
          , ACM Press,
          <year>2005</year>
          , pp.
          <fpage>432</fpage>
          -
          <lpage>437</lpage>
          . URL: https://doi.org/10.1145/ 1120725.1120907. doi:
          <volume>10</volume>
          .1145/1120725.1120907.
        </mixed-citation>
      </ref>
      <ref id="ref16">
        <mixed-citation>
          [16]
          <string-name>
            <given-names>F.</given-names>
            <surname>Hemery</surname>
          </string-name>
          ,
          <string-name>
            <given-names>C.</given-names>
            <surname>Lecoutre</surname>
          </string-name>
          ,
          <string-name>
            <given-names>L.</given-names>
            <surname>Sais</surname>
          </string-name>
          ,
          <string-name>
            <given-names>F.</given-names>
            <surname>Boussemart</surname>
          </string-name>
          ,
          <article-title>Extracting mucs from constraint networks</article-title>
          , in: G. Brewka,
          <string-name>
            <given-names>S.</given-names>
            <surname>Coradeschi</surname>
          </string-name>
          ,
          <string-name>
            <given-names>A.</given-names>
            <surname>Perini</surname>
          </string-name>
          , P. Traverso (Eds.),
          <source>ECAI 2006, 17th European Conference on Artificial Intelligence, August 29 - September 1</source>
          ,
          <year>2006</year>
          ,
          <article-title>Riva del Garda, Italy, Including Prestigious Applications of Intelligent Systems (PAIS</article-title>
          <year>2006</year>
          ), Proceedings, volume
          <volume>141</volume>
          <source>of Frontiers in Artificial Intelligence and Applications</source>
          , IOS Press,
          <year>2006</year>
          , pp.
          <fpage>113</fpage>
          -
          <lpage>117</lpage>
          . URL: http://www.booksonline.iospress.nl/Content/View.aspx?piid=
          <fpage>1657</fpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref17">
        <mixed-citation>
          [17]
          <string-name>
            <surname>É. Grégoire</surname>
            ,
            <given-names>B.</given-names>
          </string-name>
          <string-name>
            <surname>Mazure</surname>
            ,
            <given-names>C.</given-names>
          </string-name>
          <string-name>
            <surname>Piette</surname>
          </string-name>
          ,
          <article-title>Extracting muses</article-title>
          , in: G. Brewka,
          <string-name>
            <given-names>S.</given-names>
            <surname>Coradeschi</surname>
          </string-name>
          ,
          <string-name>
            <given-names>A.</given-names>
            <surname>Perini</surname>
          </string-name>
          , P. Traverso (Eds.),
          <source>ECAI 2006, 17th European Conference on Artificial Intelligence, August 29 - September 1</source>
          ,
          <year>2006</year>
          ,
          <article-title>Riva del Garda, Italy, Including Prestigious Applications of Intelligent Systems (PAIS</article-title>
          <year>2006</year>
          ), Proceedings, volume
          <volume>141</volume>
          <source>of Frontiers in Artificial Intelligence and Applications</source>
          , IOS Press,
          <year>2006</year>
          , pp.
          <fpage>387</fpage>
          -
          <lpage>391</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref18">
        <mixed-citation>
          [18]
          <string-name>
            <surname>H. van Maaren</surname>
            ,
            <given-names>S.</given-names>
          </string-name>
          <string-name>
            <surname>Wieringa</surname>
          </string-name>
          ,
          <article-title>Finding guaranteed muses fast</article-title>
          , in: H.
          <string-name>
            <surname>K. Büning</surname>
            ,
            <given-names>X.</given-names>
          </string-name>
          Zhao (Eds.),
          <source>Theory and Applications of Satisfiability Testing - SAT</source>
          <year>2008</year>
          , 11th International Conference, SAT 2008, Guangzhou, China, May
          <volume>12</volume>
          -15,
          <year>2008</year>
          . Proceedings, volume
          <volume>4996</volume>
          of Lecture Notes in Computer Science, Springer,
          <year>2008</year>
          , pp.
          <fpage>291</fpage>
          -
          <lpage>304</lpage>
          . URL: https://doi.org/10. 1007/978-3-
          <fpage>540</fpage>
          -79719-7_
          <fpage>27</fpage>
          . doi:
          <volume>10</volume>
          .1007/978-3-
          <fpage>540</fpage>
          -79719-7\_
          <fpage>27</fpage>
          .
        </mixed-citation>
      </ref>
    </ref-list>
  </back>
</article>