acceptodds
Under review as a conference paper at ICLR 2027

Policy-Conditioned Joint Learning For Node Selection And Variable Branching In Branch-and-Bound

Abstract

Modern solvers for mixed-integer linear programs (MILPs) rely on branch-andbound, whose efficiency depends largely on two recurring decisions, namely node selection and variable branching. While machine learning has been applied to both decisions, most existing methods learn them separately and overlook their interdependence. To address this issue, we propose a Policy-Conditioned Joint Learning (PCJL) framework, which learns node selection and variable branching as a coupled pair. PCJL encodes the variable–constraint graph of each instance once at the root and reuses this encoding at every branching decision. PCJL then couples two value networks, a branching network that ranks candidate variables in the context of the selected node and a node network that evaluates each candidate node by the cost measured under the action of this learned branching policy. Node targets are thus conditioned on the branching actions taken at deployment and measured under a common reference continuation. To adapt the depth of each descent to the state of the search, PCJL further overrides the fixed plunging rule whenever a gradient-boosted regressor predicts a cheaper depth. Experiments on four NP-hard benchmark families show that PCJL is the fastest of the compared methods on every family and reduces the solving time of SCIP by 15% to 63% on three of them. Moreover, its advantage carries over to larger instances on two families, where the reduction remains 28% to 42%.

Primary area:
optimization
Keywords:
machine learning for combinatorial optimization, mixed-integer linear programming, branch-and-bound, node selection, variable branching, graph neural networks

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_5HXTOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies coordination between node selection and variable branching in MILP branch-and-bound. Node targets obtained under a reference brancher may become misaligned when a learned brancher is deployed. PCJL uses staged cost-supervised learning: it fits and freezes a branching policy using matched replays under a fixed reference continuation, generates node targets under that policy's actions, and then learns descent lengths under the frozen node–branching pair. Cached root graph representations and lightweight predictors reduce inference overhead. Experiments on four synthetic families report runtime, LP work, optimality rates, component ablations, and larger-instance transfer, with gains on several main-test families and mixed transfer outcomes.

Critical strengths
  • Identifies a meaningful target-mismatch problem between node selection and the deployed brancher, with a practical correction.
  • Multiple solver-level metrics and relevant baselines are evaluated, with substantial target-ablation gains on some tasks.
Critical weaknesses
  • The methodological increment is relatively narrow: the main contribution is to regenerate node targets under a frozen branching policy, building on established continuation-cost learning and staged fitting. While the target ablation demonstrates practical value, the algorithmic novelty remains modest.
  • The CPU-efficient hybrid approach of Gupta et al. (2020), which motivates the root-caching design, is not directly evaluated, leaving the additional benefit over existing lightweight alternatives unclear.

I am open to raising my rating if the rebuttal clarifies the methodological contribution and the additional practical benefit over existing lightweight branching approaches.

Questions for authors
  • Table 2 shows substantial gains from conditioned targets on FCMCNF and MaxSAT but smaller gains on GISP and CA. Can you explain this variation?
  • Under matched reference node-selection/plunging settings, what additional gains do PCJL-B and full PCJL achieve over the hybrid-style branching approach of Gupta et al.?
  • Why is training limited to a single branching–node-selection pass rather than alternating updates? After learning the node-selection policy, could updating the brancher under that policy and then regenerating node targets yield further improvements?
Reviewer_y4YGOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes Policy-Conditioned Joint Learning (PCJL) for node selection and variable branching in MILP branch-and-bound. The method first learns and freezes a branching policy, then constructs node-selection targets using the actions of that policy under a fixed reference continuation. It also incorporates cached root-level graph representations and a learned plunging-depth controller. Experiments on four synthetic problem families demonstrate practical runtime improvements over SCIP and the evaluated learning-based baselines, with mixed generalization to larger instances.

Critical strengths

The central motivation is convincing: the cost of selecting a node depends on the branching action subsequently taken there, so aligning node targets with the deployed branching policy is a sensible design. The target ablation provides useful evidence for this idea beyond simply sharing representations between two models. The attention to inference overhead is also valuable, since reductions in LP work translate into actual runtime improvements on three benchmark families. Overall, I consider this a well-motivated and practically useful contribution.

Critical weaknesses
  1. A mismatch between training and deployment remains. Node targets incorporate the learned branching action only at the selected node, after which replay returns to the reference policy. Actual deployment repeatedly applies the learned policies. The single-decision bounds in Appendix A do not address this discrepancy or the resulting changes in the visited-state distribution.

  2. The sources of the overall speedup could be separated more clearly. The cumulative and target ablations are helpful, but comparisons with prior methods also involve differences in graph-encoding cost, additional replay supervision, and a reference plunging implementation that differs from native SCIP on the maximization families. Matched implementations and reporting of total replay and training costs would strengthen the practical comparison.

  3. Robustness and generalization are not yet fully established. Evaluation covers four synthetic families and one selected model per family. The improvement on GISP is not statistically significant. On larger instances, PCJL is slower on CA and proves optimality less frequently on FCMCNF despite its lower capped runtime. These results limit the breadth of the performance claims.

  4. An important prediction used for intervention lacks direct supervision. Appendix B.2 excludes the reference candidate from the branching regression loss, although its predicted cost enters both the intervention threshold and the consistency term. The accuracy and calibration of this prediction therefore deserve further examination.

Questions for authors
  1. How sensitive is performance to the reference continuation used for generating node targets? Would collecting additional targets along trajectories of the learned policies improve robustness?

  2. Could you report the total cost of replay generation and training, together with a comparison using matched graph caching and node-selection implementations?

  3. Can you provide results across multiple training seeds and further analyze the lower optimality-certification rate on larger FCMCNF instances and the degradation on larger CA instances?

  4. Why is the reference candidate excluded from the branching loss? Would directly supervising its cost improve prediction calibration or the reliability of the intervention rule?

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

This paper proposes Policy-Conditioned Joint Learning (PCJL), a framework that coordinates node selection, variable branching, and descent depth in branch-and-bound for mixed-integer linear programming (MILP). PCJL measures the downstream LP work of individual decisions through search replay. It first trains and freezes a branching network, then constructs policy-conditioned targets for node selection under the frozen branching policy, and finally trains a depth regressor. The framework also caches root-level graph embeddings to reduce inference overhead. Experiments on four MILP benchmark families show that PCJL achieves the shortest solving time among the compared methods on the main test sets, with performance gains persisting on larger instances in two families.

Critical strengths

S1. Policy-conditioned learning for node selection.

The paper explicitly accounts for the dependence between node selection and variable branching by constructing node targets under the frozen learned branching policy. Compared with reference-policy targets, this design improves solving performance across multiple benchmark families.

S2. Strong solving efficiency and meaningful component validation.

PCJL reduces inference overhead through cached root-level graph embeddings and lightweight prediction networks, achieving the shortest solving time among the compared methods on all four main benchmark families. The cumulative ablations, policy-conditioned target comparisons, and adaptive descent-depth experiments provide meaningful empirical support for the proposed framework.

Critical weaknesses

W1. Insufficient ablation of the coupling mechanisms.

The paper further couples node selection and variable branching through a shared node encoder and a consistency loss, but does not provide separate ablations for these components. Although the effectiveness of policy-conditioned targets is demonstrated, it remains unclear whether the shared representation and consistency regularization provide additional benefits.

W2. Limited diversity of evaluation benchmarks.

PCJL demonstrates strong solving performance on four classical MILP benchmark families and maintains substantial improvements on larger instances in two of them. However, all evaluation instances are generated using the corresponding benchmark generators, without evaluation on more diverse real-world MILP instances, such as those from the ML4CO Competition or D-MIPLIB. Its applicability across broader MILP problem distributions therefore remains insufficiently explored.

W3. Insufficient analysis of replay data collection costs.

PCJL relies on search replay to generate decision-cost supervision, but the paper reports only the replay data volumes and per-run limits, without quantifying the actual data collection time or total offline training cost. Consequently, it is difficult to assess the additional computational expense of this supervision compared with conventional expert imitation learning, or whether the resulting solving-time improvements justify that expense.

Questions for authors

Q1. Ablation of the coupling mechanisms

Could the authors provide ablations without the shared node encoder and the consistency loss to clarify their individual contributions to joint node selection and variable branching?

Q2. Evaluation on more diverse MILP benchmarks

Could the authors consider evaluating PCJL on more diverse, application-oriented benchmarks, such as the ML4CO Competition or D-MIPLIB, to further assess its applicability and robustness across different MILP problem distributions?

Q3. Computational cost of replay data collection

Could the authors report the actual replay data collection time at each training stage and the total offline training time of PCJL? A comparison with the cost of collecting conventional strong-branching supervision would help clarify the trade-off between additional training cost and solving-time improvements.

Q4. Sensitivity to the reference continuation

Could the authors analyze how different reference continuation policies affect the replay costs and candidate action rankings, to further assess the robustness of the policy-conditioned training targets?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.