Merged.

You are right, I changed the default in Lab (don't remember why, though). I
reverted that and you can now reload the report with the correct summed
aggregation:
https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue849-v1-issue849-base-issue849-v1-compare.html

Experimental results look good. However, I wonder why things like
"score_total_time" show the arithmetic mean rather than the sum. I think I'm
used to seeing the sum in other experiments. Is that because you use a different
experiment script compared to, e.g., Jendrik and Florian?

The issue with the arithmetic mean is that we only get two significant digits,
which is not a whole lot. With the sum we get something like five significant
digits because we have three digits in front of the decimal point.

Not a reason to rerun things, of course. Apart from the comments I left on the
commits, I think this is ready to merge.

I've looked at the individual commits and left a few small polishing comments.
Apologies if any of the things I'm asking should be obvious from previous
discussion; it's hard to see previous comments on the pull request when looking
at individual commits.

None of the commits since the experiments warrant rerunning the experiments, but
I haven't had a look at the experiments in the first place. :-) (When I did the
code review, the tracker was down.) So let me have a a quick look...

Issue tracker is back online :-) For the sake of completeness: Malte left some
comments at bitbucket, I addressed them. Do you want to go through the small
commits or should I merge? Or even re-run experiments?

This is how I implemented it so far, but still keeping everything related to
Options in the algorithm class to allow easier use of that class. Of course, if
we argue that only the M&S heuristic is and can use it, then we could leave
everything related to options there.

I haven't looked at the code yet, so without the benefit that the code gives: my
first intuition is that I would not expose MergeAndShrinkAlgorithm as a
command-line plug-in until it can be used in more than one context.

Thanks, I addressed the minor ones.

Regarding your comment "MergeAndShrinkAlgorithm should be constructed by
passing in the options explicitly rather than an OptionParser object", I think
that this is linked to the design discussion below.

If you suggest to go down the route to not treat the algorithm "plugin-like",
then we also shouldn't have functions for it to add options to parser (why
would a class provide such functions but then not accept an Options object for
its construction?), to dump options, to verify options etc. Then all this
should remain in the heuristic.

Another alternative of course is to turn the algorithm into a plugin as well,
possibly adding a short-hand alias like
"merge_and_shrink(...)=mas_heuristic(mas_algorithm(...))" to avoid additional
nesting. Malte and I weren't really sure at which point it would be justified
to make the algorithm pluggable; right-away or only later when we might have
other users than the M&S heuristic.

I left a few comments on Bitbucket.

(I ran some experiments to confirm that nothing went wrong:
https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue849-v1-issue849-base-issue849-v1-compare.html)

I will also try to find time for this ASAP. But as I'm travelling today and
tomorrow and Tuesday will be my first day meeting everyone in Toronto, this
likely won't happen before Wednesday Toronto time, i.e., very late on Wednesday
or early on Thursday in Europe.

Since this issue will cause many merge conflicts with my other repositories, I'd
like to get it merged very soon. As it further doesn't change any of the
existing functionality, maybe a heavy-weight review is not necessary besides
discussing the design questions that I raised below, thus answering where which
code should end up.

@Jendrik: could you maybe read through the discussion and also have a look at
the code? To actually get a diff and not just a new file, it could be helpful to
compare the old merge_and_shrink_heuristic.* against the new
merge_and_shrink_algorithm.*. I attached these four files.

> Do you think you can review this soon, or should I add it to the queue?

Hard to tell. One option is to just add it to the queue, which doesn't
immediately imply that it will take a long time to review. ;-) Or wait a day or
two, and if nothing happens, add it to the queue then.

I prepared a pull-request at
https://bitbucket.org/SilvanS/fd-dev/pull-requests/41/issue849/diff

There are certainly several possible ways of splitting the responsibilities
between heuristic and algorithm, and I for now decided to move almost everything
into the algorithm. That means that the only thing the heuristic has to do is to
use the algorithm to compute an FTS and to then determine which factor to use
(there are several if one is unsolvable, and it uses an unsolvable in this case;
otherwise, there is exactly one). 

This also means that while all options related to M&S are of course still being
added by the heuristic (which is the object created from the command line), the
options are added (via public static methods), extracted, and dumped only in the
algorithm. This allows creating the algorithm with a single options object. This
could certainly be changed towards a constructor accepting a list of individual
options, and I wouldn't mind changing this if you found this the better design.

Another design question is whether the algorithm should store all the things it
needs when being constructed and be called only with the task object to compute
the FTS, or whether it should be a one-shot factory that should not store
anything (we could use an external function in that case and internally use a
class to avoid passing around many arguments). My current solution uses the
former design. (Also note that the algorithm could not be directly reused to
compute another FTS for another task, at least not without modifying it to keep
the merge strategy factory around and to reset various other things such as
label reduction.)

Do you think you can review this soon, or should I add it to the queue?

This is part of meta issue567. In order to more easily integrate a time limit
(issue802), we think it will be very useful to separate the computation of the
merge-and-shrink algorithm from its user, the heuristic.