Optimal cost partitioning can produce high quality heuristic estimates
even from small abstractions. It can be computed with a linear program
(LP) but the size of this LP often makes this impractical. Recent work
used Lagrangian decomposition to speed up the computation. Here we use a
different decomposition technique called Dantzig-Wolfe decomposition to
tackle the problem. This gives new insights into optimal cost
partitioning and has several advantages over Lagrangian decomposition:
our method detects when a cost partition is optimal; it can deal with
general cost functions; and it does not consider abstractions in the
linear program that do not contribute to the heuristic value. We also
show the advantage of the method empirically and investigate several
improvements that are useful for all cost partitioning methods.
