With the rise of Financial Operations (FinOps), cloud resource management requires the enforcement of strict budgetary guardrails rather than soft cost objectives. However, discrete Virtual Machine (VM) types often cause structural infeasibility, which existing methods fail to address. We formulate the Budget-Constrained VM Resizing problem under temporal hard constraints and establish the NP-hardness of the scalarized problem as a completeness result. To solve this, we propose the Budget-aware Dual (BD) solver, which utilizes a dual variable as a shadow price to dynamically steer candidate decisions toward budget feasibility without opaque penalty tuning. Extensive experiments demonstrate that BD significantly improves budget feasibility and operational stability compared to the baselines. In the run-rate setting, BD reduces candidate budget violations to zero once the budget enters feasible regimes at and substantially reduces operational churn, decreasing the change rate from 53.95% to 7.80% in an oscillatory workload scenario. BD also exhibits near-linear scalability and remains more than 100× faster than NSGA-II at large fleet sizes. This framework provides a theoretically grounded and scalable approach for balancing economic efficiency, operational stability, and strict budget compliance.
Choong-Hee Cho (Sun,) studied this question.