Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut

Authors: hongyu  cheng
sammy  khalife
barbara  fiedorowicz
amitabh  basu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 19:40:50

Abstract: Data-driven algorithm design is a paradigm that uses statistical and machine learning techniques to select from a class of algorithms for a computational problem an algorithm that has the best expected performance with respect to some (unknown) distribution on the instances of the problem. We build upon recent work in this line of research by considering the setup where, instead of selecting a single algorithm that has the best performance, we allow the possibility of selecting an algorithm based on the instance to be solved, using neural networks. In particular, given a representative sample of instances, we learn a neural network that maps an instance of the problem to the most appropriate algorithm *for that instance*. We formalize this idea and derive rigorous sample complexity bounds for this learning problem, in the spirit of recent work in data-driven algorithm design. We then apply this approach to the problem of making good decisions in the branch-and-cut framework for mixed-integer optimization (e.g., which cut to add?). In other words, the neural network will take as input a mixed-integer optimization instance and output a decision that will result in a small branch-and-cut tree for that instance. Our computational results provide evidence that our particular way of using neural networks for cut selection can make a significant impact in reducing branch-and-cut tree sizes, compared to previous data-driven approaches.

Main paper: 
 background and motivation: 
 Often there are several competing algorithms for a computational problem and no single algorithm dominates all the others. The choice of an algorithm in such cases is often dictated by the "typical" instance one expects to see, which may differ from one application context to another. Data-driven algorithm design has emerged in recent years as a way to formalize this question of algorithm selection and draws upon statistical and machine learning techniques; see Balcan [2020] for a survey and references therein. More formally, suppose one has a class I of instances of some computational problem with some unknown distribution, and a class of algorithms that can solve this problem parameterized by some "tunable parameters". Suppose that for each setting of the parameters, the corresponding algorithm can be evaluated by a score function that tells us how well the algorithm does on different instances (e.g., running time, memory usage etc.). We wish to find the set of parameters that minimizes (or maximizes, depending on the nature of the score) the expected score on the instances (with respect to the unknown distribution), after getting access to an i.i.d. sample of instances from the distribution. For example, I could be a family of mixed-integer optimization problems and the class of algorithms are branch-and-cut methods with their different possible parameter settings, and the score function could be the size of the branch-and-cut tree.In Balcan et al. [2021a] , the authors prove a central result on the sample complexity of this problem: if for any fixed instance in I, the score function has a piecewise structure as a function of the parameters, where the number of pieces is upper bounded by a constant R independent of the instance, the pieces come from a family of functions of "low complexity", and the regions partitioning the parameter space into pieces have "low complexity" in terms of their shape, then the sample complexity is a precise function of R and these two complexity numbers (formalized by the notion of pseudo-dimension -see below). See Theorem 3.3 in Balcan et al. [2021a] for details. The authors then proceed to apply this key result to a diverse variety of algorithmic problems ranging from computational biology, computational economics to integer optimization.Our work in this paper is motivated by the following consideration. In many of these applications, one would like to select not a single algorithm, i.e., a single setting of the parameters, but would like to decide on the parameters after receiving a new instance of the problem. In other words, we would like to learn not the best parameter, but the best mapping from instances to parameters. We consider this version of the problem, where the mapping is taken from a class of neural network functions. At a high level, switching the problem from finding the "best" parameter to finding the "best" mapping in a parameterized family of mappings gives the same problem: we now have a new set of parameters -the ones parameterizing the mappings (neural networks) -and we have to select the best parameter. And indeed, the result from Balcan et al. [2021a] can be applied to this new setting, as long as one can prove good bounds on pseudo-dimension in the space of these new parameters. The key point of our result is two fold:1. Even if original space of parameters for the algorithms is amenable to the analysis of pseudodimension as done in Balcan et al. [2021a] , it is not clear that this immediately translates to a similar analysis in the parameter space of the neural networks, because the "low complexity piecewise structure" from the original parameter space may not be preserved.2. We suspect that our proof technique results in tighter sample complexity bounds, compared to what one would obtain if one could do the analysis from Balcan et al. [2021a] in the parameter space of the neural network directly. However, we do not have quantitative evidence of this yet because their analysis seems difficult to carry out directly in the neural parameter space.One of the foundational works in the field of selecting algorithms based on specific instances is Rice [1976] , and recently, Gupta and Roughgarden [2016] , Balcan et al. [2021c] have explored the sample complexity of learning mappings from instances to algorithms for particular problems. Our approach is also related to recent work on algorithm design with predictions; see Mitzenmacher and Vassilvitskii [2022] for a short introduction and the references therein for more thorough surveys and recent work. However, our emphasis and the nature of our results are quite different from the focus of previous research. We establish sample complexity bounds for a general learning framework that employs neural networks to map instances to algorithms, which is suitable for handling some highly complex score functions, such as the size of the branch-and-cut tree. The introduction of neural networks in our approach bring more intricate technical challenges than traditional settings like linear predictors or regression trees Gupta and Roughgarden [2016] . On the application side, as long as we know some information about the algorithms (see Theorems 2.5 and 2.6), our results can be directly applied. This is demonstrated in this paper through applications to various cutting plane selection problems in branch-and-cut in Propositions 3.3, 3.5, 3.6 and 3.7. Several references to fundamental applied work in data-driven algorithm selection can be found in the Balcan [2020] , Gupta and Roughgarden [2016] , Balcan et al. [2021a,c] .1.1 Applications in branch-and-cut methods for mixed-integer linear optimization Mixed-integer linear optimization is a powerful tool that is used in a diverse number of application domains. Branch-and-cut is the solution methodology of choice for all state-of-the-art solvers for mixed-integer optimization that is founded upon a well-developed theory of convexification and systematic enumeration Schrijver [1986], Nemhauser and Wolsey [1988] , Conforti et al. [2014] . However, even after decades of theoretical and computational advances, several key aspects of branch-and-cut are not well understood. During the execution of the branch-and-cut algorithm on an instance, the algorithm has to repeatedly make certain decisions such as which node of the search tree to process next, whether one should branch or add cutting planes, which cutting planes to add, or which branching strategy to use. The choices that give a small tree size for a particular instance may not be good choices for a different instance and result in a much larger tree. Thus, adapting these choices to the particular instance can be beneficial for overall efficiency. Of course, the strategies already in place in the best implementations of branch-and-cut have to adapt to the instances. For example, certain cutting plane choices may not be possible for certain instances. But even beyond that, there are certain heuristics in place that adapt these choices to the instance. These heuristics have been arrived at by decades of computational experience from practitioners. The goal in recent years is to provide a data driven approach to making these choices. In a recent series of papers Balcan et al. [2021a Balcan et al. [ ,d,b, 2022 Balcan et al. [ , 2018]] , the authors apply the general sample complexity result from Balcan et al. [2021a] in the specific context of branch-and-cut methods for mixed-integer linear optimization to obtain several remarkable and first-of-their-kind results. We summarize here those results that are most relevant to the cut selection problem since this is the focus of our work.1. In Balcan et al. [2021d] , the authors consider the problem of selecting the best Chvátal-Gomory (CG) cutting plane (or collection of cutting planes) to be added at the root node of the branch-and-cut tree. Thus, the "tunable parameters" are the possible multipliers to be used to generate the CG cut at the root node. The score function is the size of the resulting branch-and-cut tree. The authors observe that for a fixed instance of a mixed-integer linear optimization problem, there are only finitely many CG cuts possible and the number can be bounded explicitly in terms of entries of the linear constraints of the problem. Via a sophisticated piece of analysis, this gives the required piecewise structure on the space of multipliers to apply the general result explained above. This gives concrete sample complexity bounds for choosing the multipliers with the best expected performance. See Theorem 3.3, 3.5 and 3.6 in Balcan et al. [2021d] for details. Note that this result is about selecting a single set of multipliers/cutting planes that has the best expected performance across all instances. This contrasts with selecting a good strategy to select multipliers depending on the instance, that has good expected performance (see point 2. below). 2. The authors in Balcan et al. [2021d] also consider the problem of learning a good strategy that selects multipliers based on the instance. In particular, they consider various auxiliary score functions used in integer optimization practice, that map a pair of instance I and a cutting plane c for I that measures how well c will perform for processing I. The strategy will be a linear function of these auxiliary scores, i.e., a weighted average of these auxiliary scores, and the learning problem becomes the problem of finding the best linear coefficients for the different auxiliary scores. So now these linear coefficients become the "tunable parameters" for the general result from Balcan et al. [2021a] . It is not hard to find the piecewise structure in the space of these new parameters, given the analysis in the space of CG cut multipliers from point 1. above. This then gives concrete sample complexity bounds for learning the best set of weights for these auxiliary score functions for cut selection. See Theorem 4.1 and Corollary 4.2 in Balcan et al. [2021d] for details. 3. In all the previous results discussed above, the cutting planes considered were CG cuts, or it was essentially assumed that there are only a finite number of cutting planes available at any stage of the branch-and-cut algorithm. In the most recent paper Balcan et al. [2022] , the authors consider general cutting plane paradigms, and also consider the possibility of allowing more general strategies to select cutting planes beyond using weighted combinations of auxiliary score functions. They uncover the subtlety that allowing general mappings from instances to cutting planes can lead to infinite sample complexity and learning such mappings could be impossible, if the class of mappings is allowed to be too rich. See Theorem 5.1 in Balcan et al. [2022] . This point will be important when we discuss our approach below. On the positive side, they show that the well-known class of Gomory-Mixed-Integer (GMI) cuts has a similar structure to CG cuts, and therefore, using similar techniques as discussed above, they derive sample complexity bounds for selecting GMI cuts at the root node. See Theorem 5.5 in Balcan et al. [2022] . As far as we understand, the analysis should extend to the problem of learning weighted combinations of auxiliary score functions to select the GMI cuts as well using the same techniques as Balcan et al. [2021d] , although the authors do not explicitly do this in Balcan et al. [2022] .Our approach and results. Our point of departure from the line of work discussed above is that instead of using weighted combinations of auxiliary scores to select cutting planes, we wish to select these cutting planes using neural networks that map instances to cutting planes. In other words, in the general framework described above, the "tunable parameters" are the weights of the neural network.The overall score function is the size of the branch-and-cut tree after cuts are added at the root. We highlight the two main differences caused by this change in perspective.1. In the approach where weighted combinations of auxiliary score functions are used, after the weights are learnt from the sample instances, for every new/unseen instance one has to compute the cut that maximizes the weighted score. This could be an expensive optimization problem in its own right. In contrast, with our neural approach, after training the net (i.e., learning the weights of the neural network), any new instance is just fed into the neural network and the output is the cutting plane(s) to be used for this instance. This is, in principle, a much simpler computational problem than optimizing the combined auxiliary score functions over the space of cuts.2. Since we use the neural network to directly search for a good cut, bypassing the weighted combinations of auxuliary scores, we actually are able to find better cuts that reduce the tree sizes by a significant factor, compared to the approach of using weighted combinations auxiliary scores.The above two points are clearly evidenced by our computational investigations which we present in Section A. The theoretical sample complexity bounds for cut selection are presented in Section 3. As mentioned before, these are obtained using the main sample complexity result for using neural networks for data driven algorithm design that is presented in Section 2.Comparison with prior work on cut selection using learning techniques. As already discussed above, our theoretical sample complexity work in cut selection is closest in spirit to the work in Balcan et al. [2021a Balcan et al. [ ,d,b, 2022 Balcan et al. [ , 2018]] . However, there are several other works in the literature that use machine learning ideas to approach the problem of cut selection; see Deza and Khalil [2023] for a survey. Tang et al. Tang et al. [2020] initiated the exploration of applying Reinforcement Learning (RL) to select CG cuts derived from the simplex tableau. Huang et al. Huang et al. [2022] apply supervised learning to rank a "bag of cuts" from a set of cuts to reduce the total runtime. More recently, the authors in Turner et al. [2023] propose a novel strategy that use RL and Graph Neural Networks (GNN) to select instance-dependent weights for the combination of auxiliary score functions.Our computational investigations, as detailed in Appendix A, distinguishes itself from these prior computational explorations in several key aspects:1. Previous methods were limited to a finite set of candidate cuts, requiring either an optimal simplex tableau or relying on a finite collection of combinatorial cuts. In contrast, our approach allows the possibility of selecting from a possibly infinite family of cutting planes. Moreover, our method eliminates the need for computing a simplex tableau which can lead to a significant savings in computation (see Table 1 and the discussion in Section A.2).2. Many prior studies aimed at improving the objective value rather than directly reducing the branch-and-cut runtime-with the exception of Huang et al. Huang et al. [2022] , who explored this through supervised learning. To the best of our knowledge, our RL-based model is the first to directly target the reduction of the branch-and-cut tree size as its reward metric, which is strongly correlated with the overall running time.3. Prior deep learning approaches are not underpinned by theoretical guarantees, such as sample complexity bounds. Our empirical work takes the theoretical insights for the branch-and-cut problem presented in Theorem 2.3 and Proposition 3.3 as its basis.The limitations of our approach are discussed in Section 4.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: The abstract and introduction indeed clearly state the main contributions and scope of the paper.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
formal statement of results: 
 We denote [d] as the set {1, 2, . . . , d} for any positive integer d ∈ Z + . For a set of vectors {x 1 , . . . , x t } ⊆ R d , we use superscripts to denote vector indices, while subscripts specify the coordinates in a vector; thus, x i j refers to the j-th coordinate of x i . Additionally, the sign function, denoted as sgn : R → {0, 1}, is defined such that for any x ∈ R, sgn(x) = 0 if x < 0, and 1 otherwise. This function is applied to each entry individually when applied to a vector. Lastly, the notation ⌊•⌋ is used to indicate the elementwise floor function, rounding down each component of a vector to the nearest integer. Definition 2.2 (Pseudo-dimension). Let F be a non-empty collection of functions from an input space I to R. For any positive integer t, we say that a set {I 1 , ..., I t } ⊆ I is pseudo-shattered by F if there exist real numbers s 1 , . . . , s t such that2 t = |{(sgn(f (I 1 ) -s 1 ), . . . , sgn(f (I t ) -s t )) : f ∈ F}| .The pseudo-dimension of F, denoted as Pdim(F) ∈ N ∪ {+∞}, is the size of the largest set that can be pseudo-shattered by F.The main goal of statistical learning theory is to solve a problem of the following form, given a fixed parameterized function class defined by some h with output space O = R:EQUATIONfor an unknown distribution D, given access to i.i.d. samples I 1 , . . . , I t from D. In other words, one tries to "learn" the best decision p for minimizing an expected "score" with respect to an unknown distribution given only samples from the distribution. Such a "best" decision can be thought of as a property of the unknown distribution and the problem is to "learn" this property of the unknown distribution, only given access to samples.The following is a fundamental result in empirical processes theory and is foundational for the above learning problem; see, e.g., Chapters 17, 18 and 19 in Anthony et al. [1999] , especially Theorem 19.2. Theorem 2.3. There exists a universal constant C such that the following holds. Let H be a hypothesis class defined by some h :I × P → R such that the range of h is in [0, B] for some B > 0.For any distribution D on X , ϵ > 0, δ ∈ (0, 1), andt ≥ CB 2 ϵ 2 Pdim(H) ln B ϵ + ln 1 δ ,we have1 t t i=1 h(I i , p) -E I∼D [h(I, p)] ≤ ϵ for all p ∈ P,with probability 1 -δ over i.i.d. samples I 1 , . . . , I t ∈ I of size t drawn from D.Thus, if one solves the sample average problem min p∈P 1 t t i=1 h(I i , p) with a large enough sample to within O(ϵ) accuracy, the corresponding p would solve (1) to within O(ϵ) accuracy (with high probability over the sample). Thus, the pseudo-dimension Pdim(H) is a key parameter that can be used to bound the size of a sample that is sufficient to solve the learning problem.We formalize the definition of neural networks for the purposes of stating our results. Given any function σ : R → R, we will use the notation σ(x) for x ∈ R d to mean [σ(x 1 ), σ(x 2 ), . . . , σ(x d )] T ∈ R d .Definition 2.4 (Neural networks). Let σ : R → R and let L be a positive integer. A neural network with activation σ and architecture w= [w 0 , w 1 , . . . , w L , w L+1 ] T ∈ Z L+2 + is a paremterized function class, parameterized by L + 1 affine transformations {T i : R wi-1 → R wi , i ∈ [L + 1]} with T L+1linear, is defined as the functionT L+1 • σ • T L • • • • T 2 • σ • T 1 .L denotes the number of hidden layers in the network, while w i signifies the width of the i-th hidden layer for i ∈ [L]. The input and output dimensions of the neural network are denoted by w 0 and w L+1 , respectively. If T i is represented by the matrixA i ∈ R wi×wi-1 and vector b i ∈ R wi , i.e., T i (x) = A i x + b i for i ∈ [L + 1],then the weights of neuron j ∈ [w i ] in the i-th hidden layer come from the entries of the j-th row of A i while the bias of the neuron is indicated by the j-th coordinate of b i . The size of the neural network is defined asw 1 + • • • + w L , denoted by U .In the terminology of Definition 2.1, we define the neural network parameterized functions N σ : R w0 × R W → R w L+1 , with R w0 denoting the input space and R W representing the parameter space. This parameter space is structured through the concatenation of all entries from the matrices A i and vectors b i , for i ∈ [L + 1], into a single vector of length W . The functions are defined asN σ (x, w) = T L+1 (σ(T L (• • • T 2 (σ(T 1 (x))) • • • )))for any x ∈ R w0 and w ∈ R W , where each T i represents the affine transformations associated with w ∈ R W .In the context of this paper, we will focus on the following activation functions:• sgn: The Linear Threshold (LT) activation function sgn : R → {0, 1}, which is defined as sgn(x) = 0 if x < 0 and sgn(x) = 1 otherwise.• ReLU: The Rectified Linear Unit (ReLU) activation function ReLU : R → R ≥0 is defined as ReLU(x) = max{0, x}. • CReLU: The Clipped Rectified Linear Unit (CReLU) activation function CReLU : R → [0, 1] is defined as CReLU(x) = min{max{0, x}, 1}.• Sigmoid: The Sigmoid activation function Sigmoid : R → (0, 1) is defined asSigmoid(x) = 1 1+e -x .In this study, we extend the framework introduced by Balcan et al. Balcan et al. [2021a] to explore the learnability of tunable algorithmic parameters through neural networks. Consider a computational problem given by a family of instances I. Let us say we have a suite of algorithms for this problem, parameterized by parameters in P. We also have a score function that evaluates how well a particular algorithm, given by specific settings of the parameters, performs on a particular instance. In other words, the score function is given by S :I × P → [0, B], where B ∈ R + determines a priori upper bound on the score. The main goal of data-driven algorithm design is to find a particular algorithm in our parameterized family of algorithms -equivalently, find a parameter setting p ∈ P -that minimizes the expected score on the family of instances with respect to an unknown distribution on I, given access to a sample of i.i.d instances from the distribution. This then becomes a special case of the general learning problem (1), where h = S and one can provide precise sample complexity bounds via Theorem 2.3, if one can bound the pseudo-dimension of the corresponding hypothesis class. A bound on this pseudo-dimension is precisely the central result in Balcan et al. [2021a] ; see the discussion in Section 1.We assume the parameter space P is a Cartesian product of intervals[η 1 , τ 1 ] × • • • × [η ℓ , τ ℓ ], where η i ≤ τ i for each i ∈ [ℓ].The transformation from the instance space I to the parameter space P is structured through the following mappings:1. An encoder function Enc : I → R d is defined to convert an instance I ∈ I into a vector x = Enc(I) ∈ R d , facilitating the instances to be suitably processed by a neural network.A simple example of such an encoder could be a compilation of all the instance's numerical data into a single vector; but one can allow encodings that use some predetermined features of the instances. 2. A family of neural network mappings, denoted as N σ : R d × R W → R ℓ , is utilized. These mappings are characterized by an activation function σ, and a fixed architecture represented by w = [d, w 1 , . . . , w L , ℓ] ∈ Z L+2 + . For any given neural network parameters w ∈ R W , this network maps an encoded instance x ∈ R d into y := N σ (x, w) ∈ R ℓ . 3. A squeezing activation function, σ ′ : R → [0, 1], is introduced to adjust the neural network's output to the parameter space P. The parameter p ∈ P is computed byp i = η i + (τ i - η i )σ ′ (y i ) for i = 1, . . . , ℓ.The composite mapping from the instance space I to the parameter space P is denoted by φ N σ ,σ ′ w , since the results of this study are applicable for any fixed and predetermined encoder function Enc.The problem of learning the best neural mapping then becomes the learning problem (1) with h : I × R W → R defined by h(I, w) := S I, φ N σ ,σ ′ w (I) . We useF S N σ ,σ ′ := S •, φ N σ ,σ ′ w (•) : I → [0, B] | w ∈ R Wto denote the corresponding hypothesis class (Definition 2.1).Our first result employs linear threshold neural networks for generating algorithm parameters, inspired by their analytically tractable structure and rich expressive capabilities, as supported by findings in Khalife et al. [2023] .Theorem 2.5. Consider a set I of instances of a computational problem with a suite of algorithms parameterized by In addition to this, we investigate the sample complexity associated with the use of ReLU neural networks for parameter selection. Theorem 2.6. Under the same conditions as Theorem 2.5, with ReLU neural networks N ReLU : R d × R W → R ℓ having the same fixed architecture and clipped ReLU squeezing function, we haveP = [η 1 , τ 1 ] × • • • × [η ℓ , τ ℓ ],Pdim F S N ReLU ,CReLU = O (LW log(U + ℓ) + W log(γΓ(λ + 1))) . Remark 2.7. Theorem 2.6 can be easily extended to the case where general piecewise polynomial activation functions are used instead of ReLU, with each function having at most p ≥ 1 pieces and degree at most q ≥ 1. By applying the same proof techniques as in the theorem above and using Theorem 7 in Bartlett et al. [2019] , the pseudo-dimension changes to O LW log(p(U + ℓ)) + L 2 W log(q) + W log(γΓ(λ + 1)) . While we present the ReLU case as the main theorem due to its common use in practical applications, from a theoretical perspective, ReLU activation functions are not fundamentally different from other piecewise polynomial activation functions in the context of this paper.It is not hard to adapt the proofs of Theorem 2.5 and Theorem 2.6 to show that if any dimension of the parameter space is all of R rather than a bounded interval, the pseudo-dimension bounds will only be smaller, under the same conditions. Additionally, if P = {p 1 , . . . , p r } is a finite set, the problem can be viewed as a multi-classification problem. That is, consider a neural network N σ : R d × R W → R r , where for any x ∈ R d and w ∈ R W , N σ (x, w) outputs an r-dimensional vector, and we select the parameter corresponding to the largest dimension. The pseudo-dimension of this problem is given by the following: Corollary 2.8. Under the same conditions as Theorem 2.5 and 2.6, but with P = {p 1 , . . . , p r },Pdim(F S N sgn ,Sigmoid ) = O (W log(U r)) and Pdim(F S N ReLU ,CReLU ) = O (LW log(U + r)) .3 Application to branch-and-cut 3.1 Preliminaries Definition 3.1 (Integer linear programming (ILP)). Let m, n ∈ N + be fixed natural numbers, and letA ∈ Q m×n , b ∈ Q m , c ∈ R n .The integer linear programming problem is formulated asmax{c T x : Ax ≤ b, x ≥ 0, x ∈ Z n }.The most successful algorithms and solvers for integer programming problems are based on a methodology called branch-and-cut. In a branch-and-cut algorithm, one maintains two things in every iteration of the algorithm: 1) a current guess for the optimal solution, 2) a collection of polyhedra that are subsets of the original polyhedral relaxation of the ILP. In every iteration, one of these polyhedra are selected and the continuous linear programming (LP) solution for that selected polyhedron is computed. If the solution has objective value worse than the current guess, this polyhedron is discarded from the list and the algorithm moves to the next iteration. Otherwise, if the solution is integral, the guess is updated with this integral solution and this polyhedron is removed from further consideration. If the LP solution is not integral, one decides to either add some cutting planes or branch. In the former case, additional linear constraints are added to this polyhedron under consideration without eliminating any feasible solutions. In the latter case, one selects a fractional variable x i in the LP solution and partitions the current polyhedron into two polyhedra by adding constraints x i ≤ ⌊f i ⌋ and x i ≥ ⌊f i ⌋ + 1, where f i is the value of this fractional variable. The current polyhedron is then replaced in the list by these two new polyhedra. This entire process can be tracked by a branch-and-cut tree whose nodes are precisely the different polyhedra processed by the algorithm. The algorithm terminates when there are no more polyhedra left in the active list and the current guess is reported as the optimal solution. As is often done in practice, an a priori bound B is set on the size of a tree; if this bound is exceeded by the algorithm at any stage, the algorithm exist early and the current guess for the solution is returned. The branch-and-cut tree size is a very good indication of how long the algorithm takes to solve the problem since the main time is spent on solving the individual LPs in the iterations of the algorithm. We will thus use the tree size as the "score" function to decide how well branch-and-cut did on any instance.There are many different strategies to generate cutting planes in branch-and-cut Conforti et al. [2014] , Nemhauser and Wolsey [1988] , Schrijver [1986] . We will focus on the so-called Chvátal-Gomory (CG) cutting planes and Gomory Mixed-Integer (GMI) cuts Conforti et al. [2014] . There are usually several choices of such cutting planes to add (and some families are even infinite in size Conforti et al. [2014] ). We wish to apply the results of Section 2 to decide which cutting plane to select so that the branch-and-cut tree size is small.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: The limitations of our work are adequately discussed in the final section of the paper.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
learnability of parameterized cg cut(s): 
 Let m, n be positive integers. We consider the ILP instance space I ⊆ {(A, b, c) : Balcan et al. [2021d] , we define f CG (I, u) as the size of the branch-andbound tree for a given ILP instance I ∈ I with a CG cut parameterized by a multiplier u ∈ [0, 1] m added at the root. We interpret f CG as a score function elaborated in Section 2.2. The piecewise structure of f CG in its parameters is characterized by: Lemma 3.2 (Lemma 3.2 in Balcan et al. [2021d] ). For any ILP instance I ∈ I, there are at most M := 2(a+b+n) hyperplanes partitioning the parameter space [0, 1] m into regions where f CG (I, u) remains constant for all u within each region.A ∈ Q m×n , b ∈ Q m , c ∈ R n },Applying Theorem 2.5 and Theorem 2.6 to f CG yields these pseudo-dimension bounds: Proposition 3.3. Under the same conditions as Theorem 2.5 and 2.6, with the score function f CG ,Pdim F fCG N sgn ,Sigmoid = O (W log(U M )) , Pdim F fCG N ReLU ,CReLU = O (LW log(U + m) + W log M ) .Extending this to adding k CG cuts sequentially, we define f k CG (I, (u 1 , . . . , u k )) as the branch-andbound tree size after adding a sequence of k CG cuts parameterized by u 1 , . . . , u k at the root for a given ILP instance I ∈ I. The piecewise structure of f k CG in its parameters is given by: Lemma 3.4 (Lemma 3.4 in Balcan et al. [2021d] ). For any ILP instance I ∈ I, there are O(k2 k M ) multivariate polynomials with mk + k(k -1)/2 variables and degree at most k partitioning the parameter space [0, 1] mk+k(k-1)/2 into regions where f k CG (I, (u 1 , . . . , u k )) remains constant for all (u 1 , . . . , u k ) within each region.Accordingly, the pseudo-dimension bounds are Proposition 3.5. Under the same conditions as Theorem 2.5 and 2.6, with the score functionf k CG , Pdim F f k CG N sgn ,Sigmoid = O (W log(U M ) + W k) , Pdim F f k CG N ReLU ,CReLU = O (LW log(U + mk) + W log M + W k) .The selection of an optimal cut from an infinite pool of candidate cuts, as discussed in Proposition 3.3 and Proposition 3.5, is often difficult and inefficient in practice. Consequently, a popular way is to select cuts based on information from the simplex tableau (such as GMI cuts), as well as some combinatorial cuts, which inherently limit the number of candidate cuts considered to be finite.Suppose we have a finite set of cuts C, and we define f ROW (I, c) as the branch-and-bound tree size after adding a cut c ∈ C at the root for a given ILP instance I ∈ I. Then Corollary 2.8 implies Proposition 3.6. Under the same conditions as Theorem 2.5 and 2.6, with the score function f ROW ,Pdim F fROW N sgn ,Sigmoid = O (W log(U |C|)) and Pdim F fROW N ReLU ,CReLU = O (LW log(U + |C|)) .One of the leading open-source solvers, SCIP Gamrath et al. [2020] , uses cut selection methodologies that rely on combining several auxiliary score functions. For a finite set of cutting planes C, instead of directly using a neural network for selection, this model selects c * ∈ arg max c∈C ℓ i=1 µ i Score i (c, I) for each instance I ∈ I. Here, Score i represents different heuristic scoring functions that assess various aspects of a cut, such as "Efficacy" Balas et al. [1996] and "Parallelism" Achterberg [2007] , for a specific instance I, and the coefficients µ ∈ [0, 1] ℓ are tunable weights for these scoring models. Since C is considered to be finite, the above optimization problem is solved through enumeration. The authors in Turner et al. [2023] have experimentally implemented the idea of using a neural network to map instances to weights. We provide an upper bound on the pseudo-dimension in the following proposition of this learning problem. Proposition 3.7. Under the same conditions as Theorem 2.5 and 2.6, let f S (I, µ) denote the size of the branch-and-bound tree for I after adding a cutting plane determined by the weighted scoring model parameterized by µ ∈ [0, 1] ℓ . The pseudo-dimension bounds are given by:Pdim F f S N sgn ,Sigmoid = O (W log(U |C|)) , Pdim F f S N ReLU ,CReLU = O (LW log(U + ℓ) + W log(|C|)) .Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: This paper has no societal impact. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
discussions and open questions: 
 In our study, we concentrated on adding CG cuts solely at the root of the branch-and-cut tree. However, devising a strategy that generates high quality cutting planes while being efficient across the entire branch-and-cut tree poses a significant and intriguing challenge for future research. Further, our theoretical findings are applicable to any encoder that maps instances into Euclidean spaces. Hence, utilizing a fixed encoder capable of converting ILPs with different number of constraints into a same Euclidean space can in principle enable the training of a unified neural network to generate cutting planes across the branch-and-cut tree. Moreover, an effective encoder could improve the neural network's performance beyond the one achieved with the basic stacking encoder used in our paper.The neural network training problem (2) also requires further study. We used an RL approach (see Appendix A) to update the neural network parameters and minimize the average tree size for ILP instances sampled from a given distribution. However, this method does not guarantee convergence to optimal parameters, and relies heavily on the exploratory nature of the RL algorithm. For ILP distributions where random exploration of Chvátal multipliers is unlikely to yield smaller tree sizes, the RL algorithm may struggle to identify an effective parameter setting. Developing a more efficient and robust training methodology would greatly improve the practical value of our work. In this section, for a given ILP instance space I conforming to the description in Section 3.2, and a fixed distribution D over it, we primarily attempt to employ ReLU neural networks for choosing a CG cut multiplier for each instance in the distribution, which translates into addressing the following neural network training (empirical risk minimization) problem:EQUATIONwhere I 1 , . . . , I t ∈ I are i.i.d. samples drawn from D, and recall that φ N ReLU ,CReLUw (•) = CReLU(N σ (Enc(•), w)).This problem, concerning the selection from an infinite pool of cuts, presents a significant challenge. The target function f CG , in relation to its parameters, is an intricately complex, high-dimensional, and piecewise constant function with numerous pieces (recall Lemma 3.2), making direct application of classical gradient-based methods seemingly impractical. As such, we use an RL approach, with our goal switched to identify a relatively "good" neural network for this distribution. Then, based on Proposition 3.3 and Theorem 2.3 the average performance of the chosen parameter setting on sampled instances closely approximates the expected performance on the distribution in high probability, given that the sample size t is sufficiently large.Data. We consider the multiple knapsack problems Kellerer et al. [2004] with 16 items and 2 knapsacks, using the distribution utilized in Balcan et al. [2021b] that the authors refer to as the "Chvátal distribution" as it is inspired by Chvátal [1980] . Our synthetic dataset has a training set of 5,000 instances and a test set of 1,000 instances from the same distribution.Training. Each instance I sampled from the distribution D is treated as a state in RL, with the outputs of the neural network considered as actions in the RL framework. The neural network thus functions as the actor in an actor-critic scheme Silver et al. [2014] , where the reward is defined as the percentage reduction in the tree size after adding a cut, i.e., fCG(I,0)-fCG(I,u) fCG(I,0). The Twin Delayed Deep Deterministic Policy Gradient (TD3) algorithm Fujimoto et al. [2018] is used here for the training of the neural network.The experiments were conducted on a Linux machine with a 12-core Intel i7-12700F CPU, 32GB of RAM, and an NVIDIA RTX 3070 GPU with 8GB of VRAM. We used Gurobi 11.0.1 Gurobi Optimization, LLC [2023] to solve the ILPs, with default cuts, heuristics, and presolve settings turned off. The neural networks were implemented using PyTorch 2.3.0. The details of the implementation are available at https://github.com/Hongyu-Cheng/LearnCGusingNN.Better cuts. The experimental results indicate that even a suboptimal neural network parameterization can outperform the cut selection methodologies used in leading solvers like SCIP. Figure 1 presents the average tree size comparison across 1,000 novel test instances, with three distinct strategies:1. The blue solid line represents the tree size when the cut is selected based on the highest convex combination score of cut efficacy and parallelism, adjusted by a parameter µ ∈ [0, 1] (incremented in steps of 0.01). The candidate set of cuts includes all CG and GMI cuts generated from the appropriate rows of the optimal simplex tableau.2. The green dash-dotted line demonstrates a notable reduction in tree size when using cuts generated through our RL approach;3. The purple dash-dotted line follows the same approach as 2., but uses linear threshold neural networks to generate CG cut parameters. The training process uses the idea of Straight-Through Estimator (STE) Bengio et al. [2013] , Yin et al. [2019] . Faster selection of cuts. The cut selection using neural networks only requires matrix multiplications and ReLU activations, and is notably rapid and lends itself to efficient parallelization on GPUs. In contrast, the procedure for selecting CG and GMI cuts from a simplex tableau based on a weighted combination of cut efficacy and parallelism scores requires solving LPs to get the simplex tableaux, which is considerably slower, even without taking into account the time to score and compare potential cuts. Our empirical studies, conducted on a test set of 1,000 instances repeated 100 times, highlight the significant disparity in computational speed, as shown in Table 1 . Lemma B.1. For any x 1 , . . . , x n , λ 1 , . . . , λ n > 0, the following inequalities hold:EQUATIONEQUATION)Lemma B.2 (Theorem 5.5 in Matousek [1999] , Lemma 17 in Bartlett et al. [2019] , Lemma 3.3 in Anthony et al. [1999] , Theorem 1.3 in Edelsbrunner [1987] ). Let P ⊆ R ℓ and let f 1 , . . . , f t : R ℓ → R with t ≥ ℓ be functions that are polynomials of degree m when restricted to P. Then|{(sgn(f 1 (p)), . . . , sgn(f t (p))) : p ∈ P}| = 1, m = 0, |{(sgn(f 1 (p)), . . . , sgn(f t (p))) : p ∈ P}| ≤ et ℓ + 1 ℓ+1 , m = 1, |{(sgn(f 1 (p)), . . . , sgn(f t (p))) : p ∈ P}| ≤ 2 2etm ℓ ℓ , m ≥ 2.Lemma B.3. Let h : I × P → R define a parameterized function class with P ⊆ R ℓ , and let H be the corresponding hypothesis class (Definition 2.1). Let m ∈ N and R : N → N be a function with the following property: for any t ∈ N and I 1 , . . . , I t ∈ I, there exist R(t) subsets P 1 , . . . , P R(t) of P such that P = ∪ R(t) i=1 P i and, for all i ∈ [R(t)] and j ∈ [t], h(I j , p) restricted to P i is a polynomial function of degree at most m depending on at most ℓ ′ ≤ ℓ of the coordinates. In other words, the map p → (h(I 1 , p), . . . , h(I t , p)) is a piecewise polynomial map from P to R t with at most R(t) pieces. Then, Pdim(H) ≤ sup t ≥ 1 : 2 t-1 ≤ R(t) 2et(m + 1) ℓ ′ ℓ ′ Proof. Given, . . . , W Q of R W with Q ≤ 2 L 2et L i=1 (iwi) LW LWwhose union is all of R W , such that N (x j , w) restricted to w ∈ W i is a polynomial function of degree at most L + 1 for all (i, j)∈ [Q] × [t].Proof. Follows from Section 2 in Bartlett et al. [1998] and Section 4 in Bartlett et al. [2019] .Lemma B.5 (Anthony et al. [1999] , Sontag et al. [1998] ). Let N sgn : R w0 × R W → R ℓ be a neural network function with sgn activation and architecture w = [w 0 , w 1 , . . . , w L , ℓ], where the final linear transformation T L+1 is taken to be the identity (Definition 2.4). Let U = w 1 + . . . + w L denote the size of the neural network. Then for every t ∈ N, and any x 1 , . . . , x t ∈ R w0 , there exists subsetsW 1 , . . . , W Q of R W with Q ≤ etU W ′ W ′whose union is all of R W , whereW ′ = L i=1 (w i-1 +1)w i , such that N sgn (x j , w) restricted to any W i is constant for all (i, j) ∈ [Q] × [t].Proof. Fix a t ∈ N and x 1 , . . . , x t ∈ R w0 . Consider a neuron in the first hidden layer. The output of this neuron on the input x j is sgn(⟨a, x j ⟩ + b), where a ∈ R w0 , b ∈ R are the weights associated with this neuron. As a function of these weights, this is a linear function, i.e., a polynomial function of degree 1. Applying Lemma B.2, there are at most et w0+1 w0+1 regions in the space (a, b) ∈ R w0 ×R such that within each region, the output of this neuron is constant. Applying the reasoning for the w 1 neurons in the first layer, we obtain that the output of the first hidden layer (as a 0/1 vector in R w1 ) is piecewise constant as a function of the parameters of the first layer, with at most et w0+1 (w0+1)w1 pieces. For a fixed output of the first hidden layer (which is a vector in R w1 ), we can apply the same reasoning and partition space of weights of the second layer into et w1+1(w1+1)w2regions where the output of the second hidden layer is constant. Applying this argument iteratively across the hidden layers, and using the inequality (4) in Lemma B.1, we deduce that a decomposition exists for R W with at mostet w 0 + 1 (w0+1)w1 et w 1 + 1 (w1+1)w2 • • • et w L-1 + 1 (w L-1 +1)w L ≤   et w 0 + 1 (w 0 +1)w 1 W ′ et (w 1 + 1) (w 1 +1)w 2 W ′ • • • et w L-1 + 1 (w L-1 +1)w L W ′   W ′ ≤ etw 1 W ′ + • • • + etw L W ′ W ′ = etU W ′ W ′regions, such that within each such region the output of the last hidden layer of the neural network is constant, as a function of the neural network parameters, for all the vectors x 1 , . . . , x t .Proof of Theorem 2.5. Let h :I × R W → R as h(I, w) := S(I, φ N sgn ,Sigmoid w (I)),using the notation from Section 2.2. We wish apply Lemma B.3 on the parameterized function class given by h with P = R W . Accordingly, we need to find a function R : N → N such that for any natural number t > W , and any I 1 , . . . , I t , the function w → (h(I 1 , w), . . . , h(I t , w)) is a piecewise polynomial function on R W with at most R(t) pieces.We consider the space of the neural parameters as a Cartesian product of the space W ′ of all the parameters of the neural network, except for the last linear transformation T L+1 , and the space R ℓ×w L of matrices representing this final linear transformation. Thus, we identify a one-to-one correspondence between R W and W ′ × R ℓ×w L .By Lemma B.5, there exist a decomposition of W ′ into at most etUW ′ W ′regions, where W ′ = W -ℓw L is the number of parameters determining the space W ′ , such that within each region, the output of the final hidden layer of the neural network is constant (as a function of the parameters in the region) for each input Enc(I j ), j ∈ [t].We fix the parameters w ∈ W ′ to be in one of these regions and let z j be the (constant) output corresponding to input Enc(I j ) for any parameter settings in this region. Let us consider the behaviour of Sigmoid(A L+1 z j ), which is the result of a sigmoid activation applied on the final output of the neural network, as a function of the final set of parameters encoded by the matrix A L+1 ∈ R ℓ×w L . We follow the approach used in the proof of Theorem 8.11 in Anthony et al. [1999] .For each k ∈ [ℓ], (Sigmoid(A L+1 z j )) k = 1 1 + exp(- w L i=1 (A L+1 ki z j i )) = w L i=1 (e -A L+1 ki ) w L i=1 (e -A L+1 ki ) + w L i=1 (e -A L+1 ki ) 1+z j i . Let θ ki = e -A L+1 ki for i ∈ [w L ], we have (Sigmoid(A L+1 z j )) k = w L i=1 θ ki w L i=1 θ ki + w L i=1 θ 1+z j i ki .Note that the right hand side above is a ratio of polynomials in θ ki with degrees at most 2w L .Next, as per the hypothesis of Theorem 2.5, let ψ j 1 , . . . , ψ j Γ be the polynomials on R ℓ , each of degree at most γ, such that the function S(I j , •) is a polynomial with degree at most λ within each of the regions where the signs of ψ j 1 , . . . , ψ j Γ are constant. Moreover, let T : [0, 1] ℓ → P be the affine linear map T (u) k = η k + (τ k -η k )u k . We observe then that for all A L+1 such that the functionsψ j 1 (T (Sigmoid(A L+1 z j ))), . . . , ψ j Γ (T (Sigmoid(A L+1 z j )))have the same signs, then h(I j , (w, A L+1 )) = S(I j , φ N sgn ,Sigmoid w,A L+1 (I j )) is a polynomial of degree at most λ. By the observations made above, the functions ψ j 1 (T (Sigmoid(A L+1 z j ))), . . . , ψ j Γ (T (Sigmoid(A L+1 z j ))) are rational functions, i.e., ratios of polynomials, in the transformed parameters θ ki and the numerators and denominators of these rational functions have degrees bounded by 2w L γ. Since sgn P Q = sgn(P Q) for any multivariate polynomials P , Q (whenever the denominator is nonzero), we can bound the total number of sign patterns for ψ j 1 (T (Sigmoid(A L+1 z j ))), . . . , ψ j Γ (T (Sigmoid(A L+1 z j ))) using Lemma B.2 where the polynomials defining the regions have degree at most 3w L γ on the transformed parameters θ ki . We have to consider all the functions ψ j 1 (T (Sigmoid(A L+1 z j ))), . . . , ψ j Γ (T (Sigmoid(A L+1 z j ))) for j ∈ [t], giving us a total of tΓ rational functions. Thus, an application of Lemma B.2 gives us a decomposition of R ℓ×w L into at most2 2e • tΓ • 3γw L ℓw L ℓw L ≤ 2 6etγΓ ℓ ℓw Lregions such that h(I j , (w, A L+1 )) is a polynomial of degree at most λ within each region. Combined with the bound etUW ′ W ′on the number of regions for w ∈ W ′ , we obtain a decomposition of the full parameter spaceW ′ × R ℓ×w L into at most R(t) := etU W ′ W ′ • 2 6etγΓ ℓ ℓw Lregions, such that within each region h(I j , (w, A L+1 )), as a function of (w, A L+1 ), is a polynomial of degree at most λ, for every j ∈ [t]. Moreover, note that within each such region, h(I j , (w, A L+1 ))depends only on A L+1 . Applying Lemma B.3, Pdim F S N sgn ,Sigmoid is bounded by the largest t ∈ N such that 2 t-1 ≤ etU W ′ W ′ • 2 6etγΓ ℓ ℓw L • 2et(λ + 1) ℓw L ℓw L .Taking logarithms on both sides, we want the largest t such that1 2 (t -2) ≤ W ′ log etU W ′ + ℓw L log 6etγΓ ℓ + ℓw L log 2et(λ + 1) ℓw LAs we only need to derive an upper bound for the pseudo-dimension, we can loosen the inequality above using the inequality (3) in Lemma B.1:1 2 (t -2) ≤W ′ etU/W ′ 8eU + log(8U ) + ℓw L 6etγΓ/ℓ 48eγΓw L + log(48γΓw L ) + ℓw L 2et(λ + 1)/(ℓw L ) 16e(λ + 1) + log(16(λ + 1)) ≤ 1 8 t + W ′ log(8U ) + 1 8 t + ℓw L log(48γΓw L ) + 1 8 t + ℓw L log(16(λ + 1)) ≤ 3 8 t + W log(8U ) + ℓw L log 48γΓw L • 16(λ + 1) 8U ≤ 3 8 t + W log(8U ) + ℓw L log(96γΓ(λ + 1)w L /U ) then it's not hard to see that Pdim F S N sgn ,T •Sigmoid = O (W log U + ℓw L log (γΓ(λ + 1))) = O (W log(U γΓ(λ + 1))) .Proof of Theorem 2.6. Let h : I × R W → R as h(I, w) := S(I, φ N ReLU ,CReLU w (I)), using the notation from Section 2.2. We wish apply Lemma B.3 on the parameterized function class given by h with P = R W . Accordingly, we need to find a function R : N → N such that for any natural number t > LW , and any I 1 , . . . , I t , the function w → (h(I 1 , w), . . . , h(I t , w)) is a piecewise polynomial function on R W with at most R(t) pieces.Note that φ ReLU,CReLU w (I) can be seen as the output of a neural network with ReLU activations and architecture [d, w 1 , . . . , w L , 2ℓ, ℓ], where the final linear function is the fixed function T (u) k = (τ k -η k )u k . This is because CReLU(x) = ReLU(x) -ReLU(x -1) can be simulated using two ReLU neurons. Applying Lemma B.4, this implies that given t ∈ N and I 1 , . . . , I t ∈ I, there areQ ≤ 2 L+1 2et • L+1 i=1 (iw i ) (L + 1)W (L+1)W ≤ 2 L+1 2et(U + 2ℓ) W (L+1)W regions W 1 , . . . , W Q whose union is all of R W , such that φ N ReLU ,CReLU w (I j ) restricted to w ∈ W i is a polynomial function of degree at most L + 2 for all (i, j) ∈ [Q] × [t].Next, as per the hypothesis of Theorem 2.5, let ψ j 1 , . . . , ψ j Γ be the polynomials on R ℓ , each of degree at most γ, such that the function S(I j , •) is a polynomial with degree at most λ within each of the regions where the signs of ψ j 1 , . . . , ψ j Γ are constant. Thus, for all w ∈ R W such thatψ j 1 (φ ReLU,CReLU w (I j )), . . . , ψ j Γ (φ ReLU,CReLU w (I j ))have the same signs, then h(I j , w) = S(I j , φ ReLU,CReLU w (I j )) is a polynomial of degree at most λ(L + 2). The functions ψ j 1 (φ ReLU,CReLU w (I j )), . . . , ψ j Γ (φ ReLU,CReLU w (I j )) are polynomials of degree at most γ(L + 2). Considering all these polynomials for j ∈ [t], by Lemma B.2, each W i ⊆ R W from the decomposition above can be further decomposed into at most 2 2etΓγ(L+2) W W regions such that for all w in such a region, h(I j , w) is a polynomial function of w of degree at most λ(L + 2).To summarize the arguments above, we have a decomposition of R W into at mostR(t) := 2 L+1 2et(U + 2ℓ) W (L+1)W• 2 2etΓγ(L + 2) W W regions such that within each region, h(I j , w) is a polynomial function of w of degree at most λ(L + 2). Applying Lemma B.3, Pdim F S N ReLU ,CReLU is bounded by the largest t ∈ N such that NeurIPS Paper Checklist2 t-1 ≤ 2 L+1 2et(U + 2ℓ) W (L+1)W • 2 2etΓγ(L + 2) W W • 2et(λ + 1)(L + 2) W W , 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: This paper does not release any data or models that have a high risk for misuse. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: The assets used in this paper have been properly cited.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.38th Conference on Neural Information Processing Systems (NeurIPS 2024). 
 
 Appendix:  


Decision: The paper contributes to the development of the data-driven algorithm design area by providing theoretical results (sample complexity bounds ) for the learnability (via neural networks) of a mapping from problem instances to branch-and-cut algorithm parameters.
Notwithstanding issues about the real efficiency that can be obtained by exploiting the bounds, mainly linked to the training process of the neural network, the proposed results are timely and significant. 
Rebuttal contributed to clarify several of the related issues raised by reviewers, leading some of them to raise their scores. Moreover, in the AC/reviewers discussion the most negative reviewer (borderline accept) was in agreement with the proposal to accept the paper.

Reviews: review: paper_summary: paper_summary: The authors study the problem of algorithm selection for specific instances of a problem. In particular they provide theoretical results for the learnability of a mapping from problem instances to algorithm parameters with application to branch-and-cut. They establish sample complexity bounds for learning a few different neural network architectures for this task. The appendix includes some synthetic experiments where they apply this method.
strength_weakness: strength_weakness: - although sample complexity bounds are valuable, their practical interpretation for large scale problems is unclear. relating the established bounds to the state of practice for branch and cut, for example, might help shed some light on the importance to practitioners.

- the actual neural network training is done via reinforcement learning, suggesting sample complexity is only one of many challenges to be addressed in generating high-utility NNs to solve this mapping problem. 

- the paper focuses on branch-and-cut methods for mixed-integer optimization, and generalization to other algorithmic problems is not thoroughly explored.

- the work is centrally focused on theory, so naturally the empirical contribution is minimal, essentially left to the appendix.

Miscellaneous:

- the algorithm exist early -> exits early
questions: questions: - Theorems 2.5 and 2.6 assume that the parameter space can be decomposed into regions where the function remains polynomial with bounded degree. Is this realistic? 
- Besides tree size, have you evaluated other measures of performance for branch and cut or other problems?
- What is the practical interpretation of the established bounds for algorithm selection on this problem? How does it inform network design / historical instance curation ?
limitations: limitations: The authors discuss the limitations appropriately in the conclusion.
paper_summary: paper_summary: This paper studies data-driven algorithm design, which learns a class of algorithms to optimize the expected performance scores given i.i.d. samples of instances.
In particular, the paper studies the sample complexity of learning (the weights of) neural networks computing the size of certain branch-and-cut trees for mixed-integer programming.

Based on the results of Balcan et al. to bound pseudo-dimension, this paper studies learning neural network weights to compute the size of certain branch-and-cut trees, avoiding the need to optimize for weighted combinations of auxiliary score functions for each new instance, and getting smaller tree sizes.
strength_weakness: strength_weakness: 1. The application to the size of branch-and-cut tree for integer linear programming with Chvátal-Gomory cuts (parameterized by multipliers at *root*), or with Gomory Mixed-Integer cuts (at *root*), are somewhat limiting (as pointed out in the Discussion section). This reader thinks that the applications are chosen so that the geometric analysis argument can go through to bound the pseudo-dimension (hence to apply Theorems 2.5 and 2.6, Corollary 2.7), and unlikely to generalize to effective bounds in more general settings, where the geometric picture will be more complicated, which needs to account for both the neural netorks and (the nodes inside) the branch-and-cut trees.
2. The theoretical bounds are asymptotic which are unlikely to have effective/small constants.

Nitpick:
* In some places, the paper uses branch-and-*bound* tree, while in most places (including the title) the paper uses branch-and-*cut*. It may help to use a consistent name.
questions: questions: For the original question—solving mixed-integer programming but not only to minimize branch-and-cut tree sizes—what does the results of the paper imply?
limitations: limitations: This is a theoretical paper that do not have broader societal impacts.
paper_summary: paper_summary: The paper introduces an approach to data-driven algorithm design by leveraging neural networks to select the most appropriate algorithm for a given instance of a computational problem. The motivation is clear. This paper decision to extend the paradigm from selecting a single best algorithm to a context-specific selection. The introduction of neural networks as the parameterized family of mappings is a novel approach that could potentially offer significant benefits in terms of adaptability and performance. Overall, the paper presents an interesting approach to algorithm selection and parameter tuning using neural networks. The theoretical grounding and practical motivation are commendable.
strength_weakness: strength_weakness: (1) Training Overhead: Training neural networks can be computationally intensive, especially when dealing with large and complex datasets. The time and resources required for training may limit the scalability of the approach.

(2) Inference Time: While the method aims to optimize performance on a per-instance basis, the inference time for selecting the optimal parameters using a neural network could be longer than traditional static parameter selection methods.
questions: questions: (1) Can the author elaborate on the role of theoretical guarantees such as the bounds on pseudo-dimension and sample complexity? How do these theoretical results translate into practical performance, and what are the limitations of the theoretical framework?

(2) For neural networks with different activation functions, this paper gives different bounds. What results will be produced when there are different activation functions in the neural network?

(3) Neural networks are often considered black boxes, making it difficult to understand why a particular parameter set was chosen for a given instance. How does the sample complexity of theoretical analysis guide the learning of specific algorithms?
limitations: limitations: While the paper mentions deriving rigorous sample complexity bounds, the tightness of these bounds and their practical implications need to be carefully evaluated. The theoretical guarantees may not always translate directly to strong empirical performance.

Comments: comment: I acknowledge the rebuttal.
I thank the authors for their response. I think the insight is interesting (sample complexity bound growing linearly in the number of NN parameters) given that this isn't empirically the case in other domains (e.g. the "scaling laws" literature, which is totally experiment-based). I think the authors have made meaningful progress on this problem and i've raised my score to indicate that.
I appreciate the authors' thorough response. They have effectively addressed several of my concerns, leading me to raise my score to 5.