=Paper=
{{Paper
|id=Vol-1128/intro1
|storemode=property
|title=Toward Automatically Learned Search Heuristics for CSP-encoded Configuration Problems - Results from an Initial Experimental Analysis
|pdfUrl=https://ceur-ws.org/Vol-1128/paper1.pdf
|volume=Vol-1128
|dblpUrl=https://dblp.org/rec/conf/confws/Jannach13
}}
==Toward Automatically Learned Search Heuristics for CSP-encoded Configuration Problems - Results from an Initial Experimental Analysis==
https://ceur-ws.org/Vol-1128/paper1.pdf
Dietmar Jannach 9
Toward automatically learned search heuristics for CSP-encoded configuration
problems – results from an initial experimental analysis
Dietmar Jannach
Department of Computer Science, TU Dortmund, Germany
dietmar.jannach@tu-dortmund.de
Abstract tics are used that guide the search process. In [4], for ex-
ample, Fleischanderl et al. report of a configuration problem
Constraint Programming historically been one of
in the context of telecommunication switches where the final
the most important approaches for compactly en-
configuration can comprise thousands of interconnected com-
coding and solving product configuration prob-
ponents. The so-called “Partner Units Problem” is another ex-
lems. Solving complex configuration problems
ample of a hard real-world configuration problem, for which
efficiently however often requires the usage of
recently a heuristic algorithm was proposed which allows the
domain-specific search heuristics, which have to be
problem to be solved in an efficient way [12].
explicitly modeled by domain experts and knowl-
edge engineers. Since this is a time-consuming Such heuristics are however domain-specific or even
task, our long term research goal is to develop tech- problem-specific and their identification, formalization and
niques to automatically learn appropriate search evaluation usually is a time-consuming and manual process.
heuristics for a given configuration problem. It would therefore be desirable to have domain-independent
techniques, which help us to automatically derive appropriate
Compared to other types of Constraint Satisfaction
heuristics for a given problem setting. In principle, differ-
Problems (CSPs), practical configuration problems
ent approaches to achieve this goal are possible. First, one
have certain specific characteristics. First, often
could try to analytically examine the configuration problem
only a few of the variables are used to specify the
(or constraint network) and its solution space. Alternatively,
problem (“inputs”); in addition, the specific user in-
one could follow a learning-based approach by analyzing a
puts and the corresponding final configurations are
number of past solution searches in order to derive appropri-
not equally distributed in the solution space.
ate search heuristics.
In this paper, we present results of an initial
In our ongoing research, we will focus on the latter type of
simulation-based experimental analysis, in which
systems. The long term goal of this research activity being to
we aimed to evaluate if already simple statistics can
develop a set of methods that use a learning-based approach
help to speed up the search process. The first results
to derive search heuristics for configuration problems. We
indicate that already trivial branching statistics can
decided to follow the path of a learning-based approach for
help to improve search efficiency.
several reasons. First, in real-world applications, the configu-
ration reasoning process (e.g., to complete a partial configura-
1 Introduction tion) is initiated several times, so that more and more training
Encoding product configuration problems as Constraint Satis- data will be naturally available over time and the heuristics
faction Problems (CSPs) [13] has a comparably long tradition can thus be made self-adaptive. Furthermore, in many do-
both in research and in industrial practice. Using CSPs and mains, the actual configurations requested by customers are
Constraint Programming techniques has various advantages, not equally distributed in the solution space and there might
compared, e.g., to rule-based systems, as CSP encodings are be configurations which are far more popular than others1 .
declarative in nature and thus often easier to maintain. Fur- When using a learning approach, such information, which
thermore, a number of extensions to the basic CSP encod- might only be available once the system is deployed, can be
ing scheme as well as specific solving techniques have been integrated in the heuristics learning process.
proposed in the past, which are at least partially inspired by In this paper, we report the results of an initial experi-
the specific characteristics of product configuration problems, mental analysis, in which we implemented a basic value or-
see [1], [5], [7] or [11]. Today, there also exists a number effi- dering heuristic for CSPs, which simply ranks the possible
cient free and commercial constraint solvers that can be used variable values based on the number of times they were suc-
to check configurations for consistency or to complete partial
configurations given some customer inputs. 1
In some complex configuration scenarios, every configuration
However, some larger and complex configuration problems might be unique; still, some subassemblies are usually similar or
can only be solved efficiently when domain-specific heuris- identical across different configurations.
Michel Aldanondo and Andreas Falkner, Editors
Proceedings of the 15th International Configuration Workshop
August 29-30, 2013, Vienna, Austria
10 Dietmar Jannach
cessfully chosen in previous configuration runs. Our evalu- strategies based on a case base of past solution searches for
ation is based on a simulation, in which we artificially and similar problem instances, have shown to be very successful
randomly generated inputs for a number of benchmark prob- in CSP Solver competitions [8].
lems from a Constraint Solver competition. The correspond- 2.2 Proposed baseline and experimental setup
ing solutions were used as an input for the “training” phase
in which statistics were collected. The benchmark problems For our experiments, we extended the open source constraint
were then solved again based on this statistics-based heuris- solver Choco and implemented a new CSP value ordering
tic. To compare the efficiency, the required running times strategy called MostFrequent, which picks the next value
were measured. Our initial results show that significant re- to test in the search process simply based on the number of oc-
ductions for some types of problems can be achieved even currences of this value in solutions in previous search runs4 .
when a very simple learning strategy is applied. When considering, for example, a PC configurator, if “Intel
Overall, we consider our work to be first evidence for the Core i5” was the most frequent choice in previous configu-
general feasibility of such approaches in the configuration do- ration sessions, the solver would simply try to use this value
main and as an initial step toward the development of more first when asked to complete a partial configuration. While
advanced learning strategies. Our basic technique can further- in reality the choice of the CPU of course depends on the
more be used as a baseline in further experiments. Finally we specific requirements of the current customer, our underlying
propose an experimental evaluation protocol to evaluate the assumption is that not every possible configuration is equally
effectiveness of such learning-based approaches. popular. Therefore, if the specific CPU type was compatible
with a larger number of popular and frequent configurations,
it might be helpful to try this particular value first (as long as
2 Approach and Initial Results it is not already ruled out by other constraints specified in the
In our analysis, we focus on standard CSPs which are repre- current session)5 .
sented by a tuple < V, D, C >, where V is a set of variables, In order to evaluate this approach, we conducted exper-
D a set of finite domain associated with these variables, and iments in which we measured the running times when us-
C a set of constraints on the variables. A solution to a CSP ing different branching strategies for a number of benchmark
comprises an assignment of values to each problem variable problems of the CPAI’08 solver competition6 . As a baseline
in V such that no constraint from C is violated, see, e.g., [13] in our comparison the typical built-in IncreasingDomain
for a comprehensive discussion of CSPs. default strategy was used. The chosen benchmark problems
used in our experiments, see Section 2.3, had to fulfill certain
2.1 The role of branching strategies properties. First, they of course had to be solvable. Further-
When systematic tree search is used as a problem solving more, as we had to run a larger number of solution searches,
scheme for CSPs, the choice of the branching strategy, that e.g. to factor out random factors, we picked problems for
is, which variable to consider next and which values to try which the solver could determine a solution (or report infea-
first, can have a significant impact on the required search sibility) for a given set of random inputs relatively quickly,
time. Over the last decades, a number of different and often i.e., in less than a second7 . The experiment consisted of two
domain- or problem-independent branching heuristics have phases.
therefore been proposed to speed up the search process. (A) Statistics collection phase. Depending on the size of
Consider the following example, which shall demonstrate the problem, we randomly designated a small number of the
the impact of the branching strategy on the solution effi- problem variables to be input variables. When the CSP for
ciency. When searching for one solution for the classical “all- example contained 50 variables with an average domain size
interval series” problem2 of a given size without any problem of 20, we, e.g., picked up to 5 variables as inputs, so that
specific optimizations, the running times when using the pop- we could make sure that several thousand input combinations
ular Choco3 constraint solver with different built-in heuristics (and resulting configurations) are possible. Next, we created
range from 30ms to 1 minute. Interestingly, the best strategy random input values for these variables, started a solution
for this setting seems to be to pick variable values in decreas- search and recorded the variable assignments, if a solution
ing order (30ms), which is an order of magnitude faster than was found. In order to simulate that some configurations are
the usual “increasing domain” strategy (500ms) or the dy- more popular than others, we picked the input values using a
namic “impact-based branching” [9] strategy (800ms). When Gaussian distribution and repeated the process until 300 solu-
no specific strategy is explicitly defined, the search can take tions with the default branching heuristic were found. As we
up to one minute. are also interested how the number of training instances ef-
In many cases, the question of which heuristic to chose for fects the statistics-based approach, we defined different mea-
a certain problem setting cannot be easily decided analyti- surement points during the simulation run, in which we made
cally and requires an experimental analysis or can be explored
4
with a so-called portfolio solver. Such portfolio solvers, Technically, we used Choco’s built-in extension mechanism and
which try out different solvers and corresponding solving implemented a new ValIterator class.
5
Note that the general solution space for a given configuration
2 problem is not affected by the different heuristics.
The goal is to find permutations of a given list of numbers that
6
fulfills certain properties, see http://www.cs.st-andrews. http://www.cril.univ-artois.fr/CPAI08/
7
ac.uk/˜ianm/CSPLib/prob/prob007/refs.html We furthermore excluded benchmark problems which could not
3
http://www.emn.fr/z-info/choco-solver/ be imported by Choco’s current XML import program.
Michel Aldanondo and Andreas Falkner, Editors
Proceedings of the 15th International Configuration Workshop
August 29-30, 2013, Vienna, Austria
Dietmar Jannach 11
Figure 1: Measurements for example problems. Running times are given in milliseconds.
a snapshot of the collected statistics so far. These snapshots Using the solver’s built-in default value selection heuristic,
were taken after 30, 50, 100, 150, 200 and 300 solutions. As the problem could on average be solved in 134.44 millisec-
a baseline for the required running times using the default onds. When using the statistics-based strategy, however, the
strategy, we calculated the average search time for the 300 average running times could be reduced to 26.20ms, which is
solutions. a reduction of over 80%. Interestingly, this effect could be
(B) Measuring the effects. After the training phase, achieved already after a very small number of training runs.
we repeated the experiment with random inputs 300 times. Later on, when more training data is available, the values
This time we however used the statistics-based value se- seem to slightly increase again. As we did not measure if
lection strategy and using the training data for each of the these differences are statistically different so far, the slight
snapshots to analyze the effect when different amounts of increase could however be a random effect.
training data was available. For cases when individual val- When using the default branching strategy, the standard de-
ues never appeared in a previous solution, we used the viation for all experiment runs for the Renault problem was
IncreasingDomain strategy as a fallback. around 220ms. With the statistics-based strategy, this value
Note that we used the same set of input variables in that could be reduced to the half of that. However, when com-
phase as in the training phase, but did not use exactly the same pared to the absolute overall running times, the standard de-
input values. Instead, we again generated them randomly. viation is much higher for the statistics-based strategy. This
Otherwise, a simple solution caching technique would have in general means that some problems can be very efficiently
obviously led to the best results. solved with the statistics-based approach, while in some cases
Since the total time of finding a solution for many prob- the statistics-based strategy can also lead the solver to wrong
lems depends on the specific set of variables used as an in- areas of the search space8 . Overall, however, the average
put set, we repeated the whole above-described procedure number of required backtracks, which we measured but do
for 5 times, each time with a different set of input vari- not report here for space reasons, could also be reduced to a
ables. Each problem therefore had to be solved successfully third using the statistics-based strategy.
(300 + 300) ∗ 5 = 3000 times, which explains why we only The other problems of our analysis shown in Figure 1 have
considered problems which could be solved efficiently. different characteristics and are in particular not configura-
tion problems but other types of general constraint problems.
2.3 Initial results Problem 2 in Figure 1, for example, is an artificially created
one and has over 500 variables and 400 constraints. Also in
As a performance indicator, we used the average CPU time this case, a significant reduction of the running times could be
needed for the solver to find a solution. We also col- observed. Problems 4 and 5 are quite similar, but in the case
lected statistics about the standard deviation of the differ- of problem 5 we used many more variables as inputs which
ent runs. Figure 1 shows the average running times for 300 led to a drastically higher number of possible inputs while at
runs using the default strategy and the running times for the the same time the solution search was more constrained. As
MostFrequent strategy at different training levels. a result, the improvements for Problem 5 were very small.
The first row shows the results of a benchmark car config- For Problem 7, no improvement was observable. Problems
uration problem from Renault, which in our view is therefore 8 and 9 are classical magic square problems with a highly
the most relevant of all measurements. The problem has 111 symmetric problem structure that does not correspond to the
variables and an average domain size of around 5. As inputs, typical characteristics of configuration problems. In particu-
we used 6 variables, which leads to a range of 56 = 15, 625 lar for case 9, in which the inputs were chosen from an equal
input combinations. The number of possible configurations
is actually lower as not all input combinations correspond to 8
In all experiments we limited the allowed computation time to
feasible product variants. In this case, about one third (about avoid effects of extreme outliers. In the Renault example, the time
5,000) of the randomly generated input combinations were limit was set to 1,000ms. Situations in which the time frame was not
feasible. sufficient were however very rare.
Michel Aldanondo and Andreas Falkner, Editors
Proceedings of the 15th International Configuration Workshop
August 29-30, 2013, Vienna, Austria
12 Dietmar Jannach
distribution, nearly no improvement was achieved with the learn such heuristics automatically from previous solution
statistics-based strategy, because every variable value has an searches. In this paper, we have reported results of an initial
nearly equal probability to appear in a random solution. For analysis of the general feasibility of such an approach based
case 8, a slight improvement could be observed because the on a simulation with small examples and a simple statistics-
inputs values were chosen using a Gaussian distribution. based branching strategy. Our first results indicate that mea-
surable efficiency improvements can be achieved, when the
3 Previous and future works special characteristics of configuration problems are taken
into account.
To the best of our knowledge, limited research has been done
so far on the automatic derivation of search heuristics in References
the area of product configuration. There are, however, ap-
proaches in the area of general CSPs that include a learn- [1] J. Amilhastre, H. Fargier, and P. Marquis. Consistency
ing component in the search process. In the context of our restoration and explanations in dynamic CSPs appli-
work, we are particularly interested in approaches which aim cation to configuration. Artificial Intelligence, 135(1-
to learn from previous solution searches or similar problem 2):199–234, 2002.
instances (in contrast to works which try to adapt the search [2] M. Balduccini. Learning and using domain-specific
strategy within a single search, often referred to as “online heuristics in ASP solvers. AI Commun., 24(2):147–164,
learning”, or based on multiple restarts). 2011.
In [3], for example, the authors propose an “advice gen- [3] R. Dechter and J. Pearl. Network-based heuristics for
eration” framework for value ordering in CSPs which is constraint-satisfaction problems. Artif. Intell., 34(1):1–
based on estimating the likelihood of the existence of at least 38, 1987.
one solution in the area of the search graph to be explored.
[4] G. Fleischanderl, G. Friedrich, A. Haselböck,
Such estimates can be obtained by analyzing a simplified and
backtrack-free version of the problem, where the hope is that H. Schreiner, and M. Stumptner. Configuring Large
the number of solutions in the simplified version with less Systems Using Generative Constraint Satisfaction.
constraints correlates with the solution count for the original IEEE Intelligent Systems, 13(4):59–68, 1998.
problem. Overall, while the general goal of their work is sim- [5] A. Haselböck. Exploiting interchangeabilities in
ilar to ours, the approach in [3] is not based on past solutions constraint-satisfaction problems. In IJCAI’03, pages
but from an analysis of adapted problem instances, which can 282–289, Chambery, France, 1993.
also induce significant additional computational costs. In our [6] H. Ingimundardottir and T. P. Runarsson. Super-
work, we assume that the solver can learn by collecting infor- vised learning linear priority dispatch rules for job-shop
mation from previous search runs for different users. scheduling. In Proc. LION 2011, pages 263–277, Rome,
In the area of Answer Set Programming, Balduccini in [2] Italy, 2011.
presents an approach for learning branching heuristics from [7] D. Jannach and M. Zanker. Modeling and solving
past solution instances. Similar to our work, the proposed
distributed configuration problems: A CSP-based ap-
DORS framework aims to derive a problem-specific policy to
proach. IEEE TKDE, 25(3):603–618, 2013.
guide the solving procedure, i.e. which branch of the search
graph should be explored first. While there are differences [8] E. O’Mahony, E. Hebrard, A. Holland, C. Nugent, and
related to the actual search procedures, the general idea of [2] B. O’Sullivan. Using case-based reasoning in an algo-
corresponds to the work presented in this paper. Our future rithm portfolio for constraint solving. In Proc. AICS
work includes an analysis of how the more advanced but still 2008, 2008.
not very complex approach from [2] can be integrated in the [9] P. Refalo. Impact-based search strategies for constraint
CSP solving process. programming. In Proc. CP 2004, pages 557–571,
Finally, the idea of deriving heuristics from past observa- Toronto, Canada, 2004.
tions in an automated way can be also found in other applica- [10] T. Russell, A. M. Malik, M. Chase, and P. van
tion areas. In [10], for example, supervised machine learning Beek. Learning heuristics for the superblock instruc-
techniques are used to at least partially automate the construc- tion scheduling problem. IEEE Trans. on Knowl. and
tion of heuristics for the NP-complete problem of instruction Data Eng., 21(10):1489–1502, 2009.
scheduling on modern processors. While the specific relation
[11] T. Soininen, E. Gelle, and I. Niemelä. A fixpoint def-
to our work is limited, our future work includes the explo-
ration of techniques such as decision tree learning or classifi- inition of dynamic constraint satisfaction. In Proc.
cation, see e.g., [6], for the generation of branching heuristics CP’99, volume 1713, pages 419–433, Alexandria, Vir-
for configuration problems. ginia, USA, 1999.
[12] E. Teppan, G. Friedrich, and A. A. Falkner. Quick-
4 Summary Pup: A heuristic backtracking algorithm for the partner
units configuration problem. In Proc. AAAI/IAAI 2012,
Problem-specific search heuristics are a key element for the Toronto, Canada, 2012.
practical success of many configurator applications. Since
[13] E. Tsang. Foundations of Constraint Satisfaction. Aca-
the manual definition of such heuristics is time-consuming,
our research goal is to develop techniques that help us to demic Press, 1993.
Michel Aldanondo and Andreas Falkner, Editors
Proceedings of the 15th International Configuration Workshop
August 29-30, 2013, Vienna, Austria