=Paper=
{{Paper
|id=Vol-1453/09_GebserRyabokonSchenner_SolvingCombinedConfiguration_Confws-15_p55
|storemode=property
|title=Solving combined configuration problems: a heuristic approach
|pdfUrl=https://ceur-ws.org/Vol-1453/09_GebserRyabokonSchenner_SolvingCombinedConfiguration_Confws-15_p55.pdf
|volume=Vol-1453
|dblpUrl=https://dblp.org/rec/conf/confws/GebserRS15
}}
==Solving combined configuration problems: a heuristic approach==
https://ceur-ws.org/Vol-1453/09_GebserRyabokonSchenner_SolvingCombinedConfiguration_Confws-15_p55.pdf
Solving Combined Configuration Problems:
A Heuristic Approach1
Martin Gebser2 and Anna Ryabokon3 and Gottfried Schenner4
Abstract. This paper describes an abstract problem derived from classical computer science problems for which there already exist
a combination of Siemens product configuration problems encoun- some well-known heuristics and algorithms that can be applied to
tered in practice. Often isolated parts of configuration problems can speed up computations and/or improve the quality of solutions.
be solved by mapping them to well-studied problems for which ef- As the main contribution, we present a novel approach on how
ficient heuristics exist (graph coloring, bin-packing, etc.). Unfortu- heuristics generated by a greedy solver can be incorporated in an
nately, these heuristics may fail to work when applied to a problem ASP program to improve computation time (and obtain better so-
that combines two or more subproblems. In the paper we show how lutions). The application of domain-specific knowledge formulated
to formulate a combined configuration problem in Answer Set Pro- succinctly in an ASP heuristic language [8] allows for better solu-
gramming (ASP) and to solve it using heuristics à la hclasp. The tions within a shorter solving time, but it strongly deteriorates the
latter stands for heuristic clasp that is nowadays integrated in clasp search process when some additional requirements (conflicting with
and enables the declaration of domain-specific heuristics in ASP. In the formulated heuristics) are included. On the other hand, the for-
addition, we present a novel method for heuristic generation based mulation of complex heuristics might be cumbersome using greedy
on a combination of greedy search with ASP that allows to improve methods. Therefore, we exploit a combination of greedy methods
the performance of clasp. with ASP for the generation of heuristics and integrate them to ac-
celerate an ASP solver. We evaluate the method on a set of instances
derived from configuration scenarios encountered by us in practice
1 Introduction and in general. Our evaluation shows that for three different sets of
Researchers in academia and industry have tried different approaches instances solutions can be computed an order of magnitude faster
to configuration knowledge representation and reasoning, including than compared to a plain ASP encoding.
production rules, constraints languages, heuristic search, description The remainder of this paper is structured as follows. Section 2 in-
logics, etc.; see [16, 14, 9] for surveys. Although constraint-based troduces a combined configuration problem (CCP) which is exempli-
methods remain de facto standard, Answer Set Programming (ASP) fied in Section 3. Section 4 discusses heuristics for solving the CCP.
has gained much attention over the last years because of its expres- We present our evaluation results in Section 5. Finally, in Section 6
sive high-level representation abilities. we conclude and discuss future work.
As evaluation shows ASP is a compact and expressive method to
capture configuration problems [15, 18, 9], i.e. it can represent con- 2 Combined Configuration Problem
figuration knowledge consisting of component types, associations,
attributes, and additional constraints. The declarative semantics of The Combined Configuration Problem (CCP) is an abstract prob-
ASP programs allows a knowledge engineer to choose the order in lem derived from a combination of several problems encountered in
which rules are written in a program, i.e. the knowledge about types, Siemens practice (railway interlocking systems, automation systems,
attributes, etc. can be easily grouped in one place and modularized. etc.). A CCP instance is defined by a directed acyclic graph, called
Sound and complete solving algorithms allow to check a configu- just graph later on in this paper for simplicity. Each vertex of the
ration model and support evolution tasks such as reconfiguration. graph has a type and each type of the vertices has a particular size.
Generally, the results prove that ASP has limitations when applied In addition, each instance comprises two sets of vertices specifying
to large-scale product (re)configuration instances [1, 5]. The best re- two vertex-disjoint paths in the graph. Furthermore, an instance con-
sults in terms of runtime and solution quality were achieved when tains a set of areas, sets of vertices defining possible border elements
domain-specific heuristics were applied [17, 12]. of each area and a maximal number of border elements per area. Fi-
In this paper we introduce a combined configuration problem nally, a number of available colors as well as a number of available
that reflects typical requirements frequently occurring in practice at bins and their capacity are given.
Siemens. The parts of this problem correspond (to some extent) to Given a CCP instance, the goal is to find a solution that satisfies
a set of requirements. All system requirements are separated into
1 This work was funded by COIN and AoF under grant 251170 as well as
the corresponding subproblems which must be solved together or in
by FFG under grant 840242. An extended version of this paper is to appear combinations:
in the proceedings of the 13th International Conference on Logic Program-
ming and Non-monotonic Reasoning.
2 Aalto University, HIIT, Finland and University of Potsdam, Germany, • P1 Coloring Every vertex must have exactly one color.
email: martin.gebser@aalto.fi • P2 Bin-Packing For every color a Bin-Packing problem must be
3 Alpen-Adria-Universität Klagenfurt, Austria, email: anna.ryabokon@aau.at solved. For every color the same number of bins are available.
4 Siemens AG Österreich, Austria, email: gottfried.schenner@siemens.com
Every vertex must be assigned to exactly one bin of its color and
55 Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
for every bin it holds that the sum of sizes must be smaller or equal Paths constraint (P3) is active. Consequently, in this case the
to the bin capacity. solution shown in Figure 2 violates this constraint and must be
• P3 Disjoint Paths Vertices of different paths cannot be colored in modified as given in Figure 4 where the vertices of different paths
the same color. are colored with different colors (path1 with dark grey and grey, and
• P4 Matching Each border element must be assigned to exactly path2 with white and light grey).
one area such that the number of selected border elements of an
area does not exceed the maximal number of border elements and b5 e1 b6
all selected border elements of an area have the same color.
• P5 Connectedness Two vertices with the same color must be con- b1 s1 p1 b2 p2 b3 p3 s2 b4
nected via a path that contains only vertices of that color.
b7 s3 p4 b8 p5 b9 p6 s4 b10
Origin In the railway domain the given graph represents a track lay-
out of a railway line. A coloring P1 can then be thought as an assign- b11 e2 b12
ment of resources (e.g. computers) to the elements of the railway line.
In real-world scenarios different infrastructure elements may require Figure 2: Used colors in a solution of the Coloring and Bin-Packing
different amounts of a resource that is summarized in P2. This may problems (P1-P2)
be hardware requirements (e.g. a signal requiring a certain number
of hardware parts) or software requirements (e.g. an infrastructural
element requiring a specific processing time). The requirements of b9
P1 and P2 are frequently used in configuration problems during an e2
s4 b8 s2
p5
assignment of entities of one type to entities of another type [11, 5]. b3
p2 p6 p3
s3
p4 p1 e1
The constraint of P3 increases availability, i.e. in case one resource b5 b11 s1 b7
b4 b10 b1 b2 b12 b6
fails it should still be possible to get from a source vertex (no in-
coming edges) of the graph to a target vertex (no outgoing edges) of Figure 3: Used bins in a solution of the Coloring and Bin-Packing
the graph. In the general version of this problem one has to find n problems (P1-P2)
paths that maximize availability. The CCP uses the simplified prob-
lem where 2 vertex-disjoint paths are given.
P4 stems from detecting which elements of the graph are occu-
pied. The border elements function as detectors for an object leaving b5 e1 b6
or entering an area. The Partner Units Problem [2, 1] is a more elab-
b1 s1 p1 b2 p2 b3 p3 s2 b4
orate version of this problem. P5 arises in different scenarios, e.g. if
communication between elements controlled by different resources
is more costly, then neighboring elements should be assigned to the b7 s3 p4 b8 p5 b9 p6 s4 b10
same resource whenever possible.
b11 e2 b12
3 Example Figure 4: Solution of the Coloring, Bin-Packing and Disjoint Paths
problems (P1-P3)
Figure 1 shows a sample input CCP graph. In this section we illus-
trate how particular requirements can influence a solution. Namely,
Figure 5 shows an example of Matching (P4). In this example
we add the constraints of each subproblem one by one. If only P1
there are seven areas in the matching input graph, each correspond-
is active, any graph corresponds to a trivial solution of P1 where all
ing to a subgraph surrounded with border elements (Figure 1). For in-
vertices are colored white.
stance, area a1 represents the subgraph {b1, s1, p1, b2, b5} and area
a2 the subgraph {b5, e1, b6}. The corresponding border elements,
b5 e1 b6
{b1, b2, b5} and {b5, b6}, are displayed in Figure 5.
Assume that an area can have at most 2 border elements assigned
b1 s1 p1 b2 p2 b3 p3 s2 b4
to it. In the resulting matching (Figure 5) b1, b2 are assigned to a1,
whereas b5, b6 are assigned to a2. Note that the sample selected
b7 s3 p4 b8 p5 b9 p6 s4 b10
matching shown in Figure 5 is not valid with the coloring presented
b11 e2 b12
previously, because, for example, b5 and b6 are assigned to the same
area a2 although they are colored differently.
Figure 1: Input CCP graph and a trivial solution of Coloring (P1) In addition, the coloring solution shown in Figure 4 violates the
Connectedness constraint (P5). Therefore, the previous solutions
must be updated to take the new requirements into account. Figure 6
Let us consider the input graph as a Bin-Packing problem instance shows a valid coloring of the given graph that satisfies all problem
with four colors and three bins per color of a capacity equal to five. requirements (P1-P5).
The vertices of type b, e, s and p have the sizes 1, 2, 3 and 4, respec-
tively. A solution of Coloring and Bin-Packing (P1-P2) is presented
4 Combining Heuristics for Configuration
in Figures 2 and 3.
Problems
Moreover, two vertex-disjoint paths are declared by
path1 = {b1, s1, p1, b2, p2, b3, p3, s2, b4} as well as We formulated the CCP using ASP and the corresponding encod-
path2 = {b7, s3, p4, b8, p5, b9, p6, s4, b10}, and the Disjoint ing can be found at http://isbi.aau.at/hint/problems.
Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors 56
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
tion algorithms (construction heuristics) that allow efficient computa-
a1 a2 a3 a4 a5 a6 a7
tion of good approximations of a solution [6], e.g. Best/First/Next-Fit
heuristics. They can, of course, be used as heuristics for the CCP.
Let the Bin-Packing problem instance be encoded using a set of
b1 b2 b5 b6 b4 b3 b8 b9 b7 b11 b10 b12 predicates among which nrofbins/1 and order /2 denote a number
of bins in the instance and an ordered set of input vertices, respec-
Figure 5: A sample input and solution graphs for P4. The selected tively. The predicate vertex bin/2 is used to encode a solution and
edges of the input graph are highlighted with solid lines. denotes an assignment of a vertex to a bin. As shown in Listing 2,
given a (decreasing) order of vertices, we can force the solver to
b5 e1 b6
place vertex Vi into the lowest-indexed bin for which the size of al-
ready placed vertices does not exceed the capacity, i.e. in a first-fit
b1 s1 p1 b2 p2 b3 p3 s2 b4 bin. The heuristic never uses a new bin until all the non-empty bins
are full and it can be expressed by rules that generate always a higher
b7 s3 p4 b8 p5 b9 p6 s4 b10 level for the bins with smaller number:
b11 e2 b12 1 binDomain(1..NB) :- nrofbins(NB).
2 offset(NB+1) :- nrofbins(NB).
Figure 6: A valid solution for P1-P5 3 _heuristic(vertex_bin(V,B),true,M+O*NB-B) :-
binDomain(B), nrofbins(NB), order(V,O),
offset(M).
To formulate a heuristic within ASP we use the declarative heuris-
tic framework developed by Gebser et al. [8]. In this formalism the
heuristics are expressed using atoms heuristic(a, m, v, p), where Listing 2: First-Fit heuristic for an assignment of vertices to bins
a denotes an atom for which a heuristic value is defined, m is one of
four modifiers (init, factor, level and sign), and v, p are integers de- It is also possible (with an intense effort) to express other heuristics
noting a value and a priority, respectively, of the definition. A num- for P1-P5 that guide the search appropriately and allow to speed up
ber of shortcuts are available, e.g. heuristic(a, v, l), where a is an the computation of solutions if we solve these problems separately.
atom, v is its truth value and l is a level. The heuristic atoms modify However, as our experiments show, the inclusion of heuristics for
the behavior of the VSIDS heuristic [10]. Thus, if a heuristic atom different problems at the same time might drastically deteriorate the
is true in some interpretation, then the corresponding atom a might performance for real-world CCP instances.
be preferred by the ASP solver at the next decision point.
There are different ways to incorporate heuristic atoms in a pro-
4.2 Greedy Search
gram. The standard approach [8] requires an implementation of a
heuristic at hand using a pure ASP encoding, whereas the idea of our From our observations in the context of product configuration, it is
method is to delegate the (expensive) generation of a heuristic to an relatively easy to devise a greedy algorithm to solve a part of a config-
external tool and then to extend the program with generated heuristic uration problem. This is often the case in practice, because products
atoms to accelerate the ASP search. Below we will exemplify how are typically designed to be easily configurable. The hard configu-
both approaches can be applied. ration instances usually occur when new constraints arise due to the
combination of existing products and technologies.
The same can be said for the CCP. Whereas it is easy to develop
4.1 Standard generation of heuristics in ASP greedy search algorithms for the individual subproblems, it becomes
Several heuristics can be used for the problems that compose the increasingly difficult to come up with an algorithm that solves the
CCP. For instance, for the coloring of vertices (P1) we seek to use as combined problem. For instance, a greedy algorithm for the Match-
few colors as possible by the following rule: ing problem of the CCP (P4) can be formulated as follows: For every
vertex v find a related area a with the fewest assigned vertices so
1 _heuristic(vertex_color(V,C),true,MC-C) :- far and match v with a. The algorithm assumes that all border ele-
vertex(V), color(C), nrofcolors(MC). ments are colored with one color, as it trivially satisfies the coloring
requirement of the matching problem. A greedy algorithm for solv-
ing the CCP wrt. Coloring, Bin-Packing and Connectedness (P1, P2
Listing 1: Heuristic for an assignment of colors to vertices and P5) can be described as follows:
Roughly speaking, this rule means that the assignment of 1. Select the first available color c and add the first vertex not as-
colors to vertices must be done in an ascending order of signed to any bin to a queue Q;
colors. Given a vertex (b1) and two colors nrofcolors(2) 2. Get and remove from Q the first element v, label it with c and try
encoded as color (1) and color (2), the solver can derive to assign it to a bin using some Bin-Packing heuristic, e.g. First-Fit
two heuristic atoms heuristic(vertex color (b1, 1), true, 1) and or Best-Fit [6];
heuristic(vertex color (b1, 2), true, 0). These atoms indicate the 3. If v is assigned to some bin, add neighbors of v to Q;
solver that the atom vertex color (b1, 1) must be assigned the truth 4. If Q 6= ∅, then goto 2;
value true first since the atom with the higher level is preferred. 5. Otherwise, if there are unassigned vertices, then make the color c
Additionally, we can apply the well-known Bin-Packing heuris- unavailable and goto 1.
tics for the placement of colored vertices into the bins of specified
capacity (P2). The Bin-Packing problem is known to be an NP-hard Suppose one wants to combine these two algorithms. One strategy
combinatorial problem. However, there are a number of approxima- would be to run greedy Matching and then solve the Bin-Packing
57 Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
idea of combining local search with a complete solver is also found
Algorithm 1: Greedy & ASP
in large neighborhood search [4].
Input: A problem P , an ASP program Π solving the problem P
Output: A solution S
1 GreedySolution ← solveGreedy(P ); 5 Experimental results
2 H ← generateHeuristic(GreedySolution);
Experiment1 In our evaluation we compared a plain ASP en-
3 return solveWithASP(Π, H);
coding of the CCP with an ASP encoding extended with domain-
specific knowledge. The Bin-Packing problem (P2) of the CCP cor-
problem taking matchings into account. Namely, the combined algo- responds to the classic Bin-Packing problem and the same heuristics
rithm preforms the following steps: can be applied. We implemented several Bin-Packing heuristics such
as First/Best/Next-Fit (Decreasing) heuristics using ASP as shown in
1. Call the matching greedy algorithm and get a set of matchings Section 4.1. For the evaluation we took 37 publicly available Bin-
M = {(v1 , a1 ), . . . , (vn , am )}; Packing problem instances5 , for which the optimal number of bins
2. For each vertex vi of the input graph G do: optnrofbins is known, and translated them to CCP instances. The
(a) Assign a new color to vi , if vi has no assigned color; biggest instance of the set includes 500 vertices and 736 bins of the
capacity 100. In the experiment, the maximal number of colors was
(b) Put vi into a bin, as in the greedy Bin-Packing (steps 2-3); set to 1 and the maximal number of bins was set to 2 · optnrofbins.
(c) If vi is a border element, then retrieve an area aj that matches All instances were solved by both approaches6 . For a plain ASP
vi in M and color all vertices of this area in the same color as encoding the solver required at most 27 seconds to find a solution
vi . whereas for the heuristic ASP program solving took at most 6 sec-
onds, which is 4.5 times faster. The best results for the heuristic ap-
The combined algorithm might violate Connectedness, because it proach were obtained using the First-Fit heuristic with the decreasing
colors all border vertices assigned to an area with the same color. order of vertices. Corresponding solutions utilized less bins then the
However, these vertices are not necessarily connected. That is, there ones obtained with the plain ASP program. Moreover, using First-Fit
might be a solution with a different matching, but the greedy algo- heuristic, for 23 from 37 instances a solution with optimal number of
rithm tests only one of all possible matchings. Moreover, there is no bins was found and for 13 other instances at most 4 bins more were
obvious way how to create an algorithm solving all three problems required. The plain ASP encoding resulted in solutions that used on
efficiently. This is a clear disadvantage of using ad-hoc algorithms in average 4 bins more than corresponding solutions of the heuristic
contrast to the usage of a logic-based formalism like ASP, where the approach.
addition of constraints is just a matter of adding some rules to an en-
coding. On the other hand, domain-specific algorithms are typically Experiment2 In the next experiment we tested the same Bin-
faster and scale better than ASP-based or SAT-based approaches that Packing heuristics implemented in ASP for the combined CCP, i.e.
cannot be used for large instances. For instance, the memory demand when all subproblems P1-P5 are active, on 100 real-world test in-
of the greedy Bin-Packing algorithm is polynomial in graph size. stances of moderate size (maximally 500 vertices in an input). The
instances in this experiment were derived from a number of indus-
4.3 Combining Greedy Search and ASP trial configuration tasks. Neither the plain program nor the heuristic
program were able to improve runtime/quality of solutions. More-
One way to let a complete ASP solver and a greedy search algo- over, our greedy method described in Section 4.2 also failed to find a
rithm benefit from each other is to use the greedy algorithm to com- connected solution, i.e. when P5 is active. For this reason, we inves-
pute upper bounds for the problem to solve. The tighter upper bound tigated the combined approach (Greedy & ASP) described in Sec-
usually means smaller grounding size and shorter solving time, be- tion 4.3. This approach uses the greedy method to generate a partial
cause the greedy solver being domain-specific usually outperforms solution ignoring the Connectedness constraint and provides this so-
ASP for the relaxed version of the problem. For instance, running the lution as heuristic atoms to the ASP solver. Our experiments show
greedy algorithm for the Bin-Packing problem and Matching prob- (see Figure 7a) that the combined approach can solve all 100 bench-
lem gives upper bounds for the maximal number of colors, i.e. num- marks from the mentioned set, whereas the plain encoding solves
ber of different Bin-Packing problems to solve. The same applies to only 54 instances (the time frame was set to 900 seconds in this
the Matching problem. This kind of application of greedy algorithms and the next experiment). Moreover, for those instances which were
has a long tradition in branch and bound search algorithms, where solved using both approaches, the quality of solutions measured in
greedy algorithms are used to compute the upper bound of a problem. terms of used bins and colors was the same. However, the runtime of
For an example see [19], where a greedy coloring algorithm is used the combined approach was 18 times faster on average and required
to find an upper bound for the clique size in a graph for the computa- at most 24 seconds instead of 848 seconds needed for the plain ASP
tion of maximum cliques. In this paper we investigate a novel way to encoding.
combine greedy algorithms and ASP (Algortihm 1). Consequently,
in our approach we, first, use a greedy algorithm to find a solution of Experiment3 In addition, we tested more complex real-world in-
a relaxed version of the problem. Next, this solution is converted into stances (maximally 1004 vertices in an input)7 which we have also
a heuristic for an ASP solver which assigns the atoms of the greedy submitted to the ASP competition 2015. Similarly to Experiment2
solution a higher heuristic value.
5 http://www.wiwi.uni-jena.de/Entscheidung/binpp/index.htm
As an example for solving the complete CCP problem, we can, 6 The evaluation was performed using clingo version 4.3.0 from the Potassco
first, find an unconnected solution for the combination of Coloring, ASP collection [7] on a system with Intel i7-3030K CPU (3.20 GHz) and
Bin-Packing, Disjoint paths and Matching problems (P1-P4), and 64 GB of RAM, running Ubuntu 11.10.
7 The instances are available at: http://isbi.aau.at/hint/problems
then, use the ASP solver to fix the Connectedness property (P5). The
Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors 58
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
1000 1000
100 100
10 10
TIME, SEC
TIME, SEC
1
1
0,1
0,1
0,01
0,01
0,001
0,001
g01
g06
g11
g16
g21
g26
g31
g36
g41
g46
g51
g56
g61
g66
g71
g76
g81
g86
g91
g96
Plain ASP Greedy & ASP Plain ASP Greedy & ASP
(a) Experiment2 (b) Experiment3
Figure 7: Evaluation results using Plain ASP and Greedy & ASP
we compared the plain ASP encoding to the combined approach REFERENCES
from Section 4.3. Again, regarding the quality of solutions, both ap-
[1] M. Aschinger, C. Drescher, G. Friedrich, G. Gottlob, P. Jeavons,
proaches are comparable, i.e. they use on average the same number A. Ryabokon, and E. Thorstensen, ‘Optimization Methods for the Part-
of colors and bins, with the combined approach having a slight edge. ner Units Problem’, in Proceedings of CPAIOR, pp. 4–19, (2011).
Generally, from 48 instances considered in this experiment, 36/38 in- [2] M. Aschinger, C. Drescher, G. Gottlob, P. Jeavons, and E. Thorstensen,
stances were solved using the plain/combined encoding, respectively. ‘Tackling the Partner Units Configuration Problem’, in Proceedings of
IJCAI, pp. 497–503, (2011).
On average/maximally the plain encoding needed 69/887 seconds to [3] M. Balduccini, ‘Learning and using domain-specific heuristics in ASP
find a solution whereas the combined method took 14/196 seconds, solvers’, AI Communications, 24(2), 147–164, (2011).
respectively, which is about 5 times faster. Figure 7b shows the in- [4] Raffaele Cipriano, Luca Di Gaspero, and Agostino Dovier, ‘A hybrid
fluence of heuristics on the performance for the instances from Ex- solver for large neighborhood search: Mixing gecode and easylocal++’,
in Hybrid metaheuristics, 141–155, Springer, (2009).
periment3 that were solved by both approaches within 900 seconds.
[5] G. Friedrich, A. Ryabokon, A. A. Falkner, A. Haselböck, G. Schenner,
Although the grounding time is not presented for both experiments, and H. Schreiner, ‘(Re) configuration based on model generation’, in
we note that it requires about 10 seconds using both approaches for Proceedings of LoCoCo, pp. 26–35, (2011).
the biggest instance when all subproblems P1-P5 are active. [6] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide
to the Theory of NP-Completeness, W. H. Freeman, 1979.
[7] M. Gebser, R. Kaminski, B. Kaufmann, and T. Schaub, Answer Set
6 Discussion Solving in Practice, Morgan & Claypool Publishers, 2012.
[8] M. Gebser, B. Kaufmann, J. Romero, R. Otero, T. Schaub, and
Choosing the right domain-specific heuristics for simple backtrack- P. Wanko, ‘Domain-Specific Heuristics in Answer Set Programming’,
based solvers is essential for finding a solution at all, especially for in Proceedings of AAAI, (2013).
large and/or complex problems. The role of domain-specific heuris- [9] L. Hotz, A. Felfernig, M. Stumptner, A. Ryabokon, C. Bagley, and
K. Wolter, ‘Configuration Knowledge Representation and Reasoning’,
tics in a conflict-driven nogood learning ASP solver seems to be less Knowledge-Based Configuration: From Research to Business Cases,
important when it comes to solving time. Here the size of the ground- 41–72, (2014).
ing and finding the right encoding is often the limiting factor. Never- [10] C.F. Madigan, S. Malik, M.W. Moskewicz, L. Zhang, and Y. Zhao,
theless, domain-specific heuristics are very important to control the ‘Chaff: Engineering an efficient SAT solver’, in Proceedings of DAC,
order in which answer sets are found and are an alternative to opti- (2001).
[11] W. Mayer, M. Bettex, M. Stumptner, and A. Falkner, ‘On solving com-
mization statements. As we have shown, domain-specific heuristics plex rack configuration problems using CSP methods’, in Proceedings
also provide a mechanism to combine greedy algorithms with ASP of the IJCAI Workshop on Configuration, (2009).
solvers, which opens up the possibility to use ASP in a meta-heuristic [12] A. Ryabokon, G. Friedrich, and A. A. Falkner, ‘Conflict-Based Pro-
setting. However, the possible applications go beyond this. The same gram Rewriting for Solving Configuration Problems’, in Proceedings
of LPNMR, pp. 465–478, (2013).
approach could be used to repair an infeasible assignment using an [13] T. Schrijvers, G. Tack, P. Wuille, H. Samulowitz, and P. J. Stuckey,
ASP solver. This is currently a field of active research for us and has ‘Search combinators’, Constraints, 18(2), 269–305, (2013).
applications in the context of product reconfiguration. Reconfigura- [14] C. Sinz and A. Haag, ‘Configuration’, IEEE Intelligent Systems, 22(1),
tion occurs when a configuration problem is not solved from scratch, 78–90, (2007).
but some parts of an existing configuration have to be taken into ac- [15] T. Soininen, I. Niemelä, J. Tiihonen, and R. Sulonen, ‘Representing
configuration knowledge with weight constraint rules’, in Proceedings
count. of the Workshop on ASP, pp. 195–201, (2001).
An open question is how to combine heuristics for different sub- [16] M. Stumptner, ‘An overview of knowledge-based configuration’, AI
problems in a modular manner without the adaptation of every Communications, 10(2), 111–125, (1997).
domain-specific heuristic. Here approaches like search combinators [17] E. C. Teppan, G. Friedrich, and A. A. Falkner, ‘QuickPup: A Heuristic
Backtracking Algorithm for the Partner Units Configuration Problem’,
[13] from the constraint programming community might be useful. in Proceedings of IAAI, pp. 2329–2334, (2012).
Another interesting topic for future research would be how to learn [18] J. Tiihonen, M. Heiskala, A. Anderson, and T. Soininen, ‘WeCoTin -
heuristics from an ASP solver, i.e. to investigate the variable/value A practical logic-based sales configurator’, AI Communications, 26(1),
order chosen by an ASP solver for medium size problem instances 99–131, (2013).
and use heuristics in a backtrack solver for larger instances that are [19] Etsuji Tomita and Toshikatsu Kameda, ‘An efficient branch-and-bound
algorithm for finding a maximum clique with computational experi-
out of scope of an ASP solver due to the grounding size. Some as- ments’, Journal of Global Optimization, 37(1), 95–111, (2007).
pects of this topic were discussed in [3].
59 Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria