Dantzig-Wolfe Decomposition for Cost Partitioning

Pommerening, Florian and Keller, Thomas and Halasi, Valentina and Seipp, Jendrik and Sievers, Silvan and Helmert, Malte. (2021) Dantzig-Wolfe Decomposition for Cost Partitioning. In: Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS 2021), 31. pp. 271-280.

[img] PDF - Accepted Version

Official URL: https://edoc.unibas.ch/84307/

Downloads: Statistics Overview


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.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Pommerening, Florian and Keller, Thomas and Seipp, Jendrik and Sievers, Silvan and Helmert, Malte
Item Type:Conference or Workshop Item, refereed
Conference or workshop item Subtype:Conference Paper
Publisher:AAAI Press
Note:Publication type according to Uni Basel Research Database: Conference paper
edoc DOI:
Last Modified:27 Aug 2021 10:30
Deposited On:25 Aug 2021 15:27

Repository Staff Only: item control page