Optimal classical planning aims to find minimal-cost action sequences in deterministic,fully observable problems. Strong domain-independent admissible heuristics are crucial for optimal A* searches, and cost partitioning is one of the most powerful techniques for generating them. However, computing optimal cost partitions is challenging because it requires solving a linear program for each encountered state. There exist two strategies to make cost partitioning more practical. First there exist non-optimal cost partitioning strategies that offer weaker guidance but are easier to compute. Second, cost partitioning heuristics are often approximated by not computing one for every encountered state.

This thesis investigates how efficiently the non-approximative, say perfect, versions of non-optimal cost partitioning strategies can be computed, which helps to understand their true practical complexity and limits. We show that the perfect variant of two common cost partitioning strategies, saturated cost partitioning (SCP) and saturated post-hoc optimization (SPhO), can be computed much more efficiently than the naive strategy.

SPhO computes cost partitions by solving a linear program for each state encountered during the search, which is prohibitively expensive in practice. We introduce cover rules based on the sensitivity analysis of linear programs that enable the reuse of cost partitions across states without sacrificing heuristic quality. This drastically reduces the number of linear program solver calls while preserving optimality. We also analyze the structure of the saturated post-hoc optimization linear program, including degeneracy and non-uniqueness, and propose an algorithm to maximize cost partition reusability.

SCP does not require a linear program to be solved and is cheaper to compute. However,its quality depends heavily on the ordering of component heuristics. The best SCP heuristic would maximize over all possible orders, but this is infeasible due to factorial growth. We address this issue by representing SCP collections as term graphs,which allows for the identification and elimination of trivial redundancies. By formalizing conditions for equivalent orders, we can eliminate non-trivial redundancies and reduce the graph size by several orders of magnitude. This enables the first computation of the perfect SCP heuristic and the first comparison of existing SCP approaches with their theoretical limit.