=Paper=
{{Paper
|id=Vol-2945/21-RT-ConfWS21_paper_4
|storemode=property
|title=Solving Configuration Problems with ASP and Declarative Domain Specific Heuristics
|pdfUrl=https://ceur-ws.org/Vol-2945/21-RT-ConfWS21_paper_4.pdf
|volume=Vol-2945
|authors=Richard Taupe,Gerhard Friedrich,Konstantin Schekotihin,Antonius Weinzierl
|dblpUrl=https://dblp.org/rec/conf/confws/TaupeFSW21
}}
==Solving Configuration Problems with ASP and Declarative Domain Specific Heuristics==
https://ceur-ws.org/Vol-2945/21-RT-ConfWS21_paper_4.pdf
Solving Configuration Problems with ASP and
Declarative Domain-Specific Heuristics1
Richard Taupe2 and Gerhard Friedrich3 and Konstantin Schekotihin3 and Antonius Weinzierl4
Abstract. Domain-specific heuristics are an essential technique solving have already been proposed: a procedural approach for the
for solving configuration problems efficiently. Current approaches to WASP system [7] and a declarative approach for CLINGO [17].
integrate domain-specific heuristics with Answer Set Programming Both existing approaches to integrate domain-specific heuristics
(ASP) are unsatisfactory when dealing with heuristics that are spec- with ASP solving are unsatisfactory: Procedural heuristics counter-
ified non-monotonically on the basis of partial assignments. Such act the declarative nature of ASP, and the existing declarative ap-
heuristics frequently occur in practice, for example, when picking proach does not permit dynamic heuristics reasoning about partial as-
a component that has not yet been placed in a configuration prob- signments. Dynamically evaluating heuristics w.r.t. a partial assign-
lem. Therefore, we present novel syntax and semantics for declar- ment can be an essential feature for practical domains. For example,
ative specifications of domain-specific heuristics in ASP. Our ap- heuristics in product configuration may need to compute the amount
proach supports heuristic statements that depend on the partial as- of space left after placing a component.
signment maintained during solving, which has not been possible We tackle the challenge of finding a satisfying solution to integrate
before. We provide an implementation in A LPHA that makes A LPHA declarative domain-specific heuristics with ASP programs. To this
the first lazy-grounding ASP system to support declaratively speci- end, we extend CLINGO’s approach. Our extension supports dynamic
fied domain-specific heuristics. Two well-known configuration prob- heuristics while at the same time keeping the language simple and
lems are used to demonstrate the benefits of our proposal. The exper- easy to use.
iments confirm that combining lazy-grounding ASP solving and our We implemented our approach as an extension to the lazy-
novel heuristics can be vital for solving industrial-size configuration grounding ASP system A LPHA. Two well-known configuration
problems. problems – the House Reconfiguration Problem (HRP) and the Part-
ner Units Problem (PUP) – are used to demonstrate our approach and
to obtain experimental results. The experiments confirm that combin-
1 INTRODUCTION ing lazy-grounding ASP solving and our novel heuristics can be vital
for solving industrial-size configuration problems.
Answer Set Programming (ASP) [2, 14, 20, 25] is a declarative pro- After briefly covering preliminaries in Section 2, we introduce the
gramming approach that has successfully been applied to product state of the art of domain-specific heuristics in ASP in Section 3.
configuration [11, 12, 19, 21, 27]. Our novel approach is presented in Section 4. Section 5 describes
However, large-scale industrial problems are challenging for ASP. applications and experimental results, and Section 6 concludes this
One issue is the so-called grounding bottleneck: Large problem in- paper.
stances often cannot be grounded by modern grounders like GRINGO
[16] or I-DLV [4] in adequate time and space [8]. Another issue is
that, even if the problem can be grounded, computation of answer 2 PRELIMINARIES
sets may take considerable time, as indicated by the ASP Competi-
tions [5, 18]. The declarative programming approach of ASP allows a programmer
Lazy grounding is a technique that tackles the grounding bottle- to formulate the problem as a logic program specifying the search
neck. The approach presented in this paper is implemented in the space and the properties of solutions instead of stating how to solve
lazy-grounding system A LPHA [35]. Thus we can handle large-scale a problem. An ASP solver then finds models (so-called answer sets)
problem instances. for this logic program, which correspond to solutions for the original
The main topic of this work concerns domain-specific heuristics, problem.
an essential technique for improving solving performance by equip- Most state-of-the-art ASP systems implement “ground and solve”,
ping the solver with hints on how to solve a problem efficiently. i.e., they first produce the full grounding (i.e., variable-free equiva-
Several approaches to integrate domain-specific heuristics with ASP lent) of the input program, which is then solved. This results in the
so-called grounding bottleneck: As soon as the grounding exceeds
1 This paper contains extracts from a journal paper [28] that extends an earlier all available memory, the problem cannot be solved anymore. Lazy
conference paper [29] and is currently under review. grounding avoids the grounding bottleneck by interleaving ground-
2 Siemens AG Österreich and Alpen-Adria-Universität Klagenfurt, Austria,
ing and solving. This approach is implemented by ASP systems such
email: richard.taupe@siemens.com (Richard Taupe is the main author of
as A LPHA [24, 35].
this paper; other authors contributed equally and are listed in the alphabet-
ical order.) Due to space constraints, we assume familiarity with syntax and
3 Alpen-Adria-Universität Klagenfurt, Austria semantics of ASP, and refer to [3, 13, 27] for details.
4 TU Wien, Vienna, Austria
In the remainder of this section, we introduce the notation that will
Copyright 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0)
be used later in the article. 4 DYNAMIC DECLARATIVE HEURISTICS
An assignment A is a set of signed literals Ta, Fa, or Ma, where
Ta and Fa express that an atom a is true and false, respectively, and Declaratively specifying domain-specific heuristics in ASP plays a
Ma indicates that a “must-be-true”. M signifies that an atom must vital role in enabling ASP to solve large-scale industrial problems.
eventually become true by derivation in a correct solution extending CLINGO has been the only ASP system to support such heuristics
the current partial assignment, but no derivation has yet been found so far. Although language and semantics of heuristic directives in
that would make the atom true. Let As = {a | s a ∈ A} for s ∈ CLINGO have shown to be beneficial in many cases, dynamic aspects
{F, M, T} denote the set of atoms occurring with a specific sign of negation as failure in heuristic conditions have not been addressed
in assignment A. We assume assignments to be consistent, i.e., no satisfactorily.
negative literal may also occur positively (AF ∩ (AM ∪ AT ) = ∅), We present novel syntax and semantics for heuristic directives
and every positive literal must also occur with must-be-true (AT ⊆ in ASP that improve this situation. We assume that the underlying
AM ). solver can assign one of three values to any atom: true (denoted with
An assignment A is complete if every atom is assigned true or T), false (F), and must-be-true (M) (cf. [35]). The following defini-
false. An assignment that is not complete is partial. tions can be used without modification for solvers that do not use the
The function truthA for a (partial) assignment A maps an atom third truth value M. The set of atoms assigned must-be-true will be
to the truth value that the atom is currently assigned in the given empty in this case.
assignment, or to U if the atom is currently unassigned:
Definition 1 (Heuristic Directive) A heuristic directive is of the
form h1i, where hai (0 ≤ i ≤ n) are heuristic atoms of the form
F a ∈ AF ,
si ai , in which s0 ∈ {{F}, {T}} and si ⊆ {F, M, T} are sets of
M a ∈ AM \ AT , sign symbols and ai is an atom, and w and l are integer terms.
truthA (a) =
T a ∈ AT ,
#heuristic ha 0 : ha 1 , . . . , ha k ,
U otherwise. h1i
not ha k+1 , . . . , not ha n . [w@l]
The heuristics’ head is given by ha 0 and its condition by
3 DOMAIN-SPECIFIC HEURISTICS IN ASP {ha 1 , . . . , ha k , not ha k+1 , . . . , not ha n }, which is similar to a rule
body.
State-of-the-art ASP solvers are well suited to solve a wide range
of problems, as shown in ASP competitions, experiments, and (in- Where the meaning is clear from the context, we may omit all sym-
dustrial) applications reported in the literature [9, 11, 18, 23]. How- bols except sign symbols themselves in a set of sign symbols, e.g.,
ever, domain-specific heuristics are needed to achieve breakthroughs we write TM instead of {T, M}.
in solving industrial configuration problems with ASP. Several ap-
proaches have implemented embedding heuristic knowledge into the Example 1 Consider the following heuristic directive h:
ASP solving process.
HWASP [7] facilitates external procedural heuristics that are con- #heuristic Fa : TMb, Tc, not TMFd.
sulted at specific points during the solving process via an API. As
a result, HWASP can find solutions for all published instances of the This directive means that the atom a shall be assigned F if b is as-
Partner Units Problem (PUP) by exploiting external heuristics for- signed T or M, c is assigned T, and d is not assigned.
mulated in C++ or Python.
The CLINGO system supports a declarative approach to formulat- We now introduce some notation that will be used in further defini-
ing domain-specific heuristics in ASP in the form of #heuristic tions. The function atm maps a heuristic atom ha i to ai by removing
directives [13, 17]. Heuristics extend the ASP language to allow for the sign, and a set of heuristic atoms to the set of atoms occurring in
declarative specification of atom weights and signs for the solver’s them (e.g., atm(Ma) = a, atm({Ma, Tb}) = {a, b}). The func-
internal heuristics. An atom’s weight influences the order in which tion signs maps a heuristic atom ha i to si by removing the atom
atoms are considered by the solver when making a decision. A sign (e.g., signs(Ma) = {M}).
modifier instructs whether the selected atom must be assigned true or The head of a heuristic directive h of the form h1i is denoted by
false. Atoms with a higher weight are assigned a value before atoms head(h) = ha 0 , its weight by weight(h) = w if given, else 0, and
with a lower weight. its level by level(h) = l if given, else 0. The (heuristic) condition
CLINGO ’s semantics for heuristic directives seem to introduce of a heuristic directive h is denoted by cond(h) := {ha 1 , . . . , ha k ,
some limitations for formulating heuristics that require to reason not ha k+1 , . . . , not ha n }, the positive condition is cond+ (h) :=
about the absence of truth-values for atoms, e.g. the absence of de- {ha 1 , . . . , ha k } and the negative condition is cond− (h) := {ha k+1 ,
cisions in a search state. For example, in configuring technical sys- . . . , ha n }.
tems, we might prefer to assign, in the current search state, the most Let HA be a set of heuristic atoms. Then, for s ⊆ {F, M, T},
relevant yet unplaced electronic component to a free slot of a moth- HA|s = {a | s a ∈ HA} denotes the set of atoms in HA whose set
erboard. These limitations are discussed in detail in our other publi- of sign symbols equals s.
cations [28, 29].
To overcome this issue we propose, in the following section, to Example 2 Consider the heuristic directive h from Example 1
evaluate negation as failure (i.e., not) in heuristic statements w.r.t. again. Here, cond+ (h)|MT = {b}; cond+ (h)|T = {c}; and
the current partial assignment in the solver. This partial assignment cond+ (h)|F = ∅. Furthermore, cond− (h)|FMT = {d}; note that
represents the search state. As a consequence, not X is true if X is the order of sign symbols does not matter due to set semantics.
false or unassigned in a partial assignment.
2
The distinguishing features of our approach are as follows: heuristic for a configuration problem that only applies to components
not yet placed.
• Each heuristic atom contains a set of sign symbols. Each sign sym- What remains to be defined is the semantics of weight and level.
bol represents one of the truth values F (false), T (true), and M Given a set of applicable heuristic directives, one directive with the
(must-be-true). highest weight will be chosen from the highest level. Suppose there
• In the condition, sign symbols provide a richer way of controlling are several with the same maximum priority (i.e., weight and level).
when the condition is satisfied. A positive literal in the condition In that case, the solver can use domain-independent heuristics like
is satisfied if the truth value currently assigned to its atom is con- VSIDS [26] as a fallback to break the tie.
tained in its set of sign symbols (which is {M, T} by default if
not explicitly given). A negative literal in the condition is satisfied Definition 5 (Heuristics Eligible for Immediate Choice) Given a
if the truth value currently assigned to its atom is not contained in set H of applicable ground heuristic directives, the subset eligible
its set of sign symbols or if its atom is currently not assigned any for immediate choice is defined as maxpriority(H) in two steps:
truth value.
maxlevel(H) := {h |h ∈ H and level(h) = max level(h)}
• In the heuristic head, the sign symbol is used to determine the h∈H
truth value to be chosen by the heuristics. If s0 is T or empty, the maxpriority(H) := {h |h ∈ maxlevel(H) and
heuristics makes the solver guess a0 to be true; if s0 is F, a0 will
weight(h) = max weight(h)}
be made false.5 h∈maxlevel(H)
• Terms w and l denote weight and level as familiar from optimize-
After choosing a heuristic using maxpriority, a solver makes a de-
statements in ASP-Core-2 [3] or weak constraints in DLV [22].
cision on the directive’s head atom. Note that heuristics only choose
The level is more important than the weight; both default to 0, and
between atoms derivable by currently applicable rules. Other solving
together they are called priority.
procedures, e.g., deterministic propagation, are unaffected by pro-
We now describe our semantics more formally, beginning with the cessing heuristics.
condition under which a heuristic atom is satisfied.
Example 3 Consider the following program.
Definition 2 (Satisfying a Heuristic Atom) Given a ground heu-
{ a(2) ; a(4) ; a(6) ; a(8) ; a(5) } ← .
ristic atom ha and a partial assignment A, ha is satisfied w.r.t. A iff:
truthA (atm(ha)) ∈ signs(ha), i.e., if its atom is assigned a truth ← #sum { X : a(X) } = S, S\2 6= 0.
value that is included in the heuristic atom’s sign set.6 #heuristic a(5). [1] h2i
Whether a heuristic directive is satisfied depends on whether the #heuristic a(4) : not a(5). [2] h3i
atoms occurring in the directive are satisfied. #heuristic Fa(5) : a(4). [2] h4i
#heuristic a(6) : Fa(5), Ta(4). [2] h5i
Definition 3 (Satisfying a Heuristic Directive) Given a ground
heuristic directive h and a partial assignment A, cond(h) is Intuitively, directive h2i unconditionally prefers to make a(5) true
satisfied w.r.t. A iff: every ha ∈ cond+ (h) is satisfied and no with weight 1. All other directives have a higher weight, 2, but they
ha ∈ cond− (ha) is satisfied. become applicable at different times. Directive h3i prefers to make
a(4) true if a(5) is neither true nor must-be-true, directive h4i prefers
Intuitively, a heuristic condition is satisfied iff its positive part is fully
to make a(5) false if a(4) is true or must-be-true, and h5i prefers to
satisfied and none of its default-negated literals is contradicted.
make a(6) true if a(5) is false and a(4) is true.
Definition 4 (Applicability of a Heuristic Directive) A ground Let A0 = ∅ be the empty partial assignment before any deci-
heuristic directive h is applicable w.r.t. a partial assignment A iff: sion has been made. W.r.t. A0 , h2i is applicable because its con-
cond(h) is satisfied, and truthA (atm(head(h))) ∈ {U, M}. dition is empty and its head is still unassigned. Directive h3i is also
applicable because a(5) is still unassigned. Directives h4i and h5i
Intuitively, a heuristic directive is applicable iff its condition is sat- are not applicable w.r.t. A0 . Directive h3i is chosen because it has
isfied and the atom in its head is assigned neither T nor F. If the the highest priority among applicable directives. Thus, a(4) is as-
atom in the head is assigned M, the heuristic directive may still be signed T, updating our assignment to A1 = {Ma(4), Ta(4)}. This
applicable, because any atom with the non-final truth value M must makes h4i applicable, a(5) is assigned F and our assignment is
be either T or F in any answer set. A2 = {Ma(4), Ta(4), Fa(5)}. Note that the condition of h3i was
Definitions 2 to 4 reveal the distinguishing features of the newly still satisfied at this point, but it was not applicable because its head
proposed semantics: In our approach, heuristic signs composed of was already assigned. Now, h2i is also not applicable anymore, and
truth values T, M, and F can be used in heuristic conditions to rea- the only directive that remains is h5i. Since h5i is applicable, a(6)
son about atoms that are already assigned specific truth values in a is made true and added to the assignment. Next, the atoms that re-
partial assignment. Furthermore, default negation can be used to rea- mained unassigned are guessed by the default heuristics until an an-
son about atoms that are assigned or still unassigned. Our semantics swer set is found.
truly means default negation in the current partial assignment, while
the one implemented by CLINGO amounts to strong negation in the
current search state. This difference is crucial since reasoning about
5 APPLICATIONS AND EXPERIMENTS
incomplete information is essential in many cases. An example is a In this section, we present an application of our approach on two
5 In the head, we only support truth values T and F because, from a user’s
configuration problems. Experimental results are also included, us-
point of view, it does not make sense to assign M to an atom heuristically. ing an implementation of our approach in the lazy-grounding ASP
6 Note that the function truth maps to only one truth value even though Ta ∈ system A LPHA. Instance sets include instances that were challeng-
A implies Ma ∈ A, so truthA (a) = M iff Ma ∈ A and Ta ∈
/ A. ing to ground and solve.
3
5.1 Experimental Setup The task is then to find an assignment of things to cabinets TC ⊆
T × C and cabinets to rooms CR ⊆ C × R, that satisfies all re-
Encodings (including heuristics) and instances, and the A LPHA bina- quirements of HCP as well as the following ones: (1) a cabinet is
ries used for our experiments, are available on our website.7 Details either small or high; (2) a long thing can only be put into a high cab-
on the sources of the encodings are mentioned in the sections de- inet; (3) a small cabinet occupies 1 and a high cabinet 2 of 4 slots
scribing the domains. Optimisation statements were not used since available in a room; (4) all legacy cabinets are small.
A LPHA does not support them yet. However, heuristic directives can
be written in a way that optimal or near-optimal solutions are prefer- The sample HRP instance shown in Fig. 1 comprises two cabinets,
ably found. two rooms, five things that belong to person p1 , and one thing that
Problem instances were selected by first defining an instance- belongs to person p2 . A legacy configuration is empty, and all things
generating algorithm and then exploring instance sizes to find a set are small. In a solution, the first person’s things are placed in cabinet
in which all systems could solve some instances under consideration c1 in the first room, and the thing of the second person is the cabinet
within a time limit of 10 minutes, and some instances could be solved c2 in the second room. For this sample instance, a solution of HRP
by none (or very few) of these systems. corresponds to a solution of HCP.
The ASP systems used for the experiments were A LPHA8 , In the problem encoding [12], two main choice rules are responsi-
9 10
CLINGO [15] version 5.4.0 and DLV 2 [1] version 2.1.0.
ble for guessing the assignment of things to cabinets and the assign-
A LPHA is used in two configurations, grounding constraints either ment of cabinets to rooms:
strictly or permissively [30]. Traditionally in lazy grounding, rules { cabinetTOthing(C, T ) } ← cabinetDomain(C), thing(T ).
are grounded when their positive body is fully satisfied (strict lazy
{ roomTOcabinet(R, C) } ← roomDomain(R), cabinet(C)
grounding). Permissive grounding, on the other hand, enables rules
to be grounded if their positive body is not fully satisfied, as long as Instances consist of facts over the following predicates:
all variables can be bound by positive body literals that are already cabinetDomain/1 defines potential cabinets and roomDomain/1
satisfied. For example, consider the following non-ground constraint: defines potential rooms; thingLong/1 defines which things are long;
← a(X, Y ), b(X). and legacy/1 defines all the other data in the legacy configuration,
Under the partial assignment A = {Ma(1, 2), Ta(1, 2)}, the e.g., legacy(personTOthing(p1, t1)) defines that person p1 owns
ground constraint ← a(1, 2), b(1). will only be produced if permis- thing t1, and legacy(roomTOcabinet(r1, c1)) specifies one tuple
sive grounding of constraints is enabled. in the legacy assignment of cabinets to rooms.
All solvers were configured to search for the first answer set of The domain-specific heuristics for HRP implemented in our novel
each problem instance. Finding one or only a few solutions is often approach works by (1) first trying to re-use the legacy configuration;
sufficient in industrial use cases since solving large instances can be (2) then filling cabinets with things; (3) then filling rooms with
challenging [10]. Therefore, the domain-specific heuristics used in cabinets; (4) and finally closing remaining choices. Long things are
the experiments are designed to help the solver find one answer set always assigned before short things.
that is “good enough”, even though it may not be optimal. By “closing remaining choices” we mean assigning F to choice
points not yet assigned by the heuristics. The purpose of this is to
avoid the default heuristics (e.g., VSIDS) from causing conflicts by
5.2 The House Reconfiguration Problem (HRP) choosing the wrong truth values.
We now present some selected heuristic directives. The directives
The House Reconfiguration Problem [12] is an abstracted version of use some intermediate predicates whose meaning should become ev-
industrial (re)configuration problems, e.g., rack configuration. ident from their names. The full encoding is available online. The fol-
Formally, HRP is defined as a modification of the House Configu- lowing heuristics re-use the legacy assignment of cabinets to things
ration Problem (HCP). and of rooms to cabinets (1):
#heuristic reuse(cabinetTOthing(C, T )) :
Definition 6 (HCP) The input for the House Configuration Problem legacy(cabinetTOthing(C, T )), thingLong(T ). [4@4]
(HCP) is given by four sets of constants P , T , C, and R representing
persons, things, cabinets, and rooms, respectively, and an ownership #heuristic reuse(cabinetTOthing(C, T )) :
relation PT ⊆ P × T between persons and things. legacy(cabinetTOthing(C, T )), not thingLong(T ). [3@4]
The task is to find an assignment of things to cabinets TC ⊆ #heuristic reuse(roomTOcabinet(R, C)) :
T × C and cabinets to rooms CR ⊆ C × R, such that: (1) each legacy(roomTOcabinet(R, C)). [2@4]
thing is stored in a cabinet; (2) a cabinet contains at most five things;
(3) every cabinet is placed in a room; (4) a room contains at most The following heuristic assigns things to cabinets, preferring long
four cabinets; and (5) a room may only contain cabinets storing over short things (2):
things of one person. #heuristic cabinetTOthing(C, T ) :
cabinetDomain(C), not fullCabinet(C),
Definition 7 (HRP) The input for the House Reconfiguration Prob- not T assignedThing(T ), personTOthing(P, T ),
lem (HRP) is given by an HCP instance H = hP, T, C, R, P T i, a not otherPersonTOcabinet(P, C),
legacy configuration hTC 0 , CR 0 i, and a set of things T 0 ⊆ T that maxCabinet(MC ), thingLong(T ). [(MC − C)@3]
are defined as “long” (all other things are “short”). #heuristic cabinetTOthing(C, T ) :
cabinetDomain(C), not fullCabinet(C),
7 https://ainf.aau.at/dynacon
8 https://github.com/alpha-asp/Alpha not T assignedThing(T ), personTOthing(P, T )
9 https://potassco.org/clingo/ not otherPersonTOcabinet(P, C),
10 https://dlv.demacs.unical.it/ maxCabinet(MC ), not thingLong(T ). [(MC − C)@2]
4
p1 p2 t5
c1
t4
c2
r1 c1 t3 r2 c2 t6
r1 t2
t1 t2 t3 t4 t5 t6 r2 t1
Figure 1. Sample HRP instance (left) and one of its solutions (right)
alpha (kco = 0) (0) h-alpha (kco = 0) (59) clingo (35) dlv2 (23)
alpha (kco = ∞) (1) h-alpha (kco = ∞) (19) h-clingo (40)
(a) Solver configurations, with numbers of solved instances
180 32
160
28
140
Real time (minutes)
24
Memory (GiB)
120
20
100
80 16
60 12
40 8
20 4
0 0
0 8 16 24 32 40 48 56 0 8 16 24 32 40 48 56
Number of instances Number of instances
(b) Accumulated time consumption (c) Memory consumption
Figure 2. Time and memory consumption for solving each HRP instance
The following heuristic assigns cabinets to rooms (3): ing of constraints; DLV 2; CLINGO with (H - CLINGO) and without
#heuristic roomTOcabinet(R, C) : domain-specific heuristics.
roomDomain(R), not fullRoom(R), Substantial differences can be observed. The curves for H - ALPHA
cabinet(C), not T assignedCabinet(C), (kco = 0) reach farthest to the right, meaning that A LPHA with
personTOcabinet(P, C), not otherPersonTOroom(P, R), domain-specific heuristics solved the highest number of instances
maxRoom(MR). [(MR − R)@1] (59 out of 94) when grounding constraints strictly. Surprisingly, with
permissive grounding of constraints, A LPHA with domain-specific
Finally, we close choice points that are still unassigned (4): heuristics exhibited relatively low time and space performance.
#heuristic F cabinetTOthing(C, T ) : No curves are visible at all for A LPHA without domain-specific
not cabinetTOthing(C, T ), cabinetDomain(C), thing(T ). heuristics because, in this configuration, the system could solve at
most one instance only. The other solvers’ performance was some-
#heuristic F roomTOcabinet(R, C) :
where in between the A LPHA configurations at both ends of the spec-
not roomTOcabinet(R, C), roomDomain(R), cabinet(C).
trum. Notably, H - CLINGO with domain-specific heuristics solved
more instances in less time compared to CLINGO without domain-
The heuristics we created for A LPHA cannot be used with CLINGO specific heuristics, but consumed slightly more memory. The largest
due to the usage of T and default negation. An alternative encoding instance solved by H - ALPHA contained 600 things, which is over
containing faithfully adapted heuristic directives for CLINGO has also 30% more than the size of the largest instance solved by H - CLINGO
been created. (455). Recall that the time limit for solving each instance was 10
Figure 2 shows performance data for experiments with HRP. Cac- minutes.
tus plots were created in the usual way. In Fig. 2b, the x-axis gives the
number of instances solved within real (i.e., wall-clock) time, given
on the y-axis. Time is accumulated over all solved instances. Memory 5.3 The Partner Units Problem (PUP)
consumption is given on the y-axis of Fig. 2c, where data points are
sorted by y-values, which are not accumulated. Figure 2a contains a Like HRP, the Partner Units Problem (PUP) [31, 34] is an abstracted
legend with all solver configurations. The number of instances solved version of industrial (re)configuration problems.
by each system is shown next to its name (in parentheses).
One curve was drawn for each solver configuration: A LPHA with- Definition 8 (PUP) The input to the Partner Units Problem (PUP) is
out domain-specific heuristics, with strict (kco = 0) and permis- given by a set of units U and a bipartite graph G = (S, Z, E), where
sive (kco = ∞) grounding of constraints; A LPHA with domain- S is a set of sensors, Z is a set of zones, and E is a relation between
specific heuristics (H - ALPHA), with strict and permissive ground- S and Z.
5
s1 s2 s3 s4 s5 s6 u1 s1 s2 s3 s4 s5 s6
u2
u3 u1 u2 u3
UCAP = 2
z1 z123 z24 z35 z456 z6 z1 z123 z24 z35 z456 z6
IUCAP = 2
Figure 3. Sample PUP instance (left) and one of its solutions (right)
alpha (kco = 0) (7) h-alpha (kco = 0) (100) clingo (13) dlv2 (10)
alpha (kco = ∞) (7) h-alpha (kco = ∞) (100) h-clingo (34)
(a) Solver configurations, with numbers of solved instances
140 27
24
120
21
Real time (minutes)
100
Memory (GiB)
18
80 15
60 12
9
40
6
20 3
0 0
0 15 30 45 60 75 90 0 15 30 45 60 75 90
Number of instances Number of instances
(b) Accumulated time consumption (c) Memory consumption
Figure 4. Time and memory consumption for solving each PUP instance
The task is to find a partition of vertices v ∈ S ∪ Z into bags ui ∈ First, a start zone is determined and denoted by startZone/1. In
U such that for each bag the following requirements hold: (1) the bag our encoding, the start zone is always the first one and instances are
contains at most UCAP vertices from S and at most UCAP vertices designed so that solutions can easily be found when starting with this
from Z; and (2) the bag has at most IUCAP adjacent bags, where zone. QuickPup should actually try to use each zone as the start zone
the bags u1 and u2 are adjacent whenever vi ∈ u1 and vj ∈ u2 for one after the other and abort search after a certain amount of time has
some (vi , vj ) ∈ E. passed. This part of the algorithm cannot currently be represented in
our framework.
Figure 3 shows an example of a PUP instance. The bipartite graph
QuickPup assigns zones and sensors to units in a breadth-first-
comprises six sensors and six zones. Each of the three units can be
order, called “topological order” because the graph is traversed level
adjacent to at most two other units, and each unit can contain at most
by level. First, the start zone is assigned, then the sensors connected
two sensors and two zones. An assignment of sensors and zones to
to the start zone, then the zones connected to those sensors and so on.
units that satisfies all PUP requirements is also presented in Fig. 3.
A helper predicate layer/3 is introduced to compute the topological
PUP instances consist of atoms over the predicates comUnit/1
order. In an atom layer(T, X, L), T denotes the type of element (“s”
(specifying units U ) and zone2sensor/2 (specifying the zone-to-
for sensor and “z” for zone), X is the element’s identifier, and L is
sensor relation E).11
its layer in the computed breadth-first order.
Our encoding for PUP is based on encodings from the ASP Com-
A realisation of QuickPup in our framework requires several heu-
petitions [5, 6]. The following rules constitute the main guessing part
ristic directives. These directives use the level term in the annotation
of the encoding:
to process the zones and sensors according to the topological order.
elem(z, Z) ← zone2sensor(Z, D). The weight term in the annotation is used to assign the units in the
elem(s, D) ← zone2sensor(Z, D). right order. The directives use some intermediate predicates whose
meaning should become evident from their names. The full encoding
{ assign(U, T, X) } ← elem(T, X), comUnit(U ). is available online.
QuickPup is a heuristic for PUP that successfully solves many QuickPup first tries to assign an element to the first unit:
hard problem instances [33]. Our approach supports implementing #heuristic assign(U, T, X) : comUnit(U ), elem(T, X),
large parts of the originally procedural algorithm for QuickPup. Our maxLayer(ML), layer(T, X, L),
encoding uses rules to derive a topological order of the zones and not full(U, T ), not assigned(T, X), not T used(U ),
sensors (cf. [31,32]). Heuristic directives subsequently use this topo- nUnits(NU ), U = 1. [NU @(ML − L)]
logical order.
11 In the instances used for our experiments, both UCAP and IUCAP are If one unit cannot be assigned, QuickPup tries preceding units in
fixed at the value 2. decreasing order next:
6
#heuristic assign(U, T, X) : comUnit(U ), elem(T, X), rectives that make it possible to reason about the current partial as-
maxLayer(ML), layer(T, X, L), signment, facilitating heuristics based on what has or has not yet been
not full(U, T ), not assigned(T, X), decided by the solver. Although the earlier approach has worked very
T used(U ). [U @(ML − L)] well on planning problems, it seems that more flexibility in the defi-
nition of heuristics, supported by the novel features of our approach,
A fresh unit is only touched if all preceding units have been tried: is necessary to represent heuristics for other kinds of problems.
#heuristic assign(U, T, X) : comUnit(U ), elem(T, X), Our results undeniably show that domain-specific heuristics im-
maxLayer(ML), layer(T, X, L), prove solving performance for the domains under consideration. This
not full(U, T ), not assigned(T, X), is not only true for A LPHA but also for CLINGO. However, domain-
not T used(U ), comUnit(U − 1), T used(U − 1), specific heuristics usually increase CLINGO’s memory consumption,
F assign(U − 1, T, X). [U @(ML − L)] thus exacerbating the grounding bottleneck from which ground-and-
solve systems such as CLINGO are suffering. Domain-specific heuris-
tics for DLV 2 were out of scope because DLV 2 does not support the
Note the condition F assign(U − 1, T, X) in the last heuristic di-
declarative specification of heuristics.
rective. Due to this condition, the heuristic is only applicable if the
Solution quality is another aspect to keep in mind. Since domain-
same element could not be assigned to the preceding unit U −1. This
specific heuristics lead the solver towards “better” solutions, the
situation may be caused by backtracking or by the following heuristic
quality of answer sets computed by H - ALPHA or H - CLINGO is higher
avoiding assignments to units that are already full:
than the quality of answer sets computed by A LPHA, CLINGO, or
#heuristic F assign(U, T, X) : comUnit(U ), elem(T, X),
DLV 2.
maxLayer(ML), full(U, T ),
However, we do not claim that heuristics based on partial assign-
not assign(U, T, X). [1@ML]
ments are always beneficial. Our findings cannot reject the possibility
that H - CLINGO might outperform H - ALPHA when other encodings
Choice points not assigned by any of these heuristics are finally or other heuristics are used since there might be encoding optimi-
assigned false by a dedicated heuristic directive, similarly as shown sations that we have not thought of. Still, we are confident that our
for HRP in Section 5.2. approach’s novel features make the specification of practical heuris-
The heuristics we created for A LPHA cannot be used with CLINGO tics more intuitive and effortless.
due to the usage of T, F, and default negation. An alternative encod- Results for HRP (Fig. 2) indicate that permissive grounding (cf.
ing containing heuristic directives for CLINGO has been created that [30]), i.e., providing the solver with more nogoods representing
is similar to the QuickPup*-like heuristics created for A LPHA. ground constraints than necessary, can be counterproductive when
Cactus plots for PUP (Fig. 4) were generated in the same way as domain-specific heuristics are used. We conjecture the reason for
for HRP (cf. Section 5.2). this to be that suitable domain-specific heuristics can assist the solver
Again, A LPHA with domain-specific heuristics solved the highest even better than additional constraints while avoiding the overhead of
number of instances (all 100). The curves for H - ALPHA (kco = 0) additional nogoods (in terms of space consumption and propagation
and H - ALPHA (kco = ∞) are almost indistinguishable, meaning that efforts). This assumption is supported by the considerable increase
it did not make a difference in the PUP domain whether constraints in A LPHA’s memory consumption when grounding constraints per-
were grounded strictly or permissively. missively in this domain.
At the other extreme, A LPHA without domain-specific heuristic To sum up, domain-specific heuristics implemented in our novel
could solve only 7 of the 100 instances. framework, combined with strict lazy grounding by A LPHA, outper-
The systems DLV 2, CLINGO, and H - CLINGO performed some- formed all other tested systems when applied to large instances of
where between those extremes. H - CLINGO with domain-specific the House Reconfiguration Problem and the Partner Units Problem.
heuristics solved many more instances than CLINGO without domain- Applications to other domains should be easy to put into practice and
specific heuristics. belong to future work.12
The largest instance in our instance set contained 300 units. H -
ALPHA was able to solve all these instances. In contrast, the size of
the largest instance that could be solved by any other system, us- 6 CONCLUSION
ing the given encoding, was only 105. Recall that the time limit for
solving each instance was 10 minutes. For 11 instances, H - CLINGO We have proposed novel syntax and semantics for declara-
returned an error (“Id out of range”). tive domain-specific heuristics in ASP that can depend non-
monotonically on the partial assignment maintained during solving.
Furthermore, we have presented experimental results obtained with
5.4 Discussion an implementation of our approach within the lazy-grounding solver
A LPHA.
Our results show that we have extended the application area of ASP. Our semantics has proven beneficial for several practical applica-
By combining our novel approach to domain-specific heuristics with tion domains, advancing CLINGO’s previous approach [17]. In exper-
lazy-grounding answer set solving, we could solve large-scale prob- iments, our implementation exhibited convincing time and memory
lem instances that are out of reach for conventional ASP systems. consumption behaviour. Thus, we extended the application area of
This finding supports our initial hypothesis that both lazy ground- ASP by solving large configuration problem instances that conven-
ing and domain-specific heuristics are crucial for solving large-scale tional ASP systems could not solve.
industrial problems. Our approach’s suitability to implement heuristics for other prac-
Our approach extends an earlier extension of ASP’s input language tical (configuration) problems should be assessed by the community.
by a declarative framework for domain-specific heuristics [17]. Our
12 One other domain, A* search, is investigated in our journal paper [28].
advancement consists of novel syntax and semantics for heuristic di-
7
Some real-world domain-specific heuristics will require extensions [14] Martin Gebser, Roland Kaminski, Benjamin Kaufmann, and Torsten
of our approach, such as by supporting randomness and restarts. Schaub, Answer Set Solving in Practice, Morgan and Claypool Pub-
lishers, 2012.
Thinking more broadly, the question of how to generate domain- [15] Martin Gebser, Roland Kaminski, Benjamin Kaufmann, and Torsten
specific heuristics automatically is of great importance since, cur- Schaub, ‘Clingo = ASP + control: Preliminary report’, CoRR,
rently, such heuristics have to be invented by humans familiar with abs/1405.3694, (2014).
the domain (and partly also with solving technology). [16] Martin Gebser, Roland Kaminski, Arne König, and Torsten Schaub,
‘Advances in gringo series 3’, in LPNMR, volume 6645 of LNCS, pp.
345–351. Springer, (2011).
ACKNOWLEDGEMENTS [17] Martin Gebser, Benjamin Kaufmann, Javier Romero, Ramón Otero,
Torsten Schaub, and Philipp Wanko, ‘Domain-specific heuristics in an-
This work has been conducted in the scope of the research project swer set programming’, in AAAI. AAAI Press, (2013).
DynaCon (FFG-PNr.: 861263), which was funded by the Austrian [18] Martin Gebser, Marco Maratea, and Francesco Ricca, ‘The seventh an-
swer set programming competition: Design and results’, TPLP, 20(2),
Federal Ministry of Transport, Innovation and Technology (BMVIT) 176–204, (2020).
under the program “ICT of the Future” between 2017 and 2020.13 [19] Martin Gebser, Anna Ryabokon, and Gottfried Schenner, ‘Combining
This research was also supported by the Academy of Finland, project heuristics for configuration problems using answer set programming’,
251170, and by EU ECSEL Joint Undertaking under grant agreement in LPNMR, volume 9345 of LNCS, pp. 384–397. Springer, (2015).
[20] Michael Gelfond and Yulia Kahl, Knowledge Representation, Reason-
no. 737459 (project Productive4.0).
ing, and the Design of Intelligent Agents: The Answer-Set Programming
We are thankful to Peter Schüller for his contributions to our ear- Approach, Cambridge University Press, 2014.
lier conference paper on this topic, and Stephen Cummings for lan- [21] Lothar Hotz, Alexander Felfernig, Markus Stumptner, Anna Ryabokon,
guage editing. Claire Bagley, and Katharina Wolter, ‘Chapter 6 - Configuration
Knowledge Representation and Reasoning’, in Knowledge-Based Con-
figuration, 41–72, Morgan Kaufmann, (2014).
REFERENCES [22] Nicola Leone, Gerald Pfeifer, Wolfgang Faber, Thomas Eiter, Georg
Gottlob, Simona Perri, and Francesco Scarcello, ‘The DLV system for
[1] Mario Alviano, Francesco Calimeri, Carmine Dodaro, Davide Fuscà, knowledge representation and reasoning’, ACM Trans. Comput. Log.,
Nicola Leone, Simona Perri, Francesco Ricca, Pierfrancesco Veltri, and 7(3), 499–562, (2006).
Jessica Zangari, ‘The ASP system DLV2’, in LPNMR, volume 10377 [23] Nicola Leone and Francesco Ricca, ‘Answer set programming: A tour
of LNCS, pp. 215–221. Springer, (2017). from the basics to advanced development tools and industrial applica-
[2] Chitta Baral, Knowledge Representation, Reasoning and Declarative tions’, in Reasoning Web, eds., Wolfgang Faber and Adrian Paschke,
Problem Solving, Cambridge University Press, 2003. volume 9203 of LNCS, pp. 308–326. Springer, (2015).
[3] Francesco Calimeri, Wolfgang Faber, Martin Gebser, Giovambattista [24] Lorenz Leutgeb and Antonius Weinzierl, ‘Techniques for efficient lazy-
Ianni, Roland Kaminski, Thomas Krennwallner, Nicola Leone, Marco grounding ASP solving’, in DECLARE, volume 10997 of LNCS, pp.
Maratea, Francesco Ricca, and Torsten Schaub, ‘ASP-Core-2 input lan- 132–148. Springer, (2017).
guage format’, TPLP, 20(2), 294–309, (2020). [25] Vladimir Lifschitz, Answer Set Programming, Springer, 2019.
[4] Francesco Calimeri, Davide Fuscà, Simona Perri, and Jessica Zangari, [26] Matthew W. Moskewicz, Conor F. Madigan, Ying Zhao, Lintao Zhang,
‘I-DLV: the new intelligent grounder of DLV’, Intelligenza Artificiale, and Sharad Malik, ‘Chaff: Engineering an efficient SAT solver’, in 38th
11(1), 5–20, (2017). Design Automation Conference (DAC), pp. 530–535. ACM, (2001).
[5] Francesco Calimeri, Martin Gebser, Marco Maratea, and Francesco [27] Gottfried Schenner and Richard Taupe, ‘Techniques for solving large-
Ricca, ‘Design and results of the fifth answer set programming com- scale product configuration problems with ASP’, in Proceedings of the
petition’, Artif. Intell., 231, 151–181, (2016). 19th International Configuration Workshop, eds., Linda L. Zhang and
[6] Francesco Calimeri, Giovambattista Ianni, and Francesco Ricca, ‘The Albert Haag, pp. 12–19, La Défense, France, (2017).
third open answer set programming competition’, TPLP, 14(1), 117– [28] Richard Taupe, Gerhard Friedrich, Konstantin Schekotihin, and Anto-
135, (2014). nius Weinzierl, ‘Domain-specific heuristics in answer set programming:
[7] Carmine Dodaro, Philip Gasteiger, Nicola Leone, Benjamin Musitsch, A declarative non-monotonic approach’. Under review.
Francesco Ricca, and Konstantin Schekotihin, ‘Combining answer set [29] Richard Taupe, Konstantin Schekotihin, Peter Schüller, Antonius
programming and domain heuristics for solving hard industrial prob- Weinzierl, and Gerhard Friedrich, ‘Exploiting partial knowledge in
lems (application paper)’, TPLP, 16(5-6), 653–669, (2016). declarative domain-specific heuristics for ASP’, in ICLP Technical
[8] Thomas Eiter, Wolfgang Faber, Michael Fink, and Stefan Woltran, Communications, volume 306 of EPTCS, pp. 22–35, (2019).
‘Complexity results for answer set programming with bounded pred- [30] Richard Taupe, Antonius Weinzierl, and Gerhard Friedrich, ‘Degrees
icate arities and implications’, Ann. Math. Artif. Intell., 51(2-4), 123– of laziness in grounding – effects of lazy-grounding strategies on ASP
165, (2007). solving’, in LPNMR, volume 11481 of LNCS, pp. 298–311, (2019).
[9] Esra Erdem, Michael Gelfond, and Nicola Leone, ‘Applications of an- [31] Erich C Teppan, ‘Solving the partner units configuration problem with
swer set programming’, AI Magazine, 37(3), 53–68, (2016). heuristic constraint answer set programming’, in Configuration Work-
[10] Andreas A. Falkner, Gerhard Friedrich, Alois Haselböck, Gottfried shop, pp. 61–68, (2016).
Schenner, and Herwig Schreiner, ‘Twenty-five years of successful ap- [32] Erich Christian Teppan and Gerhard Friedrich, ‘Heuristic constraint an-
plication of constraint technologies at Siemens’, AI Magazine, 37(4), swer set programming’, in ECAI, volume 285 of Frontiers in Artificial
67–80, (2016). Intelligence and Applications, pp. 1692–1693. IOS Press, (2016).
[11] Andreas A. Falkner, Gerhard Friedrich, Konstantin Schekotihin, [33] Erich Christian Teppan, Gerhard Friedrich, and Andreas A. Falkner,
Richard Taupe, and Erich Christian Teppan, ‘Industrial applications of ‘QuickPup: A heuristic backtracking algorithm for the partner units
answer set programming’, KI, 32(2-3), 165–176, (2018). configuration problem’, in IAAI. AAAI, (2012).
[12] Gerhard Friedrich, Anna Ryabokon, Andreas A. Falkner, [34] Erich Christian Teppan, Gerhard Friedrich, and Georg Gottlob,
Alois Haselböck, Gottfried Schenner, and Herwig Schreiner, ‘Tractability frontiers of the partner units configuration problem’, J.
‘(Re)configuration using answer set programming’, in IJCAI 2011 Comput. Syst. Sci., 82(5), 739–755, (2016).
Workshop on Configuration, volume 755 of CEUR Workshop Proceed- [35] Antonius Weinzierl, ‘Blending lazy-grounding and CDNL search for
ings, pp. 17–24, (2011). answer-set solving’, in LPNMR, volume 10377 of LNCS, pp. 191–204.
[13] Martin Gebser, Roland Kaminski, Benjamin Kaufmann, Marius Lin- Springer, (2017).
dauer, Max Ostrowski, Javier Romero, Torsten Schaub, Sven Thiele,
and Philipp Wanko, Potassco guide version 2.2.0, 2019. Retrieved
from https://github.com/potassco/guide/releases/
tag/v2.2.0.
13 See https://iktderzukunft.at/en/ for more information.
8