Learning Cut Generating Functions for Integer Programming

Authors: hongyu  cheng
amitabh  basu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 19:49:19

Abstract: The branch-and-cut algorithm is the method of choice to solve large scale integer programming problems in practice. A key ingredient of branch-and-cut is the use of *cutting planes* which are derived constraints that reduce the search space for an optimal solution. Selecting effective cutting planes to produce small branch-and-cut trees is a critical challenge in the branch-and-cut algorithm. Recent advances have employed a data-driven approach to select good cutting planes from a parameterized family, aimed at reducing the branch-and-bound tree size (in expectation) for a given distribution of integer programming instances. We extend this idea to the selection of the best cut generating function (CGF), which is a tool in the integer programming literature for generating a wide variety of cutting planes that generalize the well-known Gomory Mixed-Integer (GMI) cutting planes. We provide rigorous sample complexity bounds for the selection of an effective CGF from certain parameterized families that provably performs well for any specified distribution on the problem instances. Our empirical results show that the selected CGF can outperform the GMI cuts for certain distributions. Additionally, we explore the sample complexity of using neural networks for instance-dependent CGF selection.

Main paper: 
 introduction: 
 Integer linear programming is an optimization framework that has diverse applications in logistics [Arntzen et al., 1995 , Sinha et al., 1995 , Hane et al., 1995] , finance [Bertsimas et al., 1999] , engineering [Grossmann and Kravanja, 1995] , national defense [Gryffenberg et al., 1997 , Jiang et al., 2014] , healthcare [Ajayi et al., 2024 , Valeva et al., 2023] , statistics [Bertsimas et al., 2016 , Dash et al., 2018 , Wei et al., 2019] and machine learning [Bertsimas and Dunn, 2017 , Chen et al., 2021 , Malioutov et al., 2023] , to give a small sample of applications and related literature. The method of choice for solving integer programming problems is the well-known branch-and-cut paradigm [Schrijver, 1986 , Nemhauser and Wolsey, 1988 , Conforti et al., 2014] . This procedure has two critical ingredients: branching, which is a way to subdivide the problem into smaller subproblems, and the use of cutting planes which is a way to reduce the feasible region of a (sub)problem by deriving additional linear constraints that are implicitly implied by the integrality of the decision variables. To get to a concrete algorithm from this high level framework, one needs to make certain choices (such as how to branch, which cutting plane to use etc.) Thus, at a high level, the branch-and-cut method is really a collection of algorithms equipped with a common set of "tunable parameters". Upon a specific choice of values for these parameters, one actually obtains a well-defined algorithm that one can deploy on instances of the problem.38th Conference on Neural Information Processing Systems (NeurIPS 2024).There is a substantial amount of literature on the mathematical foundations of cutting planes and branching, and many of their theoretical properties are well understood. Nevertheless, current theory does not give very precise recipes for making these parameter choices in branch-and-cut for getting the best performance on particular instances. There are some general insights available from theory, but a large part of the actual deployment of these algorithms in practice is heuristic in nature. This state of affairs has prompted several groups of researchers to explore the possibility of using machine learning tools to make these parameter choices in branch-and-cut; see [Scavuzzo et al., 2024] for a survey and the references therein.In this paper we focus on some foundational aspects of the use of machine learning to improve algorithmic performance of branch-and-cut. One can formalize the problem as follows. Given a family of instances of integer programming problems, one wishes to select the parameters of branch-and-cut that will perform well on average, and one wishes to do this in a data-driven manner. More formally, one assumes there is a probability distribution over the family of instances and the goal is to find the choice of parameters that gives the best performance in expectation with respect to this distribution. The probability distribution is not explicitly known, but one can sample instances from the distribution and use these samples to guide the choice of parameters. This puts the problem in a classical learning theory framework and one can ask questions like the sample size required to guarantee success with high accuracy and high probability (over the samples). This perspective was pioneered in a recent series of papers [Balcan et al., 2021a [Balcan et al., ,c,b, 2022 [Balcan et al., , 2018] ] with several important insights and technical contributions. The broader question of selecting a good algorithm from a suite of algorithms for a computational problem, given access to samples from a distribution over the instances of the problem, is generally called data-driven algorithm design and has received attention recently; see [Balcan, 2020 , Balcan et al., 2021a] and the references therein. There is also a lot of recent activity in the related aspect of algorithm design with predictions; see, e.g., [Mitzenmacher and Vassilvitskii, 2022] .This paper contributes to this line of research that analyzes the sample complexity of using machine learning tools for parameter selection in branch-and-cut. In particular, we focus on the cut selection problem, which is also a central theme in the papers [Balcan et al., 2021c [Balcan et al., ,b, 2022]] . Thus, we wish to learn what choice of cutting planes within the branch-and-cut procedure gives the best performance. Our results differ from this previous work in two main ways.1. In [Balcan et al., 2021c [Balcan et al., ,b, 2022]] , the authors focus on the classical cutting plane families of Chvátal-Gomory (CG) and Gomory Mixed-Integer (GMI) cutting planes. These are actually two very special cases of a much more general framework for deriving cutting planes for integer programming problems, which is called cut generating function theory.The idea behind cut generating functions goes back to seminal work by [Balas, 1971] and [Gomory and Johnson, 1972a,b] from the 1970s, and there has been a tremendous amount of progress in our understanding of this theory in the past 15 years. The main point is that cut generating functions give a parameterized family of cutting planes to choose from, which vastly generalizes the CG and GMI cuts. We provide sample complexity results for cut selection from this larger family. This requires new understanding of the structure of these cutting planes and their interplay with learning theory tools. While we do rely on some of the ideas from [Balcan et al., 2021c [Balcan et al., ,b, 2022]] , several new technical and algorithmic challenges need to be overcome. The full potential of cut generating functions has not been realized despite sustained efforts in the past decade; see [Poirrier, 2014, Chapter 6] for a nuanced discussion. We believe an important factor behind this is that the cut selection problem for this much larger class is very hard. Thus, while they promise significant gains over traditional ideas like GMI cuts, it has been difficult to utilize them in practice. Using modern machine learning tools to help with the cut selection could be the key to deploying these powerful tools in practice. Thus, we believe our results to be significant in that they are the first of their kind in terms of establishing a rigorous foundation for using machine learning to solve the cut selection problem for cut generating functions. 2. All of the work in [Balcan et al., 2021a [Balcan et al., ,c,b, 2022 [Balcan et al., , 2018] ] focuses on making a single choice of parameters that does well in expectation. However, it can be significantly more beneficial to allow the choice of parameters to depend on the instance [Rice, 1976, Gupta and Roughgarden, 2016] . In recent work, the use of neural networks was suggested as a way to map instances to the choice of parameters in data-driven algorithm design [Cheng et al., 2024] , and sample complexity bounds were derived for learning such a neural network. The authors in [Cheng et al., 2024] worked with CG and GMI cuts. Here we extend that analysis to learn neural mappings to more general cut generating functions.Cut generating functions derive cutting planes by using the data from an optimal simplex tableaux for the linear programming relaxation of the integer programming problem. CG and GMI cutting planes are a special case of such cutting planes where data from a single tableaux row is used. Our first result (Theorem 3.2) establishes sample complexity bounds for a parameterized family of cut generating functions that uses information from single rows of the simplex tableaux, but goes beyond CG and GMI cuts. Cut generating function theory also allows the use of information from multiple rows of the tableaux, which will naturally result in stronger cutting planes because more information from the problem is used to derive these cuts. Our second result (Theorem 4.4) gives sample complexity results for a parameterized family of cut generating functions that uses information from k rows, for any fixed natural number k ≥ 2. In Section 5, these sample complexity results are extended to learning neural networks that map instances to cut generating functions, achieving an instance dependent performance.The choice of the cut generating function families that we study in this paper were dictated by three things: 1) we should be able to derive cutting planes from them in a computationally efficient way, 2) we should be able to derive concrete sample complexity bounds, and 3) we should be able to demonstrate that these new cutting planes are better in practice than classical cuts. Sections 3, 4 and 5 achieve aims 1) and 2). Section 6 gives evidence for 3) by showing that our choice of cut generating functions can indeed improve performance of branch-and-cut, especially with the use of instance dependent cutting planes. Our performance criteria is the overall tree size (number of nodes explored by the solver) for solving the problem. For those familiar with cut generating function theory, we mention that our cut generating functions are all extreme functions. This provides some additional theoretical underpinning to the claim that these cutting planes are of good quality.We begin our formal presentation in Section 2 where we introduce the required concepts, terminology and notation from integer programming and learning theory that are needed to state and prove our results formally, which is done in Sections 3, 4 and 5. 
formal setup of the problem: 
 Throughout the paper, we will use the following standard notations. The sign function sgn : R → {0, 1} is defined by sgn(x) = 1 if x ≥ 0 and sgn(x) = 0 if x < 0. The set ∆ τ d = x ∈ R d : x 1 , . . . , x d ≥ 1 τ , d i=1 x i = 1 represents a d-dimensional simplex,where τ ≥ 2d is some predefined number. For a set of vectors {x 1 , . . . , x t } ⊆ R d , we use superscripts to denote vector indices and subscripts to specify the coordinates in a vector; thus, x i j refers to the j-th coordinate of vector x i . The floor and ceiling functions, denoted by ⌊•⌋ and ⌈•⌉ respectively, round each component of a vector down or up to the nearest integer. We denote [x] = x -⌊x⌋ for any x ∈ R d , representing the fractional part of each component of the vector.Given positive integers m, n, a pure integer linear programming (ILP) problem in canonical form can be described as:EQUATIONfor some A ∈ Z m×n , b ∈ Z m , and c ∈ R n . This problem is represented by the tuple (A, b, c). In this paper, we consider the set of ILP instances I such that for any I = (A, b, c) ∈ I, there exists a universal constant ϱ such that sup {⌈∥x∥ ∞ ⌉ : Ax ≤ b, x ≥ 0} ≤ ϱ.A cutting plane for (1) is given by (α, β) ∈ R n × R such that the inequality α T x ≤ β is satisfied by all points in the feasible region {x ∈ Z n : Ax ≤ b, x ≥ 0} of (1).Cut generating functions. We now present the technique of cut generating functions to derive cutting planes for (1). Consider the equivalent standard form of (1) after introducing slack variables:EQUATIONwhere A = [A, I] ∈ Z m× (n+m) . The simplex tableaux of the above problem with respect to a basis B ⊆ {1, . . . , m + n} with |B| = m is given byEQUATIONwhere A B and A N represent the submatrices of A corresponding to the columns indexed by B and N = {1, . . . , m + n} \ B, respectively. We select any k rows, where k ∈ {1, ..., m}, from (3) such that the right-hand side vector is not integral, and write the resulting system as:EQUATIONwhere r 1 , . . . ,r n ∈ R k and f ∈ R k \Z k are subvectors of A -1 B A N and A -1 B b, respectively, corresponding to the selected rows. Suppose we have a function π : R k → R + satisfying the following conditions:1. π(0) = 0, π(f ) = 1, 2. subadditivity: π(r + r ′ ) ≤ π(r) + π(r ′ ), ∀r, r ′ ∈ R k , 3. periodicity: π(r + w) = π(r), ∀r ∈ R k , w ∈ Z k ,then for any feasible y N and z we have the following inequality:EQUATIONIt's noteworthy that the optimal solution to the relaxed linear programming problem, y B , y N = A -1 B b, 0 , will always violate this inequality. By substituting out the slack variables using (2), the inequality n i=1 π r i y N i ≥ 1 becomes a cutting plane α T x ≤ β for (1); see Lemma A.3. We present two classical examples of one-dimensional (i.e., k = 1) cut generating functions here (as well as their plots in Figure 1a and Figure 1b ). A family of one-dimensional cut generating functions we will use in this paper will be presented in Section 3, and a family of k-dimensional cut generating functions, for arbitrary k ≥ 1, will be presented in Section 4.Gomory fractional cut [Gomory, 1958] : Define CG f (r) = [r] [f ] . Applying this function to the j-th row of the simplex tableau (4) with f j / ∈ Z, the valid cut (5) translates to the Gomory fractional cut:n i=1 [r i j ] [f j ] y N i ≥ 1 ⇐⇒ n i=1 r i j -⌊r i j ⌋ f j -⌊f j ⌋ y N i ≥ 1 ⇐⇒ n i=1 r i j -⌊r i j ⌋ y N i ≥ f j -⌊f j ⌋.This cut generating function gives cutting planes that are equivalent to the well-known Chvátal-Gomory (CG) cuts; see [Conforti et al., 2014, Section 5.2.4 ] for a discussion.Gomory's mixed-integer cut [Gomory, 1960] : The GMI cut function GMI f (r) is defined as [r] [f ]when [r] ≤ [f ], and 1-[r] 1-[f ] when [r] > [f ].Applying to the j-th row with f j / ∈ Z, the valid cut (5) translates to the GMI cut:i:[r i j ]≤[fj ] [r i j ] [f j ] y N i + i:[r i j ]>[fj ] 1 -[r i j ] 1 -[f j ] y N i ≥ 1 ⇐⇒ i:[r i j ]≤[fj ] [r i j ]y N i + [f j ] 1 -[f j ] i:[r i j ]>[fj ] 1 -[r i j ] y N i ≥ [f j ]. (a) CG f (b) GMI f (c) π p,q f,s 1 ,s 2Figure 1 : Three cut generating functions on [0, 1), where π p,q f,s1,s2 is defined in Section 3.We will consider parameterized families of cut generating functions and the sample complexity of learning which cut generating functions work well. More precisely, we will track how well branchand-cut performs when the cutting plane corresponding to a specific cut generating function is added to the initial linear programming relaxation of the problem, a.k.a the root node of the branch-and-cut tree. In this paper, we consider the branch-and-cut tree built with a product scoring policy for variable selection, a depth-first search policy for node selection, and only one cutting plane added at the root node. We will use the overall tree size needed to solve the problem as the quantitative measure of performance, which is strongly correlated with the overall solve time.Consider an unknown probability distribution D over the instance space I. We are presented with problems drawn independently and identically distributed (i.i.d.) from this distribution. We also have a family of cut generating functions parameterized by µ ∈ P. Let c(I, µ) denote the cutting plane obtained by applying the cut generating function corresponding to µ to the instance I as explained in the previous section. h(I, µ) ∈ [0, B] ∩ Z will denote the truncated branch-and-cut tree size for some B > 0, when the cutting plane c(I, µ) is used at the root node for processing I.The objective is to find the cut generating function that minimizes the expected tree size over the distribution D, i.e., we want to solve the stochastic optimization problem min µ∈P E I∼D h(I, µ). For any ε > 0 and δ ∈ (0, 1), the sample complexity of the problem is a natural number N = N (ε, δ) such that if the number of sampled instances exceeds N , the expected tree size for the distribution D and the average tree size for the sampled instances differ by less than ε for every µ ∈ P, with probability (over the samples) at least 1 -δ. Thus, if we have that many samples, we can use the cut generating function that minimizes the average tree size on our instances (this is a deterministic optimization problem since the sample is at hand, a.k.a the empirical risk minimization (ERM) or sample average approximation (SAA) problem) and we will do well in expectation, i.e., generalize to unseen instances, with high probability.The pseudo-dimension Pdim(H) is a measure of the 'complexity' of the associated function classH := {h(•, µ) : µ ∈ P},and is a key concept closely related to sample complexity. It is defined as the largest integer t for which there exists a set of instances and real values (I 1 , s 1 ), . . . ,(I t , s t ) ∈ I × R such that 2 t = |{(sgn(h(I 1 , µ) -s 1 ), . . . , sgn(h(I t , µ) -s t )) : µ ∈ P}| .A classical result in statistical learning theory (e.g., Theorem 19.2 in [Anthony et al., 1999] ) implies the sample complexity boundN (ε, δ) = O B 2 ε 2 Pdim(H) log B ε + log 1 δ .Thus, our task reduces to finding an upper bound for Pdim(H).In learning theory, identifying the piecewise structure of the function class H = {h(•, µ) : µ ∈ P} is a standard technique for bounding its pseudo-dimension (see [Anthony et al., 1999 , Bartlett et al., 1998 , 2019 , Sontag et al., 1998 , Balcan et al., 2021a] ). For a fixed instance I ∈ I, one shows that the parameter space P can be partitioned into regions such that the function h(I, µ) behaves as a fixed 'simple function' within each region. The partition is defined by a set of functions on P and the regions of the partition correspond to parameter values in µ ∈ P where these functions have invariant signs.Given that our tree size function is an integer-valued function, we present a particular such result below in Lemma 2.1, which motivates the piecewise structure results presented later in Proposition 3.1 and Proposition 4.3. These results will be used in the proofs of Theorem 3.2 and Theorem 4.4 to bound the pseudo-dimension. The proof of Lemma 2.1 is provided in Appendix A. Note that a more general version of this result is given in [Balcan et al., 2021a ], but our specific version is asymptotically better than a direct application of the general result, since Sauer's lemma ( [Sauer, 1972 , Shelah, 1972] ) is not involved in the proof. Lemma 2.1. Let h : I × P → Z, where P ⊆ R d for a natural number d. Suppose that for any fixed I ∈ I, there exist at most Γ functions, each expressible as the quotient of a polynomial of degree at most a and a strictly positive function. These functions partition P into regions in which h(I, µ) remains constant. Then, the pseudo-dimension of the function class {h(•, µ) : µ ∈ P} is given by:Pdim ({h(•, µ) : µ ∈ P}) = O(d log(Γa)).Remark 2.2. In Theorems 3.2 and 4.4 that bound the pseudo-dimensions, we assume that the row(s) used for generating the cut are prefixed for all instances I ∈ I. However, it is straightforward to extend the analysis to give bounds on the pseudo-dimension when the choice of rows is also learned along with the cut generating function. We leave these details out of this conference version of the paper.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: The major part of this paper is theoretical, so the limitations are clear in the statements of the theorems. The limitations of our numerical approach are mentioned in Section 6. 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. 
one-dimensional cut generating functions: 
 In this section, we present a family of one-dimensional cut generating functions (originally proposed in [Gomory and Johnson, 2003] ) that we believe satisfy the three criteria laid out in the Introduction, i.e., cutting planes can be obtained efficiently from them (we present closed form formulas below), sample complexity (pseudo-dimension) bounds can be established rigorously (Theorem 3.2 below), and they result in significantly smaller tree sizes compared to traditional cutting planes (Section 6).(a) π 2,2 0.3,-2,7 (r) (b) π 3,3 0.5,-5,5 (r) (c) π 4,3 0.6,-12.5,2.5 (r)Figure 2 : Three examples of the one-dimensional cut generating functions π p,q f,s1,s2 on [0, 1).For any f ∈ (0, 1), p, q ∈ [2, +∞] ∩ Z, s 1 , s 2 ∈ R, let π p,q f,s1,s2 (r) = max min ϕ 1 i (r), ϕ 2 i (r) : i = 1, . . . , p ∪ min ψ 1 j (r), ψ 2 j (r) : j = 1, . . . , q -1 , where ϕ 1 i (r) = s 1 r + i 1 -f s 1 p , ϕ 2 i (r) = s 2 r + (i -1) 1 -f s 2 p -1 , i = 1, . . . , p, ψ 1 j (r) = s 1 (r -1) + (j -1) 1 + (1 -f )s 1 q -1 , ψ 2 j (r) = s 2 (r -1) + j 1 + (1 -f )s 2 q , j = 1, . . . , q -1.See Figures 1c and 2 for examples with different f, p, q and s 1 , s 2 . Let D p,q f denote the set of all (s 1 , s 2 ) such that π p,q f,s1,s2 (•) is a valid cut generating function, i.e., it satisfies the three conditions outlined in Section 2.1. The closed form of this set is provided in Lemma B.1, which indicates that D p,q f is always a (possibly semi-infinite) rectangle.We first show that the cutting plane coefficients for (2) derived from this family of cut generating functions has a piecewise affine linear structure. This is key to establishing the pseudo-dimension bounds in Theorem 3.2 using Lemma 2.1. Proposition 3.1. For any fixed f ∈ (0, 1), p, q ∈ N ∩ [2, +∞], and r 1 , . . . , r n ∈ [0, 1), there exists a decomposition of the (s 1 , s 2 ) space D p,q f given by at most n hyperplanes such that, within each region, each coordinate of the cutting plane π p,q f,s1,s2 (r 1 ), . . . , π p,q f,s1,s2 (r n )T is a fixed affine linear function of (s 1 , s 2 ).To make the parameter selection in more controlled manner, we introduce a large positive constant M and adjust the bounds of s 1 and s 2 given in Lemma B.1 to finite ranges by replacing -∞ and +∞ with 1 f -1 -M and 1 f + M , respectively, in the corresponding cases. This restricts (s 1 , s 2 ) to the product of 2 bounded intervals, denoted as[l 1 , u 1 ] × [l 2 , u 2 ], which is a bounded subset of D p,qf . This allows us to use parameters µ = (µ 1 , µ 2 ) ∈ [0, 1] 2 to control s 1 and s 2 as follows:s 1 = u 1 -µ 1 (u 1 -l 1 ), s 2 = l 2 + µ 2 (u 2 -l 2 ).(6) We remark that setting µ 1 = µ 2 = 0 gives the GMI f function.We now have all the pieces to state the precise pseudo-dimension bound. Theorem 3.2. Let p, q ≥ 2 be arbitrary, but fixed, natural numbers. Let T (I, µ) denote the tree size of the branch-and-cut algorithm after adding the cut induced by the cut generating function π p,q f,s1,s2 (•) at the root for a given instance I ∈ I, where s 1 , s 2 are given by the mappings (6) based on µ 1 , µ 2 , and f is determined by I. Then, the pseudo-dimension is given by Pdim T (•, µ) :I → [0, B] | µ ∈ [0, 1] 2 = O n 2 log((m + n)ϱ) .Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
k-dimensional cut generating functions: 
 In this section, we present a family of k-dimensional cut generating functions, for arbitrary k ≥ 2, that we believe satisfy the three criteria laid out in the Introduction, i.e., cutting planes can be obtained efficiently from them (Theorem 4.2 below), sample complexity (pseudo-dimension) bounds can be established rigorously (Theorem 4.4 below), and they result in smaller tree sizes compared to traditional cutting planes (Section 6). We note that this particular family of cut generating functions has not been studied previously in the literature (from a theory or computational perspective), though they are a subclass of cut generating functions studied in [Basu and Sankaranarayanan, 2019] .Recall that m is the total number of constraints in the original integer program (1), and k ≤ m is the number of rows from the simplex tableaux used to derive the cutting planes. For anyf ∈ [0, 1) k \{0} and µ = [µ 1 , . . . , µ k ] T ∈ ∆ τ k with a universal large constant τ ≥ 2m, let a 0 = k i=1 µ i e i k i=1 µ i f i , a 1 = 1 f 1 -1 e 1 , ..., a k = 1 f k -1 e k ∈ R k ,where e i denotes the i-th standard basis vector in R k . Define π f ,µ : R k → R byπ f ,µ (r) := min z∈Z k max i=0,...,k ⟨a i , r + z⟩.Using well-known results from cut generating function theory, it can be shown that π f ,µ satisfies the three conditions in Section 2.1 to qualify as a cut generating function; see, for example, the analysis in [Basu and Sankaranarayanan, 2019] . It is noteworthy that for each µ = e i with i ∈ {1, . . . , k}, the function π f ,µ is equivalent to the one-dimensional GMI function GMI fi , defined in Section 2.1. Remark 4.1. As we pointed out in the introduction, both families of cut generating functions considered in this paper are extreme for the pure integer infinite relaxation problem [Conforti et al., 2014, Gomory and Johnson, 1972a,b] . The first family, described in Section 3.1, was proved to be extreme in Gomory and Johnson's original paper [Gomory and Johnson, 2003] . For k-dimensional CGFs, they are minimal valid functions as they are the trivial lifting of the gauge function of maximal f + Z k -free convex sets with the covering property [Basu et al., 2013a , Conforti et al., 2014 , Averkov and Basu, 2015] . Then, these k-dimensional CGFs are extreme by the (k + 1)-slope theorem [Basu et al., 2013b] .(a) (f , µ) = 0.2 0.7 , 0.3 0.7 (b) (f , µ) = 0.4 0.5 , 0.5 0.5 (c) (f , µ) = 0.3 0.6 , 0.8 0.2Algorithm 1 shows how to compute the function values π f ,µ (r) (the cutting plane coefficients), in time that is linear in the dimension k. We then expose an important piecewise structure of the corresponding family of cutting planes for (2) in Proposition 4.3. This piecewise structure is the key to establishing upper bounds on the pseudo-dimension (recall Lemma 2.1) for learning the optimal cut generating function from this family in Theorem 4.4.Algorithm 1 Computation of π f ,µ (r) 1: Input: k ∈ N + ∩ [2, ∞), f ∈ [0, 1) k \{0}, µ = [µ 1 , . . . , µ k ] T ∈ ∆ τ k , r ∈ R k 2: Output: π f ,µ (r) 3: r ← r -⌊r⌋ - k i=1 1(r i ≥ f i + ⌊r i ⌋)e i ▷ 1(•) is the indicator function 4: p ← k i=1 µ i ri 5: q ← k i=1 µ i f i 6: s ← r1 f1-1 , . . . , rk f k -1 7: a ← max {s i : i ∈ {1, . . . , k}} 8: i * ← arg max {s i : i ∈ {1, . . . , k}} 9: b ← max {s i : i ∈ {1, . . . , k}\{i * }} 10: λ * ← ri * q-(f i * -1)p µ i * (f i * -1)-q 11: π f ,µ (r) ← min max p+µ i * ⌈λ * ⌉ q , ri * +⌈λ * ⌉ f i * -1 , b , max p+µ i * ⌊λ * ⌋ q , ri * +⌊λ * ⌋ f i * -1 , b , max p q , a Theorem 4.2. For any f ∈ [0, 1) k \{0}, τ ≥ 2k, and µ ∈ ∆ τ k , Algorithm 1 computes π f ,µ (r) in O(k) time. Therefore, the cutting plane obtained from π f ,µ can be computed in O(kn) time. Proposition 4.3. For any fixed k ∈ Z ∩ [2, +∞], f ∈ [0, 1) k \{0}, r 1 , . . . , r n ∈ R k ,and τ ≥ 2k, there exists a decomposition of ∆ τ k obtained by at most 2n(τ + 3) 2 hyperplanes such that within each region, each coordinate of the cutting plane π f ,µ (r 1 ), . . . , π f ,µ (r n )T is a fixed rational function given by the quotient of two affine linear functions of µ, where the denominator is always a fixed positive function of µ.Theorem 4.4. For any fixed k ∈ Z ∩ [2, +∞], let T k (I, µ) denote the tree size of the branch-and-cut algorithm after adding the cut induced by π f ,µ at the root for a given instance I ∈ I, where f is determined by I. Then, the pseudo-dimension is given byPdim T k (•, µ) : I → [0, B] | µ ∈ ∆ τ k = O kn 2 log((m + n)ϱ) + k 2 log(nτ ) .5 Learnability of instance-dependent cut generating functionsThe authors in [Cheng et al., 2024] studied the learnability of neural networks that select instancedependent algorithms for any computational problem, as opposed to selecting a single algorithm that has the best expected performance, and applied this to the problem of selecting from the Chvatal-Gomory cutting plane family. Inspired by their work, this section discusses employing neural networks to dynamically select the most suitable cut generating function from a given family, tailored to each instance, as opposed to selecting a single cut generating function that has the best expected performance overall (as was done in Sections 3 and 4). In other words, given access to samples from the instance distribution, we want to learn the parameters of the optimal neural network that will map instances to instance specific cut generating functions.We define a neural network φ ℓ : R d × R W → R ℓ consisting of a fully connected architecture with ReLU activations, L layers, W parameters, d input units, ℓ output units, and U units in total. An encoder function Enc : I → R d is employed to transform instances I = (A, b, c) ∈ I into suitable neural network inputs, where a straightforward choice for Enc could be the flattening of I into a vector, although more complex encoding strategies can be adopted to capture additional structural information about the instances. The primary goal is to input the encoded instance Enc(I) into the neural network, which then predicts parameters for the cut generating function that were discussed in Section 3 and Section 4. This idea is supported by empirical evidence of performance improvements when enumerating cutting plane parameters in an instance-dependent manner, as demonstrated in Table 1 . A direct application of the main theorem in [Cheng et al., 2024] yields the following results:Theorem 5.1. Let h, h k : I × R W → [0, B]denote the branch-and-cut tree size after adding the cutting planes induced by corresponding cut generating functions, using parameters determined by the neural network described above. Formally, they are defined as h(I, w) = T (I, φ 2 (Enc(I), w)) and h k (I, w) = T k (I, φ k (Enc(I), w)), where T and T k are the tree size functions defined in Theorems 3.2 and 4.4 respectively. Then the pseudo-dimension of these two learning problems have the following upper bounds:Pdim h(•, w) : w ∈ R W = O LW log(U + 2) + n 2 W log((m + n)ϱ) , Pdim h k (•, w) : w ∈ R W = O LW log(U + k) + kW log(nτ ) + n 2 W log((m + n)ϱ) .6 Numerical experiments Setup. We conducted numerical experiments to evaluate the performance of both one-dimensional and k-dimensional cut generating functions, as discussed in Section 3 and Section 4, across various distributions. The performance of these functions was compared to the GMI cut. The parameters for the cut generating functions were selected to minimize the average branch-and-cut tree size on the training set of size 100, and these parameters were then applied to the test set of size 100 to evaluate performance. All results presented in Table 1 are based on the test set, except for the last column. The experiments were run on a Linux machine equipped with a 12-core Intel i7-12700F CPU and 32GB of RAM. We solved the integer programming problems using Gurobi 11.0.1 [Gurobi Optimization, LLC, 2023], with default cuts, heuristics, and presolve settings turned off. The code and data used in all experiments are available at https://github.com/Hongyu-Cheng/LearnCGF.Problem descriptions. We considered two types of problems: Knapsack and Packing.1. Knapsack(N, K): Multiple knapsack problem with N items and K knapsacks. Instances were generated using the so-called "Chvátal distribution" from [Balcan et al., 2021b] . Note that there are some trivial upper bound constraints on the variables that contribute to the simplex tableaux. Even so, the table has n/a entries for the k-row cut strategies for the 1-knapsack problem, as there are not enough fractional rows to generate multi-row cuts for many instances.2. Packing(m, n): Packing problem with m constraints and n variables. We note that the knapsack problem can be viewed as a special case of the packing problem with binary variables. The packing instances were generated using the distribution from [Tang et al., 2020] .Cutting plane strategies. The following cutting plane strategies were evaluated and compared:1. GMI: Classical Gomory's mixed integer cut as defined in Section 2.1.2. 1-row cut: Generated using the one-dimensional cut generating function defined in Section 3.We fixed p = q = 2 and performed a grid search with a step size of 0.1 to select the best parameter µ ∈ {0, 0.1, . . . , 0.9, 1} 2 .3. k-row cut: Generated using π f ,µ defined in Section 4 with k ∈ {2, 5, 10}. We uniformly sampled 121 different µ on the simplex ∆ ∞ k (see [Gordon-Rodriguez et al., 2020, Smith and Tromble, 2004] ), and selected the best parameter based on the training set.4. Best 1-row cut: The average tree size using the best parameter for each instance on the training set. This is not a practical strategy but indicates the strength of the cut generating functions and the potential for instance-dependent cut generating using neural networks.Since we aim to demonstrate that cut generating functions can produce stronger cuts than classical cutting planes, we did not specifically consider which row to select to generate the cut. This problem, while important in integer programming literature, is outside the scope of this paper. All cuts are generated from the first row of the simplex tableau with a non-integer right-hand side, and the k-row cut is generated from the first k such rows. Also, to select the best parameters based on samples (i.e., solve the ERM problem), we used a simple grid search and optimized through enumeration, since the branch-and-cut tree size is a highly sophisticated function of the added cutting planes at the root node.Numerical results. As shown in Table 1 , the two cut generating function families considered in this paper reduce the size of the branch-and-cut tree compared to the GMI cut. Although the improvement over the GMI cut on the test set is less obvious for the packing problem, the last column in the table shows that there are still cutting planes that perform much better for each instance. Moreover, all the multi-row cuts on the Knapsack(30, 3) problems outperform the best 1-row cut, indicating that multi-row cuts can sometimes achieve performance levels that single-row cuts cannot reach. Lemma A.1 (Theorem 5.5 in [Matousek, 1999] , Lemma 17 in [Bartlett et al., 2019] , Lemma 3.3 in [Anthony et al., 1999] , Proposition 2.4 in [Stanley et al., 2004] ). Let ϕ 1 , . . . , ϕ t : R d → R be t multivariate polynomials of degree at most a with t ≥ d and a ≥ 1. Then|{(sgn(ϕ 1 (µ)), . . . , sgn(ϕ t (µ))) : µ ∈ R d }| ≤ et d d , if a = 1, 2 2eta d d , if a ≥ 2,where e is the base of the natural logarithm.Proof of Lemma 2.1. For any t ∈ N + ∩ [d, +∞) and (I 1 , s 1 ), . . . , (I t , s t ) ∈ I × R, there are at most Γt rational functions, denote as p1 q1 , . . . , pΓt qΓt , where each p i is a multivariate polynomial of degree at most a on µ ∈ P ⊆ R d , and each q i > 0 on P. For any µ within each of these decomposed regions, the vector [h(I 1 , µ), . . . , h(I t , µ)] T is invariant. The number of the decomposed regions is given bysgn p 1 (µ) q 1 (µ) , . . . , sgn p Γt (µ) q Γt (µ) : µ ∈ P ≤ (sgn (p 1 (µ))) , . . . , sgn (p Γt (µ))) : µ ∈ R d ≤2 2eΓta d d ,where the last inequality holds by Lemma A.1. We denote these regions as Q 1 , . . . , Q K , whereK ≤ 2 2eΓta d d .Then we have,|{(sgn(h(I 1 , µ) -s 1 ), . . . , sgn(h(I t , µ) -s t )) : µ ∈ P}| ≤ K i=1 |{(sgn(h(I 1 , µ) -s 1 ), . . . , sgn(h(I t , µ) -s t )) : µ ∈ Q i }| = K i=1 1 ≤2 2eΓta d d ,where the equality holds since each h(I j , µ) -s j is an invariant constant for µ varying in any fixed Q i . Therefore, the pseudo-dimension is the largest t such that2 t ≤ 2 2eΓta d d ,which is bounded by the largest t such that1 2 (t -1) ≤ d log 2eΓta d ≤ d 2eΓta/d 8eΓa + log (8Γa) = 1 4 t + d log (8Γa) ,where the second inequality holds because log(x) ≤ x c + log c e for positive reals x and c. Then it follows that Pdim(H) = O(d log(Γa)).Lemma A.2 (Theorem 4.5 in Balcan et al. [2022] ). For any fixed I = (A, b, c) ∈ I, there are at most O (14) n (m + 2n) 3n 2 ϱ 5n 2 degree 5 polynomials decomposing the cutting plane space R n+1 into regions such that the size of the branch-and-cut tree after adding the cut α T x ≤ β at the root remain the same over all (α, β) within a given decomposed region.Lemma A.3 ([Tang et al., 2020 , Conforti et al., 2014] ). For every A ∈ Z m×n , b ∈ Z m , there exists an affine linear transformation that maps a cutting plane derived from a cut generating function for the standard form integer linear programming feasible region{(x, s) ∈ R n × R m : Ax + s = b, x, s ≥ 0, x ∈ Z n , s ∈ Z m } into the corresponding cutting plane for the corresponding canonical form feasible region {x ∈ R n : Ax ≤ b, x ≥ 0, x ∈ Z n }.Proof. Let a T x x + a T s s ≥ 1 be a cutting plane for the standard form integer linear programming problem. For any feasible x and s, we have s = b -Ax. Substituting into the inequality, we obtain the equivalent cutting plane a T s A -a T x x ≤ a T s b -1 in the canonical form problem. Then it's clear that α(a)β(a) = A T a s -a x b T a s -1 = -I A T 0 b T a x a s - 0 1is affine linear on a = a x a s since A, b are considered to be fixed.Theorem 6 in [Gomory and Johnson, 2003 ] yields the following lemma.Lemma B.1. Consider fixed f ∈ (0, 1) and p, q ∈ [2, +∞) ∩ N. π p,q f,s1,s2 (•) is a valid cut generating function, i.e., it satisfies the three conditions outlined in Section 2.1, if s 1 and s 2 are chosen from D p,q f , which is established as follows:D p,q f =                p+q-1 (p+q-1)f -p , 1 f -1 × 1 f , p+q-1 q-(p+q-1)(1-f ) if (p + q -1)f -p < 0 and (p + q -1)(1 -f ) -q < 0, p+q-1 (p+q-1)f -p , 1 f -1 × 1 f , +∞ if (p + q -1)f -p < 0 and (p + q -1)(1 -f ) -q ≥ 0, -∞, 1 f -1 × 1 f , p+q-1 q-(p+q-1)(1-f ) if (p + q -1)f -p ≥ 0 and (p + q -1)(1 -f ) -q < 0, -∞, 1 f -1 × 1 f , +∞ if (p + q -1)f -p ≥ 0 and (p + q -1)(1 -f ) -q ≥ 0.(a) π 3,3 0.6,-10,3 (r) (b) π 3,3 0.6,-7,4.5 (r) (c) π 3,3 0.6,-4,3 (r)Figure 4 : For fixed f ∈ (0, 1), p, q ∈ [2, +∞) ∩ N, the intersection points of π p,q f,s1,s2 (•) and GMI f (•) are fixed.Lemma B.2. For any fixed f ∈ (0, 1), p, q ∈ [2, +∞) ∩ N, and any (s 1 , s 2 ) ∈ D p,q f , the intersection points of π p,q f,s1,s2 (•) and GMI f (•) are fixed. More specifically, for any (s 1 , s 2 ) ∈ D p,q f with s1 ̸ = 1 f -1and s 2 ̸ = 1 f , the set of intersection points is explicitly given byif p , i p : i = 0, . . . , p ∪ 1 - j(1 -f ) q , j q : j = 0, . . . , q -1 ∪ if p -1 , i p -1 : i = 1, . . . , p -2 ∪ 1 - j(1 -f ) q -1 , j q -1 : j = 1, . . . , q -2 ,and these intersection points decompose the interval [0, 1] into 2(p + q -2) subintervals given by the following break points in ascending order:0, f p , f p -1 , . . . , (p -2)f p , (p -2)f p -1 , (p -1)f p , f, 1 - (q -1)(1 -f ) q , . . . , 1.Proof of Lemma B.2. Let s 1 < 1 f -1 and s 2 > 1 f be any valid slopes. A direct calculation shows that the intersection points of π p,q f,s1,s2 (r) and GMI f (r) within r ∈ [0, 1] are given by:ϕ 1 i (r) = GMI f (r) ⇐⇒ s 1 r + i 1 -f s 1 p = r f ⇐⇒ r = i f p , ϕ 2 i (r) = GMI f (r) ⇐⇒ s 2 r + (i -1) 1 -f s 2 p -1 = r f ⇐⇒ r = (i -1) f p -1 , ψ 1 j (r) = GMI f (r) ⇐⇒ s 1 (r -1) + (j -1) 1 + (1 -f )s 1 q -1 = 1 -r 1 -f ⇐⇒ r = 1 -(j -1) 1 -f q -1 , ψ 2 j (r) = GMI f (r) ⇐⇒ s 2 (r -1) + j 1 + (1 -f )s 2 q = 1 -r 1 -f ⇐⇒ r = 1 -j 1 -f q ,where i ∈ {1, . . . , p} and j ∈ {1, . . . , q -1}. Eliminating duplicate points and observing a maximum of 2p + 2q -3 intersection points in nondegenerate cases, the lemma statement regarding the intersection points is confirmed. The interval decomposition is easy to be verified by sorting these points along their first coordinates.Proof of Proposition 3.1. Given any fixed r 1 , . . . , r n ∈ [0, 1), by Lemma B.2, each r j , j = 1, . . . , n, must lie in one of the intervals independent of s 1 , s 2 (if r j is on the boundary of any of these intervals, then π p,q f,s1,s2 (r j ) is a constant). It is not hard to see from the construction and Lemma B.2 that within each interval's interior, there is exactly one nondifferentiable point of π p,q f,s1,s2 (•) in the form of the quotient of two affine linear functions of s 1 and s 2 . For instance,ϕ 1 i (r) = ϕ 2 i (r) ⇐⇒ s 1 r + i 1 -f s 1 p = s 2 r + (i -1) 1 -f s 2 p -1 ⇐⇒ r = (i -1) 1-f s2 p-1 -i 1-f s1 p s 1 -s 2 .We denote these corresponding nondifferentiable points in the form f1(s1,s2) g1(s1,s2) , . . . , fn(s1,s2) gn(s1,s2) , where f i and g i are affine linear functions of s 1 and s 2 . We introduce the following n hyperplanes of s 1 and s 2 :{(s 1 , s 2 ) ∈ D p,q f : f i (s 1 , s 2 ) = r i g i (s 1 , s 2 )}, i = 1, . . . , n. Then, within each region decomposed by these hyperplanes, each π p,q f,s1,s2 (r j ) is a fixed affine linear function of (s 1 , s 2 ). of Theorem 3.2. Lemma A.2 states that there are at most Γ = O (14) n (m + 2n) 3n 2 ϱ 5n 2 degree 5 polynomials decomposing the cutting plane (α, β) space R n+1 such that the branch-and-cut tree size after adding the corresponding cutting plane at the root is the same within each decomposed region. We denote these degree 5 polynomials as ξ 1 , . . . , ξ Γ . In other words, for any (α, β) ∈ R n+1 such that the vectorsgn ξ 1 α β , . . . , sgn ξ Γ α βremains constant, the branch-and-cut tree size after adding α T x ≤ β at the root is invariant.Proposition 3.1 provides a decomposition of the (s 1 , s 2 ) space D p,q f by n hyperplanes. Consequently, there exists a corresponding decomposition of the µ space [0, 1] 2 by n hyperplanes as well, since µ is a fixed affine linear function of (s 1 , s 2 ) as specified by the mapping (6). We denote these decomposed regions by Q 1 , . . . , Q K ⊆ [0, 1] 2 , where K = O(n 2 ) due to Lemma A.1. Fix a region Q i for any i ∈ {1, . . . , K}, the mapping (6), Proposition 3.1 and Lemma A.3 give three different fixed affine transformations from µ to a cutting plane for the canonical linear programming problem. We denote the corresponding cutting plane asα(µ) β(µ) = g(µ) ∈ R n+1 ,where g i , i ∈ {1, . . . , n + 1}, are affine linear functions of µ. Notice thatsgn ξ 1 α(µ) β(µ) , . . . , sgn ξ Γ α(µ) β(µ) = (sgn (ξ 1 (g(µ)) , . . . , sgn (ξ Γ (g(µ))) ,then there are Γ degree-5 polynomials(ξ 1 • g) , . . . , (ξ Γ • g)over [0, 1] 2 such that when they have invariant sign patterns, the branch-and-cut tree size after adding the corresponding cutting plane at the root is the same. Thus, there are O (KΓ) such degree 5 polynomials in total. Then the pseudo-dimension result follows from Lemma 2.1.Proof of Theorem 4.2. The O (k) and O (nk) complexity of Algorithm 1 is straightforward to verify. We now prove the correctness of the algorithm. Given the vectors a 0 , a 1 , . . . , a k ∈ R k defined in Section 4.1, notice that the setx ∈ R k : ⟨a 0 , x⟩ ≤ 1, ⟨a 1 , x⟩ ≤ 1, . . . , ⟨a k , x⟩ ≤ 1 , = (f -1) + x ∈ R k : k i=1 µ i x i ≤ 1, x 1 ≥ 0, . . . , x k ≥ 0 :=G(f , µ)is a translation of a k-dimensional simplex. From the literature on cut generating functions, there exists a so-called lifting region (refer to [Dey and Wolsey, 2010 , Basu and Paat, 2015 , Basu et al., 2013a] ), R ⊆ G(f , µ), such that for any r ∈ R k , there exists a r∈ R ∩ f + Z k such that π f ,µ (r) = max j=0,...,k ⟨a i , r⟩.Theorem 2.2 in [Basu and Sankaranarayanan, 2019] implies that Notice that for any i ∈ {1, . . . , k}, max j=0,...,kR ⊆ G(f , µ) ⊆ ∪ k i=1 [f 1 -1, f 1 ] × • • • × [f k -1, f k ] + {λe i : λ ∈ Z + } ⊆ ∪ k i=1 [f 1 -1, f 1 ] × • • • × [f k -1, f k ] + λe i : λ ∈ Z then for any given r ∈ R k , we take w = ⌊r⌋ + k i=1 1(r i ≥ f i + ⌊r i ⌋)e i ∈ Z k , which is an integer vector such that r := r -w ∈ [f 1 -1, f 1 ] × • • • × [f k -1, f k ]. Therefore, π f ,µ (r) = min z∈Z n maxEQUATIONis a one-dimensional piecewise linear function in λ with at most three pieces (relaxing the feasible region of λ from Z to R). Using the notation in Algorithm 1, let p =k j=1 µ j rj , q = k j=1 µ j f j ≥ 1 τ k j=1 f j > 0 (since f ̸ = 0), a = max rj fj -1 : j ∈ {1, . . . , k} , i * = arg max rj fj -1 : j ∈ {1, . . . , k} , b = max rj fj -1 : j ∈ {1, . . . , k}\{i * } .Then for i ∈ {1, . . . , k}, there are two cases:Case 1: i ̸ = i * . In this case, notice that for λ ≥ 0 we havea = ri * f i * -1 ≥ ri f i -1 ≥ ri + λ f i -1 since f i -1 < 0. Then, max j=0,...,k ⟨a j , r + λe i ⟩ = max p + µ i λ q , ri + λ f i -1 , a = max p + µ i λ q , ais a nondecreasing function of λ over [0, +∞). Therefore,min λ∈Z+ max p + µ i λ q , a = min λ∈R+ max p + µ i λ q , a = max p q , a .Case 2: i = i * . In this case, we can rewrite (7) as max j=0,...,k⟨a j , r + λe i ⟩ = max p + µ i * λ q , ri * + λ f i * -1 , b .The slopes of these three affine linear functions are µ i * q ≥ 1 τ q > 0, 1 f i * -1 < 0, and 0 respectively. The intersection point of the graphs of the first two functions is given by J = λ * , ri * +λ * f i * -1 , whereλ * = qr i * -p(f i * -1) (f i * -1)µ i * -q since p + µ i * λ * q = ri * + λ * f i * -1 ⇐⇒ ((f i * -1)µ i * -q) <0 λ * = qr i * -p(f i * -1) ⇐⇒ λ * = qr i * -p(f i * -1) (f i * -1)µ i * -q .Observe that λ * is always an optimal solution to min λ∈R max j=0,...,k ⟨a j , r + λe i * ⟩, regardless of whether the constant function b is below or above J. Since the maximum of three affine linear functions forms a convex function, the optimal solution of min λ∈Z max j=0,...,k ⟨a j , r + λe i * ⟩ is attained at either ⌊λ * ⌋ or ⌈λ * ⌉. Therefore, we havemin λ∈Z max j=0,...,k ⟨a j , r + λe i * ⟩ = min max j=0,...,k a j , r + ⌊λ * ⌋e i * , max j=0,...,k a j , r + ⌈λ * ⌉e i * = min max p + µ i * ⌈λ * ⌉ q , ri * + ⌈λ * ⌉ f i * -1 , b , max p + µ i * ⌊λ * ⌋ q , ri * + ⌊λ * ⌋ f i * -1 , b .Thus, take the minimum of the two cases, we haveπ f ,µ (r) = min max p + µ i * ⌈λ * ⌉ q , ri * + ⌈λ * ⌉ f i * -1 , b , max p + µ i * ⌊λ * ⌋ q , ri * + ⌊λ * ⌋ f i * -1 , b , max p q , a .Proof of Proposition 4.3. Observe that the lifting regionR ⊆ G(f , µ) ⊆ k i=1 [f 1 -1, f 1 ] × • • • × [f k -1, f k ] + λe i : λ ∈ 0, 1 µ i ⊆ k i=1 [f 1 -1, f 1 ] × • • • × [f k -1, f k ] + λe i : λ ∈ [0, τ ] = k i=1 [f 1 -1, f 1 ] × • • • × [f k -1, f k ] + λe i : λ ∈ {0, 1, . . . , τ } . Let rj = r j -⌊r j ⌋ - k i=1 1(r j i ≥ f i + ⌊r j i ⌋)e i ∈ [f 1 -1, f 1 ] × • • • × [f k -1, f k ], j = {1, .. . , n}. Then for any fixed j, based on the proof of Theorem 4.2, we haveπ f ,µ (r j ) = min i∈{1,...,k} min λ∈{0,1,...,τ } max l=0,...,k ⟨a l , rj + λe i ⟩ = min i∈{1,...,k} min λ∈{0,1,...,τ } max p j + µ i λ q , rj i + λ f i -1 , max rj l f l -1 : l ∈ {1, . . . , k}\{i} = min    max p j q , a j , min λ∈{0,1,...,τ } max    p j + µ i * j λ q , rj i * j + λ f i * j -1 , b j       ,where, as defined in Algorithm 1 and Theorem 4.2,p j = k i=1 µ i rj i , q = k i=1 µ i f i ≥ 1 τ k i=1 f i > 0, a j = max rj i fi-1 : i ∈ {1, . . . , k} , i * j = arg max rj i fi-1 : i ∈ {1, . . . , k} , b j = max rj i fi-1 : i ∈ {1, . . . , k}\{i * j } .This motivates considering the numbers, for any fixed j ∈ {1, . . . , n}:p j q , a j , p j + µ i * j λ q , rj i * j + λ f i * j -1 , b j , λ ∈ {0, 1, . . . , τ }.There are 1 + 1 + (τ + 1) + (τ + 1) + 1 = 2τ + 5 numbers in total, so the pairwise comparison of these numbers can be done by at most (2τ + 5)(2τ + 6)/2 ≤ 2(τ + 3) 2 hyperplanes in the µ space ∆ τ k . This is because, in the worst scenario, the equalityp j + µ i * j λ q = rj i * j + λ ′ f i * j -1 ⇐⇒ p j + λµ i * j - rj i * j + λ ′ f i * j -1 q = 0is a hyperplane on µ, and similar arguments apply to other pairs. These hyperplanes decompose the ∆ τ k space into some regions such that, within each region, the order of the above 2τ + 5 numbers is fixed. Within each region, π f ,µ (r j ) can be expressed as the quotient of two affine linear functions in µ, with the denominator being q = k i=1 µ i f i > 0. Overlapping all hyperplanes across j ∈ {1, . . . , n} results in at most 2n(τ + 3) 2 hyperplanes decomposing the ∆ τ k space.Proof of Theorem 4.4. Similar to what we have done in the proof of Theorem 3.2, let ξ 1 , . . . , ξ Γ denote the degree 5 polynomials given in Lemma A.2, where Γ = O (14) n (m + 2n) 3n 2 ϱ 5n 2 . By Proposition 4.3, there are at most 2n(τ + 3) 2 hyperplanes decomposing the ∆ τ k space such that, within each decomposed region, each coordinate of the cutting plane derived from the cut generating functions π f ,µ is a fixed rational function given by the quotient of two affine linear functions on µ. Also, by Lemma A.1, these hyperplanes decompose the µ space ∆ τ k into at most2n(τ + 3) 2 k k ≤ 2 k n k (τ + 3) 2k := K regions, denoted as Q 1 , . . . , Q K , where K ≤ K.We fixed a region Q i for any i ∈ {1, . . . , K}. For any µ ∈ Q i , we claim that α(µ) β(µ) can always be expressed as p i (µ) q(µ) ∈ R n+1 , where each coordinate of p i is an affine linear function of µ, and q is a fixed affine linear function of µ. This is because, according to the form derived in Proposition 4.3, the values of the trivial liftings are either rational functions with the denominator q(µ) = µ i f i > 0 (which is fixed once the instance I = (A, b, c) is fixed), or just some constants independent of µ. Then by Lemma A.3, with a fixed I = (A, b, c), the cutting plane for the original problem is a fixed affine transformation of the above form. Therefore, in this fixed region Q i , the final form of the cutting plane is fixed and can be written as p i q (µ) ∈ R n+1 . Therefore,ξ 1 α(µ) β(µ) , . . . , ξ Γ α(µ) β(µ) = ξ 1 • p i q (µ), . . . , ξ Γ • p i q (µ)gives Γ fixed rational functions of µ, decomposing Q i , in the form of the quotient of two degree 5 polynomials. For any µ ∈ Q i within each decomposed region, these Γ rational functions have an invariant sign pattern, hence the tree size after adding α(µ) T x ≤ β(µ) at the root remains the same. By traversing all Q i , the total number of such rational functions is given byO 2 k n k (τ + 3) 2k (14) n (m + 2n) 3n 2 ϱ 5n 2 ,then the pseudo-dimension result follows from Lemma 2.1:Pdim T k (•, µ) : I → [0, B] | µ ∈ ∆ τ k = O kn 2 log((m + n)ϱ) + k 2 log(nτ ) .NeurIPS Paper Checklist 1. Claims 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. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: This paper primarily focuses on theoretical aspects. However, implementation details can be found in Section 6 and in the code.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [No] Justification: This paper primarily focuses on theoretical aspects. The computational experiments in the Section 6 are only to provide some crisp insights and to verify the theoretical results.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • 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). 
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. 
 
 Appendix:  


Decision: In this submission branch-and-cut algorithms are studied in a data-driven framework. For this, parameterized families of cut generating functions are considered and their sample complexity is analyzed. One assumes that problem instances are generated according to some unknown probability distribution and the question is how many samples have to be observed to find values for the parameters of the cut generating functions such that the expected size of the truncated branch-and-cut tree is approximately minimal. It is well-known that this question can be reduced to bounding the pseudo-dimension of the associated function class.

The main theoretical contribution is the analysis of the pseudo-dimension of different classes of cut generating functions, leading to upper bounds on the sample complexity. The submission concludes by an experimental evaluation for the multiple knapsack problem and packing problems. These experiments show that learning the parameters of the cut generating functions can indeed lead to be smaller branch-and-cut trees than the classical Gomory's mixed integer cut.

The reviewers think that this line of research is interesting and that the submission makes a strong theoretical contribution. The reviewers, however, also agree that it would be interesting to extend the experimental study, which seems somewhat preliminary at the moment.

Reviews: review: paper_summary: paper_summary: This work presents sample complexity results for learning parameters for certain classes of cut generating functions, along with some numerical experiments. These are functions that determine coefficients of cutting planes to help solve mixed-integer programming problems, and some of the most effective cutting planes in practice (e.g. GMI cuts) can be expressed as cut generating functions. More specifically, this paper proves pseudo-dimension bounds on an established class of one-dimensional cut generating functions, and on a class of k-dimensional functions, both of which generalize GMI cuts. This latter function can be (non-trivially) computed efficiently. Furthermore, the authors provide pseudo-dimension bounds for these functions for the case where the parameters are learned by a neural network. Finally, the paper provides numerical experiments to highlight the learnability of parameters for these families of cuts on small instances.
strength_weakness: strength_weakness: None of the weaknesses that I see are particularly major. I would have liked to see further experiments on more realistic scenarios, but I understand that we can derive insights from a very focused experimental setup and the theoretical contributions are the main focus of this paper. I leave specific issues for the Questions section below.
questions: questions: These are all minor comments.

1. It would be nice to add the geometrical interpretation of the parameters of the functions to provide a quicker understanding for the reader. It takes a little while by looking at the functions and the examples (which are helpful) to understand, and for me it was easier to understand some of the proofs after I understood what those parameters were doing. You can for example add them with Figure 2 in the Appendix. 

2. I am not sure I can visualize the k-dimensional function very well. Would you be able to explain what motivates this particular function, and perhaps include 3d examples for the case where k = 2 (like you did with k = 1)?

3. Is the definition of tree size here the worst-case tree size across variable and node selection? If relevant, could you add a precise definition of tree size to the paper?

4. Could you add to the paper why these cut generating functions are extreme? I believe those come from previous work (e.g. the 1-row one has two slopes)?

5. I am confused as to how you have 5-row cuts and 10-row cuts for knapsack with 2 and 3 rows. If I missed something, please add the explanation to the paper.

6. This question is mainly out of curiosity (though could be interesting to discuss in the paper if you have a good answer): I see that increasing the number of rows sometimes help, but generally do not seem to be too helpful. It may be more difficult to find a good multi-row cut with more rows but a fixed number of samples. Do you have any sense on how the quality of your cuts would improve with more samples?

7. Please fix the citation types (those missing parenthesis).
limitations: limitations: There is not much discussion on limitations, though the paper is mostly theoretical. Perhaps the paper could discuss some more what these results could lead to in future work, and limitations of interpreting these small-scale experiments.
paper_summary: paper_summary: This paper studies the learning of generic classes of cut generating functions, which can be used as an algorithmic tool for solving integer programming problems. The paper presents a handful of cut generating function families, studies the learning complexity of these functions, and presents a computational study of those CGF families on standard integer programming problems.
strength_weakness: strength_weakness: I feel like there is some connective tissue missing from the paper, particularly joining the computational study with the rest of the paper. Section 5 seems like an interesting connection to draw, but does not appear in the computational study and feels a bit disjointed from the rest of the paper. 

And while the paper spends much of its effort to show that the cut generating functions _can_ be learned, the computational study is relatively rudimentary and does not really attempt to develop very sophisticated techniques to actually learn the CGFs in practice (to be clear, this is a reasonable tradeoff to make for a theoretical paper).
questions: questions: None.
limitations: limitations: Yes.
paper_summary: paper_summary: The paper is concerned with the interplay of learning theory and the branch-and-cut algorithm for solving mixed-integer programs (MIPs).
Concretely the authors analyse the problem of cut selection.
In general, cut selection asks for a given (class of) MIPs: What cut(s) should be added to the lp relaxation, to speed up the branch-and-bound algorithm as much as possible? The authors limit the scope of this board question to:
How should one parameterize a concrete cut-generating function, to generate a single cut, which, when added to the problem at the root node, minimizes the number of branch-and-bound nodes the solver has to create?
For the selection of a cut generating function, the authors list three criteria:
1: There should be an efficient way, to compute the cutting planes 2: One should be able to prove concrete sample complexity bounds 3: One should be able to demonstrate that the cutting planes are “significantly better in practice than classical cuts”
The authors then proof sample complexity bounds for three different settings.
1) One wants to find the parameters for the Gomory and Johnson [2003] cut generating function (which generates cuts from a single row of the simplex tableau) minimizing the expected tree size for instances drawn from $D$.
2) One wants to find the parameters for a subfamily of cut generating functions studied by Basu and Sankaranarayan [2019]  (which generate cuts from k many rows of the simplex tableau) again minimizing the expected tree size for instances drawn from $D$.
3) One wants to train a neural network to choose a good instance (not distribution) dependent cut generating function.

In their numerical experiments, the authors investigate the effect of the cut generating functions on some generated knapsack and partition problems. The goal is to find evidence for better performance of the chosen cut generating functions when compared to classical (here GMI only) cuts. For 1-d knapsack, the cut generating function is shown to clearly outperform GMI cuts in the chosen setting. For all other instances, GMI performs worse than at least one cut generating function, but the difference is smaller, especially for the packing instances.
strength_weakness: strength_weakness: The main weakness I see is the little empirical evidence for some strong claims about the  Gomory and Johnson [2003] cut generating functions. See e.g. line 220 and 251: “and they result in significantly smaller tree sizes compared to traditional cutting planes”. This statement seems over the top.
1) the numerical experiments do not always indicate “significant”
2) the only tested classical baseline are GMI cuts, which are by far not the only class of cuts doing heavy lifting in modern branch-and-cut solvers
3) for the instances on which the impact is high (1-d Knapsack), I think the combination of setting and instance class, does not allow general claims, see below.

L 316: “Instances were generated using the distribution proposed by Chvátal in Chvátal [1980], also used in Balcan et al. [2021b].”
-> this is not correct. The authors use the same parameters as Balcan et al., but they are at best related to Chvátal instances. Chvátal explicitly designs instances, which are provably hard to solve for certain branch-and-bound algorithms.
To achieve this, all constraint coefficients $a_{ij}$ are sampled from $[1, 10^{(n/2)}]$ and $b_j = floor(\sum (a_i / 2))$.
Balcan et al. sample a_ij from a uniform normal distribution $N(50, 2)$. This leads to extremely similar a_ij (so quite far from Chvátals distribution) values and makes the instances extremely easy in practice. For 1-dimensional knapsack the original constraint of the problem formulation is tight. When turning on primal heuristics (which are turned off by the authors, but not by Balcan et al.) Gurobi solves all instances at the root node, before even solving the relaxation. From my perspective, there is little to learn from experiments on these types of instances (1-d knapsack).
I am well aware, that the authors focus on theoretical aspects of machine learning and cut selections, but when explicitly listing “3) we should be able to demonstrate that these new cutting planes are significantly better in practice than classical cuts” (line 109) as one of three requirements for the cut generating functions, I expect stronger empirical evidence.
questions: questions: Additional and minor remarks:
- L 6: “optimal cutting planes”. “Optimal” is very global and strict. Maybe “good”
- L 24: “small representative sample”. Representative seems subjective
- L 36: “we understand many of their theoretical properties”. “We” sounds ambiguous here. Maybe “many theoretical properties are understood”
- L 53: “with several excellent insights”. “Excellent” is quite subjective
- L 144: Z^n should be Z^k
- Figure 1: The use of the label “y” for the y-Axis is confusing to me
- Figure 1: For r = 1 the graph has a red circle, indicating it is not defined here. The same should hold for r=0?
- Figure 1: The font seems unnecessarily small
- L 296: If “their” in “A direct applications of their main theorem” refers to Cheng et al. [2024] from line 278, I feel like the reference is too far away, for the reader to parse “their” in the context of Cheng et al.
- L 314: The two types of instances under consideration are quite similar (in referenced Tang 2020: “A knapsack problem is a binary packing problem”.) I think it might make sense to mention their similarity and the fact, that one is integer and one is binary
- Table 1: For $d$-dimensional knapsack, there are $d$ constraints significantly different from the remaining $n$. Are these constraints considered first, for k-row? Does this explain why e.g. 2-row is best for 2-d knapsack?
- Small and capital letter inconsistency in references. E.g. 352 & 358: “cambridge university press” and “Cambridge University Press”
limitations: limitations: The author's discussion of their limitations is fine, apart from the part about the numerical experiments (see weaknesses).

Comments: comment: Thank you for the response. This answers all my questions and I appreciate the changes to the paper. I have read all reviews and rebuttals and I will keep my score. I am not too concerned with the limited computational experiments given the nature of this paper, and while I agree with the main concern of 6RAE, in my opinion it should be sufficient to change the language so that it is clearer that this is more of a scientific study rather than a practical one.