Theoretical Challenges in Learning for Branch-and-Cut

Machine learning is increasingly used to guide branch-and-cut (B&C) for mixed-integer linear programming by learning score-based policies for selecting branching variables and cutting planes. Many approaches train on local signals from lookahead heuristics such as strong branching, and linear programming (LP) bound improvement for cut selection. Training and evaluation of the learned models often focus on local score accuracy. We show that such local score-based methods can lead to search trees exponentially larger than optimal tree sizes, by identifying two sources of this gap. The first is that these widely used expert signals can be misaligned with overall tree size. LP bound improvement can select a root cut set that yields an exponentially larger strong branching tree than selecting cuts by a simple proxy score, and strong branching itself can be exponentially suboptimal (Dey et al., 2024). The second is that small discrepancies can be amplified by the branch-and-bound recursion. An arbitrarily small perturbation of the right-hand sides in a root cut set can change the minimum tree size from a single node to exponentially many. For branching, arbitrarily small score discrepancies, and differences only in tie-breaking, can produce trees of exponentially different sizes, and even a small number of decision differences along a trajectory can incur exponential growth. These results show that branch-and-cut policies trained and learned using local expert scores do not guarantee small trees, thus motivating the study of data-driven methods that produce policies better aligned with tree size rather than only accuracy on expert scores.

Many planning problems, such as scheduling, routing, and resource allocation, require modeling using decision variables that are constrained to take integer values. Modern branch-and-cut solvers handle these problems by adding constraints that tighten simplified versions of the problem, and by repeatedly partitioning the search space into smaller parts that are easier to process. Recent work uses machine learning to guide these local choices, often by training a model to imitate expert scores that are expensive to compute directly. A natural hope is that if the learned model imitates the expert well at each local decision, then the whole solver will also perform well. Our paper shows that this hope can fail in a strong mathematical sense. We construct examples where tiny errors in learned scores, tiny changes in added constraints, or even different tie-breaking rules can be amplified into exponentially larger search trees. The message of our paper is not that machine learning should be avoided in optimization solvers. It is that local imitation alone is not enough, and learning methods should also be tested against the global search behavior they induce.