Learning Cut Generating Functions for Integer Programming
Authors: Hongyu Cheng
Amitabh Basu
Venue: NeurIPS 2024 poster (2024)
Keywords: Integer programming
branch-and-cut
cut generating functions
cutting planes
branch-and-bound
sample complexity
learning theory
Primary area: optimization

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.

Learning Cut Generating Functions for Integer Programming
Hongyu Cheng
Amitabh Basu
Dept. of Applied Mathematics & Statistics
Dept. of Applied Mathematics & Statistics Johns Hopkins University Baltimore, MD 21218 basu. ami taai@jabh@@u edu
Johns Hopkins University
Baltimore, MD 21218 hongyucheng@jia edu
Abstract
The branch-and-cus algorithm the method of choice to solve large scale integer programming problems in practice. A key ingredient of branch-and-cut is the use cutting planes which are derived constraints that reduce the search space for an optimal solution. Selecting effective cutting planes produce small branch-and-cut trees is a critical challenge in the branch-and-cut algorithm. Recent advances have employed data-driven approach select good cutting planes from parameterized family, aimed at reducing the sranch-and-bowd tree size (in expectation) for given distribution of integer programming instances. We extend this idea the selection of the best cut generating function (CGF), which is a tool in the integer programming literature for generating wide variety of cutting planes that generalize the well-known Gomory 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.
Introduction
Integer linear programming is an optimization framework that has diverse applications in logis-
ties [Arntzen et al.) 1995] Sinha et al., 1995 Hane 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 Chen et al. 202 Malioutov
ct al. solving integer programming problems is the well-known branch-and-cut paradigm [Schrijver 1986 Nemhauser and Wolsey, 1988 Conforti et al., [014]. This procedure has two critical ingredients: branching, which way to subdivide the problem into smaller subproblems, and the use of cutling planes which a way to reduce the feasible region of a (sub)problem by deriving additional linear constraints that implicitly implied by the integrality of the decision variables. To get concrete algorithm from this high level framework, one needs to make certain choices (such as how to branch, which cutting plane use etc.) Thus, at high level, the branch-and-cht method is really collection of algorithms equipped with a common set of "tunable parameters". Upon a specific choice of values for these parameters, one actually obtains well-defined algorithm that one can deploy on instances of the problem.
2023 to give a small sample of applications and related literature. The method of choice for
38th Conference on Neural Information Processing Systems (NcurIPS 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 survey and the references therein.
In this paper we focus on some foundational aspects of the use of machine learning to improve One can formalize the problem as follows. Given
algorithmic performance of 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 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 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 recent series of papers [Balcan et al.) [221aa è b. 2022 2018) with several important insights and technical contributions. The broader question of selecting a good algorithm from a suite of algorithms for 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 lot of recent activity in the related aspect of algorithm design with predictions; see, e.g., [Mizzenmacher 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 b 2022]. Thus, we wish to learn what choice of cutting planes within the branch-and-oo procedure gives the best performance. Our results differ from this previous work in two main ways.
1. In [Balcan et al. 2021c 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 tremendous amount of progress in our understanding of this theory in the past 15 years. The main point is that cut generating functions give 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 al. 2021c 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., 202 b 2022, 2018 focuses on making 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 (016]. 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 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 special case of such cutting planes where data from a single tableaux row is used. Our first result (Theorem (.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 parameterized family of cut generating functions that uses information from k rows, these sample complexity results are extended to learning neural networks that map instances to cut generating functions, achieving an instance dependent performance.
for any fixed natural number k 2 2. In Section 5
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 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 and achieve aims 1) and 2). 6ocction6]giver 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 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 and
2 Formal setup of the problem
Throughout the paper, we will use the following standard notations. The sign function sgn R + 10 defined by sgn(x) 1 if 2 0 and sgn(x) = 0 if x < 0. The set Aj ( : 24 D.
x, = represents d-dimensional simplex, where T 2 2d is
some predefined number. For set of vectors (x'.....x' x²) S. Rdd we use superscripts to denote vector indices and subscripts to specify the coordinates in vector; thus, x² refers to the j-th coordi- nate of vector x'. The floor and ceiling functions, denoted by [.] and [-] respectively, round each component of a vector down up to the nearest integer. We denote [x] x [x] for any E Rd representing the fractional part of each component of the vector.
2.1 Integer linear programming background
Given positive integers m, n, pure integer linear programming (ILP) problem in canonical form can be described as:
max cTx
(I)
s.t. Ax < b. 0,x
for some A E gm b E 2n and e E RR. This problem is represented by the tuple (A, b, c). In this paper, we consider the set of ILP instances such that for any (A, c) E Z. there exists universal constant such that sup [[||]||oo Ax < b, 2 0} S e.
cutting plane for ① is given by (ox, 83 E RM x R such that the inequality aTx x S ,3 satisfied by
all points in the feasible region (x 2" Ax b, 2 0} of D.
3

---

Cut generating functions. We now present the technique of cut generating functions to derive cutting planes for T.. Consider the equivalent standard form of TT] after introducing slack variables:
Äy b, _
(2)
where Ā = [A,1] E zmx(=tm), The simplex tableaux of the above problem with respect to basis B _ (1....,m n} with [B] = m is given by
B A ANY = A y E Zm+n
where Ap and An represent the submatrices of Á corresponding to the columns indexed by and N (I...., + n) \ B, respectively. We select any k rows, where k E {1, (l,..,, from ( such that the right-hand side vector is not integral, and write the resulting system as:
n Σ rry.' =f, y. 24 Zt.
z
Z are subvectors of A AN and A respectively, corre- sponding to the selected rows. Suppose we have a function क R + I2, satisfying the following conditions:
where rl ,.... r E RR* and E R
1. (0) = 0, x(f) 1,
2. subadditivity: <[r + r') S (T) + +(r'), Vr, R
3. periodicity: л(r + w) = क (r), Vr RR, w e Zt,
then for any feasible y and z we have the following inequality:
n
π (r)) s Σ n Σ x (r'y
(f) x z rry:"
(5)
It's noteworthy that the optimal solution to the relaxed linear programming problem, [y y
A b, o). will always violate this inequality. By substituting out the slack variables using ② the inequality Σm (r')
becomes a cutting plane ax S for [ see Lemma A.3
We present two classical examples of one-dimensional (i.e., k = 1) cut generating functions here (as and Figure lb A family of one-dimensional cut generating functions
well as their plots in Figure and
we will use in this paper will be presented in Section 3 and a family of k-dimensional cut generating
functions, for arbitrary 1, will be presented in Section 4
Gomory fractional cut [Gomory. 1958 : Define CG = H Applying this function to the j-th row of the simplex tableau 4 with I & Z. the valid cut (5) translates to the Gomory fractional cut:
(r)
[fy].
f
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-integen cut [oomory 1960
The GMI cut function GMI is defined as Ir]
fr]
when [r] < [ʃ]. and i-17 when [r] > [.] Applying to the j-th row with fy & Z, the valid cut
1-(r)
translates to the GMI cut:
F
Σ d
Σ 1
2
Σ Fyy
Σ
(1
(D [t)]
y
E|

---

0
size for (a) C
(b) GMI,
(c)
Figure I: Three cut generating functions on [0, 1), where P.g Fes.32
is defined in Section 3
2.2 Sample complexity of selecting cut generating functions
We will consider parameterized families of generating functions and the sample complexity of learning which cut generating functions work well. More precisely, we will track how well branch- and-cut performs when the cutting plane corresponding to specific generating function is added to the imitial linear programming relaxation of the problem, a.k.a the root node of the branch-and-cre free. In this paper, we consider the branch-and-cut tree built with 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 the quantitative measure of performance, which is strongly correlated with the overall solve time.
Consider unknown probability distribution DD the instance space I. We presented with problems drawn independently and identically distributed (i.i.d.) from this distribution. We also have family
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(1, , μ1) [0, B] Ž will denote the truncated branch-and-cut some B > O, when the cutting plane c(I, (u) is used at the root node for processing T.
The objective is find the cut generating function that minimizes the expected tree size the distribution D, i.e., we want to solve the stochastic optimization problem min E,~ph(I, (1, p.). For any 0 and 8 E (0, 1), the sample complexity of the problem is natural number N ((s, 5) 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 5. Thus, if we have that many samples, we can use the cut generating function that minimizes the average tree size on our instances (this 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 will do well in expectation, i.e., generalize unseen instances, with high probability.
The pseudo-dimension (dim(H) is measure of the 'complexity' of the associated function class H = [M(-, 14) E PJ. and a key concept closely related to sample complexity. it defined as the largest integer for which there exists set of instances and real values (J1, 81),..., (,, such that
IR
2' ((sgn(((41 μ1) $1), ..., sg p1) st)) p E P)]
A classical result in statistical learning theory (e.g., Theorem 19.2 in [Anthony et al. 1999 implies the sample complexity bound
((E - B²
(1))
(P) log
+ log
Thus, our task reduces to finding an upper bound for Pdim(?().
In learning theory, identifying the piecewise structure of the function class H = [h(, P} is a standard technique for bounding its neuuoodimensionn (see [Anthony et 1999 Bartlett al.
1998 2019 Sontag et al.) 1998 Balcan et al. 2021a] aa) ). For a fixed instance E I. one shows that
5

---

the parameter space P can be partitioned into regions such that the function h[I, (4) behaves as fixed 'simple function' within each region. The partition defined by of functions P and the regions of the partition correspond to parameter values in lA 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 Proposition 3.
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 more general version of this result is given in [Balcan et al. 2021 but our specific version is asymptotically better than direct application of the general result, since Sauer's lemma ([Sauer
1972. Shelah 1972)) is not involved in the proof.
Lemma 2.1. Let
Z, where S R for a natural number d. Suppose that for any fixed I E I, there exist at most I functions, each expressible as the quotient of polynomial of degree most and strictly positive function. These functions partition P into regions in which 1(T, 1)) remains constant. Then, the pseudo-dimension of the function class (h( ()) E PP is given by:
Pdim (fh(-, (z)
P}) = O(dlog(Ta)).
Remark 2.2. In Theorems 3.2 and 4.4 that bound the pseudo-dine souudddimmeniins. we assume that the row(s) used for generating the cut are prehxed for all instances I E However, 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.
straightforward to
3 One-dimensional cut generating functions
In this section, we present a family of one-dimensional cut generating functions (originally proposed in (Gomory and Johnson, 22003) that we believe satisfy the three criteria laid out in the Introduction, i.c. cutting planes can be obtained efficiently from them (we present closed form formulas below), sample complexity (pseudo-dimensee bounds can be established rigorously (Theorem 3.2 below). and they result in significantly smaller tree sizes compared to traditional cutting planes (Section
3.1 The construction
(a) vo.3. 2.7
(b) mu.s. -..., (r.
(c) TD.. 12.6.2.5 (r)
Figure Three examples of the one-dimensional generating functions F.s.. [0, 1).
For any f E 1), p. (0 $1, E R, let
P.g Fe (r) max min (r)( : : 1= 1....
.......P........... ....pp U min v())
:j=
where
1 1- fsi
(,(r) s2r + (i - 1) 1 f82 =1,..... 1,...,P,
(r) 818 +
p
(r)) si(r + (j 1) 1+ 1+ (1- f)
(3(r) s2(r 1) + + f)
..... 1.
0-1
q

---

See Figures Ic and for examples with different f. P. q and $1, Let D denote the set of all (s1, 82) such that Tf (+) is 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. which indicates that D. is always a (possibly semi-infinite) rectangle.
3.2 Pseudo-dimension bound
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 seudo-dimennion bounds in Theorem 3.2 using Lemma 2.1
Proposition 3.1. For any fixed f (0, 1), P.qe 2, +o0,, and ri,..... ......,Ty. In E [0, 1), there exists decomposition of the (2) space D given by at most n hyperplanes such that, within each
region, each coordinate of the cutting plane function of ($1,82).
Th Theess (ri).....
T. San (rw) is fixed affine linear
To make the parameter selection in more controlled manner, introduce large positive constant M and adjust the bounds of 81 and 82 given in Lemma B. to finite ranges by replacing -oc and too with --1 M and 7 M, respectively, in the corresponding cases. This restricts (#1, 82) to
the product of 2 bounded intervals, denoted as [1,, u1] x [72, u2]. which is a bounded subset of D
This allows to use parameters μ4 (11 122 E [0, 1] to control $1 and $2 as follows:
$1 = U1 μn (u1 12), 82 = l2 + #2(222 (2).
(6)
We remark that setting fa A42 0 gives the GMI, function.
We now have all the pieces to state the precise cecudo-dimension bound.
Theorem 3.2. Let p, q 2 2 be arbitrary, but fixed, natural numbers. Let T(I, μu) denote the tree size
of the branch-and-cre algorithm after adding the cut induced by the cut generating function x ff, (+) the root for a given instance I I. where $1, $2 are given by the mappings (6) based on fl1 p2g and f is determined by T. Then, the pseudo-dimense
is given by
Pdim (fT(: (b) I - [0, B] & E [0, 1]3)) = (n² log((m + n)e))
4 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-dimensioe 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 been studied previously in the literature (from a theory or computational perspective). though they are subclass of cut generating functions studied in Basu and Sankaranarayanan, 2019).
bounds can
4.1 The construction
Recall that is the total number of constraints in the original integer program ① and A: S m is the number of rows from the simplex tableaux used to derive the cutting planes. For any f E [0, 1) MO)
and μ Mi..... [4]] E A with a universal large constant > 2mn let
a E u.e'
a
a*
fr e R
Σ M,f,
where ex denotes the i-th standard basis vector in IR Define Tf. I + R R
(r) == min max (a (a', r 2). z52* i=.....
Using well-known results from cut generating function theory, can be shown that ,i, satisfies the three conditions in Section 2.1 to qualify as cut generating function; see, for example, the analysis in Basu and Sankaranarayanan| 2019]. is noteworthy that for each μ e' with E (1....,k)) the function Tf v is equivalent the oneddimensional GMI function GMIr, defined in Section 2.1
7

---

1.9
1.0
8.0
0.5
0.0
0.5
0.0
0.0
0..2 0.7
00.3
(0..5
0..5 0.5
[0.33 [o.8 {0.6) 0.6 0.2
(a) (f, p))
(b) (f. p1) =
(c) ()
0.7
Figure 3: Three examples of the 2-dimensional cut generating functions Tf on [0, 1)
Remark 4.1. As pointed out in the introduction, both families of cut generating functions considered this paper are extreme for the pure integer infinite relaxation problem [Conforti et al.) 2014 Gomory and Johnson 1972a bj. The first family, described in Section [.. was proved to be extreme in Gomory and Johnson's 's original paper [Gomory and Johnson 2003 For k-dimensional
CGFs, they minimal valid functions as they the trivial lifting of the gauge function of maximal
(f Z*) -free convex sets with the covering property [Basu et al. 201 3a 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
4.2 Computation and pseudo-dimension
Algorithm [ shows how to compute the function values (T) (the cutting plane coefficients), in time that is linear in the dimension k. We then expose important piecewise structure of the corresponding family of cutting planes for (2) in Proposition 4.3 This piecewise structure the key
to establishing upper bounds on the pseudo-dimension (recallTemma 2.T for learning the optimal
cut generating function from this family in Theorem
Algorithm 1 Computation of TT. (r)
I: Input: & E N₂ n [2, oo), f 10,1)* MO), = ux] E AT, 12
2: Output: TF (r)
3: Fer r [r]
Eh 21=1 1(r 2 f + [rr)
D I(.) is the indicator function
4: p Σ P.P.
5: < E p.f.
6: 8 + f--1:... f-1
Fr
7: + max (s, : {1....,k}}
8: 1" <- arg max (s, : {1..... ... k))
9: b t max {s, : (1..... k) M
(f. 1)p
X p: (F.- 11-
11: [T, (r) + min max
ptp.
[*1
F. +
b) max
ptp. [X*
+u+
6) max %2.4 f,
9
9
Theorem 4.2. For any [0, (0), (k) time. Therefore, the cutting plane obtained from Te, can be computed in (km) time.
2k, and μ E AT, Algorithm 1 computes TT. in
Proposition 4.3. For any fixed E Z [2, +oo), f E [o, 1)*1 (0), r r E R* and 7 2 2k, there exists decomposition of A obtained by at most 2n(7 + 3)² hyperplanes such that within each region, each coordinate of the cutting plane [TTE, (r)), FF (r") is fixed rational function given by the quotient two affine linear functions of μa, where the denominator is always fixed positive function of μ.

---

Theorem 4.4. For any fixed & E 2n too,, let (I, μ1) denote the tree size of the branch-and andnchh-nd-uutt algorithm after adding the cut induced by " the root for given instance I E I. where is determined by T. Then, the pseudo-dimension is given by
Pdim (1Th (c/1)) I + [0. B] 1a (T) O (km? log((m - n) + k2 log(nr)).
5 Learnability of instance-dependent cut generating functions
The authors in [Cheng et al., 2024] studied the learnability of neural networks that select instance- dependent algorithms for any computational problem, as opposed to selecting 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 single cut generating function that has the best expected performance overall (as was done in Sections 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 neural network (pr Rd x R IR consisting of 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 + Ie is employed to transform instances / = (A, b, c) E I into suitable neural network inputs, where a straightforward choice for Enc could be the flattening of T into a vector, although more complex encoding strategies can be adopted capture additional structural information about the instances. The primary goal is to input the encoded instance Enc(T) 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 instance-dependee manner, as demonstrated in Table | A direct application of the main theorem in [Cheng et al. 2024] yields the following results:
Theorem 5.1. Let h, h²* 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 h[I, w) = T(I, (22 (Enc(I)) (I), w)) and Me(T w T [T, pa (Enc(T), w)), where T and T are the tree size functions defined in Theorems 3.2 and 44.4] respectively. Then the pseudo-dimension of these two learning problems have the following upper bounds:
Pdim (fb(,, w) w E IR ") = O (LW log(U (U + +) + n² log((m + n)e))
Pdim (f1 (,w)
w) w E ER)) O (LW log(U + k)) + A:W log(nr) + +n² n2W log((m + n))))
6 Numerical experiments
Setup. We conducted numerical experiments to evaluate the performance of both die-dimensional and k-dimensional cut generating functions, as discussed in Section 3 and Section 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 the test set of size 100 to evaluate performance. All results presented in Table are based on the test set, except for the last column. The experiments were run on Linux machine equipped with a 12-core Intel 12-0 CPU and 32GB of RAM. We solved the integer programming problems using Gurobi 11 11.0.1 (Gurobi Optimization/ LLC 2023 with default cuts, heuristics, and presolve settings turned off. The code and data used in all CX experiments are available at https: / thub. Saamm/oonyy--hhhneee Learn
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. (022b)) 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 constraints and n variables. We note that the knapsack problem can viewed as special case of the packing problem with binary variables. The packing instances were generated using the distribution from [ang et al. 20201.
Cutting plane strategies.
The following cutting plane strategies were evaluated and compared:
1. GMI: Classical Gomory's ' mixed integer cut defined in Section 2.
2. 1-row cut: Generated using the oeeeiinnsionnl cut generating function defined in Section We fixed
2 and performed a grid search with step size of 0.1 to select the best parameter μ E {0, 0.1.0.1..... 0.9, 1)2.
3. k-row cut: Generated using z defined in Section with E (2, 5, 10). We uniformly sampled 121 different la the simplex A (see [Gordon-Rodriguee 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 the training ser. 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 integer programming literature, is outside the scope of this paper. All cuts are generated from the first of the simplex tableau with non-integer right- hand side, and the k-row cut is generated from the first such rows. Also, to select the best parameters based on samples (i.e., solve the ERM problem), used simple grid search and optimized through enumeration, since the branch-ande tree size is highly sophisticated function of the added cutting planes at the root node.
Numerical results. As shown in Table the two cut generating function families considered in this paper reduce the size of the branch-and-cuu tree compared to the GMI cut. Although the improvement over the GMI cut on the test set less obvious for the packing problem, the last column 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.
Table 1: Average tree sizes on 100 instances, after adding a single type of cut at the root.
Problem Type
GMI
1-row cut
2-row cut 5-row cut
10-row cut
best I-row cut
Knapsack( (20 1)
158.88
87.0
n/a
n/a
n/a
35.54
Knapsack(30, 1)
832.16 16
58.84
n/a
n/a
n/a
13.98
Knapsack(50)
3543.91
277.01
n/a
n/a
n/a 125.85
Knapsack 2)
399.86
316.8
178.68
234.09
203.66
102.07
(hapsack(30,5
4963.91
431 1.04
3430.37
2817.55
2822.37
3561.36
Packing 15, 30)
389.67
367.48
376.86
401.87
391.44
303.72
Packing (20, (20,40) 40)
1200.55
1123.9
1214.92
1113,82
1185.26
738.58
Acknowledgments and Disclosure of Funding
Both authors gratefully acknowledge support from Air Force Office of Scientific Research (AFOSR) grant FA95502010341 and National Science Foundation (NSF) grant CCF2006587. The first author also acknowledges support from the Johns Hopkins University Mathematical Institute for Data Science (MINDS) Fellowship. the Duncan Award 24-33, and the Rufus P. Isaacs Graduate Fellowship.
10

---

References
Temitayo Ajayi, Seyedmohanmadhosseiin Hosseinian, Andrew J Schaefer, and Clifton D Fuller. Combination chemotherapy optimization with discrete dosing. INFORMS Journal Computing. 36(2):434455, 2024.
Martin Anthony, Peter L. Bartlett, Peter L Bartlett, al. Neural network learning: Theoretical foundations, volume 9. Cambridge: Cambridge University Press, 1999.
Bruce C Arntzen, Gerald G Brown, Temyy P Harrison, and Linda L Trafton. Global supply chain management at Digital Equipment Corporation. Interfaces, 25:69-93, 1995.
Gennadiy Averkov and Amitabh Basu. Lifting properties of maximal latrice-free polyhedra. Mathe- matical Programming. 154:81-111, 2015.
Egon Balas. Intersection cuts a new type of cutting planes for integer programming. Operations Research, 19:19-39, 1971.
Maria-Florina Balcan. Data-driven algirithm design. In Tim Roughgarden, editor, Beyond the Worst Case Analysis of Algorithms. Cambridge University Press, 2020.
Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch. In International conference on machine learning, pages 344-353. PMLR, 2018.
Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data is sufficient learn perforenfn algorithms? generalization guarantees for data-driven algorithm design. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pages 919-932, 2021a.
Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. Improved sample complexity bounds for branch-and-cut arXiv preprint arXiv:2111.11201 2021b.
Maria-Florina F Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitereik. Sample com- plexity of tree search configuration: Cutting planes and beyond. Advances in Neural Information Processing Systems, 34:4015-4027. 2021c.
Maria-Florina F Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik, Structural anal- ysis of branch-and-cut and the learnability of gomory mixed integer cuts. Advances in Neural Information Processing Systems, 35:33890-33903, 2022.
Peter Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear ve dimension bounds for piecewise polynomial networks. Advances in neural information processing systems, 11, 1998.
Peter L Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mchrabian. Nearly-tight ve-dimension and pscudodimension bounds for piecewise linear neural networks. The Journal of Machine Learning Research, 20(1):2285-3011 2019.
Amitabh Basu and Joseph Paat. Operations that preserve the covering property of the lifting region.
SIAM Journal on Optimization, 25(4):2313-2333 2015.
Amitabh Basu and Sriram Sankaranarayanan. Can cut-generating functions be good and efficient?
SIAM Journal on Optimization, 29(2):1190-1210 2019.
Amitabh Basu, Manoel Campëlo, Michele Conforti, Gérard Cornucjoss, and Giacomo Zambelli. Unique lifting of integer variables in minimal inequalities. Mathematical Programminng 141: 561-576, 2013a.
Amitabh Basu, Robert Hildebrand, Matthias Koppe, and Marco Molinaro. A (k+1)-slope theorem for the k-dimensional infinite group relaxation. SIAM Journal on Optimization, 23(2):1021-1040, 2013b.
Dimitris Bertsimas and Jack Dunn. Optimal classification trees. Machine Learning, 106:1039-1082, 2017.

---

Dimitris Bertsimas, Christopher Darnell, and Robert Soucy. Portfolio construction through mixed integer programming Grantham, Mayo, van Otterloo and Company. Interfaces, 29:49-66, 1999.
Dimitris Bertsimas, Angela King, and Rahul Mazumder. Best subset selection via modern opti- mization lens. The Annals of Statistics, pages 813-852, 2016.
Rui Chen, Sanjeeb Dash, and Tian Gao. Integer programming for causal structure learning in the presence of latent variables. In International Conference on Machine Learning (ICML), pages 1550-1560. PMLR, 2021.
Hongyu Cheng, Sammy Khalife, Barbara Fiedorowicz, and Amitabh Basu. Data-drivens algorithm design using neural networks with applications to branch-and-cut, arXiv preprint 02Xx:2240..02328., 2024.
Michele Conforti, Gérard Cornuéjols, and Giacomo Zambelli. Integer programming, volume 271. Springer, 2014.
Sanjeeb Dash, Oktay Gunluk, and Dennis Wei. Boolean decision rules via column generation. Advances in neural information processing systems (NeurIPS), 31, 2018.
Santanu S Dey and Laurence A Wolsey. Two row mixed-integer cuts via lifting. Mathematical
Programming, 124:143-174, 2010.
Ralph E Gomory. Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society, 64(5):275-22 278. 1958.
Ralph E. Gomory and Ellis L. Johnson. Some continuous functions related to corner polyhedra, I. Mathematical Programmingg 3:23 85, 1972a. ISSN 0025-5610. doi: 10. 10.10///FF0588000. URL
http::/dae doi. orgoorg////oo 10. 1007/0000000 BF0//850005550
Ralph E. Gomory and Ellis L. Johnson. Some continuous functions related to corner polyhedra, II. Mathematical Programming, 3:359 389, 1972b. ISSN 0025-5610. doi: 10.1007/BF11585000.
URL http://dx doi. org/ 10. 1007/FF1555800
Ralph E. Gomory and Ellis I. Johnson. T-space and cutting planes. Mathematical Programming, 96:
341-373 2003.
Ralph Edward Gomory. An algorithm for the mixed integer problem. Rand Corporation California, 1960.
Elliott Fordon--Rodrgueee Gabriel novel simplex-van valued exponential family. In International Conference on Machine Learning. pages 3637-3647. PMLR, 2020.
and John Cunningham. The continuous categorical:
Ignacio E. Grossmann and Zdravko Kravanja. Mixed-integer nonlinear programming techniques for process systems engineering. Computers Chemical Engineering, 19:189-2000 1995.
Ivan Gryffenberg, Jean Lausberg. Willem Smit, Stephanus Uys. Sally Botha, F Rauten Hofmeyr, Ruppert P Nicolay, Willie I. van der Merwe, and Gysbert Wessels. Guns or butter: decision support for determining the size and shape South African defense force. Interfaces, 27:7-28, 1997.
Rishi Gupta and Tim Roughgarden. A pac approach to application-specifie algorithm selection. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 123-134, 2016.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023, URL https: // www gurobi com
Christopher Hane, Cynthia Barnhart, Ellis Johnson, Roy Marsten, George I. Nemhauser, and Gabriele Sigismondi. The fleet assignment problem: Solving large-scale integer program. 70: 211-232, 1995.
Albert Xin Jiang, Manish Jain, and Milind Tambe. Computational game theory for security and sustainability. Journal of Information Processing, 22(2):176-185, 2014.
12

---

Dmitry Malioutov, Sanjeeb Dash, and Dennis Wei. Heavy sets with applications to interpretable machine learning diagnosties. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 5918-5930. PMLR, 2023.
Jiri Matousek. Geometric discrepancy; An illustrated guide, volume 18. Springer Science & Business Media, 1999.
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Communications of the ACM, 65(7):33-33) 2022.
George L Nemhauser and Laurence Wolsey, Integer and combinatorial optimization, volume 18. Wiley New York, 1988.
Laurent Poirrier. Mul approaches to cutting plane generation. PhD thesis, University of Liege, Belgium, 2014.
John R Rice. The algorithm selection problem. Advances in computers, volume 15, pages 65-118. Elsevier, 1976.
Norbert Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A, 13(1): 145-147, 1972.
Lara Scavuzzo, Karen Aardal, Andrea Lodi, and Neil Yorke-Smith. Machine learning augmented branch and bound for mixed integer linear programming. arXiv preprint wxXiv:240.005500 2024.
Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley and Sons, New York, 1986.
Saharon Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific Journal of Mahematics, 41 (1():247,,2 1972.
Gopal Sinha, BS Chandrasekaran, Niloy Mitter, Goutam Dutta, Sudhir B Singh, Aditya Roy Choudhury, and PN Roy. Strategic and operational management with optimization at Tata Steel. Interfaces, 25:6-19, 1995.
Noah A Smith and Roy W Tromble. Sampling uniformly from the unit simplex. Johns Hopkins University, Tech. Rep, 29, 2004.
Eduardo D Sontag al. Ve dimension of neural networks. NATO ASI Series F Computer and Systems Sciences, 168:69-96, 1998.
Richard P Stanley et al. An introduction to hyperplane arrangements. Geometric combinatorics, 13 (389-496):24, 2004.
Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Reinforcement learning for integer programming: Learning to cut. In International conference on machine learning, pages 9367-9376. PMLR, 2020.
Silviya Valeva, Guodong Pang, Andrew J Schaefer, and Gilles Clermont. Acuity- based allocation of icu-downstream beds with flexible staffing. INFORMS Journal on Computing, 3532):403-422, 2023.
Dennis Wei, Sanjeeb Dash, Tian Gao, and Oktay Gunluk. Generalized linear rule models. In International Conference on Machine Learning (ICML), pages 6687-6696. PMLR, 2019.
13

---

A Auxiliary Lemmas
Lemma A.1 (Theorem 5.5 in [aatousek 1999 Lemma 17 in Bartlett et 2019]
Lemma 3.3 in Anthony et al. 1999]. Proposition 2.4 in [Stanley et al. 2004 D. Let P1,.... 0r R + R be t
multivariate polynomials of degree most a with & and
1. Then
[at 2 (
a 1, if 2,
((sgn()i(14))......) (g()),
R -
where e is the base of the natural logarithm.
Proof of Lemma 2. For any E N n (d, +00) and (11,8),..... (/, x RR there are most pre, where each is multivariate polynomial of degree at d1 ..... gre
It rational functions, denote as 21
most a on μ E P S RR, and each q > 0 on P. For any within each these decomposed regions, the vector [h (). ..... h(I, p4] is invariant. The number of the decomposed regions is given by
pi (1()
pro(Ht) (
p mEP)
sgn
sgn
(1(
{{ (sgn (Pr (p)))
sgn (pre(p))) f R3
te d
<2
d
where the last inequality holds by Lemma A.1 We denote these regions as Q....., Q2. where
K < 2 (2e ( Then we have.
((sgn(((T1, st))...,sgn((((T,, 8t)) P)]
((sgn(h(11.44 - s1),..., sgu(h(()))(((( -s)) E QiH
Σ
i=1
LeTla d
where the equality holds since each h[T, /)) s, is an invariant constant for μe varying in any fixed Qi Therefore, the pseudo-dimension is the largest t such that
d 2eTta
2 s
d
which is bounded by the largest such that
(t ( 1) S dlog
(2er d
(2eTta)
sd (2eTla/d (
log (STa)) - dlog (8Ta),
SeTa
where the second inequality holds because log(x) < I + log (9) for positive reals and c. Then it follows that Pdim H) O(d (og("a)))
Lemma A.2 (Theorem 4.5 in Balcan et al. 2022 ). For any fixed I = (A, b. E I. there are at
most O (14))((m + 22) 3m e km degree polynomials decomposing the cutting plane space R=+
into regions such that the size of the branch-and-cur tree after adding the cut a x S 3 at the root remain the same over all (a., (3) within given decomposed region.
Lemma A.3 (Tang et al., 2020 Conforti et al. [014)). For every A m b E zm, there exists an affine linear transformation that maps a cutting plane derived from cut generating function for the standard form integer linear programming feasible region {(x,s) RR' Th Ax + s b, x, 2 0, E 2", s E Zm) into the corresponding cutting plane
for the corresponding canonical form feasible region fx R" Ax < b. > 0. 2n}.
14

---

Proof. Let a + a 2 1 be cutting plane for the standard form integer linear programming problem. For any feasible x and have b Ax. Substituting into the inequality, we obtain the equivalent cutting plane (a! A that
ax) x
S ag b
1 in the canonical form problem. Then it's clear
(a) ((aa
A a a. ax
-
A
ax
0 1
b bTag -1
=
0
b
as
ax ag
affine linear on
since A, b are considered to be fixed.
B Proofs for results in Section 3
Theorem in [Gomory and Johnson, 2003] yields the following lemma.
Lemma B.1. Consider fixed f (0, 1) and p, q [2, +-0) n N. nhe ee (.) is valid cut generating
function, i.e., it satisfies the three conditions outlined in Section 2.1 if $1 and $2 are chosen from D which is established as follows:
if (p 1)f and (p (p+q 1) q 0,
(pt
p4--1
f +00
if ( and (p+ ( if ( 1)ʃ - 2 and (p + 1)(1-f) -f)-920
and (p+ 1)(1 ff) 17-922 0,
D
(pt- 111
00,
--1
q- 1--0-11111
p---1
131
J +
20,
(a) mg.G (r))(r)
(b) Ta.G (.4.,-7.4.5r) (r)
(c) #p.6. (.)
Figure 4: For fixed f E (0,1),p,q [2, +o0+ n.N N, the intersection points of Pig fixed.
f. (-) and G-I
Lemma B.2. For any fixed f f (0.1). [2, +o0) N,, and any (81, E Dj. the intersection points of n-9 (esi (-) and GMI are fixed. More specifically, for any (81, 82) D with 81 + ト
and 82 * the set of intersection points is explicitly given by DL
f i
p.....p...
{ j(1-f) 1 : =j=0..... :;=00...,q-11
:i O,... o
if 1' 1011pp11
1
I.... 2 Ju(( j(1 f) 1
9-1 9 1, 1..., --2
and these intersection points decompose the interval [0, 1] into 2(p + g 2) subintervals given by the following break points in ascending order:
f f
(p-2) (p- 2) (p 1)f
(q 1) f)
0,
f.
P
q
15

---

Proof of Lemmal B.2
be any valid slopes. A direct calculation shows that the intersection points of 8,11,02 (r) and (r) within E [0, 1] are given by:
Let 81 <
f-1 and >
}
(r) = GMl = S17 +
fsi
r
-==
p
f
D
1 f32
(r) GMl = 82r + (i 1)
-
r= (=
p-1
p-1
p
1 + (1
-f)s1
1-r
03 (r) GMl = s1(r 1) + (j 1)
9-1
1-f
q
(r) (r) = GMl + 32(r 1) + 1 + (1 f)82
1-r
where E f1.....PP p} and j E fl.....q-11 1}. Eliminating duplicate points and observing a maximum 2p + 2q- 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 In E [0, 1), by Lemma B.2 each r,, J = 1....
must lie one of the intervals independent of $1, $2 (if ry is the boundary of any of these intervals, f.s (ry) 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.g Tf (-) in the form of the
then P.g
quotient of two affine linear functions of $1 and For instance,
1 f82 1 f8i s2r + (i- p p-1
1)
1-1 -
1--181
(1 ())) = si
p-l
F
p
$1 82
We denote these corresponding nondifferentiable points in the form (e(ere)) and gi affine linear functions of $1 and $2- We introduce the following n hyperplanes of $1 and 82
(21.52)) where fi
{(s1, D f( s2) (s1, == i=....,,
(1z) is fixed affine linear Then, within each region decomposed by these hyperplanes, each s2 function of s2).
(M) M2) E [0, 1
(a,, B) E RB+1
(a(11, (2), S(11, H2))
Figure 5: Illustration of the proof of Theorem 3.2
Proof of Theorem 3.2 Lemma A.2 states that there are at most r = O (14)"(m + 2n)3n² gan²)
degree 5 polynomials decomposing the cutting plane (ar, B) space 1B=+1 such that the branch-and-cut tree size after adding the corresponding cutting plane at the root the same within each decomposed region. We denote these degree 5 polynomials {1, fI...., fr. In other words. for any (a, 8) e g=+1 such that the vector
[
sgn
E1
sgn &r
16

---

remains constant, the branch-and-cut tree size after adding a axx S 3 at the root is invariant.
Proposition 3.1 provides decomposition of the (81, space " by n hyperplanes. Consequently, there exists a corresponding decomposition of the fa space [0, 1] by n hyperplanes as well, since μ is a fixed affine linear function of (81, (2) as specified by the mapping (6) We denote these decomposed regions by Q1..... QK C [o, 1 where K Onn²) due to Lemma A.1 Fix a region Q, for any i {I...., ) the mapping (6), Proposition 3.1 and and Lemma A.3 give three different fixed affine
transformations from f to a cutting plane for the canonical linear programming problem. We denote
the corresponding cutting plane
[a(1]] = g(H) E R++1 ((1))
where gi, i {I,..., 1}, are affine linear functions of μ.. Notice that
sgn & ((ww))
())m)) = (sgu (g(()) sgn (Er(g()))) (5n(( ( ((w)
................................ sgn &r
then there are I d polynomials
(E1 gg ..... (fr g)
over [0, 1]² such that when they have invariant sign patterns, the branch-and-cur tree size after adding the corresponding cutting plane at the root is the same. Thus, there are O (KT) such degree polynomials total. Then the pseudo-dimension result follows from Lemma 2.1
C Proofs for results in Section
Proof of Theorem The O (k) and O (nk) complexity of Algorithm is straightforward to verify. We now prove the correctness of the algorithm. Given the vectors a a a² E IR* defined in Section 4. notice that the
x E R
x)
S 1, (a x)
(a", S 11}.
(f - 1) +
X X
R
p.x: < 1,x 0, ...,, X 2 0
Gff,
is translation of a k-dimenssonal simplex. From the literature on cut generating functions, there exists so-called lifting region (refer to (Dey and Wolsey 2010, Basu and Paat 2015 Basu et al.. 2013al). R C G(f, μ), such that for any R², there exists Rn (f 2 such that Tf. (r) max (a
j j=o....kk
Theorem 2.2 in (asu and Sankaranarayanan
2019 implies that
R g G(f. C _ (ffi - 1, x x [f. - 1, + De X E 2+}) f,
C C (ff
x [fa 1,fu (ee' x E z))
then for any given r E R we take w = [r] + >
1(r: 2 + [r, [r,]] ee E z which is an integer f 1. Therefore,
vector such that F w fi 1,
x
(r) = min max (a (a',r=) +r+2 z)
=E2" j=u.....k
min max (a + z)
=E2" j=U....k
min min max (a', + Xe
:E(I.....)) XE2 j=0.....
min min max (a F Xe²).
ie ie(L. fe(l....)) XEZ b
17

---

Notice that for any E k.....,k..
(a .
max 1=
-mxx
(a
de
F1
F
Fi
X
Fi41
fl
f
1' f.
ff-11
fx
j== j
p4
Fj [
i E 18 1 /]
max
b j=1 1
f
f-
X, max
(7)
is one-dimensional piecewise linear function in À with at most three pieces (relaxing the fea- sible region of À from Z to R). Using the notation in Algorithm let = Σ)= M3Tz, =
Σ Mify 2 E
k +
(since f * 0), max j (I....,,k]..
arg max f--
}.. (..
b max f-1 : fl........................
Then for i
(I...., kj. there are cases:
Case 1: i + 1* In this case, notice that for À 2 we have
F₃-
F +\
f--1
since f; - 1 < O. Then,
p u.d
F, + A
p p.d
max (a' F
Xe")
max
max
j=O....kk
q
fg
q
a nondecreasing function of À over [0, +oo). Therefore,
p-+uu) u:d
p + vid
1
p
min max XEZ
min max XE3
:0
a = max
(9.0)
9
Case 2: 1=i=0 1", In this case, we can rewrite as
p p Fí- +
max (a², F Ac") = max J=
9 f.. 1 {).
The slopes of these three affine linear functions #i >
0, F--1 < 0, and 0 respectively.
1
rg
The intersection point of the graphs of the first two functions is given by J = (x F where
x gF. -p(f.- since
(T.- 1)p
p U. X* Fr. X
(ff-- - 1)p - 9) X" = -p(,.,((;..1) X' gr. -p(ff- -
(f,. 1) -
<0
Observe that X is always an optimal solution to min max (a', + Xe"") regardless of whether XER j=0....k
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 max (a + Xe"") is attained at either [X* XEZ j=.....k
or [] Therefore, we have
min max (a F + ) XER j=......... min
a F (A"Je")
( F + IA7e"))
max f=
max y=0....
+ u.- [\a] ri- + [X1]
(p+ per-
1
Fr- + [**] f:- - .0]]
min
max
b
max
q
f. -
q
Thus, take the minimum of the two cases, we have
min max + X
F, +
[
ub [X1
Fi- + LX*1
p
(r)
b
max
b
max
(
9 f.r
q
f -
18

---

Proof of Proposition 4.3
Observe that the lifting region
R _ G(f,
U
[f 1, x [fs 1, oo AE 0, 1
pi 11
1=1
k
((f 1, x..x x...xxe [fx 1,6x) {>xe> : dE (0,=+]}
i=1
k
U ([f ==1
1, x ... [fn - 1, + {te' X {0, (,,
Let F = r IN - Ei= 1( 2 + [r. E [G - 1, x .... x [fa - 1, = -1,...,
Then for any fixed j, based the proof of Theorem 4.2
we have
(r²) =
min min
max tU......
(a', F + Xee)
(e(),.))) (e
Dj + uid
A
F
min
max min
max
:l1
(1,
( (0 )
f
P/- +
Pj ag q
+ p4y
x
min
max
min
max
bj
Xe (0, ()
9
Fig
where, defined in Algorithm and Theorem
4.2 Pj Ei=1
p.F.
q
Σ HLf 2
- f; > O, aj = max f-1 :1E (1..... kk 17 arg max
F!
: [1.....,k)}
fi-1
by = max - iE (I,....,,,M
This motivates considering the following numbers, for any fixed j E (I....,m}
F + A fz;
Pi aj
Pj
pi; X
bj, xe 1, (0.
q
There are 1+ (+++)
27 + numbers in total, so the pairwise comparison of
these numbers can done by at most (2r + 52r + 6)/2 < 2(r + 3)² hyperplanes the μ space AT. This is because, in the worst scenario, the equality
PJ + M3
+ F
P. + X f.
-
Ps+ Xp2
9 0
a hyperplane on μa, and similar arguments apply to other pairs. These hyperplanes decompose the AT space into some regions such that, within each region, the order of the above 27 + 5 numbers is fixed. Within each region, Tr. (r') can be expressed as the quotient of two affine linear functions in Jr, with the denominator being q Σt p.f.; > 0. Overlapping all hyperplanes across j {1, (1,...,7) . results in at most 2n(r + 3 hyperplanes decomposing the A space.
Proof of Theorem 4.4 Similar to what we have done in the proof of Theorem 3.2 let &
Er
denote the degree polynomials given in Lemma A.2 where I' o (14) + 2n) 3n2 e By
Proposition 4.3 there are at most 2n(r + 3)2 hyperplanes decomposing the A space such that, within each decomposed region, each coordinate of the cutting plane derived from the cut generating functions Ne. is fixed rational function given by the quotient of two affine linear functions on μ. Also, by Lemma A. these hyperplanes decompose the μ space A into at most
2n(( + 3)2 +3))
< n + 3) = K
19

---

regions, denoted as Q...... QR. where K- S K.
We fixed a region Qi for any E KJ. For any l E Qi we claim that [a( [(())
can always be
expressed as ((x) E Ra+1 where each coordinate of p' is an affine linear function of μa, and is 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(μ)) = Σ j.f.f
('())
(which is fixed once the instance I = (A, b, c) is fixed), or just some constants independent of Then by Lemma A.3 with fixed = (A, b, c), the cutting plane for the original problem is fixed affine transformation of the above form. Therefore, in this fixed region Qi the final form of the cutting plane is fixed and can be written as D (H) E Ra+11 Therefore,
(51 (( ... .,T ((B())) - -(()))
(rr p (()
(I))
gives I' fixed rational functions of μt, decomposing Qi, in the form of the quotient two degree polynomials. For any E Q; within each decomposed region, these rational functions have an invariant sign pattern, hence the tree size after adding a(2)) x B(u)) the root remains the same. By traversing all Q, the total number of such rational functions is given by
(2 (T + 3) (14)" + 2n) 5m2
then the pseudo-dimension result follows from Lemma 2.1
Pdim (TT* (.) I [0. B) E AT) = O (kn² log((m - m))) + k² llg((nr))
20

---

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 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 is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations 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 theorems. The limitations of our numerical approach are mentioned in Section
Guidelines:
The answer NA means that the paper has 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 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 the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or 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 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
21

---

Answer: [Yes]
Justification:
All assumptions are clearly stated, and all proofs are provided in Appendices A
to
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The code and data used all experiments are available at chttps://githee com/ Hon/Hongyu--ao Cheng/LearnCGr LearnCGF The details are explained in the README file.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
22

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: The code and data used in all experiments are available at htttss://githuu com com/Hongyu- Cheng/ Cheng/ LearnCGF The details are explained in the README file.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, 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 and 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 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, as supplemental material.
7. 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 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 emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
23

---

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.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CL, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: These are clearly stated in Section and in the code.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer:
[Yes]
Justification:
The research conducted in this paper conforms the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws 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 no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 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 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe 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)?
Question:
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 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 best faith effort.
12. Licenses for existing assets
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?
Question:
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 dataset.
The authors should state which version of the asset used and, possible, include 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 package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
25

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not introduce any assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moddl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
26


Reviews:
[{"review_id": "mKxE1v9BCz", "reviewer": "Reviewer_yCxh", "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.", "questions": "These are all minor comments.\n\n1. 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. \n\n2. 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)?\n\n3. 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?\n\n4. 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)?\n\n5. 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.\n\n6. 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?\n\n7. Please fix the citation types (those missing parenthesis).", "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.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This work adds an interesting and novel learning-theoretical perspective to the cut generating function literature. Making general cut generating functions practical has always been challenging, and this paper suggests potential in learning them in a principled and theoretically grounded fashion. While we are still far from being able to use cut generating functions in the way that the paper promotes, this is a valuable step that advances the field further and I believe that this can inform future learning-based cut generation methods. The paper is overall written in a clear way. I checked the proofs at a high level but could not do so in detail since my familiarity with learning theory is limited. The computational results, while focused on small cases, show good potential for learning-based methods.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the insightful review and providing detailed feedback. Regarding your questions:\n\n1. This is an good point. The two families of cut-generating functions considered in this paper are indeed parametrized geometrically. We will include additional explanations and figures to clarify this further.\n\n2. The $k$-dimensional cut-generating function in this paper is a subfamily of those studied by Basu and Sankaranarayanan (2019). Specifically, it is the trivial lifting of the gauge function of a family of maximal $(\\mathbf{f} + \\mathbb{Z}^k)$-free simplices, defined as $\\mathbf{f} + \\lbrace \\mathbf{x} \\in \\mathbb{R}^k : \\sum_{i=1}^{k} \\mu_i \\mathbf{x}_i \\leq 0, \\mathbf{x}_1 \\geq -1, \\dots, \\mathbf{x}_k \\geq -1 \\rbrace$, parametrized by $\\mu$ restricted to the standard $k$-dimensional simplex. We indeed have some 3D-printed models of these generating functions, as shown in our global response (see the attached PDF). We will include these figures in the paper.\n\n3. Our main results are based on the piecewise structural results of the branch-and-cut tree size studied by Balcan et al. (2022), so we adhere to the same methods and assumptions for building branch-and-cut trees as in their paper. Therefore, the results apply to product scoring policy or lexicographic policy for variable selection and depth-first search policy for node selection. Using the same technique, one can prove similar results for other selection policies, such as the best-bound policy for node selection. We will clarify this further in the paper.\n\n4. Gomory and Johnson (2003) proved that the one-dimensional cut-generating functions (CGFs) considered in this paper are extreme. For $k$-dimensional CGFs, they are minimal valid functions as they are the trivial lifting of the gauge function of maximal $(\\mathbf{f} + \\mathbb{Z}^k)$-free convex sets with the covering property (Basu et al., 2013; Conforti et al., 2014; Averkov and Basu, 2015). Then, these $k$-dimensional CGFs are extreme by the $(k+1)$-slope theorem (Basu et al., 2011). We will include these explanations in the appendix of the paper.\n\n5. There are some trivial constraints for those $0/1$ knapsack problems restricting the decision variables to be no larger than 1. We do not explicitly handle these upper bounds differently, and consequently, they contribute to the simplex tableaux.\n\n6. This is a very interesting and important question. There are two related issues here. One is the classical bias-variance/bias-complexity/overfitting-underfitting tradeoff in any statistical method such as ours. The second issue is the difficulty in finding the optimal solution to the ERM problem $\\min_{{\\mu}} \\frac{1}{N}\\sum_{i=1}^N T^k(I_i, {\\mu})$, where $T^k(I_i,{\\mu})$ is the branch-and-cut tree size of the instance $I_i$ after adding a cutting plane induced by a $k$-dimensional CGF parameterized by ${\\mu}$ (i.e., $k$ is the number of rows used to generate the cutting plane).\n\n    Increasing the number of rows reduces the bias of the model, i.e., we expect the overall expected error to go down with the optimal choice of parameters ${\\mu}$ (for minimizing the overall expected error). However, it increases the variance/complexity of the learning procedure. As you point out, if we fix the number of samples, increasing the number of rows leads to weaker guarantees on the expected error of the learned parameters, i.e., the ERM solution ${\\hat\\mu}$. Sample complexity tracks this trade-off quantitatively: it tells us how the sample size should grow if we increase the complexity of our model (i.e., increase the number of rows $k$ used to generate the cutting plane), if we wish to keep the same error and high probability guarantees.\n\n    From an empirical perspective of solving the ERM problem, the phenomenon you mentioned is the following. In the experiments of this paper, regardless of the value of $k$, we uniformly sampled a constant number of CGF parameters on the $k$-dimensional standard simplex and chose the best one. Therefore, for higher dimensions, the probability is lower that some of these randomly sampled points are good enough to solve the ERM problem. In this setting, increasing the number of sampled candidate parameters as $k$ increases is a reasonable way to improve the performance of the $k$-dimensional CGF. However, the number of candidate parameters might grow exponentially with $k$ for a provable guarantee. We have not theoretically or computationally explored this dependence. \n\n    Therefore, with more IP instance samples, we might consider moving away from this simple yet robust enumeration method and adopting heuristic algorithms to solve the ERM problem. For instance, as suggested by Cheng et al. (2024) in their paper that also involves the optimization of a similar ERM problem, we could use some reinforcement learning (RL) algorithms, treating the CGF parameters as continuous actions in the RL setting, to find a relatively good parameter setting. \n\n7. Thank you for catching this. We will fix the citation types in the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CLLFZQRcIq", "reviewer": "Reviewer_TAJ6", "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.", "questions": "None.", "limitations": "Yes.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The setting is of clear interest to the integer programming (IP) community. I cannot vouch for the novelty or correctness of the learning-theoretic content of the paper, but the IP content is crisp and clean, and the high-level idea and computational setup all make sense to me.", "weaknesses": "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. \n\nAnd 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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the thoughtful and encouraging review. Section 5 is meant to illustrate that our analysis extends to the setting where one wishes to select cutting planes tailored to instances using, say, a neural network mapping from instances to cutting planes. This was done in a more general algorithm design setting by Cheng et al (2024), but the analysis can be easily adapted to CGFs. This can potentially lead to stronger gains since the CGFs are tailored to specific isntances, as opposed to using the same CGF for all instances.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BdJdWuoijK", "reviewer": "Reviewer_6RAE", "summary": "The paper is concerned with the interplay of learning theory and the branch-and-cut algorithm for solving mixed-integer programs (MIPs).\nConcretely the authors analyse the problem of cut selection.\nIn 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:\nHow 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?\nFor the selection of a cut generating function, the authors list three criteria:\n1: 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”\nThe authors then proof sample complexity bounds for three different settings.\n1) 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$.\n2) 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$.\n3) One wants to train a neural network to choose a good instance (not distribution) dependent cut generating function.\n\nIn 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.", "questions": "Additional and minor remarks:\n- L 6: “optimal cutting planes”. “Optimal” is very global and strict. Maybe “good”\n- L 24: “small representative sample”. Representative seems subjective\n- L 36: “we understand many of their theoretical properties”. “We” sounds ambiguous here. Maybe “many theoretical properties are understood”\n- L 53: “with several excellent insights”. “Excellent” is quite subjective\n- L 144: Z^n should be Z^k\n- Figure 1: The use of the label “y” for the y-Axis is confusing to me\n- Figure 1: For r = 1 the graph has a red circle, indicating it is not defined here. The same should hold for r=0?\n- Figure 1: The font seems unnecessarily small\n- 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.\n- 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\n- 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?\n- Small and capital letter inconsistency in references. E.g. 352 & 358: “cambridge university press” and “Cambridge University Press”", "limitations": "The author's discussion of their limitations is fine, apart from the part about the numerical experiments (see weaknesses).", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper is well-structured and easy to read.\nThe provided code allows for the reproducibility of nearly all experiments (only for knapsack_50 I get “index 0 is out of bounds for axis 0 with size 0” and no results, even if I run the code to regenerate the instances).", "weaknesses": "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.\n1) the numerical experiments do not always indicate “significant”\n2) 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\n3) 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.\n\nL 316: “Instances were generated using the distribution proposed by Chvátal in Chvátal [1980], also used in Balcan et al. [2021b].”\n-> 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.\nTo achieve this, all constraint coefficients $a_{ij}$ are sampled from $[1, 10^{(n/2)}]$ and $b_j = floor(\\sum (a_i / 2))$.\nBalcan 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).\nI 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate your thorough review and the thoughtful feedback. Regarding the experimental evidence, we acknowledge that our paper focuses primarily on theoretical aspects, and thus, the experimental section is somewhat preliminary. First, we agree that it was poor scholarship on our part to call our distribution the Chvátal distribution. Our distribution is indeed the same as what was done in the Balcan paper. We will reword to something like \"what Balcan et al call the Chvátal distribution\".\n\nHowever, we believe that even these basic experiments lend support to our claim that some of the CGFs we consider can result in significantly smaller tree sizes compared to some traditional cutting planes. Our reasoning is as follows:\n\n1. Even though the 1D knapsack problem is very simple, this does not detract from the theoretical interest of the result. Specifically, when using only branch-and-bound for certain specific distributions (such as the \"Chvátal distribution\" considered here), there are indeed some CGFs that perform significantly better than GMI cuts.\n    \n2. Even if we disregard the 1D knapsack results, we believe the other experiments on multidimensional knapsacks and packing problems also give some support to our claim:\n    - Regardless of the problem type or the number of rows used to generate cutting planes, we selected a parameter from only 121 random candidate CGF parameters, and for one-row cuts, we only considered the simple case of $p = q = 2$, resulting in only two parameters. Despite this, some CGFs performed better, which demonstrates the potential of CGFs.\n    - In the last column, we provided the \"best 1-row cut\" for the one-dimensional CGF, obtained by enumerating and selecting the best 1D CGF for each instance. We believe this result shows significant improvement over GMI cuts, even for the packing problem settings. While this method is not really \"learning,\" we believe it does demonstrate the potential of CGFs. Also, for this method, in Section 5 we proved the learnability and rigorous sample complexity for solving the problem of \"selecting good CGFs for each instance\" using neural networks, which may provide some insights to practitioners to develop some neural network based instance-specific selection methods.\n    \n3. We compare with GMI cuts because this is considered a \"gold standard\" in evaluating cutting planes in IP computational literature. While there are indeed several other cutting plane families that are used in modern solvers, the first test for any new family of cutting planes (from a practical perspective) is usually to see how well they do in comparison to GMIs. They are arguably the most important and popular *general purpose* cutting planes, adopted by commercial solvers for almost thirty years now (Conforti et al., 2014). Additionally, GMI cutting planes are generated by an extreme CGF (Section 2.1 has the corresponding CGF definition). Given that the main focus of the paper is on the theory developed, we wanted to keep the message of our experimental section crisp and streamlined. Comparisons with GMI seemed like a good way to achieve this.\n\nWe do agree that perhaps our choice of wording in the experimental section (and in references to it) is overenthusiastic. We will reword and tone down some of the language. The reason behind our excitement is that we have not seen such promising results with CGFs in the computational IP literature. We concede that some of instances are not the most challenging ones for modern solvers. Nevertheless, we do not know of any published (or folklore) cases of instances where CGFs have previously been demonstrated to have such stark improvements over GMI cuts. And this is even more true for the Gomory-Johnson family of CGFs. While there are some computational results showing some promise with CGFs coming from lattice-free sets and their liftings, to the best of our knowledge, the Gomory-Johnson families have not been shown to do better than GMIs (beyond some artifical instances) in any previous study. Observing an improvement with these CGFs that was quite a contrast from previous computational experience was the basis for our enthusiastic wording. One reason could indeed be the choice of instances. Nevertheless, we think another reason is that previous work focused more on the gap closed at the root, as opposed to the overall tree size. We hope that our preliminary results convinces the community to revisit these CGFs, especially with the view to investigate their effect on the overall tree sizes (both theoretically and practically). We will also expand our computational investigation to look at other families of instances to see if the improvement in tree size is as dramatic as we observed on these knapsack instances.\n\nTo summarize, our hope with the experimental section is to \"whet the IP community's appetite\" and rejuvenate its interest in CGFs. We believe they can be useful, and using learning techniques may be a good way to unlock their true potential. \n\nSome responses to your more detailed questions: \n\n- > Z^n should be Z^k\n\n    It should be $\\mathbb{Z}^n$ since $\\mathbf{r}^1,...,\\mathbf{r}^n \\in \\mathbb{R}^k$ are vectors. \n\n- > Figure 1: For $r=1$ ... should hold for $r=0$?\n\n    The plots in Figure 1 are on the interval $[0,1)$, so $r = 1$ is not included, which is necessary because the generating function of Chvátal-Gomory cut, $\\text{CG}_f(r)$, is not continuous at $r \\in \\mathbb{Z}$. However, $r = 0$ is defined, and by periodicity, for these functions, the value at $r = 1$ is the same as the value at $r = 0$.\n\n- > Table 1: For $d$-dimensional ..., 2-row is best for 2-d knapsack?\n\n    Yes, this is a very insightful point. We share the same intuition. Indeed, for $k$-row cuts, we selected the first $k$ rows from the simplex tableau to generate a cut, so it makes sense that the 2-row cut works best for the 2D knapsack problem.\n\nWe will address the other minor remarks in the final version of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
The attached PDF includes figures of a 2-dimensional cut generating function, related to reviewer yCxh's question (point 2).

Meta-review: 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.
Decision: Accept (poster)