In some real applications, a plan may become unfeasible due to newly imposed budget constraints, yet using only the original actions of the plan and their order is mandatory. This paper studies the problem of extracting a valid subplan from a precomputed plan that maximizes utility while respecting a cost bound. Each goal is assigned a utility value, and the plan is reduced by removing actions that support low-utility goals, while preserving both executability and the original action order. We show that the decision variant is NP-complete and propose two exact methods to solve it: one via oversubscription planning (OSP) and another via Integer Linear Programming (ILP). This paper extends our previous work published at ICAPS 2026 (Del Toro, Fuentetaja, and García-Olaya 2026b). While the core framework remains as introduced there, we further introduce a refined ILP formulation that significantly decreases the model size and improves computational efficiency.
Blogger's Review: This research provides profound insights into plan optimization under budget constraints, especially in handling uncertainties. The proposed ILP method effectively balances computational efficiency with solution quality, laying a solid foundation for future research.