A Practical, Integer-Linear Programming Model for the Delete-Relaxation in Cost-Optimal Planning
Tatsuya Imai, Alex S. Fukunaga · Frontiers in artificial intelligence and applications · 2014
We propose a new integer-linear programming model for the delete relaxation in cost-optimal planning. While a naive formulation of the delete relaxation as IP is impractical, our model incorporates landmarks and relevance-based constraints, resulting in an IP that can be used to directly solve the delete relaxation. We show that our IP model outperforms the previous state-of-the-art solver for delete-free problems.We then use LP relaxation of the IP as a heuristics for a forward search planner, and show that our LP-based solver is competitive with the state-of-the-art for cost-optimal planning.