Finding Optimal Cost-Bounded Plan Reductions: Refined Model

This paper studies how to reduce a precomputed plan when a newly imposed budget makes the original plan infeasible, while requiring the retained actions and their order to remain unchanged. The objective is to remove actions supporting lower-utility goals and obtain an executable subplan with maximum utility under a cost bound. The authors show that the decision version is NP-complete and present two exact approaches: oversubscription planning (OSP) and integer linear programming (ILP). The main refinement is a smaller ILP formulation intended to improve computational efficiency, extending work published at ICAPS 2026.