aiqbench analysis
This research addresses a critical optimization challenge in AI planning by refining Integer Linear Programming formulations to efficiently extract high-utility subplans under strict budget constraints. By preserving original action order while maximizing goal utility, the proposed methods offer practical solutions for resource-limited autonomous systems where precomputed plans must adapt dynamically to new financial realities. The work advances algorithmic efficiency and model compactness in classical planning domains that rely heavily on automated decision-making frameworks.
Finding Optimal Cost-Bounded Plan Reductions: Refined Model
arXiv:2607.25484v1 Announce Type: new Abstract: In some real applications a plan may later become unfeasible due to newly imposed budget constraints, yet, at the same time, using only the original actions of the plan and their order is mandatory. In this paper, we study the problem of extracting, from a precomputed plan, a valid subplan that maximizes utility while respecting a cost bound. Each goal is given 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 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\'ia-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.
Abstract:In some real applications a plan may later become unfeasible due to newly imposed budget constraints, yet, at the same time, using only the original actions of the plan and their order is mandatory. In this paper, we study the problem of extracting, from a precomputed plan, a valid subplan that maximizes utility while respecting a cost bound. Each goal is given 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 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.
Extended version of a paper accepted at ICAPS 2026 (doi: https://doi.org/10.1609/icaps.v36i1.42849). Includes a new model and expanded experimental results
Artificial Intelligence (cs.AI)
arXiv:2607.25484 [cs.AI]
(or arXiv:2607.25484v1 [cs.AI] for this version)
https://doi.org/10.48550/arXiv.2607.25484 arXiv-issued DOI via DataCite (pending registration)
Full text under the publisher's open licence · 191 words
Related coverage
[AINews] Reality Checks on AI News (Yegge shuts down Gas Town, Databricks’ +60% Astra cost)
Latent Space · Sep 17, 2026
Performance Profiling on AMD GPUs – Part 5: Profiling-Driven Kernel Optimization with an AI Code-Assist Tool
AMD · Jul 16, 2026
Lattice-Based Cryptography Explained
Quantum Zeitgeist · Aug 15, 2026
Dreams of alignment in a world without politics
LessWrong · Sep 24, 2026