Exact solvers for mixed-integer linear programs (optimization problems where some variables must take whole-number values) search a tree. At each node they pick one fractional variable to split on. The most reliable way to pick is strong branching: tentatively solve the two child relaxations for every candidate and see which split raises the bound most. It produces near-minimal trees, but it is so expensive that solvers ration it with fixed rules. Learned replacements run into the same wall in a different form, because running a neural network at every node can cost more time than the smaller tree saves. This proposal borrows one idea from the Delphi method, the structured way of polling experts in which anonymous scores are collected, dispersion is measured, and only the items without consensus go to a costlier second round. We propose spending strong-branching effort only at nodes, and only on candidates, where a deliberately diverse panel of cheap branching heuristics disagrees.
In two sentences: at each node, several fast scorers (pseudocosts, inference and conflict history, fractionality, an entropy score, and a small learned scorer) each rank the candidates, and we compute a Delphi-style agreement statistic over their top choices. When the panel agrees, we branch on its consensus at almost no cost. When it disagrees, we strong-branch only the handful of variables that some panelist ranked highly, so expensive lookahead goes where uncertainty actually is rather than where a fixed per-variable counter says it is due.
Core Claim
Our claim is empirical and can be falsified. Among inexpensive branching scorers, rank disagreement at a node predicts whether the cheap choice would differ from the strong-branching choice and whether that difference matters for subtree size. If it does, a disagreement-triggered allocation of a fixed strong-branching budget will beat SCIP's default reliability pseudocost branching (relpscost) on wall-clock time and primal-dual integral. relpscost triggers strong branching through a per-variable count of how often the variable's pseudocost has been observed. That is a test of whether enough data exists for one variable, not a test of whether the decision at hand is ambiguous. The two triggers are different, and our experiments compare them at equal budget.
The statistic is a direct transcription of Lawshe's content validity ratio, which Delphi studies use to keep or discard items. Vu et al. apply it with a five-member panel to decide which cognitive subtests stay, and Wake et al. use the related content validity index to prune survey items. For candidate $j$ at a node with $K$ panelists, let $n_j$ be the number of panelists that place $j$ in their top $m$. Then
$$c_j = \frac{n_j - K/2}{K/2},$$
so $c_j = 1$ means unanimous endorsement and $c_j = -1$ means no panelist endorses it. The node counts as settled if $\max_j c_j \ge \tau$ for a threshold $\tau$, in which case we branch on the top candidate by mean rank. Otherwise the contested set is every candidate with $n_j \ge 1$, capped at size $B$, and only that set is strong-branched. Panelists contribute ranks, not raw scores. This is the computational form of Delphi anonymity: no scorer dominates because its scale happens to be larger. Dombrowski et al. motivate blind independent scoring for the analogous reason that dominant voices should not set the outcome.
Why the Delphi Lens, and Where It Constrains Us
Two Delphi ingredients carry over cleanly. The first is controlled feedback. Byrne et al. describe panelists reviewing the group distribution between rounds. In our version, the strong-branching results on contested variables update the pseudocosts and conflict statistics of exactly those variables, so the panel's later rankings at deeper nodes are informed by the round-two evidence. The second is the minority report. A variable that only one panelist ranks first is not averaged away, as it would be under a weighted sum. Instead it earns a strong-branching trial.
The Delphi literature also warns us about two weaknesses. First, a homogeneous panel compresses variance and can mistake shared bias for consensus. We therefore choose panelists that measure different things: bound movement (pseudocost), infeasibility history (inference and conflict scores), the entropy-based uncertainty reduction of Gilpin et al., plain fractionality, and a learned scorer. We also report pairwise rank correlations between panelists so that redundancy is visible. Second, classical Delphi has no ground truth and can settle on a confident wrong answer. Here we can check consensus against strong branching, and on small instances against the true optimal tree. That makes branching an unusually clean testbed for whether dispersion-gated escalation works at all.
Dey et al. both support and limit the plan. Their exact dynamic program shows strong-branching trees are within a factor of two of optimal in geometric mean, which justifies using strong branching as the round-two arbiter. They also construct instances where strong branching is exponentially worse than other rules. On those instances, a settled panel that overrules what strong branching would pick could in principle beat strong branching itself. We test that directly rather than assume it.
Research Program
We build a branching rule in PySCIPOpt inside Ecole, the gym-style interface to SCIP used by Strang et al.. The panel scorers are implemented as cheap C-side reads of SCIP's existing statistics, plus one learned panelist. That panelist is the CPU hybrid of Gupta et al., which runs a graph network once at the root and a small multilayer network at each node. We chose it because their work shows per-node graph inference is too slow on CPU. The thresholds $\tau$, $m$ and $B$ are tuned on a validation split of each problem family.
The program has three stages. The diagnostic stage logs, at sampled nodes, every panelist's ranking, the full strong-branching scores, and the subtree size under alternative choices. It measures how well $\max_j c_j$ predicts both disagreement between the cheap and strong-branching choices and the subtree penalty of the cheap choice. The policy stage runs the protocol end to end. The robustness stage asks whether disagreement between the learned panelist and the classical panelists flags out-of-distribution nodes. Here we fall back to classical consensus plus strong branching whenever the learned scorer is the lone dissenter. This addresses the collapse seen in Zarpellon et al., where a bipartite graph network failed on 7 of 8 unseen MIPLIB instances.
Baselines
The naive reference point is SCIP with default settings, which means relpscost. It is also the hardest to beat in wall-clock terms, because its overhead is near zero and it has been tuned for decades. On Distributional MIPLIB's Optimal Transmission Switching (Easy) distribution, Huang et al. report a primal-dual integral of 20.0 for default SCIP against 27.9 for a learned strong-branching imitator (lower is better). That is the bar any added per-node computation must clear. On hard Set Covering, Gasse et al. report about 5,511 nodes for relpscost and about 5,169 for their graph-convolutional policy. We rerun both under our hardware rather than quoting them. The strongest learned competitor on time is the hybrid model of Gupta et al., which reports up to a 26% running-time reduction on CPU. It is also our learned panelist, so beating it alone isolates the value of the consensus protocol. On heterogeneous MIPLIB, the reference is TreeGate from Zarpellon et al., which reports 83.7% imitation accuracy and 27% fewer nodes than a tree-unaware model. Full strong branching serves as the node-count lower reference.
Every method runs single-threaded on the same CPUs, with the same instances, time limits and seeds. Learned baselines receive the same tuning budget as our thresholds. The decisive ablations hold the total number of strong-branching LP solves per instance fixed at whatever our protocol used and vary only where that budget is spent. Allocations are triggered at random nodes, triggered by relpscost's reliability counter with a raised limit, or spent on the top-$B$ candidates by mean panel score rather than the contested set. A second ablation removes the learned panelist, and a third uses a homogeneous panel of pseudocost variants. Beating the baselines means a lower shifted geometric mean of solving time and primal-dual integral than default SCIP on at least the Set Covering, Combinatorial Auctions, Facility Location and Independent Set families, and beating every equal-budget allocation ablation. Fewer nodes alone does not count.
Why not just…?
Why not just take a weighted sum of the heuristic scores, as solvers' hybrid scores already do? A sum gives one ranking but says nothing about when that ranking is unreliable. It also suppresses the minority signal that a single panelist sees. The "mean-score top-$B$" ablation is exactly this alternative given the same strong-branching budget. If it matches our protocol, the Delphi framing adds nothing, and we will report that.
Why not just raise or tune relpscost's reliability threshold? This is the most serious threat, because it is already a cheap-first, expensive-when-needed scheme. The difference is the trigger: data sufficiency for one variable versus ambiguity of the decision at this node. The equal-budget comparison against a tuned reliability trigger settles the question. If the diagnostic stage shows that reliability counts predict strong-branching disagreement as well as panel dispersion does, the idea fails.
Why not just learn a gate that predicts when strong branching is worth calling? A learned gate trained on the diagnostic logs could match a hand-set CVR threshold in-distribution, and we include it as a baseline. Our argument for the training-free statistic is transfer. A disagreement measure has no distribution to overfit, whereas learned branching components degrade on unseen MIPLIB classes Zarpellon et al.. The heterogeneous MIPLIB split tests whether this argument holds.
Proposed Experiments
The first check gates everything else. On sampled nodes from the four Gasse et al. families, we compute the area under the ROC curve of $\max_j c_j$ for predicting whether the cheap consensus choice differs from the strong-branching choice. We compare it with the same metric for the reliability counter and for a single scorer's top-two margin. If dispersion is no better than these, we stop and report a negative result. Next comes the end-to-end comparison on those four families, with training-scale and larger evaluation instances, followed by Distributional MIPLIB's OTS Easy as the inference-bottleneck stress test against the 20.0 and 27.9 references. Then we use the 27-instance heterogeneous MIPLIB split of Zarpellon et al. to test the dissent-triggered fallback. Its success criterion is solving at least as many of the 8 test instances as TreeGate, with lower time than the learned panelist alone. Finally, on binary programs with at most 20 variables, where the dynamic program of Dey et al. gives the optimal tree size, we measure each policy's ratio to optimal. We also check, on their constructed pathological instances, whether a settled panel avoids the exponential blow-up of strong branching. A positive answer there would show something strong branching cannot deliver by construction.
References
- Feasibility, comprehensibility and acceptability of the VISION-Cog, a novel tool to assess cognitive impairment in visually impaired older adults: a cross-sectional pilot study in Singapore
- Follow-up after major traumatic injury: a survey of services in Australian and New Zealand public hospitals
- Conservative Management and Biological Treatment Strategies: Proceedings of the International Consensus Meeting on Cartilage Repair of the Ankle
- An international, Delphi consensus study to identify priorities for methodological research in behavioral trials in health research
- Information-theoretic approaches to branching in search
- A theoretical and computational analysis of full strong-branching
- A Markov Decision Process for Variable Selection in Branch & Bound
- Hybrid Models for Learning to Branch
- Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies
- Distributional MIPLIB: a Multi-Domain Library for Advancing ML-Guided MILP Methods
- Exact Combinatorial Optimization with Graph Convolutional Neural Networks