acceptodds
Desk rejected at ICLR 2027

Learning to Select Nodes in Branch-and-Bound via Tree-Aware Contrastive Learning

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

Abstract

Branch-and-bound (BnB) search is inherently hierarchical, yet learning to select its next node remains largely based on node preferences or tree-wide state representations. The central challenge is to turn this hierarchy into decision-relevant supervision. We introduce TreeCL, a contrastive framework that derives node-selection preferences from optimal-path consistency: if a reference optimum remains feasible at a node, it remains feasible at every ancestor. For competing nodes, their lowest common ancestor identifies the shared search context and anchors a contrast between branches that retain or exclude the reference optimum. This converts a structural property of BnB into an ancestor-conditioned selection rule, without requiring the reference solution at inference. Label-preserving branching-sequence augmentation further expands supervision from limited oracle trajectories. Experiments across five families of mixed-integer linear programming problems show significant gains in search efficiency over the evaluated learning-based baselines, transfer to larger instances, and fewer explored nodes on real-world instances.

Primary area:
optimization
Keywords:
Mixed integer linear programming, branch and bound, node selection, contrastive learning, learning for optimization

Related papers

Discussion (0)

Sign in to comment.