Those are clearly positive results. :-)

For the sake of completeness: here are the results of this patch (also including
the changes for issue367). All in all 17 additional tasks were solved. The time
for dominance pruning is negligible with a sum of around 1.5 seconds for all of
the 999 instances where the hill-climbing finished.

I had a look at the code and added some comments, but they are all quite
negligible. I just can't help myself to comment on even the tiniest thing that
comes to mind...


On an unrelated note, I also have another idea which might be worth remembering
if we ever write this down in a paper, but is probably not worth implementing
given that we're not worried about time anyway:

Let's assume we have patterns A, B and A \cup B, where A and B are disjoint and
additive. Then we should *omit* the edge between A and B in the additivity
graph: it's never a good idea to put them into a clique together since this
clique will always be dominated by another clique which has A \cup B in place of
A and B. (Note that everything additive with A and B will also be additive with
A \cup B.) Since we have so many cliques with singleton patterns, I would expect
that this could eliminate many dominated cliques before they are ever generated.

As I wrote, probably not worth implementing given that we don't need to worry
about speed.

Could one of you please have a look at the patch:
http://codereview.appspot.com/6590058/

After the review I can run the tests on the grid. The tests I ran so far on my
computer all look quite good with under 1 second for dominance pruning (even in
tasks with over 2000 cliques).

I experimented with different versions here:
https://bitbucket.org/flogo/fast-downward/changesets/tip/branch%28%22issue350%22%29
The first approach was based on indices and probably a bit faster than this one.
However, it was quite complicated and long code to handle the changing indices.
This version looks nicer and I guess it will not matter from the performance
point of view. We could even leave out the precomputed superset relation without
a big performance hit, if you don't like the hash_set implementation (as in
revision aa2fab4aa182).

Here are the results of the analysis with python to get a rough picture of why
this might be useful. The graphs are histograms for the percentage of saved
patterns and collections (both axes show percentages). In 43% all pattern are
needed but there are cases where up to 85% of the pattern are not needed.

For the collections the situation is even more pronounced in 34% all are needed
but in some cases it is possible to remove 99% of the cliques. 17% of the test
cases fell into the 90%-100% area.

In the canonical heuristic there are cliques that are dominated by other other
cliques in the following sense: For every pattern p_c in clique c there is a
pattern P_C in clique C with p_c <= P_C. In such a case the sum over the values
of the pattern heuristics for c cannot be higher than the sum over the heuristic
values for C and we can prune c.

Experiments with python were surprisingly fast, so we probably can use a naive
implementation.