Domain-specific heuristics are an essential technique for solving configuration problems efficiently. Current approaches to integrate domain-specific heuristics with Answer Set Programming (ASP) are unsatisfactory when dealing with heuristics that are specified non-monotonically on the basis of partial assignments. Such heuristics frequently occur in practice, for example, when picking a component that has not yet been placed in a configuration problem. Therefore, we present novel syntax and semantics for declarative specifications of domain-specific heuristics in ASP. Our approach supports heuristic statements that depend on the partial assignment maintained during solving, which has not been possible before. We provide an implementation in ALPHA that makes ALPHA the first lazy-grounding ASP system to support declaratively specified domain-specific heuristics. Two well-known configuration problems are used to demonstrate the benefits of our proposal. The experiments confirm that combining lazy-grounding ASP solving and our novel heuristics can be vital for solving industrial-size configuration problems.
Answer Set Programming (ASP) [
However, large-scale industrial problems are challenging for ASP.
One issue is the so-called grounding bottleneck: Large problem
instances often cannot be grounded by modern grounders like GRINGO
[
Lazy grounding is a technique that tackles the grounding
bottleneck. The approach presented in this paper is implemented in the
lazy-grounding system ALPHA [
The main topic of this work concerns domain-specific heuristics,
an essential technique for improving solving performance by
equipping the solver with hints on how to solve a problem efficiently.
Several approaches to integrate domain-specific heuristics with ASP
1 This paper contains extracts from a journal paper [
Both existing approaches to integrate domain-specific heuristics with ASP solving are unsatisfactory: Procedural heuristics counteract the declarative nature of ASP, and the existing declarative approach does not permit dynamic heuristics reasoning about partial assignments. Dynamically evaluating heuristics w.r.t. a partial assignment can be an essential feature for practical domains. For example, heuristics in product configuration may need to compute the amount of space left after placing a component.
We tackle the challenge of finding a satisfying solution to integrate declarative domain-specific heuristics with ASP programs. To this end, we extend CLINGO’s approach. Our extension supports dynamic heuristics while at the same time keeping the language simple and easy to use.
We implemented our approach as an extension to the lazygrounding ASP system ALPHA. Two well-known configuration problems – the House Reconfiguration Problem (HRP) and the Partner Units Problem (PUP) – are used to demonstrate our approach and to obtain experimental results. The experiments confirm that combining lazy-grounding ASP solving and our novel heuristics can be vital for solving industrial-size configuration problems.
After briefly covering preliminaries in Section 2, we introduce the state of the art of domain-specific heuristics in ASP in Section 3. Our novel approach is presented in Section 4. Section 5 describes applications and experimental results, and Section 6 concludes this paper. 2
The declarative programming approach of ASP allows a programmer to formulate the problem as a logic program specifying the search space and the properties of solutions instead of stating how to solve a problem. An ASP solver then finds models (so-called answer sets) for this logic program, which correspond to solutions for the original problem.
Most state-of-the-art ASP systems implement “ground and solve”,
i.e., they first produce the full grounding (i.e., variable-free
equivalent) of the input program, which is then solved. This results in the
so-called grounding bottleneck: As soon as the grounding exceeds
all available memory, the problem cannot be solved anymore. Lazy
grounding avoids the grounding bottleneck by interleaving
grounding and solving. This approach is implemented by ASP systems such
as ALPHA [
Due to space constraints, we assume familiarity with syntax and
semantics of ASP, and refer to [
In the remainder of this section, we introduce the notation that will be used later in the article.
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 Ma indicates that a “must-be-true”. M signifies that an atom must eventually become true by derivation in a correct solution extending the current partial assignment, but no derivation has yet been found that would make the atom true. Let As = fa j s a 2 Ag for s 2 fF; M; Tg denote the set of atoms occurring with a specific sign in assignment A. We assume assignments to be consistent, i.e., no negative literal may also occur positively (AF \ (AM [ AT) = ;), and every positive literal must also occur with must-be-true (AT AM).
An assignment A is complete if every atom is assigned true or false. An assignment that is not complete is partial.
The function truthA for a (partial) assignment A maps an atom to the truth value that the atom is currently assigned in the given assignment, or to U if the atom is currently unassigned: truthA(a) = 8F > >><M >T > >:U a 2 AF; a 2 AM n AT; a 2 AT; otherwise. 3
DOMAIN-SPECIFIC HEURISTICS IN ASP
State-of-the-art ASP solvers are well suited to solve a wide range
of problems, as shown in ASP competitions, experiments, and
(industrial) applications reported in the literature [
HWASP [
The CLINGO system supports a declarative approach to
formulating domain-specific heuristics in ASP in the form of #heuristic
directives [
CLINGO’s semantics for heuristic directives seem to introduce
some limitations for formulating heuristics that require to reason
about the absence of truth-values for atoms, e.g. the absence of
decisions in a search state. For example, in configuring technical
systems, we might prefer to assign, in the current search state, the most
relevant yet unplaced electronic component to a free slot of a
motherboard. These limitations are discussed in detail in our other
publications [
To overcome this issue we propose, in the following section, to evaluate negation as failure (i.e., not) in heuristic statements w.r.t. the current partial assignment in the solver. This partial assignment represents the search state. As a consequence, not X is true if X is false or unassigned in a partial assignment.
DYNAMIC DECLARATIVE HEURISTICS Declaratively specifying domain-specific heuristics in ASP plays a vital role in enabling ASP to solve large-scale industrial problems. CLINGO has been the only ASP system to support such heuristics so far. Although language and semantics of heuristic directives in CLINGO have shown to be beneficial in many cases, dynamic aspects of negation as failure in heuristic conditions have not been addressed satisfactorily.
We present novel syntax and semantics for heuristic directives
in ASP that improve this situation. We assume that the underlying
solver can assign one of three values to any atom: true (denoted with
T), false (F), and must-be-true (M) (cf. [
Definition 1 (Heuristic Directive) A heuristic directive is of the form h1i, where hai (0 i n) are heuristic atoms of the form si ai, in which s0 2 ffFg; fTgg and si fF; M; Tg are sets of sign symbols and ai is an atom, and w and l are integer terms. #heuristic ha0 : ha1; : : : ; hak; h1i The heuristics’ head is given by ha0 and its condition by fha1; : : : ; hak, not hak+1, . . . , not hang, which is similar to a rule body.
Where the meaning is clear from the context, we may omit all symbols except sign symbols themselves in a set of sign symbols, e.g., we write TM instead of fT; Mg.
Example 1 Consider the following heuristic directive h: #heuristic Fa : TMb; Tc; not TMFd: This directive means that the atom a shall be assigned F if b is assigned T or M, c is assigned T, and d is not assigned.
We now introduce some notation that will be used in further definitions. The function atm maps a heuristic atom hai to ai by removing the sign, and a set of heuristic atoms to the set of atoms occurring in them (e.g., atm(Ma) = a, atm(fMa; Tbg) = fa; bg). The function signs maps a heuristic atom hai to si by removing the atom (e.g., signs(Ma) = fMg).
The head of a heuristic directive h of the form h1i is denoted by head(h) = ha0, its weight by weight(h) = w if given, else 0, and its level by level(h) = l if given, else 0. The (heuristic) condition of a heuristic directive h is denoted by cond(h) := fha1; : : : ; hak; not hak+1, : : : , not hang, the positive condition is cond+(h) := fha1; : : : ; hakg and the negative condition is cond (h) := fhak+1, : : : , hang.
Let HA be a set of heuristic atoms. Then, for s fF; M; Tg, HAjs = fa j s a 2 HAg denotes the set of atoms in HA whose set of sign symbols equals s.
Example 2 Consider the heuristic directive h from Example 1 again. Here, cond+(h)jMT = fbg; cond+(h)jT = fcg; and cond+(h)jF = ;. Furthermore, cond (h)jFMT = fdg; note that the order of sign symbols does not matter due to set semantics. The distinguishing features of our approach are as follows: Each heuristic atom contains a set of sign symbols. Each sign symbol represents one of the truth values F (false), T (true), and M (must-be-true).
In the condition, sign symbols provide a richer way of controlling when the condition is satisfied. A positive literal in the condition is satisfied if the truth value currently assigned to its atom is contained in its set of sign symbols (which is fM; Tg by default if not explicitly given). A negative literal in the condition is satisfied if the truth value currently assigned to its atom is not contained in its set of sign symbols or if its atom is currently not assigned any truth value.
In the heuristic head, the sign symbol is used to determine the
truth value to be chosen by the heuristics. If s0 is T or empty, the
heuristics makes the solver guess a0 to be true; if s0 is F, a0 will
be made false.5
Terms w and l denote weight and level as familiar from
optimizestatements in ASP-Core-2 [
We now describe our semantics more formally, beginning with the condition under which a heuristic atom is satisfied.
Definition 2 (Satisfying a Heuristic Atom) Given a ground heuristic atom ha and a partial assignment A, ha is satisfied w.r.t. A iff: truthA(atm(ha)) 2 signs(ha), i.e., if its atom is assigned a truth value that is included in the heuristic atom’s sign set.6 Whether a heuristic directive is satisfied depends on whether the atoms occurring in the directive are satisfied.
Definition 3 (Satisfying a Heuristic Directive) Given a ground heuristic directive h and a partial assignment A, cond(h) is satisfied w.r.t. A iff: every ha 2 cond+(h) is satisfied and no ha 2 cond (ha) is satisfied.
Intuitively, a heuristic condition is satisfied iff its positive part is fully satisfied and none of its default-negated literals is contradicted. Definition 4 (Applicability of a Heuristic Directive) A ground heuristic directive h is applicable w.r.t. a partial assignment A iff: cond(h) is satisfied, and truthA(atm(head(h))) 2 fU; Mg. Intuitively, a heuristic directive is applicable iff its condition is satisfied and the atom in its head is assigned neither T nor F. If the atom in the head is assigned M, the heuristic directive may still be applicable, because any atom with the non-final truth value M must be either T or F in any answer set.
Definitions 2 to 4 reveal the distinguishing features of the newly proposed semantics: In our approach, heuristic signs composed of truth values T, M, and F can be used in heuristic conditions to reason about atoms that are already assigned specific truth values in a partial assignment. Furthermore, default negation can be used to reason about atoms that are assigned or still unassigned. Our semantics 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 incomplete information is essential in many cases. An example is a 5 In the head, we only support truth values T and F because, from a user’s point of view, it does not make sense to assign M to an atom heuristically. 6 Note that the function truth maps to only one truth value even though Ta 2 A implies Ma 2 A, so truthA(a) = M iff Ma 2 A and Ta 2= A. heuristic for a configuration problem that only applies to components not yet placed.
What remains to be defined is the semantics of weight and level.
Given a set of applicable heuristic directives, one directive with the
highest weight will be chosen from the highest level. Suppose there
are several with the same maximum priority (i.e., weight and level).
In that case, the solver can use domain-independent heuristics like
VSIDS [
Definition 5 (Heuristics Eligible for Immediate Choice) Given a set H of applicable ground heuristic directives, the subset eligible for immediate choice is defined as maxpriority(H) in two steps: maxlevel(H) := maxpriority(H) := fh jh 2 H and level(h) = max level(h)g
h2H fh jh 2 maxlevel(H) and weight(h) =
max h2maxlevel(H) weight(h)g
After choosing a heuristic using maxpriority, a solver makes a decision on the directive’s head atom. Note that heuristics only choose between atoms derivable by currently applicable rules. Other solving procedures, e.g., deterministic propagation, are unaffected by processing heuristics.
Example 3 Consider the following program.
f a(2) ; a(4) ; a(6) ; a(8) ; a(5) g
:
#sum f X : a(X) g = S; Sn2 6= 0:
#heuristic a(5): [
Intuitively, directive h2i unconditionally prefers to make a(5) true with weight 1. All other directives have a higher weight, 2, but they 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 to make a(5) false if a(4) is true or must-be-true, and h5i prefers to make a(6) true if a(5) is false and a(4) is true.
Let A0 = ; be the empty partial assignment before any decision has been made. W.r.t. A0, h2i is applicable because its condition is empty and its head is still unassigned. Directive h3i is also applicable because a(5) is still unassigned. Directives h4i and h5i are not applicable w.r.t. A0. Directive h3i is chosen because it has the highest priority among applicable directives. Thus, a(4) is assigned T, updating our assignment to A1 = fMa(4); Ta(4)g. This makes h4i applicable, a(5) is assigned F and our assignment is A2 = fMa(4); Ta(4); Fa(5)g. Note that the condition of h3i was still satisfied at this point, but it was not applicable because its head was already assigned. Now, h2i is also not applicable anymore, and the only directive that remains is h5i. Since h5i is applicable, a(6) is made true and added to the assignment. Next, the atoms that remained unassigned are guessed by the default heuristics until an answer set is found. 5
APPLICATIONS AND EXPERIMENTS In this section, we present an application of our approach on two configuration problems. Experimental results are also included, using an implementation of our approach in the lazy-grounding ASP system ALPHA. Instance sets include instances that were challenging to ground and solve. 5.1 Encodings (including heuristics) and instances, and the ALPHA binaries used for our experiments, are available on our website.7 Details on the sources of the encodings are mentioned in the sections describing the domains. Optimisation statements were not used since ALPHA does not support them yet. However, heuristic directives can be written in a way that optimal or near-optimal solutions are preferably found.
Problem instances were selected by first defining an instancegenerating algorithm and then exploring instance sizes to find a set in which all systems could solve some instances under consideration within a time limit of 10 minutes, and some instances could be solved by none (or very few) of these systems.
The ASP systems used for the experiments were ALPHA8,
CLINGO9 [
ALPHA is used in two configurations, grounding constraints either
strictly or permissively [
Under the partial assignment A = fMa(1; 2); Ta(1; 2)g, the ground constraint a(1; 2); b(1): will only be produced if permissive grounding of constraints is enabled.
All solvers were configured to search for the first answer set of
each problem instance. Finding one or only a few solutions is often
sufficient in industrial use cases since solving large instances can be
challenging [
The House Reconfiguration Problem (HRP)
The House Reconfiguration Problem [
Formally, HRP is defined as a modification of the House Configuration Problem (HCP).
Definition 6 (HCP) The input for the House Configuration Problem (HCP) is given by four sets of constants P , T , C, and R representing persons, things, cabinets, and rooms, respectively, and an ownership relation PT P T between persons and things.
The task is to find an assignment of things to cabinets TC T C and cabinets to rooms CR C R, such that: (1) each 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 four cabinets; and (5) a room may only contain cabinets storing things of one person.
Definition 7 (HRP) The input for the House Reconfiguration Problem (HRP) is given by an HCP instance H = hP; T ; C; R; P T i, a legacy configuration hTC 0; CR0i, and a set of things T 0 T that are defined as “long” (all other things are “short”). 7 https://ainf.aau.at/dynacon 8 https://github.com/alpha-asp/Alpha 9 https://potassco.org/clingo/ 10 https://dlv.demacs.unical.it/
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 requirements of HCP as well as the following ones: (1) a cabinet is either small or high; (2) a long thing can only be put into a high cabinet; (3) a small cabinet occupies 1 and a high cabinet 2 of 4 slots available in a room; (4) all legacy cabinets are small.
The sample HRP instance shown in Fig. 1 comprises two cabinets, two rooms, five things that belong to person p1, and one thing that belongs to person p2. A legacy configuration is empty, and all things are small. In a solution, the first person’s things are placed in cabinet c1 in the first room, and the thing of the second person is the cabinet c2 in the second room. For this sample instance, a solution of HRP corresponds to a solution of HCP.
In the problem encoding [
Instances consist of facts over the following predicates: cabinetDomain=1 defines potential cabinets and roomDomain=1 defines potential rooms; thingLong=1 defines which things are long; and legacy=1 defines all the other data in the legacy configuration, e.g., legacy(personTOthing(p1; t1)) defines that person p1 owns thing t1, and legacy(roomTOcabinet(r1; c1)) specifies one tuple in the legacy assignment of cabinets to rooms.
The domain-specific heuristics for HRP implemented in our novel approach works by (1) first trying to re-use the legacy configuration; (2) then filling cabinets with things; (3) then filling rooms with cabinets; (4) and finally closing remaining choices. Long things are always assigned before short things.
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 choosing the wrong truth values.
We now present some selected heuristic directives. The directives use some intermediate predicates whose meaning should become evident from their names. The full encoding is available online. The following heuristics re-use the legacy assignment of cabinets to things and of rooms to cabinets (1): #heuristic reuse(cabinetTOthing(C; T )) :
legacy(cabinetTOthing(C; T )); thingLong(T ): [4@4] #heuristic reuse(cabinetTOthing(C; T )) : legacy(cabinetTOthing(C; T )); not thingLong(T ): [3@4] #heuristic reuse(roomTOcabinet(R; C)) :
legacy(roomTOcabinet(R; C)): [2@4]
The following heuristic assigns things to cabinets, preferring long over short things (2): #heuristic cabinetTOthing(C; T ) : cabinetDomain(C); not fullCabinet(C); not T assignedThing(T ); personTOthing(P; T ); not otherPersonTOcabinet(P; C); maxCabinet(MC ); thingLong(T ): [(MC C)@3] #heuristic cabinetTOthing(C; T ) : cabinetDomain(C); not fullCabinet(C); not T assignedThing(T ); personTOthing(P; T ) not otherPersonTOcabinet(P; C); maxCabinet(MC ); not thingLong(T ): [(MC C)@2] The heuristics we created for ALPHA cannot be used with CLINGO due to the usage of T and default negation. An alternative encoding containing faithfully adapted heuristic directives for CLINGO has also been created.
Figure 2 shows performance data for experiments with HRP. Cactus 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 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 legend with all solver configurations. The number of instances solved by each system is shown next to its name (in parentheses).
One curve was drawn for each solver configuration: ALPHA without domain-specific heuristics, with strict (kco = 0) and permissive (kco = 1) grounding of constraints; ALPHA with domainspecific heuristics (H-ALPHA), with strict and permissive grounding of constraints; DLV2; CLINGO with (H-CLINGO) and without domain-specific heuristics.
Substantial differences can be observed. The curves for H-ALPHA (kco = 0) reach farthest to the right, meaning that ALPHA with domain-specific heuristics solved the highest number of instances (59 out of 94) when grounding constraints strictly. Surprisingly, with permissive grounding of constraints, ALPHA with domain-specific heuristics exhibited relatively low time and space performance.
No curves are visible at all for ALPHA without domain-specific heuristics because, in this configuration, the system could solve at most one instance only. The other solvers’ performance was somewhere in between the ALPHA configurations at both ends of the spectrum. Notably, H-CLINGO with domain-specific heuristics solved more instances in less time compared to CLINGO without domainspecific heuristics, but consumed slightly more memory. The largest instance solved by H-ALPHA contained 600 things, which is over 30% more than the size of the largest instance solved by H-CLINGO (455). Recall that the time limit for solving each instance was 10 minutes. 5.3
Like HRP, the Partner Units Problem (PUP) [
Definition 8 (PUP) The input to the Partner Units Problem (PUP) is given by a set of units U and a bipartite graph G = (S; Z; E), where S is a set of sensors, Z is a set of zones, and E is a relation between S and Z. UCAP = 2 IUCAP = 2 27 24 21 ) iB18 (15 G y ro12 e 9 m M6 3 0 140 The task is to find a partition of vertices v 2 S [ Z into bags ui 2 U such that for each bag the following requirements hold: (1) the bag contains at most UCAP vertices from S and at most UCAP vertices from Z; and (2) the bag has at most IUCAP adjacent bags, where the bags u1 and u2 are adjacent whenever vi 2 u1 and vj 2 u2 for some (vi; vj ) 2 E.
QuickPup is a heuristic for PUP that successfully solves many
hard problem instances [
First, a start zone is determined and denoted by startZone=1. In our encoding, the start zone is always the first one and instances are designed so that solutions can easily be found when starting with this zone. QuickPup should actually try to use each zone as the start zone one after the other and abort search after a certain amount of time has passed. This part of the algorithm cannot currently be represented in our framework.
QuickPup assigns zones and sensors to units in a breadth-firstorder, called “topological order” because the graph is traversed level by level. First, the start zone is assigned, then the sensors connected to the start zone, then the zones connected to those sensors and so on. A helper predicate layer=3 is introduced to compute the topological order. In an atom layer(T ; X; L), T denotes the type of element (“s” for sensor and “z” for zone), X is the element’s identifier, and L is its layer in the computed breadth-first order.
A realisation of QuickPup in our framework requires several heuristic directives. These directives use the level term in the annotation to process the zones and sensors according to the topological order. The weight term in the annotation is used to assign the units in the right order. The directives use some intermediate predicates whose meaning should become evident from their names. The full encoding is available online.
QuickPup first tries to assign an element to the first unit: #heuristic assign(U; T ; X) : comUnit(U ); elem(T ; X); maxLayer(ML); layer(T ; X; L); not full(U; T ); not assigned(T ; X); not T used(U ); nUnits(NU ); U = 1: [NU @(ML L)]
If one unit cannot be assigned, QuickPup tries preceding units in decreasing order next: #heuristic assign(U; T ; X) : comUnit(U ); elem(T ; X); maxLayer(ML); layer(T ; X; L); not full(U; T ); not assigned(T ; X);
T used(U ): [U @(ML L)] A fresh unit is only touched if all preceding units have been tried: #heuristic assign(U; T ; X) : comUnit(U ); elem(T ; X); maxLayer(ML); layer(T ; X; L); not full(U; T ); not assigned(T ; X); not T used(U ); comUnit(U 1); T used(U 1);
F assign(U 1; T ; X): [U @(ML L)]
Note the condition F assign(U 1; T; X) in the last heuristic directive. Due to this condition, the heuristic is only applicable if the same element could not be assigned to the preceding unit U 1. This situation may be caused by backtracking or by the following heuristic avoiding assignments to units that are already full: #heuristic F assign(U; T ; X) : comUnit(U ); elem(T ; X); maxLayer(ML); full(U; T ); not assign(U; T ; X): [1@ML]
Choice points not assigned by any of these heuristics are finally assigned false by a dedicated heuristic directive, similarly as shown for HRP in Section 5.2.
The heuristics we created for ALPHA cannot be used with CLINGO due to the usage of T, F, and default negation. An alternative encoding containing heuristic directives for CLINGO has been created that is similar to the QuickPup*-like heuristics created for ALPHA.
Cactus plots for PUP (Fig. 4) were generated in the same way as for HRP (cf. Section 5.2).
Again, ALPHA with domain-specific heuristics solved the highest number of instances (all 100). The curves for H-ALPHA (kco = 0) and H-ALPHA (kco = 1) are almost indistinguishable, meaning that it did not make a difference in the PUP domain whether constraints were grounded strictly or permissively.
At the other extreme, ALPHA without domain-specific heuristic could solve only 7 of the 100 instances.
The systems DLV2, CLINGO, and H-CLINGO performed somewhere between those extremes. H-CLINGO with domain-specific heuristics solved many more instances than CLINGO without domainspecific heuristics.
The largest instance in our instance set contained 300 units. HALPHA was able to solve all these instances. In contrast, the size of the largest instance that could be solved by any other system, using the given encoding, was only 105. Recall that the time limit for solving each instance was 10 minutes. For 11 instances, H-CLINGO returned an error (“Id out of range”). 5.4
Our results show that we have extended the application area of ASP. By combining our novel approach to domain-specific heuristics with lazy-grounding answer set solving, we could solve large-scale problem instances that are out of reach for conventional ASP systems. This finding supports our initial hypothesis that both lazy grounding and domain-specific heuristics are crucial for solving large-scale industrial problems.
Our approach extends an earlier extension of ASP’s input language
by a declarative framework for domain-specific heuristics [
Our results undeniably show that domain-specific heuristics improve solving performance for the domains under consideration. This is not only true for ALPHA but also for CLINGO. However, domainspecific heuristics usually increase CLINGO’s memory consumption, thus exacerbating the grounding bottleneck from which ground-andsolve systems such as CLINGO are suffering. Domain-specific heuristics for DLV2 were out of scope because DLV2 does not support the declarative specification of heuristics.
Solution quality is another aspect to keep in mind. Since domainspecific heuristics lead the solver towards “better” solutions, the quality of answer sets computed by H-ALPHA or H-CLINGO is higher than the quality of answer sets computed by ALPHA, CLINGO, or DLV2.
However, we do not claim that heuristics based on partial assignments are always beneficial. Our findings cannot reject the possibility that H-CLINGO might outperform H-ALPHA when other encodings or other heuristics are used since there might be encoding optimisations that we have not thought of. Still, we are confident that our approach’s novel features make the specification of practical heuristics more intuitive and effortless.
Results for HRP (Fig. 2) indicate that permissive grounding (cf.
[
To sum up, domain-specific heuristics implemented in our novel framework, combined with strict lazy grounding by ALPHA, outperformed all other tested systems when applied to large instances of the House Reconfiguration Problem and the Partner Units Problem. Applications to other domains should be easy to put into practice and belong to future work.12 6
We have proposed novel syntax and semantics for declarative domain-specific heuristics in ASP that can depend nonmonotonically on the partial assignment maintained during solving. Furthermore, we have presented experimental results obtained with an implementation of our approach within the lazy-grounding solver ALPHA.
Our semantics has proven beneficial for several practical
application domains, advancing CLINGO’s previous approach [
Our approach’s suitability to implement heuristics for other
practical (configuration) problems should be assessed by the community.
12 One other domain, A* search, is investigated in our journal paper [
Thinking more broadly, the question of how to generate domainspecific heuristics automatically is of great importance since, currently, such heuristics have to be invented by humans familiar with the domain (and partly also with solving technology).
This work has been conducted in the scope of the research project DynaCon (FFG-PNr.: 861263), which was funded by the Austrian Federal Ministry of Transport, Innovation and Technology (BMVIT) under the program “ICT of the Future” between 2017 and 2020.13 This research was also supported by the Academy of Finland, project 251170, and by EU ECSEL Joint Undertaking under grant agreement no. 737459 (project Productive4.0).
We are thankful to Peter Schu¨ller for his contributions to our earlier conference paper on this topic, and Stephen Cummings for language editing. 13 See https://iktderzukunft.at/en/ for more information.