MAESTRO: An Efficient Hierarchical Reinforcement Learning for Branch-and-Cut Orchestration

Branch-and-cut solvers achieve strong performance on integer programming but face an inherent trade-off between search progress and the memory consumed as the LP relaxation is repeatedly tightened, branched, and re-solved. We introduce MAESTRO, a hierarchical reinforcement learning framework that learns to orchestrate solver behavior by deciding when to branch, when to add cuts, and when to invoke cut pruning, within a unified Manager–Worker architecture. The Manager makes high-level strategic decisions from a global graph embedding, while the Worker performs context-aware cut selection using shared embeddings from a bipartite graph neural network. We train this hierarchy in three phases (Worker pre-training, Manager training with frozen Worker, joint fine-tuning) using Proximal Policy Optimization with a difficulty curriculum. Rather than optimizing for time or memory in isolation, MAESTRO explicitly models and jointly optimizes their interaction. Across a diverse suite of benchmark instances, we show that MAESTRO achieves 100% solve rates on easy and medium Set Cover instances while using only 53–106 MB of memory compared to SCIP's 2–3 GB, representing a 29–40$\times$ reduction. On medium instances, MAESTRO solves 16% faster than SCIP (60.5s vs. 72.4s), while on hard instances it achieves a 60% solve rate, whereas SCIP solves none within comparable time budgets. When measured by Resource Cost – the product of time and memory that captures the total computational footprint – MAESTRO achieves 39–40$\times$ better efficiency than SCIP across difficulty levels. These results enable practical deployment in memory- and latency-constrained settings such as edge devices, embedded systems, and dense multi-tenant environments where traditional solvers' multi-gigabyte footprints are prohibitive.