How hard is learning to cut? Trade-offs and sample complexity
Authors: Sammy Khalife
Andrea Lodi
Venue: ICLR 2026 Poster (2026)
Keywords: Integer programming
branch-and-cut
branch-and-bound
sample complexity
learning theory
Primary area: optimization

Abstract: In the recent years, branch-and-cut algorithms  have been the target of data-driven approaches designed  to enhance the decision making in different phases of the algorithm such as branching, or the choice of cutting planes (cuts). In particular, for cutting plane selection two score functions have been proposed in the literature to evaluate the quality of a cut: branch-and-cut tree size and gap closed.  In this paper, we present new sample complexity lower bounds, valid for both scores. We show that for a wide family of classes $\mathcal{F}$ that maps an instance to a cut, learning over an unknown distribution of the instances to minimize those scores requires at least (up to multiplicative constants) as many samples as learning from the same class function $\mathcal{F}$ any generic target function (using square loss). Our results also extend to the case of learning from a restricted set of cuts, namely those from the Simplex tableau. To the best of our knowledge, these  constitute the first lower bounds for the learning-to-cut framework. We compare our bounds to known upper bounds in the case of neural networks and show they are nearly tight, suggesting that both scores (gap closed and tree size) are of comparable difficulty from a learning standpoint. Guided by this insight, we provide empirical evidence -- by using a  graph neural network cut selection evaluated on various integer programming problems -- that gap closed is a practical and effective proxy for minimizing the tree size. Although the gap closed score has been extensively used in the integer programming literature, this is the first principled analysis discussing both scores simultaneously both theoretically and computationally.

Published as a conference paper at ICLR 2026
HoW HARD IS LEARNING TO CUT? TRADE-OFFS AND SAMPLE COMPLEXITY
Sammy Khalife
Andrea Lodi
School of Operations Research and Information Engineering Cornell Tech, Comell University
Jacobs Technion Cornell Institute Cornell Tech and Technion IIT andrea. lodi @cornell 1. edu
khali fe. sammy@ edu
ABSTRACT
In the recent years, branch-and-ce algorithms have been the target of data-driven approaches designed to enhance the decision making in different phases of the algorithm such as branching, or the choice of cutting planes (cuts). particular, for cutting plane selection two score functions have been proposed in the literature to evaluate the quality of a cut: branch-and-cut tree size and gap closed. In this paper, we present new sample complexity lower bounds, valid for both scores. We show that for a wide family of classes JF that maps an instance to a cut, learning over an unknown distribution of the instances to minimize those scores requires at least (up to multiplicative constants) as many samples as learning from the same class function F any generic target function (using square loss). Our results also extend to the case of learning from a restricted set of cuts, namely those from the Simplex tableau. To the best of our knowledge, these constitute the first lower bounds for the learning- carming-to-cut to-cut framework. We compare our bounds to known upper bounds in the case of neural networks and show they are nearly tight, suggesting that both scores (gap closed and tree size) are of comparable difficulty from a learning standpoint. Guided by this insight, we provide empirical evidence by using graph neural network cut selection evaluated on various integer programming problems - that gap closed a practical and effective proxy for minimizing the tree size. Although the gap closed score has been extensively used in the integer programming literature, this is the first principled analysis discussing both scores simultaneously both theoretically and computationally.
INTRODUCTION
Branch-and-cut algorithms form the cornerstone of integer programming solvers. In recent years, machine learning has been playing a growing role enhancing those solvers by enabling data-driven decision-makinn in various components of the algorithm. Recent attempts aim augmenting those solvers, which often rely on handcrafted heuristics, by training models on data obtained from solved instances, predict decisions that lead faster convergence (which cutting plane or cut, for short - to choose, or which variable to branch on). Specifically referring to cuts, there has been a growing body of work recently. Pauluus al.) (2022) proposed a neural architecture that employs imitation learning to select cutting planes in mixed-integer linear programs (MILPs). By mimicking lookahead expert that evaluates the potential impact of cuts on future bounds, their method aims to improve the efficiency of cut selection. In Huang et al. (2022). the authors trained neural network to learn scoring function evaluating the quality of candidate cuts based on instance-specific features. Tang et al. (2020) explored the use of deep reinforcement learning to adaptively select cutting planes in integer programming. By formulating cut selection as a Markov Decision Process, their method trains agent to make the right cut selection among the Tableaux cuts. Subsequently, Ling et al.) (2024) addressed the challenge of determining when to stop generating cuts, using reinforcement learning and different features of MILPs make informed decisions. We refer the reader to the excellent survey Deza & Khalil (2023) for a more exhaustive list on previous contributions.
A fundamental question in any learning- based approach for generating cutting planes making branching decisions during the solving process is how many training samples are needed to ensure good performance across entire (and potentially unknown) distribution of problem instances. This

---

Published as a conference paper at ICLR 2026
issue- referred to as sample complexity is critical, as it determines the scale of the learning task and directly impacts the feasibility of effectively training models. Understanding sample complexity helps address the inherent challenges of data-driven approaches by indicating how many instances must be solved to learn patterns that generalize reliably across a distribution. Establishing such bounds is therefore central providing rigorous scientific foundations for data-driven techniques in integer programming. For instance, learning effective cut generation might require so many samples that the approach becomes impractical, or, in more favorable case, only a moderate and affordable number of samples, scaling reasonably with the number of variables and constraints. Recent upper bounds have been obtained in the case of fixed cut selection across distribution of instances, Balcan et al. (02T), and more recently in the setup where neural networks map an instance to cut, with a syynomial-logarthhin
dependence on the size of the problems [Ceng et al. (2024). Our investigation asks whether those bounds are tight for broader architectures and how the given ways of measuring the effectiveness of the cut affect sample complexity. If one metric were intrinsically harder to learn than another, this would shape both the design of learning algorithms and the choice of evaluation criteria. Our lower bounds provide clarity here, showing that - at least for unknown distributions gap closed and tree size exhibit comparable sample complexity, thus preventing misleading conclusions about relative difficulty.
While these theoretical insights are important, they do not resolve their own the practical challenges of implementing learning- based strategies. In particular, even if two performance measures are comparable from the standpoint of sample complexity, the computational effort required to optimize them may differ substantially. Our second contribution addresses this gap by showing that the gap closed score, despite being proxy, aligns closely enough with tree size to serve as a practical surrogate. Taken together, these results provide coherent picture: the first establishes that gap closed and tree size are theoretically equivalent in terms of learnability, while the second demonstrates that gap closed is computationally tractable and empirically reliable alternative to tree size for guiding cut selection. In summary, the motivation for our work stems from the following two groups of observations, leading to two main results.
1.
The existing studies applicable to sample complexity of learning-to-cur provide upper bounds for specific learning algorithms, formally referred to as concept classes. Those studies are applied to special family of cutting planes, namely
(CG) cuts Gomory [9558;; Chvátal (977)). Specifically, in Balcan et al.; (202T), the concept class is restricted to functions that return constant CG weights applied to any instance. In [Cheng et al.] (0024), the CG weights are generated by a neural network taking as input an integer linear program (ILP) instance.
Our contribution is to provide the first quantitative lower bounds on sample complexity, and study lower bounds that are valid for wide family of classes. Our lower bounds are discussed in Section 3 and anticipated in Table [
2. There are two main scores proposed in the literature to evaluate the quality of a cut. The first one is based on the relative size reduction (or increase) of the branch-and -nd-huun (B&C) tree size. The second one is the relative improvement in the objective function of the relaxed problem (gap closed, where the gap for a MILP is the relative difference between the value of its linear programming. LP, relaxation and that of its optimal solution). The first score correlates well with the overall running time of the algorithm as it corresponds roughly to the number of LPs solved. However, it is easy to see that it is very expensive to train using the tree size because it requires to solve the problem to optimality to be evaluated. So, the second one could be considered as a proxy of the first, and the natural question we aim at discussing is how good the proxy is both in theory and in practice [
Our contribution is to empirically show the quality of the gap closed proxy and assess the ability of graph neural network to learn both score functions in practice. Although the gap closed score has been extensively used in the integer programming literature, this is the first principled analysis discussing both scores at the same time both theoretically and computationally. The computational evaluation is conducted in Section 4
Our first contribution sheds light on the learning difficulty of generating CG cuts from an instance when using two of the most common and theoretically grounded scores: gap closed and tree size. In
From the theory side, the upper bounds in Balcan et al. 2021;; Cheng et al. 2024) are obtained for the branch-and-cut tree size score, although similar approach would yield the same upper hound for both scores.
2

---

Published as a conference paper at ICLR 2026
Table 1: Illustration of sample complexity bounds in the case of ReLU neural networks with W weights and L layers, for IP instances with n variables and m constraints, verifying M 2 Σ |Ayl Σ [by]. Here, W W wi (n + 1)m where wi is the number of neurons the first hidden layer. The bounds in blue are our main theoretical contribution.
Setting
B&C tree or gap closed scores
Lower Bound
Upper Bound
all CG-cuts
Log QQW L Log( 1)
OLL + m) + W Woo M)
tableau cuts
OLLW log(U + +t))
particular, for classes such as neural networks, our bounds show that - absent further assumptions on the distributions it is not theoretically harder learn one than the other, as lower bounds nearly match known upper bounds. Our results can be put more broadly in the spectrum of algorithm selection, where selecting algorithms based specific instances is allowed. For example, this is the case of Rice (976);; Gupta & Roughgarden (2016) where the sample complexity of learning mappings from instances algorithms for particular problems is explored. Our approach is also related to recent work on algorithm design with predictions, see, e.g.. Mitzenmacher & Vassilvitskil (2022) and the references therein.
Our second contribution highlights that, beyond this insight, the gap closed score remains a useful practical proxy for minimizing the more challenging tree size score over distributions of instances. For example, in the case of cuts generated by neural networks, our bounds indicate that there is no significant theoretical distinction between the two scores, and our numerical experiments further support that gap closed is reasonable proxy across wide range of instance families for cut selection.
The remainder of the paper is organized as follows. In Section 2 we properly define ILPs and its most successful solution method, i.e., branch and cut, well theory. In Section 3] we discuss our main theoretical result on sample complexity lower bounds. An outline of the the proofs is given in Appendix [A] and full proofs are deferred to Appendix B In Section { we report on the computational investigation involving the two different score functions to evaluate cut quality. The full description and report of our experiments is included in Appendix due to space limitations. Finally, in Section 5 we draw some conclusions and outline open research questions.
give the basic definitions of learning
PRELIMINARIES
In this section, provide preliminaries for both ILP cutting plane methodology and learning theory.
2.1 BRANCH AND CUT AND CUTTING PLANES
We consider the ILP in the form
max T Ax S b, 0,x E Z"}.
where m, n E N,, and A E Qunxn b E Q"", C R
The algorithms implemented in every (M)ILP solver are variations of framework called branch and cut. In that algorithm, each iteration maintains: 1) a current best (integral) solution guess and 2) a list of polyhedra, each a subset of the original ILP relaxation. At each step, one polyhedron is selected and its continuous LP solution is computed. If the objective is worse than the current guess, the polyhedron is discarded. If the solution is integral, the guess is updated and the polyhedron removed. Otherwise. the algorithm either adds cutting planes valid inequalities that tighten the polyhedron - or branches. In branching, a variable x; whose current value x; is fractional is chosen, and the polyhedron is split using x; S [x]] and x; 2 [x]] 1. These the original one. This process builds a branch-and-cum tree, with each node representing a polyhedron.
polyhedra replace
"The IIP equation is called MILP if a subset of the variables is allowed to take continuous values.
"Such guess would Tikely be co initially.
3

---

Published as a conference paper at ICLR 2026
The algorithm stops when the list is empty, returning the best guess as optimal. Often, bound B is set on the tree size; if exceeded, the algorithm terminates early and returns the current best guess.
Coonfooo There many different strategies to generate cutting planes in branch-and-oon CCoforti et al. (2014);
Nemhauser & Wolsey (188); (Scrrijer 1986). The oldest one is due to Gomory |omory (9588
and later generalized by Chvátal[Cváát (1973), the family of resulting cutting planes is called Chvátal-Gomory cuts. Namely, for any x E z" satisfying Ax S b, then the inequality uAAx - |ub] valid for S for all u 2 0 such that UA 2" and is called a CG cut. Gomory suggested to read as the inverse of the basis of the tableau when the LP relaxation is solved by the Simplex method Gomory [958). Chvátal generalized the procedure any u Chvátal (1973).
Since the number of CG cuts that can derived at any iteration of the branch-and-cre algorithm is very large, any MILP solver implements its own cut selection strategy, i.e., decides which cuts are added to the current LP relaxation. The cut selection is performed by sophisticated, handcrafted heuristies and, as anticipated, the use of modern statistical learning to enhance these heuristics has been recently studied. The standard approach that has been used and that we inherit here is to decide the single next cut to be added within the CG family (or part of it). To do so, we need a score function that evaluates the quality of the cut, and two such functions have been investigated. Ideally, the sanchhand-cutt tree size after the addition of the cut is the right measure since most of the computing time is spent on solving the individual LPs in the nodes of the algorithm. However, this scoring function is very expensive to evaluate and, so far, has been used for theoretical purposes only. Instead, MILP technology generally measures the quality of cut using the gap closed, i.e., the measure of the improvement of the LP relaxation after the addition of the cut. Of course, this is cheaper to evaluate (requires solve one single LP per cut), but still too expensive in practice for performing cut selection, so the idea of learning such score
It is interesting to note that, although the gap closed could be seen as a proxy of the branch-an -nt-uct tree size, the two scores are hard to properly compare. More precisely, a cut could reduce significantly the tree size without even cutting off the optimal (fractional) solution of the LP relaxation, while a cut that does cut it off could have no effect long term, i.e., in reducing the tree size.
For example, consider the ILP {max 5zg + +8822 I1 + 22 S 6,521 + 9x² S 45, 31, 22 2 21, 22 E Z}. whose fractional solution is x = (2. 15 It can be shown that one of the CG cuts derived from the optimal tableau leads to the constraint 4x + 7x2 S 35. Adding this constraint leads to a new
3 ). located on the right (i.e., with greater z-coordinate) of the solution of the original formulation. Hence, supposing branching is performed first on T1 then T2, this leads to a larger branch- -nd-ucu tree, with more LPs to be solved. However, this CG cut actually cuts off the fractional solution, hence improves the gap closed score.
fractional solution (3. 11
2.2 LEARNING THEORY
We are interested in a statistical supervised learning problem of the following form, given a fixed parameterized function class defined by some h with output space O = I::
min T (( JEF
s1)²),
(2)
for an unknown distribution D. given access to i.i.d. samples (41 s1)..., (.e))...,,,,,))))) (4,, restrict to learning problems of a function if to minimize a given functional measuring the quality of cutting plane in wranch-and-eut type of algorithm, where 8 is score of "best cut" (according to this score), collected for instance T. In this problem, one tries to learn the best decision f & F for minimizing an expected error compared to the best encountered "cut score", with respect to an unknown distribution from which samples are drawn. In our branch-and that we have access to an oracle returning the performance of the cutting plane after adding ILP instance, that will be accounted for in the choice of the function h. We are interested in two performance scores: (i) the relative variation of the size of the rranch-and-cur tree after adding the cut, and (ii) the gap closed score. Both will be formally defined in Section 2.
from D. We
framework, we assume the
'It is worth mentioning that no solver adds one cutting plane at time, but cuts are instead added in groups called rounds. Analyzing such procedure would be way harder, so literature studies well as our paper- concentrate on this simplified version.
4

---

Published as a conference paper at ICLR 2026
In this context, learning algorithu L for ,F is function taking input fixed (but arbitrary) amount of samples, and returning a function F
L (IxR)
m=
Given e E (0, 1), ò (0, 1), the sample complexity of learning mo(e, 0) N of L is the smallest integer (allowed to be +o0) such that for any m 2 mole, 8), for any probability distribution D on I. the algorithm L evaluated at "test time" instance I is is in average close the solution on the entire distribution up
B(A,)) (hh (I, L(1 .. (I)) s1)21 min ((.aa))D(((II)))) JEF
-s)) <E
with probability 1 1 over i.i.d samples !.... Im drawn following D. The following two definitions are needed in order to formulate a fundamental result concerning the sample complexity of learning.
Definition 2.1 (VC-dimension of a real output concept class). For any positive integer I, we say that a set (1,,...; ]+] S is shattered by concept class & defined on I taking {0, 1 }--values
2 =
f(4)) EHH
The VC dimension of E, denoted VCdim(E) E NNU is the size of the largest set that can be shattered by E.
If F is non-empty collection of functions from an input space I to RR. Let Len(F) == {sgn(f) /) E F} where sgn(x) = 1g>0- Then, (C) is by definition VCdim(sgn(F)) where we adopt the standard defintion of VCdim for {0, (0,1)-funccl ffuncctnonnn described above.
Definition 2.2 (Fat-shattering dimension). Let > 0. With the same notations as Definition B.3 we say that the function class F fat-shatters 41, ... It with precision y provided there exists r E R" such that for every labeling (V1. ... M1) E 1-,,1}² there exists g E F, such that g(4) 2 + + if Yi -1 and g(4;) S r. - if y; In such conditions, called the witness of the shattering. The fat-shattering dimension of FF with precision ?, noted fat)(?)) (7) is the size of the largest that can be fat-shattered by F.
In the case of binary functions, VC-dimension gives direct way to bound from above and below learning sample complexity (Anthony & Bartlet 2009) Theorem 5.4). For real output functions, the -eeudddi remain useful to find an upper bound uniform convergence (UC). Typically, UC requires the absolute difference between the empirical mean and the full expectation to be bounded from above by for every f E F and for every distribution. However, the sample complexity of learning can be smaller than that of UC. This leads to the sample complexity of UC to be an upper bound the sample complexity of learning via Empirical Risk Minimization (ERM), which is itself greater than the sample complexity of learning in general, as there could be other algorithms performing better than ERM. In other words, uniform convergence guarantees that ERM will perform well, since the sample average closely matches the true expectation across all hypotheses. Good performance from ERM can still occur without full uniform convergence, and there may exist other learning algorithms that outperform ERM.
Therefore, lower bounds on dimensson or VC-dimensions mainly apply to UC, and do not necessarily reflect the true sample complexity of learning. This surprising gap was first highlighted in Shalev-Shwarte et al. (2009) and further explored in Feldman (0016). As a consequence, to obtain lower bounds of learning sample complexity, one cannot priori use standard traditional lower bounds of VC-dimension, and the analysis has to be performed carefully depending on the concept class considered. In this article, will rely on the following result giving general lower bound on the sample complexity of learning.
Theorem 2.3. (Anthony & Bartlett
2009
Theorem 19.5) Let F be a class of functions from to 10 2, any learning algorithm L for F has sample complexity
[o. 1]. Then for any ( c 1.0 <
(e(e,8) 8) satisfying for every
4
fat, (a))
mz
16a
'In unsupervised learning, the domain typically formed by U
5

---

Published as a conference paper at ICLR 2026
( samples guarantee that the average 16g
Thus, any learning algorithm will have use least solution at test time, independently of the distribution, will be at most at e distance from the best solution of the function class, with probability 1 6. Note that the lower bound is rigorously valid 100 (and the bound becomes independent of 5 in that regime).
only when 8
STATEMENT OF RESULTS
For any positive integer E 2+, [d] refers to the set 21,2..... The sign function sgn IR {0, 1), is defined such that for any E. sgn(z) 0 0, and otherwise. This function is applied to each entry individually when applied to a vector. The elementwise floor function [-] is used indicate the rounding down of each component of a vector the nearest integer.
3.1 OVER THE POOL OF ALL CG-CUTS
We first present results in the case where the generation of CG-cuts is unrestricted, i.e., except the limitations brought by the cut generation process, the whole pool of CG-cuts is considered. We assume the following structure on the underlying concept class F; each function of F incorporates an encoder function to transform each ILP be processed further. For Neural networks, an example of such an encoder is the concatenation of all the instance's 's numerical data into single vector. In the case of Graph Neural Networks (GNNs), one can choose graph based representation (cf. for example Chen al. 2024h). For case of presentation, used (our results naturally extend to every encoder which is surjective onto the domain of each coordinate function of F), and functions of F have domain R gonmm+mm +m+m+n and codomain I where the number of variables of the ILP, and m its number of constraints.
will suppose that the stacking encoder
Assumption 1. F is for every μ E mux=+++n f F = I +> f(x + ()) E F, and under scaling of the output of every coordinate, i.e., for every real and E [m], and f (fi," fm) F implies that any activation function that is not identically zero).
empty concept class closed under translation of the input, i...
... fmm F. Note that is true for (graph) neural networks (for
Assumption 2. (Same shattering power by restriction to some row). Let r = m x n. + m + For every i [m] representing the index of the associated CG-weight, C > VCdim (Cn](((F(n is constant (cf. Definition B.1 here F; refers to the concept class formed by the i- coordinate of f F). This is for example true for (graph) neural networks with any activation function In those conditions, we refer to this constant as (Fdim(F(p)).
Definition 3.1. Let I [0, 11m + ER be a score function, mapping each pair formed by an ILP instance and weight vector of a CG cut to real value. Let F be concept class following assumptions described above. Let a' 1m -> [0, 1 be a squeezing function so that of f (where f F) returns a vector in 10. used as weights of the CG-cuts. We also suppose that o' is continuous at & and verifies o'((-oo ((-oo, 0)) c [0, 5). o((0, +x0) C [ 1] and (0, 1) C oR)). Let
F,r be the concept class obtained. We define F.,gt as the final resulting concept class
Fa := (I (11+s(,, s(I, (())
F.r)
Theorem 3.2, Under those assumptions, for both gap-closed and branch-and-cut tree size scores, the sample complexity of learning CG-cuts via the class F.. verifies
mL(e, = VCdim(F(nl)
According to the notion of learnability, Theorem 3.2 provides lower bound on the minimum number of samples required to guarantee with probability any learning algorithm (in particular, this is true for the Empirical Risk Minimizer (ERM) algorithm) returns a solution whose predictions are at most far from the optimal neural network with high probability over the entire distribution.
å that for any distribution D. the solution of
TThis be hy adjusting the hias of the neurons in the first layer.

---

Published as a conference paper at ICLR 2026
Corollary 3.3. For any concept classes verifying Assumptions 1 and 2 my (c. 8) is bounded from below by the sample complexity of learning from Fn to a generic target function. In particular, with the same notation of Theorem 3.2 for every 7 >> O, we have
mz(e, 6) Ω (fatzin(())
(VCdim(FIn))
where similarly (at == [[ (m))).
Corollary 3.3 applies in particular neural networks (and to graph neural networks well), up to adding an extra neuron each layer
We now compare to the known upper bound in the case of neural networks (i.e., when F composed of neural networks of a certain depth and width). The upper bound of the pseudo-dimension of this concept class given by (Cheng al., 2024, Proposition 3.3) O (LW log(U + m) + W log M) for ReLU neural networks and squeezing function to constrain their outputs in [0, 1], M is an upperbound on the coefficients A and b, where U is the size of the neural network, defined as W1 + ... + ww, and are also imposed the conditions that m Σラ Aiyl S and > [b: < b for any (A, b, c) E I, and M == 2(a + b n.)
Hence, ignoring logarithmic factors in and 1 e, the best known upper bounds for m(c, 6) is given by O (2 (LW log(U' + m) + W log M) for the BC tree size score. Since the result only use the invariance by the number of regions where the CG-cuts remain constants, their proof can adapted for the gap closed score, although we suspect that better upper bound should be achievable in that case.
We now state our lower bound in the case of neural networks the next proposition. Note that our lower bound does not use any amplitude on the input data of the problem.
Proposition 3.4. Suppose F is composed of ReLU neural networks with < L layers, and < W weights, with the concatenation encoder / I (A, b, c) maxm+mtn There is universal constant C' such that the following holds. Suppose W > CL > C Consider both gap-closed and branch-and-oe tree size scores. Let W == W w1 (n + 1)m. Then, the sample complexity of learning CG-cuts via the class Fs. verifies
W L
W L log mz(e, 2 eC
few comments are in order:
The correction term of wi (n 1)m, where wi is the number of neurons in the first layer, accounts for the restriction of the concept class to n inputs, F [n]. Our approach "ignores" n x m + m (n + 1)m inputs. This leads an amount of wi + 1)m weights that are being removed in the neural network.
Recall that W =EL=1 W;-1w;; where wig := x m + m + the input dimension, and the other w 's are the widths (number of neurons) of the Neural network considered on each layer. In particular W W wi (n + 1 1)mm is always positive, and furthermore the ratio W is greater than
wh Mh
2
I+W
I+W
The lower bound supposes some structure on the layers and parameters given by W > CT. This loss of generality does not take place in our proof technique, but in the bit-extraction technique to give a lower bound the VCdim of the class of neural networks Bartlett et al. (2019). Therefore, in order remove that assumption, one would have either obtain a general lower requiring no particular structure, or adopt an entirely different approach, specific to shattering ILPs, that would not require a general VC dimension lower bound on neural networks.
Hence, supposing a regime where the number of weights in the neural network are large compared the variables n and number of constraints m, the gap of is of order 1, between our lower bound
There is asymptotic difference between Pseudo-dimension and VC-dimension of real output neural networks, up adding layer neuron per layer.
7

---

Published as a conference paper at ICLR 2026
and the best upper bound, ignoring logarithmic factors in and ! In general learning framework, this gap is inevitable: see for instances discussions in (Anthony & Bartlett 2009] Section 19.5). We suspect that this gap transfers for learning CG cuts, if no further assumption is made the distribution of instances.
3.2 OVER THE POOL OF ALL CG-CUTS FROM THE TABLEAU
We now restrict the pool of CG-cuts obtained from the tableau. the concept class has to be changed slightly. We show that despite our restriction, the sample complexity is still driven by the VC- dimension of the underlying concept class. To make this formal, we suppose the following structure: each function of the concept class is decomposable as the composition of function that takes as input an ILP instance
and returns the m CG-cuts from the tableau (a1, b1). (am, bm). This be perfomed using the the simplex algorithm. We also suppose that each function g maps (I, as, by) to a real value. The cut selected to added to the instance is the one maximizing each of the m seores, the concept class after selecting the maximum G (ties are broken by alphabetical order the constraints).
Definition 3.5. Let I x [0, 1 > E be score function, mapping cach pair formed by ILP instance and a weight vector of CG cut to a real value. Let & be concept class described above such that Assumptions I and 2 hold. We define 9, the final resulting concept class 9}.
G. := (I ((I,
Theorem 3.6. Under those conditions, for both gap-closed and branch-and-cut tree size scores, the sample complexity of learning CG-cuts via the class Gs.ar verifies
mL(c, = VCdim(9((1))
Proposition 3.7. Suppose 9 is composed neural networks with & layers, and < W layers, with the concatenation encoder E I + (A, b, c) Raxm+m+n There is a universal constant C' such that the following holds. Suppose W > CL C Let W W w (n + 1) + 1). Then the sample complexity of learning CG-cuts via the class F, from the optimal Tableau verifies
W L
mz(c, 2 c
WL log
In comparison with the upper bounds (Cheng et al.
2024, Corollary 2.8), ignoring logarithmic factors where = wi + .... Wrr is the total number of neurons. In the regime where the number of weights in the neural network are large compared to the variables n and number of constraints m, which implies W to be of the order of W, our bound could be improved by integrating logarithmic factors in m and U.
& and L. we have that m(ō,)) = O W Uog(Um)
NUMERICAL EXPERIMENTS
Our experiments start by comparing two metrics: B&C tree-size reduction, the true but costly performance measure, and gap closed, a computationally cheaper yet noisier proxy. This raises the central question of whether training gap closed can generalize improvements in tree size. To investigate that, we model (ILP instance, cut) pairs with a GNN trained on CG cuts from the Simplex optimal tableau. The model is then used predict cut quality, so to guide cut selection. The entire methodology, including loss formulation and inference procedure, is provided in Appendix C
4.1 EXPERIMENTAL SETUP
Modeling ILP as GNN. Each ILP instance augmented by a cut gets encoded by E unambiguously as weighted graph G with three dimensional feature vector on its vertices as follows: (i) The vertices G are split between the variables and constraint vertices. Each variable gets associated to vertex, and each constraint well, leading to bipartite graph with each variable vertex receives a three-dimensional feature vector corresponding to the objective vector entry, plus the coefficient of the cut for that variable, as well the right-hand side (same for all
vertices. Furthermore,
8

---

Published as a conference paper at ICLR 2026
variables). The other vertices corresponding to constraints get the vector (1, as feature (for dimensional homogeneity purposes). (ii) One edge is created between each variable vertex and constraint vertex I provided the variable appears in constraint j. The associated edge has weight azz the number of edges in the graph depends on the sparsity of A.
Data. We consider the very well-known Set Cover, Uncapacitated Facility Location, Knapsack, and Vertex Cover problems with their natural ILP formulations. The 1, 000 set cover instances have 50 subsets and 30 base elements. The 1, 000 uncapacitated facility location instances have 10 facilities and 10 clients. The knapsack instances have 2 knapsacks and 16 items. The vertex cover instances have 20 vertices and 50 edges. The details for randomly generating the instances are detailed in the supplementary material.
Training. The experiments were conducted on a Linux machine with a 24-core Intel Xeon Gold 6126 CPU, with 745Gb of RAM, and NVIDIA Tesla V100-PCIE with 32GB of VRAM. We used Gurobi 12.0.1 I Gur to solve the II.ss with default cuts, heuristics, and presolve settings turned off. The GNNs were implemented using PyTorch 2.6.0 and Pytorch Geometric 2.6.1. The details of the implementation are detailed in the supplementary material.
4.2 EMPIRICAL RESULTS
The GNN trained using the B&C tree size vs. gap closed as proxy. We report the average tree size after adding the chosen tableau cut. A subset of the results is reported in Table and full results are in Table 3 in Appendix C For all benchmarks except the GNN one, only the branch-and-cut tree size is reported, it is the final quantity of interest in this experiment. The results refer to 250 test instances for each problem class. The table compares six strategies: the perfect predictor (Optimal) always using the CG tableau cut that results in the smallest B&C tree size, classical heuristic that selects a cut according to its parallelism with respect to the objective function (Parallelism, see, e.g., Lodi (2009): Deza & Khalil (2023)), the cut efficacy (Efficacy), mix of the cut efficacy and parallelism (Mix). uniform random selection (Random), and the GNN using either the B&C tree size or the gap closed in training (GNN). The results show that the GNNs are able learn and provide solid improvement (facility location, knapsack) or stay on pair (set cover, vertex cover) with respect to state-of-te thet--art cut selection heuristic (cf. full table in Appendix C The GNN trained by the gap closed score function provides good proxy, though there is room for improvement for both GNNs with respect to the perfect predictor.
Table 2: A subset of the results: average tree size on 250 test instances of the GNN trained using either the B&C tree size gap closed proxy vs. four simple benchmarks.
(a) Set cover
(b) Facility location
Setting
B&C tree
gap closed
Setting
B&C tree
gap closed
Optimal
4.95
Optimal
86.31
Parallelism
8.29
Parallelism
144.09
Efficacy
9,90
Efficacy
123.63
Mix
9.30
Mix
133.72
Random
9.71
Random
152.46
GNN
8.27
8.65
GNN
128.85
134.61
5 DISCUSSION AND OPEN PROBLEMS
In this paper, we have presented the first sample complexity lower bounds on the learning-to-cut task and we have empirically analyzed the relationship between two score functions used to assess the quality of cut. In the sample complexity bounds, no analysis was conducted on the cut candidates that actually close the gap. i.e., cut off the fractional solution. This could give additional information to give better sample complexity bounds in the case of gap closed. Therefore, possible to obtain a better upper bound of the sample complexity for the gap closed score because, implicitly, a restricted number of cuts (only those cutting off the fractional solution) are required.
conjecture that it is
9

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
Both authors gratefully acknowledges support from the Office of Naval Research (ONR) grant N00014-24.1-2655.
REFERENCES
Gurobi Optimization, LLC.
Martin Anthony and Peter L Bartlett. Neural network learning: Theoretical university press, 2009.
foreretaialouulaationn foundations. cambridge
Maria-Florina F Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. Sample com- plexity of tree search configuration: Cutting planes and beyond. Advances in Neural Information Processing Systems, 34:4015 4024015--02...0 2021.
Peter L Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension and pscudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20(63):1-17,20 2019.
Ziang Chen, Jialin Liu, Xiaohan Chen, Wang Wang, and Wotao Yin. Rethinking the capacity of graph neural networks for branching strategy. Advances in Neural Information Processing Systems, 17:123991-124022 2024.
Hongyu Cheng, Sammy Khalife, Barbara Fiedorowicz, and Amitabh Basu. Data-driven algorithm design using neural networks with upplications to branch-and-cut arXiv preprint arXiv:2402.02328, 2024.
V. Chvátal, Edmonds polytopes and hierarchy of combinatorial problems. Discrete Mathematics, 335-337, 1973.
Michele Conforti, Gérard Cornuéjols, and Giacomo Zambelli. Integer programming, volume 271. Springer, 2014.
Arnaud Deza and Elias B Khalil. Machine learning for cutting planes in integer programming: A survey. arXiv preprint arXiv:2302.09166, 2023.
Vitaly Feldman. Generalization of erm in stochastic convex optimization: The dimension strikes back. Advances in Neural Information Processing Systems, 29, 2016.
R.E. Gomory, Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Sociery, 64:275-278 1958.
Rishi Gupta and Tim Roughgarden. A pac approach to spplicc algorithm selection. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pp. 123-134 2016.
Zeren Huang, Kerong Wang, Furui Liu, Hui-Ling Zhen, Weinan Zhang, Mingxuan Yuan, Jianye Hao, Yong Yu, and Jun Wang. Learning to select cuts for efficient mixed-integer programming. Pattern Recognition, 123: 10:3008353, 2022.
Haotian Ling, Zhihai Wang, and Jie Wang. Learning to stop cut generation for efficient mixed-integer integer linear programming. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 20759-20767, 2024.
Andrea Lodi. Mixed integer programming computation. In 50 years of integer programming 1958- 2008: From the early years to the sate--ofthh--ee pp. 619-645. Springer Berlin Heidelberg Berlin, Heidelberg, 2009.
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Communications of the ACM, 65-7)333-35, 2022.
George L Nemhauser and Laurence Wolsey. Integer and combinatorial optimization, volume 18. Wiley New York, 1988.
10

---

Published as a conference paper at ICLR 2026
Max B Paulus, Giulia Zarpellon, Andreas Krause, Laurent Charlin, and Chris Maddison. Learning to cut by looking ahead: Cutting plane selection via imitation learning. In International conference machine learning. pp. 17584-17600. PMLR, 2022.
John R Rice. The algorithm selection problem. In Advances in computers, volume 15, pp. 65-118. Elsevier, 1976.
Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley and Sons, New York, 1986.
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Stochastic convex optimization. In COLT, volume 2. pp. 5, 2009.
Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Reinforcement learning for integer programming: Learning cut. In International conference on machine learning, pp. 9367-9376. PMLR, 2020.
A OVERVIEW OF THE PROOFS
We now give overview of the proof of Theorem 3.2 and expand in Appendix B A very similar approach will be used for Theorem 3.7] Our proof builds a collection of instances that can be shattered by the concept class that integrates the generating process as well the scoring mechanism. We carefully handcraft instances making use of the assumptions made on the cut- generation mechanism, by integrating an uninformative constraint, used be shattered by the underlying concept class F.
The first observations and steps are:
We start with collection of vectors that shattered by F (as many the VC-dimension of F). Since the concept class F closed under scaling and translation, the entries of those vectors (redundant constraint vectors) can be considered to be non-negative. This allows us to ensure redundancy of the constraint.
The VC-dimension coordinate invariance (Assumption 2 allows us to use the redundant constraint without loss of shattering power. Note that approach could still work without that assumption, but this allows to make the original lower-bound statements as crisp as possible, in particular for the special case of neural networks, where upper bounds known.
We then analyze the space weights of the corresponding CG cuts and the impact of the CG cuts on the increase/decrease of objective after adding one of those CG cuts. We focus on two particular regions that are sufficient to fat-shatter our instances. These regions are given by
1
5
5
(4 4 7)
< Ug
1-
+
+2y
and
I
2
36
2
3 + +2
2
1 2 u2 <
5
2
3 - (4 - 1 -
and
U13 <
16
+ 27
where y is a fixed positive (but arbitrary) real between and J. Both regions of those CG weights lead to objective values that are at least (2()) apart.
The key reason this approach succeeds in achieving the final goal is that the constraint vectors are first shattered by F. yielding positive or negative outcomes for the redundancy constraints. In turn, this produces CG weights that lie the distinct regions described above.
B PROOFS OF MAIN RESULTS
Definition B.1 (Restriction of a concept class), Let F be a concept class (i.e., functions) from Id + R. For any i E [d] and c E Rd-;, we refer to F.(c) as shorthand for
Fil(c) = far f(n, F4, (EF
11

---

Published as a conference paper at ICLR 2026
Proof of Theorem 3.2
Theorem
2.3
guarantees that
mr.(c, 2 fat= Fat (2)
16a
holds for any 0 <<<1, 0< < 10-2 and 0 < < 1. Since F verifies Assumptions and 2 we
first use Lemma B.2 and select de with < 1 that a E (0. 2) get
mr.(c,8) VCdim(F[n))
VCdim(F(n))
64c
128c
where the last inequality holds provided (Cdim(F(m)) 2 2.
Lemma B.2 (Transfer Lemma). With the same notations and assumptions made on the concept class
described in Subsection 3.1 and verifying Assumptions I and 2 then for every 7 E (0, 2)
fat (7) 2 VCdim(F(m))
1 and let r == VCdim(F(n1) = max;e/m] (F(li(FF(nn)). Without loss of generality, will suppose that coordinate maximizing the VC-dimension is the last one (i m). Therefore, for every labeling (y).-.. ) E 13,, there exists E F. such that (g(a;)) )m 2 0 if y: and (g(a.))m 0 y/: --1.
Proof. Let O < <
Assumption guarantees that we can consider that the vectors a1 do intersect the positive orthant because the concept class is closed under translation of the input. This guarantees that we can restrict to list of instances whose admissible region is in the positive orthant.
We construct instances, described by linear equalities, to be fat-shattered by Feror with margin y as follows:
P = {x E R 0 x S 0, 2x1 S 4, 20 S 27, x 2 220
max
x1 x2: x E P, z
Those instances can be lifted to n variables and m constraints, simply by adding redundant constraints and keeping the same objective. We retain the constraint under the form 2x, S 4 rather than simplifying it to S 2, since this representation is more convenient for our choice of regions.
First, since the a, 's are intersecting the positive orthant, the first constraint is redundant, and we will use the vectors a; to shatter the instances. For each instance, the objective of the relaxed problem at the optimum is + + y, and one solution is given by x = 2 and x + 7.
to eliminate the impact of the first constraint on the In the following, we suppose that 0 < i < CG cut.
Consider the two regions in the u2 Ug space associated with the second and third constraint, giving rise to the CG cuts
corresponding to the weights S U2 < -
5
(3 27) and 1 s us <
36 For each
20
36
instance, this yields the inequality: [2ug]ar [ + [2u3] 222 & [4wz + us( + 2y)]
r2 < since < 1
Then, the two new vertices of the feasible region are (2, 1) and (2 7, + 7), and for both
of them the objective value is 3, the amount of gap closed is 1 + y (the improvement
+7 2 3 since < < 1, i.e., here, the cut actually gives the integral solution). 2+
ratio is
For any 1 < - (1 TO
5 7 and 0 < 3-(1-1->) 03 < J the CG-cut associated 4+27
with (u, U2 Uz) yields the incquality 21 S 3: this cut is redundant, the solution is the same as before and the gap closed is O.
Hence, we have two CG-cuts that yield for each instance two gap closed scores that are at least 12()) away from each other.
12

---

Published as a conference paper at ICLR 2026
In the case of B-C-tree size score: The same CG cuts can also be used for the B&C tree size score: on the one hand, it is clear that the branch-and and-cut tree size after adding the first CG-cut is one (solving the LP only once gives an optimal solution that is integral). On the other hand, adding the redundant cut associated with the second cut at the root gives a branch-and-cut tree size of at least 3 nodes since one needs to branch least once variable obtain the integral solution. Therefore, we have two CG cuts that will yield two scores that are at distance for any of the n instances.
91 (A (A)
)0--
For any function 9 in F, 9 R > R2, we refer to و as
92 92(AI,
where A1 is the
ga (AI,-....
first row of A. Since the vectors a, shattered by F, for every y (-1,1} 1) and for every i [n]]
91 (a;
1)
there exists g E F such that g(P.)
92 (a;
ri
where n 2 0f y 1 and m < 0 if
ga aa
y/ -1
Above, we implicitly use Assumption 2 by supposing that the VC dimension of all the coordinates of the functions in F, when restricted to the first entries, is the same. Remind that we now need to apply on top of ğ the squeezing function o' to each coordinate. Using again the Assumption I we rescale the first and second component to 0 and add the appropriate bias to gi and g2 that the following conditions are satisfied (the following intervals correspond to the CG weights computed previously):
Condition #1 = oq:): for every E [n], 0 (q:)) < and 0 S (gg)) < } This can be achieved by multiplying 91 (hence q:) by 0 and adding, for example, the bias (2).
Conditions on U/ = ori)::
If y: 1: o (ri) E | 1 ( 22)]- If y: 1: (r.r)) E 1- 1--- 16 -
Both can be achieved by multiplying the shattering function g2 (hence r;) by and adding the bias o (zz)), where xy := min(1
5 ( 27) 16 1)
36
Conditions on u3 = o' o'():: Let = 3-(1-3-1)
We add the bias to ga so that Vi E [n]:
+22
- If y = 1:
1
< ug <
2
36
If y: 1: 0 <
3
(4-
S ug
< 2.
++24
With in and u2 verifying the above conditions, U3 is the weight deciding which cut is being
selected. Since (0, 1) C a' (ITR), 0)) C [0, 2). o'(0, +o0)) C [ 1] (cf. Definition 3.1. only need to verify for some appropriate positive reals dn and 62:
If y = 1:
77 E [0, 81] such that ((0, 6,)) C
[
20
36
- If y: = 1: ? E [- 0) such that o' o'(l d1(1-2 0)) c 3 (3-1- 1)
+
Such 81 and 8n exist by continuity of a' in the function g3 by the appropriate scalar to ensure those conditions.
2. Using closeness of F under scaling, we can multiply
In summary, when y 1, the weights obtained after applying the squeezing function generate a first CG-cut u whose coordinates are in the first region, and when y: = -1, the weights generating the CG-cut u' are in the second region.
In the first part of the proof, we have shown that the two corresponding regions in the CG cut weight space lead to two scores (for both the gap closed and tree size) that are 2(7) apart: therefore, the instances Pi...., Pn with n = VCdim(F) are fat shattered (with a witness that depends on the score considered), so fat= (7) 2 V[dim(F(n) max4e[m] (.d..(F.(R)).
D
13

---

Published as a conference paper at ICLR 2026
Definition B.3 (seuudodiimension Let F be non-empty collection of functions from input space to R. For any positive integer t, we say that a set [/,, It} S I is pseudo-shattered by F if there exist real numbers $1, .1......5 such that
= (((gg(((()) - sggi...))g(((()) 8t)) : E F)
The pseudo-dimension F, denoted Pdim(FF) NU (+00), is the size of the largest set that can be pseudo-shattered by F.
Proof of Corollary 3.3 We use here the following fact (see Definition above) that for any concept class JF with real outputs, Pdim(F) 2 fat=(y) for all 0, see for example (Anthony & Bartlett 2009 Theorem 11.13).
Also, by assumption each Fi(r)) is closed under translation of the input so if set of vectors #1,"" , are pseudo-shattered. there are also shattered, leading to
VCdim(F.(n)) Pdlim(F.(r) 2 (m))
proving the claim.
Proof of Proposition 3.4 This a direct application of Theorem 3.2 combined with state-of-the art VC-dimension lower bound for ReLU neural networks (Bartlett et al. 2019 Theorem 3).
Proof of Theorem 3.7
We perform a similar reasoning as in the proof of Theorem 2.3 with the following ingredients and similar notations:
we first invoke Lemma B.4 that can be lifted up to more variables if needed. We create collection of instances by adding instance composed of the same instance of Lemma B.4 the redundant constraint a/x < O, where is in the nonnegative orthant.
The underlying concept class maps the vector to one CG cut or the other (CG1 or CG2 in the proof of Lemma B.4), depending on the label for that instance.
the other CG cut, given the This allows us shatter collection of instances by choosing arbitrary {0, 1} labels.
Lemma B.4. There exists two-variable ILP instance with two constraints such that the two cuts from the tableau have both scores (tree size and gap-closed) apart from a constant, positive distance.
Proof. Consider the following instance (same as in Section 2.1
max
5 8
subject to
#1 + 22 < 6
5x 9x2 45
æ1, 22 2 0
31, 322
and the linear program obtained by relaxation of the above, where the last constraint is replaced by 22 R²2 Our goal is to show that two CG cuts derived from the tableau yields two improvements over the initial objective that are far apart by a constant value.
Ater two iterations of the simplex method, the optimal solution given by (7. 17), with an optimal cost of 42. 75. The final optimal tableau of the simplex method (in the original space of two variables) given by
7 35)
so that the two CG cuts are:
3
15
1. (CGI): 2x1 + 322 < 15. We list all the vertices obtained by intersecting with the two constraints. The first one obtained with the constraint Ø1 + 22 = 6, gives the vertex (3, 3). The objective value that point is 15 24 39. The other vertex is (0, 5) with objective value of 40, and change of 1.25 objective (corresponding to the absolute gap closed). Since the other vertices (0, 0), (6, 0) have objective of 0 and 30 respectively, hence (0,5) 5)
14

---

Published as a conference paper at ICLR 2026
is the actual optimal integral solution (it has integral entries). Furthermore, the tree size after adding the cut is 1, whereas is at least 2 without the cut.
2. (CG2): 42, + 7 I 35. Similarly, the two new vertices with greatest objective are ( 4). and 5), with objective value 41.25 and 40 respectively. The gap closed is 1.5 in absolute value, and the tree size is at least after adding the cut (one needs to do an additional round branching because the solution is fractional).
Therefore, the two CG cuts have tree size and gap closed scores and gap close that are distant by positive constant.
XPP
5o1
Figure 1: Example of 2D instance used to construct the lower-bound and prove Lemma B. The
optimal fractional solution is TLP = (g. ) with objective value 42.75. Both cuts CGI (red) and CG2 (green) are two CG cuts derived from the Optimal Tableau. The red cut gives directly the integral optimum Zpp = (0,5) (objective value of 40), after solving one LP (the vertex H (3. 3) has objective value of 39). The green CG cut gives optimal fractional solution G ( 15 with objective value 41.25 and at least one additional IP has to be solved to reach the integral solution. Therefore, both cuts lead to distinct (constant) improvements for both the tree size and the gap closed score. With respect to our original proofs in the tableau case, the vectors of the redundant constraints are mapped to one CG cut vector or the other, to y-shtteer the instances according the score considered.
Proof of Proposition 3.7 This a direct application of Theorem 3.7 combined with state-of-the art VC-dimension lower bound for ReLU neural networks (Bartlett et al. 2019 Theorem 3).
C NUMERICAL EXPERIMENTS
To start the sample complexity analysis computationally, we wish investigate how both scores in the literature relate empirically, based on the premise that (i) the reduction in the B&C tree size is ultimately the score of interest but is costly to obtain and learn, and (ii) the gap closed is easier to compute but less reliable as training signal for the end-task of minimizing the B&C tree size.
potential trade-off emerges: cuts that close large gaps may not always reduce tree size due some situations where both are incomparable (see end of Section 2.1 ). or from branching decisions that change the impact of one cut overall. This setup mirrors classic proxy optimization challenges in machine learning, where want to learn for costly target (tree size), but use cheaper, noisier proxy (gap closed), hoping for performance generalization to the target.
Our computational methodology is based on the two key building blocks: (1) We represent each pair (ILP instance, cut) as a graph, i.e., we encode variables and constraints by a GNN, with proper edges and features. GNNs naturally encode ILP instances well because the solution of an ILP does not depend on the order of the rows, which is captured by the isomorphism invariance of the associated representation. (2) At training time, we generate all the CG cuts from the optimal Simplex tableau
15

---

Published as a conference paper at ICLR 2026
with corresponding scores, for any considered ILP instance. The GNN is trained to match the scores returned for each CG cut via a cross-entropy loss.
Having collected the (up to) CG cuts from the optimal Simplex tableau, and their corresponding scores $1,.... 3m (cither gap closed or B&C tree size reduction), for each of the t instances, we approximate solution of the problem
min Σ
(s))j((()))))))
where E is the instance and cut encoder (described in the next subsection). Hw is GNN parametrized by the weights W, which takes as imput a graph and vectors o, of size m+ + representing the collected cut from the tableau (left-hand side and right-hand side), and & is the cross entropy loss f R xIR"
R. (z, v) + f y) == Ek=1 Uk log(
Ei a
)- At inference time, suppose the trained parameters
given by W. On a new instance I, the CG cut will selected as arg ma Hw (1, o,), and ties are broken in an uniformly random manner.
Table 3: Average tree size 250 test instances of the GNN trained using either the B&C tree size gap closed as a proxy vs. four simple benchmarks. For benchmarks except the GNN one, only the branch-and-cut tree size is reported, as it represents the final quantity of interest in this experiment.
(a) Set cover
(b) Facility location
Setting
B&C. tree
closed
Setting
B&C tree
gap closed
Optimal
4.95
Optimal
86.31
Parallelism
8.29
Parallelism
144.09
Efficacy
9,90
Efficacy
123.63
Mix
9.30
Mix
133.72
Random
9.71
Random
152.46
GNN
8.27
8.65
GNN
128.85
134.61
(c) Knapsack
(d) Vertex cover
Setting
B&C tree
gap closed
Setting
B&C tree
gap closed
Optimal
425.44
Optimal
8.54
Parallelism
576.55
Parallelism
10.15
Efficacy
582.83
Efficacy
9.36
Mix
572.55
Mix
9.55
Random
583.43
Random
10.10
GNN
570.55
571.34
GNN
9.70
9.71
16


Reviews:
[{"review_id": "dnKxQYyhFC", "reviewer": "Reviewer_BtH5", "summary": "The paper proves sample complexity bounds in the setting of learning to cut for solving integer programs. The bounds are for two different scores, branch and cut tree size and gap closed. The theoretical results show that both scores are similarly difficult to learn. Additionally, the paper provides", "questions": "see above", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well written: it illustrates its core ideas through intuitive examples and explanations without sacrificing technical details.\n- The bounds derived don't seem to be vacuous/uninformative. The proofs are also relying on (as far as I can tell) novel constructions that are specific to the problem.\n- To the best of my knowledge, these are the best known nontrivial bounds for this learning problem.\n- The paper also provides an experimental comparison of the learned cuts of a GNN compared to well known heuristics and shows that the GNN can learn to generate cuts that are on par or better compared to those heuristics.", "weaknesses": "- In the proof of 3.2 (Around line 600), you set $a = \\epsilon$ and use the Transfer Lemma. \nDoesn't that mean you take $$\\text{fat} _{\\mathcal{F} _{s,\\sigma'}} (\\frac{\\epsilon}{\\epsilon}) \\geq \\text{VCdim}(\\mathcal{F}[n]) ?$$\nHowever the transfer lemma holds for $\\gamma \\in (0,1/2)$ so I'm not sure you want to do it this way. Maybe set $a=c\\epsilon$ for c at least 2?\n- How necessary is assumption 2 for your result? Are there any architectures that don't qualify? That's perhaps one part I'm a little unclear about and I woud like to see some more comments on.\n- There are a bunch of typos in the document so more careful proofreading is required. For example see lines: 120, 224, 459-460, \n- I am not sure how the experimental section ties into the overall contribution here. I guess it's good to see that GNNs can learn a practically viable heuristic by training on gap closed but it is a bit unclear how that connects to the theoretical findings of the paper.\n\nOverall this is a good paper that I lean towards accepting. There are some (I think minor) issues with the proof and I'm a bit unclear about assumption 2 so I start with a tentative score that I will reconsider after the rebuttal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MkbMhe4rOY", "reviewer": "Reviewer_Fk2R", "summary": "This paper provides the first sample complexity lower bounds for learning to select cutting planes in integer programming. The bounds apply to two performance scores: branch-and-cut tree size and gap closed. The authors show these lower bounds are nearly tight with known upper bounds for neural networks, indicating both scores have comparable learning difficulty. Empirical results demonstrate that gap closed serves as a practical proxy for tree size reduction when training graph neural networks on tableau Chvatal-Gomory cuts.", "questions": "1. Can the $\\epsilon$-dependence gap be closed? Is the true sample complexity $\\Theta(1/\\epsilon)$ or $\\Theta(1/\\epsilon^2)$?\n2. How would sample complexity scale for learning policies that select multiple rounds of cuts?\n3. Would results transfer to production solver configurations with presolve and heuristics enabled?\n4. Do similar lower bounds hold for other cut families beyond Chvatal-Gomory cuts?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. First sample complexity lower bounds for learning-to-cut, establishing theoretical foundations\n2. Lower bounds hold for wide function classes and are nearly tight with upper bounds up to logarithmic factors\n3. Theoretical equivalence between scores provides formal justification for using gap closed as proxy\n4. Proof construction for shattering ILP instances is non-trivial and well-executed\n5. Experiments directly test the core thesis about proxy effectiveness", "weaknesses": "1. Gap between $\\Omega(1/\\epsilon)$ lower bound and $\\Omega(1/\\epsilon^2)$ upper bound for tableau case\n2. Assumptions 1 and 2 restrict generality of theoretical claims\n3. Empirical validation uses small-scale problems in controlled environment and restricted solver configuration\n4. Performance varies: on Facility Location, Efficacy heuristic (123.63) outperforms GNN (134.61)\n5. Experimental setup disables key solver components (presolve, heuristics, default cuts)\n6. Theoretical analysis confined to Chvatal-Gomory cuts from simplex tableau\n7. Learned policy selects single cut at root node, not dynamic cut selection\n8. Worst-case bounds do not leverage structure in real-world MILP distributions\n9. Computational cost of obtaining training samples not addressed theoretically", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Vnz8Z6cvb6", "reviewer": "Reviewer_dRbm", "summary": "This paper studies lower bounds on the sample complexity of learning cut policies for Branch and Cut solvers for integer linear programs.\nA key step in the Branch and Cut framework is adding a cutting plane, which is an additional constraint that tighten the constraint set without eliminating any integral solutions.\nThere are many valid cutting planes to choose from, so traditional B&C implementations have a collection of hand-crafted heuristics designed to choose cuts that lead to fast solution times.\nRecently a line of work has explored the idea of learning cutting plane selection policies from data: given a training collection of ILP instances sampled from some distribution, each instance is solved and the resulting B&C trees are used to train cut selection policies that optimize a utility metric attempting to capture the running time required to solve the problem after the cut is applied.\nThe two most commonly considered metrics are tree-size (the actual size of the resulting B&C tree, which is strongly predictive of the runtime), and the gap-closed metric, which measures the reduction in the optimality gap after introducing the cut.\nSome prior work has provided upper bounds on the sample complexity of learning such cutting policies when the utility metric is the size of the resulting tree (but the authors claim that it can be generalized to the gap-reduction metric straight forwardly).\n\nThis paper has two main high-level contributions:\n1. The authors derive sample complexity lower bounds for learning cut selection policies from data under fairly realistic assumptions. In particular, together with the upper bounds from prior work, they establish that the sample complexity is comparable for both the the gap-closed and tree-size metrics.\n2. The authors empirically find that the gap-closed metric is a suitable proxy for the tree-size metric. This is useful because the gap-closed metric is much more computationally efficient to evaluate when generating training data.\n\nTaken together, these results support the use of gap-closed for learning cut selection policies. It is not harder to learn than the tree-size metric from a sample complexity point of view, still provides a reasonable proxy for solution time, and is easier to calculate.", "questions": "- On line 308, should it say \"returns a vector in $[0,1]^m$\" instead of $[0-1]^m$?\n- On line 309, should it say that the function is \"continuous at 1/2\"?\n- Table 2 seems to be missing some results for Facility Location compared to Table 3 in the appendix (i.e., the first column is all dashes instead of having an entry for GNN).\n- In both Table 2 and Table 3, should the second column be \"gap closed\" and the third column be \"B&C tree\". The titles aren't consistent, but if I understand what is being reported, it seems like the dashes should always appear in the \"gap closed\" column.\n- In Tables 2 and 3, since only GNN has a gap-closed variant, I wonder if it would make sense to have a single column and just include two versions of GNN: \"GNN-Tree-Size\" and \"GNN-Gap-Closed\".", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem of learning cut selection policies for the branch and cut framework is interesting and very practical, and this paper provides the first lower bounds on sample complexity for this problem.\nThe findings that the gap-reduction metric is a suitable approximation to tree-size also useful.\nOverall I found the paper well written and feel like the main contributions were clearly communicated.", "weaknesses": "I would have liked for more of the key sample complexity lower bound argument to be sketched in the main body of the paper.\nFor example, in the discussion of Proposition 3.4, it is stated that the approach ignores $n \\times m + m$ of the inputs, and I was curious to understand why.\nThere are also a number of minor typos throughout the paper, and a few significant ones in the experimental results (unless I have misunderstood something).\n\nI think at the beginning of Section 2.2, the authors could include a little bit more detail about the notation. At first I had some trouble identifying the role played by the functions $f$ and $h$ in equation (2).\n\nA few of the minor typos I noticed:\n- Line 120: \"Ou results\" -> \"Our results\"\n- Line 169: \"that can derived at any iteration\" -> \"that can be...\"?\n- Line 181: Maybe \"so this motivates the idea of learning such a score\"?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6y2GBuHy21", "reviewer": "Reviewer_hSqs", "summary": "The paper provides the first sample-complexity lower bounds for the “learning-to-cut” framework in branch-and-cut MILP solvers. It proves that, for neural-network policies mapping an ILP instance to a Chvátal–Gomory cut, minimising either tree-size or gap-closed requires  \nΩ(VCdim(F)/ε) samples, i.e. as many samples as learning any generic real-valued target with squared loss. The bounds are shown tight up to log factors for ReLU nets. Complementary experiments on four NP-hard problems indicate that a GNN trained on the cheap “gap-closed” proxy achieves tree-size reductions close to the expensive oracle, corroborating the theoretical insight that the two scores are equally learnable.", "questions": "1. Do the lower bounds hold for batch cut selection?  \n   If the learner outputs a set of cuts instead of a single one, does the sample complexity lower bound still apply? Is a new theoretical framework needed?\n2. Can the bounds be extended to general cut families?  \n   Is it possible to generalize the lower bounds beyond CG cuts to split cuts, GMI cuts, or other stronger cut classes?\n3. Can tighter bounds be obtained under structured distributions?  \n   If instances are drawn from structured generative models (e.g., stochastic block-model IPs or Gaussian `A, b`), can we prove tighter sample complexity bounds?\n4. Can we derive a distribution-dependent upper bound for gap-closed?  \n   Can the conjecture — that only cuts separating the fractional solution matter — be leveraged to derive a tighter, distribution-dependent upper bound on the sample complexity of learning with gap-closed?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. Theoretically pioneering: First distribution-free lower bounds for learning-to-cut; closes the loop with recent upper bounds [Balcan et al. 2021, Cheng et al. 2024].  \n2. Generality: Results hold for any encoder–network family that satisfies minimal closure assumptions; not restricted to CG or tableau cuts.  \n3. Tightness: Lower bound Ω(WL log(W/L)/ε) matches the best-known upper bound Õ(WL/ε²) for ReLU nets, showing no exponential gap.  \n4. Empirical validation: Carefully designed GNN experiments demonstrate that gap-closed is a practical surrogate for tree-size, bridging theory–practice.  \n5. Clarity: Proof roadmap and supplementary document are rigorous and well written.", "weaknesses": "1. Restricted concept class: The lower bounds are proved only for single-cut selection, whereas modern solvers add batches (rounds) of cuts. It remains unclear whether the lower bound still holds when the learner outputs a *set* of cuts.\n2. CG-only cutting regime: The lower bounds rely exclusively on Chvátal–Gomory (CG) cuts. Extending the results to more general cut families such as split cuts, GMI cuts, or knapsack cuts would significantly strengthen the theoretical claims.\n3. Instance distribution: overly general setting: The lower bounds are worst-case over all possible distributions, without considering structured or parametric families (e.g., IPs generated from stochastic block models or Gaussian-distributed `A, b`). This may lead to overly pessimistic bounds.\n4. No information-theoretic upper bound for gap-closed: While the authors conjecture that only cuts separating the fractional solution matter, they do not provide a distribution-dependent upper bound based on this insight. Thus, the sample complexity of gap-closed remains only partially characterized.\n5. Limited empirical scope: Experiments are conducted only on small synthetic instances (≤ 50 variables). There is no validation on medium-scale realistic benchmarks such as the “easy” subset of MIPLIB 2017, leaving open whether the proxy quality degrades on real-world IPs.\n6. Missing baselines: The empirical evaluation lacks comparison with recent learning-based cut selectors, such as LLM-guided methods (LIFT-FE, TransGPT-FE) or imitation learning with tree-size experts (Paulus et al., 2022), making it hard to assess the relative strength of the proposed approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)