Cross-Graph Attention Fusion for Learning to Branch in Chance-Constrained MILPs

Abstract

Learning to branch accelerates branch-and-bound (B&B) for mixed-integer linear programming (MILP) by replacing hand-designed variable-selection rules with data-driven policies. For the large-scale MILPs produced by the sample average approximation (SAA) of chance-constrained programming (CCP), recent work encodes each branching state with two graphs: a variable–constraint bipartite graph capturing the constraint structure, and a Hasse diagram capturing the scenario dominance partial order. The prevailing dual-tower model fuses these views by static per-node concatenation, which cannot represent how a candidate’s constraint-structure role relates to its dominance-position role. Because branching is a relational decision—the right candidate is the one that outperforms the others—we replace static concatenation with a bidirectional cross-graph attention module in which each candidate’s bipartite-graph embedding queries the Hasse embeddings of all candidates and, symmetrically, the Hasse embeddings query the bipartite-graph embeddings; the fused representations are scored by an MLP under the standard imitation-learning objective. On the chance-constrained resource planning problem at three scales (5 resources × 10 customer types, 600/1000/1500 scenarios), the proposed DT-CA model reduces B&B node counts by 18.2%–33.4% and solving times by 7.5%–22.3% over the dual-tower baseline DT under normally distributed demand, with node-count reductions of 3.6%–29.7% on a lognormal distribution and similar gains under a normal-to-lognormal shift. The results indicate that cross-graph attention is an effective and lightweight replacement for static fusion in dominance-aware learning to branch.