A Practical, Integer-Linear Programming Model for the Delete-Relaxation in Cost-Optimal Planning. Imai, T. & Fukunaga, A. 2014.
abstract   bibtex   
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.
@article{imai_practical_2014,
	title = {A {Practical}, {Integer}-{Linear} {Programming} {Model} for the {Delete}-{Relaxation} in {Cost}-{Optimal} {Planning}},
	abstract = {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.},
	language = {en},
	author = {Imai, Tatsuya and Fukunaga, Alex},
	year = {2014},
}

Downloads: 0