acceptodds
Withdrawn from ICLR 2027

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

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

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 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 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.

Primary area:
reinforcement learning
Keywords:
Reinforcement Learning, Integer Programming, Proximal Policy Optimization, Hierarchical Reinforcement Learning

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_jKJ9OpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This maniscript introduces MAESTRO, a hierarchical reinforcement learning framework designed to orchestrate branch-and-cut solvers by coordinating when to branch, add cuts, or prune cuts. The framework adopts a Manager–Worker architecture over shared bipartite GNN embeddings, where the Manager selects strategic meta-actions and the Worker performs context-aware cut selection. Evaluated primarily on Set Cover alongside three transfer benchmarks, MAESTRO demonstrates significant memory reductions while achieving competitive solve times and rates compared to default SCIP and an RL cut-selection baseline

Critical strengths

The maniscript addresses a relevant challenge in combinatorial optimization by jointly orchestrating branching, cut selection, and cut pruning within a unified learning framework rather than treating them in isolation. The reported memory reductions (29–40× compared to default SCIP) are practically meaningful for resource-constrained deployments.

Critical weaknesses

The empirical evaluation is limited in both baseline coverage and benchmark diversity. Beyond default SCIP, the paper compares against only a single machine learning baseline (MIRACLE) on Set Cover, overlooking well-established learning-to-branch and learning-to-cut methods in the literature. Furthermore, the evaluated datasets are narrow: the main experiments rely almost entirely on Set Cover instances, making the empirical results unconvincing.

The appendix contains numerous formatting and completeness issues, including multiple empty section headings without any explanatory text (e.g., A.3.1–A.3.3, A.5.1–A.5.3, A.10.1–A.10.2), as well as datasets mentioned without corresponding experimental results (e.g., MIPLIB in A.7.2). These omissions indicate that the submission is far from ready. Overall, this manuscript appears incomplete, and I strongly recommend that the authors thoroughly polish and finalize the paper prior to submitting it to another conference.

Questions for authors
  1. Could you provide the offline training overhead for the full three-phase curriculum and compare these offline costs against MIRACLE and other learning-based baselines?

  2. Could you report training dynamic curves to demonstrate learning stability?

  3. The proposed approach appears heavily engineering-driven with multiple heuristics and reward-tuning tricks, while lacking deeper algorithmic insights. It does not provide sufficient analysis to explain the mechanism behind the results in Table 2. Providing concrete insights may help readers understand the true effectiveness of the method.

Reviewer_JmupOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes MAESTRO, a hierarchical RL framework that orchestrates branch-and-cut: a Manager selects among meta-actions {BRANCH, SELECTCUTS, PRUNECUTS} from a mean-pooled bipartite-GNN embedding of the current LP state; when SELECTCUTS is chosen, a Worker scores candidate cuts using local cut features (efficacy, parallelism, density, age, activity) fused with Manager-provided GNN context, selecting up to 30 cuts; BRANCH scores the top-10 fractional variables; PRUNECUTS triggers a heuristic pruning routine. The reward combines gap progress, time and memory deltas, and a solve bonus; training uses PPO in three phases (Worker pretraining, Manager training with frozen Worker, joint fine-tuning) with a difficulty curriculum. Experiments are on synthetic Set Cover tiers (Easy/Medium/Hard, 30 instances each, a single fixed seed) against SCIP-default, MIRACLE, and ablations (No Context, Always Branch, Always Cuts, No Prune). Headline results: 100% solve rate on Easy/Medium with 53–73 MB of memory vs. SCIP's 1,975–2,449 MB (a claimed 29–40× memory reduction), 16% faster on Medium (60.5 s vs. 72.4 s), 60% vs. 0% solve rate on Hard, and a proposed "Resource Cost" (time × memory) metric improved 39–40×; on three unseen problem types (Facility Location, Combinatorial Auction, MIS), only memory usage is reported (44–319 MB, 7–41× below SCIP). Ablations show each component contributes on Hard (Full 60% vs. Always Branch 20%, Always Cuts 10%, No Context 40%).

Critical strengths
  1. A sensible and under-explored orchestration formulation, with informative ablations. Casting solver control as a Manager over action types (branch/cut/prune) with a specialized Worker for cut selection, sharing GNN embeddings between the two levels, is a reasonable decomposition, and the ablations cleanly demonstrate that dynamic orchestration outperforms fixed policies on Hard instances (60% vs. 20%/10%) and that context sharing helps (60% vs. 40%). The finding that coordination value grows with difficulty is a useful data point for the field.

  2. A resource-aware motivation that the field largely ignores. Explicitly modeling memory (in the reward and via the Resource Cost metric) responds to real deployment concerns (edge/embedded/multi-tenant solving) and is a welcome change from pure node-count or time accounting — if the measurements hold (see weaknesses).

Critical weaknesses
  1. The central efficiency claims appear to rest on invalid measurement. Comparing (apparently GPU/model-only, per Fig. 4's "GPU Memory" axis) memory for a policy that itself drives a SCIP backend via PySCIPOpt against SCIP's full-process memory is not like-for-like: the backend's tree/LP memory and the Python/PyTorch/CUDA runtime are necessarily part of MAESTRO's footprint, and 53 MB is implausible as a total. Since the 29–40× memory reduction and the 39–40× Resource Cost advantage are the paper's headline contributions — the speed contribution alone is modest (16% on Medium) — this concern, if confirmed, invalidates the main practical claims and the edge-deployment framing (the policy itself requires an RTX 6000 Ada GPU).

  2. Narrow and incomplete evaluation. All main results are on one synthetic family (uniform Set Cover, single seed, no variance reporting); "strong generalization" to unseen problem types is claimed but evidenced only by memory numbers, with no solve rates or times; SCIP-aggressive is announced as a baseline but its numbers do not appear in the main tables; and standard learned baselines for branching (Gasse et al., 2019) or cut selection (Tang et al., 2020) are not compared. As presented, the evidence cannot support claims about practical deployment.

Questions for authors
  1. (Assessment — pivotal for my rating) Exactly how was "Memory" measured in Table 1: GPU allocator memory, model parameters only, or full-process RSS (host + device) including the SCIP backend invoked via PySCIPOpt? Since MAESTRO delegates LP re-solves and branching execution to SCIP, the backend's tree/LP memory is necessarily part of MAESTRO's footprint. My rating is conditional on this answer.
  2. (Assessment) Please report solve rates and times (not just memory) for the unseen problem types in Table 3 — does MAESTRO actually solve Facility Location / Combinatorial Auction / MIS instances, and at what gaps vs. SCIP?
  3. (Clarification) Is solve time measured end-to-end, including per-decision GNN inference, and how many decision steps occur per solve?
  4. (Clarification) Where are the promised SCIP-aggressive numbers, and how does SCIP with tuned settings perform on the Hard tier? SCIP solving 0/30 there is central to the 60%-vs-0% claim.
  5. (Clarification) What are the standard deviations over the 30 test instances and across training seeds for Tables 1–2?
Reviewer_AQwvOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes MAESTRO, a learning-enhanced framework designed to jointly make branching, cut addition, and cut removal decisions in branch-and-cut algorithms. MAESTRO comprises a high-level Manager that determines the type of decision to make, along with three low-level models: a scoring head for branching variable selection, a Worker for cut selection, and another head for cut removal. Trained using a three-phase PPO algorithm, the framework reports notable improvements in solving rates, solving times, and memory consumption on SC datasets.

Critical strengths

The motivation behind this work is clear and convincing. Branching and cut decisions are inherently coupled in branch-and-cut algorithms, yet they are predominantly treated separately in existing literature. Jointly learning these components brings potential benefits. The proposed two-level decomposition strategy is reasonable, and the overall framework architecture is appealing and well-structured. The reported results on SC datasets are encouraging.

Critical weaknesses

My major concern is that the current results and explanations cannot fully support the claims. I would be willing to raise my score if the authors provide enough evidence or clearer explanations to my points below:

  1. The comparison in memory and resource cost is misleading.

a. Figures and tables in Section 5 show the comparison of MAESTRO’s peak GPU memory with SCIP’s peak CPU memory. However, MAESTRO involves not only the model inference but also SCIP solving, and the later also requires CPU memory. Thus, the CPU memory of the full MASTRO solving should also be reported for a fair comparison.

b. The resource cost is defined as “Time * Memory”. From Table 1, I find this metric is calculated as “peak memory * averaged time over solved instances”. This formulation can overestimate resource cost if a very high memory peak occurs for only a brief moment, or underestimate it if only a few instances are solved quickly while the majority remain unsolved. A more convincing evaluation would utilize the area under the memory-time curve, incorporating the actual solving time across all instances, including unsolved ones.

  1. The comparison only includes one learning-based baseline on cut selection. Since MAESTRO also learns to decide branching variable selection and cut removal, the paper could be significantly more solid by including learning-based baselines of these two directions as well.

  2. The ablation results on the Always Branch and Always Cuts variants show that restricting the available operations can be harmful. However, they do not sufficiently demonstrate the proposed method is better than a competent yet simpler scheduler. Thus, I think the benefit of orchestration has not been fully validated yet. Moreover, No Prune and SCIP-aggressive announced in Section 5 do not appear in the other part of the paper, but I believe they worth to be compared.

  3. The transfer capability is only evaluated on memory usage. Even if my already-stated concern in Weakness 1 is resolved, I’m afraid it is not enough to establish generalization capabilities without providing metrics regarding solving quality, such as solving rates, solving time, and the primal/optimal gaps.

Questions for authors
  1. Equation 3 and Equation 13-16 seem to provide two different rewards. Which was actually implemented?
  2. Table 8 gives time limits and node limits different to those in Section 5. It also provides dimensions different to those in Section 4.1. What configurations were actually used?
  3. The memory shown in Table 3 and Figure 4 does not match with each other. Is it due to different measurement?
  4. For branching variable selection, MAESTRO selects from the 10 most fractional variables. Section 2 explains that “fractional variables are the immediate source of LP infeasibility”. While I appreciate the design of reducing action space size, I don’t completely agree with this intuition. First, LP infeasibility is directly caused by variable bound propagation or constraint confliction, and such nodes will never be branched on. I assume the authors may actually mean “LP feasibility but MIP infeasibility” here. Second, a high fractional value does not necessarily imply that a variable is the most valuable candidate for branching. Could the authors provide some empirical evidence or literature support this design choice?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.