-
Notifications
You must be signed in to change notification settings - Fork 13
/
configuration.tex
193 lines (162 loc) · 8.58 KB
/
configuration.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
\section{Solver Configuration}
\label{sec:configuration}
\clasp\ has more than $80$ performance relevant parameters, some of which are shown in Section~\ref{subsec:opt:clasp}.
Even if only a discrete subset of all possible parameter settings is considered,
this amounts to approximately $10^{59}$ configurations.
In such a huge configuration space,
it is a tedious and time-consuming task
to manually determine a well-performing configuration.
Two complementary ways to automatically address this issue for \clasp\ are
the automatic configuration selection solver \claspfolio~\cite{holisc14a} and
the automatic configuration tool \piclasp.%
\marginlabel{Both tools are written in \python~2.7 and require some external packages -- please see README.}
The following description conforms with \claspfolio~2.2 and \piclasp~1.2, respectively.
\subsection{Portfolio-Solving with \claspfolio}
\label{sec:claspfolio}
The targeted use-case of \claspfolio\ is to solve a set of heterogeneous problem instances.
In such a case,
there is no single well-performing configuration for all instances
but a well-performing configuration has to be selected for each individual instance.
Therefore, \claspfolio\ should be used either
in scenarios involving instances with different characteristics,
e.g., due to different encodings, different sizes or changing constraints,
or
simply to get a first impression of a well-performing configuration on a (homogeneous) benchmark set.
The basic idea of \claspfolio\ consists of using numerical characteristics of instances
to select a well-performing configuration from a given set of pre-selected configurations
by using machine learning techniques
in order to solve a given (ground) logic program at hand.
These so-called instance features are computed by \claspre. % footnote{\url{http://www.cs.uni-potsdam.de/claspre/}}
For illustration,
consider to use \claspfolio\ to solve an instance of the ricochet robots problem~\cite{gejokaobsascsc13a},
i.e., \code{examples/ricochet\_robots.lp.gz}.
To invoke \claspfolio, we have simply to pass the instance via stdin
and tell \claspfolio\ to read from sdtin (\sysfont{-I -}).
\begin{lstlisting}[numbers=none]
$ zcat examples/ricochet_robots.lp.gz | \
python ./src/claspfolio.py -I -
[...]
Time : 3.288s
\end{lstlisting}
Comparing the performance of \clasp's default configuration
and the configuration selected by \claspfolio\ shows a $9.1$-fold speedup.
\begin{lstlisting}[numbers=none]
$ zcat examples/ricochet_robots.lp.gz | clasp
[...]
Time : 30.080s
\end{lstlisting}
Another way to use \claspfolio\ is to select a configuration for a given set of instances.
In such a setting, \claspfolio\ scores each configuration on each instance
and averages over the scores of each configuration.
Such a robust and well-performing configuration of \clasp\ can than be used without further use of \claspfolio\
which saves some overhead produced by \claspfolio\ (e.g., computing the instance features).
\begin{lstlisting}[numbers=none]
$ python ./src/claspfolio.py --oracle_dir <INSTANCE_DIR>
% [...]
% >>> Algorithm Scores <<<
%
% 1-th ranked solver: <CONFIGURATION NAME>
% Call: <CMD CALL>
% Score: <SCORE>
% ...
\end{lstlisting}
%
\claspfolio\ lists all configuration sorted by its performance score --- starting with predicted best-performing configuration.
Please note that \claspfolio\ minimizes \texttt{<SCORE>}.
\begin{note}
\claspfolio\ is trained for a runtime cutoff of $600$ seconds.
It will most likely perform well for smaller runtime cutoffs
but performance could get worse with larger runtime cutoffs.
\end{note}
\begin{note}
\claspfolio\ is trained only on decision problems.
Therefore, \claspfolio\ does not cover enumeration and optimization related parameters in its selected configurations.
\end{note}
\claspfolio\ provides also an interface to retrain machine learning models on other problem instances
(e.g., to get an \claspfolio\ for enumeration applications).
To this end, \claspfolio\ supports the Algorithm Selection Library format.\footnote{\url{www.aslib.net}}
To determine a well-performing training configuration of \claspfolio,
we recommend the use of \sysfont{autofolio}~\cite{lihohusc15a}.%\footnote{\url{http://www.cs.uni-potsdam.de/wv/autofolio}}
\subsection{Problem-oriented Configuration of \clasp\ with \piclasp}
\label{sec:piclasp}
\piclasp\ allows for identifying a single well-performing parameter configuration
in the complete parameter configuration space of \clasp.
To this end, \piclasp\ optimizes \clasp's configuration with the automatic algorithm configuration framework \smac~\cite{huhole11b}.
In the process of determining a configuration,
\piclasp\ has to assess the performance of different \clasp\ configurations on different instances.
Therefore, \piclasp\ needs a lot more computational resources than \claspfolio\
but has the advantage of adapting \clasp\ even better to a given application.
\piclasp\ has two required parameters:
%
\begin{description}
\item[\code{--instances,-I}] a directory containing a set of grounded instances on which the performance of \clasp\ will be optimized.
\item[\code{--cutoff,-c}] defines the runtime cutoff of each run of \clasp.
We recommend that \clasp's default configuration solves at least $50\%$ of the given instances with this cutoff.
The runtime of \piclasp\ (i.e., the configuration budget) will be approx. $200$ times this runtime cutoff
to determine a well-performing configuration of \clasp.
\end{description}
To install all required packages of \piclasp, please run `\code{bash install.sh}'.
This locally installs \clasp, \smac, \sysfont{runsolver} and \claspre.
For illustration, consider to use \piclasp\ to determine a well-performing configuration again for the ricochet robots problem,
you have to provide a directory with the grounded instances, e.g., a directory with \code{examples/ricochet\_robots.lp.gz}
Running \piclasp\ with a budget of $3300$ seconds (\code{-b 3300})
and a runtime cutoff of $33$ seconds per \clasp\ run
on this one instance yields the following result.
\begin{lstlisting}[numbers=none]
$ python piclasp.py -b 3300 -c 33 -I <INSTANCE_DIR>
Found 1 instances
[...]
Result of piclasp:
Performance: 0.094000
--backprop --eq=0 --no-gamma --trans-ext=all
--sat-prepro=0 --init-watches=2
--heuristic=Domain --score-other=1
--sign-def=0 --rand-freq=0.05
--strengthen=local,1 --lookahead=no
--otfs=2 --reverse-arcs=3 --dom-mod=5,0
--save-progress=129 --restarts=no
--partial-check=50 --score-res=1
--update-lbd=0 --deletion=no
--loops=common --del-grow=0
--init-moms --contraction=no
\end{lstlisting}
Comparing the performance of \clasp's default configuration
and the configuration determined by \piclasp\ shows a $295$-fold speedup.
\begin{lstlisting}[numbers=none]
$ zcat examples/ricochet_robots.lp.gz | clasp
[...]
Time : 30.080s
$ zcat examples/ricochet_robots.lp.gz | \
clasp <PICLASP CONFIGURATION>
[...]
Time : 0.102s
\end{lstlisting}
Interestingly, the configuration determined by \piclasp\ changes nearly all parameters of \clasp.
However, we do not know which of these changes (resp. which combination)
is necessary for the performance improvement.
\begin{note}
To improve the performance of \piclasp,
we recommend to run \piclasp\ with at least $10$ independent \smac\ runs (option \code{--repetition,-R}).
More \smac\ runs or a larger configuration budget (option \code{--budget,-B}) should always lead to better results.
\end{note}
\begin{note}
Algorithm configuration and hence also \piclasp\ works especially well on homogeneous instance sets (e.g.,~\cite{gejokaobsascsc13a}),
that is, there is one configuration that performs well on all given instances.
On heterogeneous instance sets, \piclasp\ will most likely need a lot more \smac\ runs and a larger configuration budget,
and it will still find only configurations with small performance improvements,
since \clasp's default configuration is already optimized to have a robust performance on a large variety of instances.
\end{note}
\begin{note}
Using \piclasp, the performance of \clasp\ on the given instance set will improve.
However ultimately, the performance of \clasp\ should improve on new (unseen) instances.
Therefore, we strongly recommend to use another (disjoint) set of instances to assess the performance of the obtained \clasp\ configuration.
\end{note}
\begin{note}
We recommend that \piclasp\ optimizes the performance of \clasp\ on at least $100$ instances
(in contrast to our mini example above).
On smaller instance sets, the determined configuration may not perform well on yet unseen instances.
\end{note}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: "guide"
%%% End: