Research map / Learning theory and algorithms / Combinatorial and search optimization

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

NeurIPS 2025 · Learning theory and algorithms › Combinatorial and search optimization · approach: Learning branch-and-cut for MILP · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Establishes pseudo-dimension and Rademacher sample complexity bounds for learning branch-and-cut policies (node, cut, branching scores) whose scoring functions are piecewise polynomial in their parameters, covering linear and ReLU MLP scorers.

Problem

Generalization guarantees (sample complexity) for learning score-based branch-and-cut policies for node, cut, and branching selection in mixed-integer programming, where prior theory mostly covered linear scoring rules.

Approach

Assume scoring functions are piecewise polynomial in learnable parameters (a (Gamma, gamma, beta)-structure); show this makes the overall B&C cost piecewise constant in parameters, yielding pseudo-dimension bounds that cover linear and ReLU neural policies and improve on prior linear-policy bounds.

Key results

• Linear B&C policies obtain pseudo-dimension O(WM sum_k log rho_k), improving the prior O(WM sum_k log rho_k + W log W) bound by removing the W log W term.
• For ReLU MLP scorers, pseudo-dimension is O((sum_k L_k W_k)(M sum_k log rho_k + log sum_k U_k)) for the overall B&C policy class.
• For a root-only cut selection ReLU policy, pseudo-dimension of tree size is O(L_2 W_2 (kappa R log r + log U_2)).

Limitations

• Results are worst-case or bounds only; no empirical validation is provided in the text.
• Assumes deterministic transitions and a bounded number of candidate actions per state.
• Infinite cut families (e.g., CGFs) are not covered by the current framework.

Experimental setup

Metrics: pseudo-dimension empirical Rademacher complexity

Baselines: linear policy pseudo-dimension bound of Balcan et al.

Builds on: Balcan et al. data-driven algorithm design / tree search model Balcan et al. learning cut selection parameters Gupta and Roughgarden sample complexity framework

Closest papers by meaning

• Theoretical Challenges in Learning for Branch-and-Cut (ICML 2026 · similarity 0.91)
• Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut (NeurIPS 2024 · similarity 0.91)
• Learning Cut Generating Functions for Integer Programming (NeurIPS 2024 · similarity 0.90)
• Learning to Remove Cuts in Integer Linear Programming (ICML 2024 · similarity 0.88)
• Search Strategy Generation for Branch and Bound Using Genetic Programming (AAAI 2025 · similarity 0.87)
• Learn2Aggregate: Supervised Generation of Chvatal-Gomory Cuts Using Graph Neural Networks (AAAI 2025 · similarity 0.87)