Generalization Guarantees for Learning Branch-and-Cut Policies in Integer Programming

Mixed-integer programming (MIP) provides a powerful frame work for optimization problems, with Branch-and-Cut (B&C) being the predomi nant algorithm in state-of-the-art solvers. The efficiency of B&C critically depends on heuristic policies for making sequential decisions, including node s election, cut selection, and branching variable selection. While traditional solve rs often employ heuristics with manually tuned parameters, recent approaches increas ingly leverage machine learning, especially neural networks, to learn these polic ies directly from data. A key challenge is to understand the theoretical underpinnin gs of these learned policies, particularly their generalization performance from finite data. This paper establishes rigorous sample complexity bounds for learnin g B&C policies where the scoring functions guiding each decision step (node, cut, branch) have a certain piecewise polynomial structure. This structure gener alizes the linear models that form the most commonly deployed policies in practice an d investigated recently in a foundational series of theoretical works by Balc an et al. Such piece-wise polynomial policies also cover the neural network arch itectures (e.g., using ReLU activations) that have been the focal point of contempo rary practical studies. Consequently, our theoretical framework closely refle cts the models utilized by practitioners investigating machine learning within B& C, offering a unifying perspective relevant to both established theory and modern empirical research in this area. Furthermore, our theory applies to quite general sequential decision making problems beyond B&C.