  We investigate upper bounds on the length of cost optimal plans that are
valid for problems with 0-cost actions. We employ these upper bounds as
horizons for a SAT-based encoding of planning with costs. Given an initial
upper bound on the cost of the optimal plan, we experimentally show that this
SAT-based approach is able to compute plans with better costs, and in many
cases it can match the optimal cost. Also, in multiple instances, the approach
is successful in proving that a certain cost is the optimal plan cost.
