Dantzig-Wolfe Decomposition for Cost Partitioning

Authors

  • Florian Pommerening University of Basel, Switzerland
  • Thomas Keller University of Basel, Switzerland
  • Valentina Halasi Unaffiliated
  • Jendrik Seipp University of Basel, Switzerland Linköping University, Sweden
  • Silvan Sievers University of Basel, Switzerland
  • Malte Helmert University of Basel, Switzerland

DOI:

https://doi.org/10.1609/icaps.v31i1.15971

Keywords:

Classical Planning Techniques And Analysis

Abstract

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.

Downloads

Published

2021-05-17

How to Cite

Pommerening, F., Keller, T., Halasi, V., Seipp, J., Sievers, S., & Helmert, M. (2021). Dantzig-Wolfe Decomposition for Cost Partitioning. Proceedings of the International Conference on Automated Planning and Scheduling, 31(1), 271-280. https://doi.org/10.1609/icaps.v31i1.15971