Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond
Authors: Nina Balcan
Siddharth Prasad
Tuomas Sandholm
Ellen Vitercik
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Automated algorithm configuration
automated algorithm design
data-driven algorithm design
integer programming
tree search
branch-and-bound
branch-and-cut
cutting planes
Chvátal-Gomory cuts
machine learning theory
sample complexity
generalization guarantees

Abstract: Cutting-plane methods have enabled remarkable successes in integer programming over the last few decades. State-of-the-art solvers integrate a myriad of cutting-plane techniques to speed up the underlying tree-search algorithm used to find optimal solutions. In this paper we provide sample complexity bounds for cut-selection in branch-and-cut (B&C). Given a training set of integer programs sampled from an application-specific input distribution and a family of cut selection policies, these guarantees bound the number of samples sufficient to ensure that using any policy in the family, the size of the tree B&C builds on average over the training set is close to the expected size of the tree B&C builds. We first bound the sample complexity of learning cutting planes from the canonical family of Chvátal-Gomory cuts. Our bounds handle any number of waves of any number of cuts and are fine tuned to the magnitudes of the constraint coefficients. Next, we prove sample complexity bounds for more sophisticated cut selection policies that use a combination of scoring rules to choose from a family of cuts. Finally, beyond the realm of cutting planes for integer programming, we develop a general abstraction of tree search that captures key components such as node selection and variable selection. For this abstraction, we bound the sample complexity of learning a good policy for building the search tree.

Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond
Maria-Florina Balcan
Siddharth Prasad Computer Science Department
Tuomas Sandholm
School of Computer Science
Computer Science Department Cameegi Mellon University Optimized Markets, Inc. Strategic Machine, Inc. Strategy Robot, Inc. sandholm@cs cmu edu
Carnegie Mellon University
Carnegie Mellon University sprasad28cs. cmu edu
ninamf menanffcs.c. cmu. edu
Ellen Vitercik
EECS Department
UC Berkeley vitercik@@erkelle..o edu
Abstract
Cutting--laa plane methods have enabled remarkable successes in integer program- ming over the last few decades. State-of-the-ar solvers integrate a myriad of cutting-plane techniques to speed up the underlying tree-search algorithm used to find optimal solutions. this paper we provide sample complexity bounds for cut-selection in branch-and-cut (B&C). Given a training set of integer programs sampled from an application-speciffi input distribution and family of cut selection policies, these guarantees bound the number of samples sufficient to ensure that using any policy in the family, the size of the tree B&C builds on average over the training set is close to the expected size of the tree B&C builds. We first bound the sample complexity of learning cutting planes from the canonical family of cuts. Our bounds handle any number of waves of any number of cuts and are fine tuned to the magnitudes of the constraint coefficients. Next, we prove sample complexity bounds for more sophisticated cut selection policies that use a combination of scoring rules to choose from a family of cuts. Finally, beyond the realm of cutting planes for integer programming. we develop a general abstraction of tree search that captures key components such as node selection and variable selection. For this abstraction, we bound the sample complexity of learning a good policy for building the search tree.
1 Introduction
Integer programming is one of the most broadly-applicable tools in computer science, used to formulate problems from operations research (such as routing, scheduling, and pricing), machine learning (such as adversarially-rouus learning, MAP estimation, and clustering), and beyond. Branch- and-cut (B&C) the most widely-used algorithm for solving integer programs (IPs). B&C highly configurable, and with a deft configuration, it can be used to solve computationally challenging problems. Finding good configuration, however,
notoriously difficult problem.
We study machine learning approaches to configuring policies for selecting cutting planes, which have enormous impact B&C's performance. At high level, B&C works by recursively partitioning the IP's feasible region, searching for the locally optimal solution within each set of the partition,
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

until it can verify that it has found the globally optimal solution. An IP's feasible region is defined by set of linear inequalities Az I b and integer constraints a E Z", where n is the number of variables, By dropping the integrality constraints, we obtain the linear programmingg (I.P) relaxation of the IP. which can be solved efficiently. A cutting plane carefully-chosen linear inequality a x S 3 which refines the LP relaxation's 's feasible region without separating any integral point. Intuitively, a well-chosen cutting plane will remove a large portion of the LP relaxation's 's feasible region, speeding up the time it takes B&C to find the optimal solution to the original IP. Cutting plane selection a crucial task, yet it is challenging because many cutting planes and cut-selection policies have tunable parameters, and the best configuration depends intimately on the application domain.
We provide the first provable guarantees for learning high- performing cutting planes and cut-selection policies, tailored to the application at hand. We model the application domain via an unknown, application-spcciiic distribution over IPs, as standard the literature on using machine learning for integer programming [e.g., 21 23
31 36 43. For example, this could be a distribution over the routing IPs that a shipping company must solve day after day. The learning algorithm's 's input is a training set sampled from this distribution. The goal is to use this training set to learn cutting planes and cut-selection policies with strong future performance on problems from the same application but which are not already in the training set-or more formally, strong expected performance.
1.1 Summary of main contributions and overview of techniques
As our first main contribution, we provide sample complexity bounds of the following form: fixing a family of cutting planes, we bound the number of samples sufficient to ensure that for any sequence of cutting planes from the family, the average size of the B&C tree is close to the expected size of the B&C tree. We measure performance in terms of the size of the search tree B&C builds. Our guarantees apply to the parameterized family of Chvétal- Chvátal-Gomory (CG) cuts 10 one of the most widely-used families of cutting planes.
The overriding challenge is that to provide guarantees, we must analyze how the tree size changes as function of the cut parameters. This is sensitive slighly shifting the parameters can cause the tree size to shift from constant to exponential in the number of variables. Our key technical insight is that as the parameters vary, the entries of the cut (i.c., the vector and offset / of the cut ax x S ()) are multivariate polynomials of bounded degree. The number of terms defining the polynomials is exponential in the number of parameters, but we show that the polynomials can be embedded in a space with dimension sublinear in the number of parameters. This insight allows us to function of the parameters. We then leverage results by Balcan et al. [8] that show how to use structure exhibited by dual functions (measuring an algorithm's 's performance, such its tree size, as a function of its parameters) derive sample complexity bounds.
better understand tree size
Our second main contribution is a sample complexity bound for learning cut-selection policies, which allow B&C to adaptively select cuts as it solves the input IP. These cut-selection policies assign number of real-valued scores to a set of cutting planes and then apply the cut that has the maximum weighted sum of scores. Tree size is a volatile function of these weights, though we prove that it is piecewise constant, as illustrated in Figure] D which allows us to prove our sample complexity bound.
Finally, as our third main contribution, we provide guarantees for tuning weighted combinations of scoring rules for other aspects of tree search beyond cut selection, including node and variable selection. We prove that there is a set of hyperplanes splitting the parameter space into regions such that if tree search uses any configuration from a single region, it will take the same sequence of actions. This structure allows us to prove our sample complexity bound. This is the first paper to provide guarantees for tree search configuration that apply simultancously to multiple different aspects of the aigorithm-prio research was specific to variable selection [5].
Sample complexity bounds are important because if the parameterized class of cuts or cut-selection policies that we optimize over is highly complex and the training set is too small, the learned cut or cut-selection policy might have great average empirical performance over the training set but terrible future performance. In other words, the parameter configuration procedure may overfit to the training set. The sample complexity bounds we provide are uniform-cconvrrgenc:: we prove that given enough samples, uniformly across all parameter settings, the difference between average and empirical performance small. In other words, these bounds hold for any procedure one might use to optimize over the training set: manual automated, optimal or suboptimal. No matter what
2

---

3000
2400
Tree size
Tree size
2200
2500
2000
1800
2000
1600
0.00
0.05
0.10
0.15
0.20
0.00
0.05
0.10
0.15
0.20
M
Figure 1: Two examples of tree size as function of SCIP cut-selection parameter j (the directed cutoff distance weight, defined in Section 2 on IPs generated from the Combinatorial Auctions Test Suite [30] (the "regions" generator with 600 bids and 600 goods). SCIP [16 the leading open-source IP solver.
parameter setting the configuration procedure comes up with, the user can be guaranteed that so long as that parameter setting has good average empirical performance over the training set, will also have strong future performance.
1.2 Related work
Applied research on tree search configuration. Over the past decade, a substantial literature has developed on the use of machine learning for integer programming and tree search [c.g.. 7 1 [3]
19 25 29 31 35 36 43). This has included research that improves specific aspects of
B&C such as variable selection 2 13 [24] 29 32, 4T], node selection [19 35 44], and heuristic
scheduling 25 These papers are applied, whereas we focus on providing theoretical guarantees.
With respect to cutting plane selection, the focus of this paper, Sandholm 36 uses machine learning techniques to customize B&C for combinatorial auction winner determination, including cutting plane selection. Tang et al. (37 and Huang et al. [20) study machine learning approaches to cutting reinforcement learning problem and plane selection. The former work formulates this problem heuristics for a variety of tasks. The shows that their approach can outperform human-designe
latter work studies cutting plane selection in the multiple-instance instance-leariing framework and proposes a ueural-netwood architecture for scoring and ranking cutting planes. Meanwhile, the focus of our paper is to provide the first provable guarantees for cutting plane selection via machine learning.
Ferber et al. study problem where the IP objective vector is unknown, but an estimate can be obtained from data. Their goal is to optimize the quality of the solutions obtained by solving the IP defined by é, with respect the true vector c. They do so by formulating the IP as a differentiable layer in neural network. The nonconvex nature of the IP does not allow for straightforward gradient computation for the backward pass, so they obtain continuous surrogate using cutting planes.
Provable guarantees for algorithm configuration. Gupta and Roughgarden [8] initiated the study of sample complexity bounds for algorithm configuration. In research most related to ours, Balcan et al. (5] provide sample complexity bounds for learning tree search variable selection policies (VSPs). They prove their bounds by showing that for any IP, hyperplanes partition the VSP parameter space into regions where the B&C tree size is constant function of the parameters. The analysis in this paper requires constant function of the CG cutting plane parameters, the boundaries between pieces are far more complex than hyperplanes: they are hypersurfaces defined by multivariate polynomials.
techniques because although we prove that the B&C tree size is piecewise-
Kleinberg et al. 26 27 and Weisz minimization that come with theoretical guarantees. Their algorithms are designed for the case where there are finitely-many parameter settings to choose from (although they are still able to provide guarantees for infinite parameter spaces by running their procedure on a finite sample of configurations; Balcan al. [ G) analyze when discretization approaches can and cannot be gainfully employed). In contrast, guarantees are designed for infinite parameter spaces.
[38] 39 design configuration procedures for runtime

---

2 Problem formulation
In this section we give more detailed technical overview of branch-and-cut, as well as an overview of the tools from learning theory we use to prove sample complexity guarantees.
2.1 Branch-and-cut
We study integer programs (IPs) in canonical form given by
max {e x. Ax b, 0,
(1)
where gmx", b E 2TH and с E R". Branch-and-cut (B&C) works by recursively partitioning the input IP's feasible region, searching for the locally optimal solution within each set of the partition until it can verify that it has found the globally optimal solution. It organizes this partition as a search tree, with the input IP stored at the root. It begins by solving the LP relaxation of the input IP; we denote the solution as "[p E R". If TPp satisfies the IP's integrality constraints (app E ) then the procedure terminates- - is the globally optimal solution. Otherwise, it uses a variable selection policy to choose a variable xr [il. In the left child of the root, it stores the original IP with the additional constraint that x=i] S [a[p[i]], and in the right child, with the additional constraint that x|i] 2 [=[p[[] [i]]- It then uses a mode selection policy to select a leaf of the tree and repeats this procedure solving the LP relaxation and branching on variable. B&C can fathom node, meaning that it will stop searching along that branch, if 1) the LP relaxation satisfies the IP's integrality constraints, 2) the LP relaxation is infeasible, or 3) the objective value of the LP relaxation's solution is no better than the best integral solution found thus far. We assume there is bound x on the size of
the tree we allow B&C to build before we terminate, as common in prior research [3] 21 26 27
Cutting planes are a means of ensuring that at each iteration of B&C, the solution to the LP relaxation
is close to the optimal integral solution possible. Formally, let P {I E IR Ax S b, 2 0} denote the feasible region obtained by taking the I.P relaxation of IP T Let P, conv(P n ) denote the integer hull of P. A valid cutting plane is hyperplane o I B3 such that if is in the integer hull (x: E P,)) then æ satisfies the inequality a² x S B.. In other words, a valid cut does not remove any integral point from the LP relaxation's 's feasible region. A valid cutting plane separates æ E 'P1 \ P if it does not satisfy the inequality, or in other words, a x > B. At any node of the search tree, B&C can add valid cutting planes that separate the optimal solution to the node's 's LP relaxation, thus improving the solution estimates used to prune the search tree. However, adding too many cuts will increase the time it takes to solve the LP relaxation at each node. Therefore, solvers such as SCIP [16), the leading open-soure solver, bound the number of cuts that will be applied.
A famous class of cutting planes is the family of Chvátal-Goman (CG) cut [10 171. which parameterized by vectors u E Thm The CG cut defined by u E Rm is the hyperplane [u" A I s [u b), which is guaranteed be valid. Throughout this paper we primarily restrict our attention to u E [0, 1) This is without loss of generality, since the facets of P n {æ E IR" [w" AAa < [u' bj Vu E RT) } can be described by the finitely many u E [0, 1)th such that u" A E 2n (Lemma 5.13 of Conforti et al. (.I..
Some IP solvers such as SCIP scoring rules to select among cutting planes, which meant to measure the quality of a cut. Some commonly-used scoring rules include efficacy [4] (score)), objective parallelism [I] (scorez), directed cutoff distance [T6] (score;), and integral support [40] (scorel) (defined in Appendix Aj. Efficacy measures the distance between the cut a x S B and
"[p: score] (a x B) = (a² TTP - ||ax||y
[|g as illustrated in Figure 2a Objective parallelism
measures the angle between the objective and the cut's 's normal vector a:: scorey (arr x S 3B
cT aaa /[[l<|| ||c|l]), as illustrated in Figures 2b and 2c Directed cutoff distance measures the distance between the LP optimal solution and the cut in a more relevant direction than the efficacy scoring rule. Specifically, let きे be the incumbent solution, which is the best-known feasible solution to the input IP. The directed cutoff distance is the distance between the hyperplane (a,, B) and the current LP solution sip along the direction of the incumbent æ. illustrated in Figures 2d and 2e acores(a") x < 8) = - zipll2 (a x[p B)/ a (x x[p)]- SCIP uses the scoring rule @acore + 1 score scooes + 1/ score, [6]]
'The set of CG cuts is equivalent to the set of Gomory (fractional) cuts [12] another commonly studied family of cutting planes with slightly different parameterization.

---

(a) Efficacy
(b) Better objective parallelism
(c) Worse objective parallelism
(d) Better directed cutoff distance
(e) Worse directed cutoff' distance
Illustration of scoring rules. In each figure, the blue region is the feasible region, the black dotted line is the cut in question, the blue solid line is orthogonal to the objective c, the black dot is the I.P optimal solution, and the white dot is the incumbent IP solution. Figure 2a illustrates efficacy, which is the length of the black solid line between the cut and the I.P optimal solution. The cut in Figure 2bahas has better objective parallelism than the cut in Figure 2c] The cut in Figure 2d has better directed cutoff' distance than the cut in Figure 2e but both have the same efficacy.
Figure 2:
2.2 Learning theory background and notation
The goal of this paper is to learn cut-selection policies using samples in order to guarantee, with high probability, that B&C builds small tree in expectation on unseen IPs. To this end, we rely on the notion of pseudo-dimension 34, a well-known measure of a function class's intrinsic complexity. The pseudo-dimension of function class F C R denoted Pdim(F), is the largest integer N for which there exist N inputs yi...., YN E y and N thresholds r1, TN E R such that for every , {0, 1 there exists F such that f f1: r; if and only if a; 1. Function classes with bounded pseudo-dimension satisfy the following uniform convergence guarantee 3 34
Let [-k, x| be the range of the functions in F, let Nz(e, 8) = O f (F) + (n(z))) and let N Nr 8). For all distributions D on y with probability
5 over the draw of yı, UN D,
for every function f E F, the average value of f over the samples is within of its expected value: 1 Em f(u) Ey-D [f)]] s e. The quantity 8)) is the sample complexity of F. We use the notation || to denote the sum of the absolute values of all the entries A.
3 Learning Chvátal-Gomory cuts
In this section we bound the sample complexity of learning CG cuts at the root node of the B&C search tree. In many IP settings, similar IPs are being solved and there be good cuts that carry across instances for example, in applications where the constraints stay the same or roughly the same across instances [ and only the objective changes. One high-stakes example of this is the feasibility checking problem in the billion- incentive auction for radio spectrum, where prices change but the radiowave interference constraints do not change.
We warm up by analyzing the case where a single CG cut added at the root (Section 3.T. and then build on this analysis to handle w sequential waves of & simultancous CG cuts (Section 3.3) This means that all cuts in the first wave are added simultancously, the new (larger) LP relaxation is solved, all & cuts in the second wave are added to the new problem simultaneously, and adds cuts in waves because otherwise, the angles between cuts would become obtuse, leading to numerical instability. Moreover, many commercial IP solvers only add cuts at the root because those cuts can be leveraged throughout the tree. However, in Section [ we also provide guarantees for applying cuts throughout the tree. In this section, assume that all aspects of B&C (such as node selection and variable selection) are fixed except for the cuts applied at the root of the search tree.
B&C
3.1 Learning a single cut
To provide sample complexity bounds, as per Section 2.2 we bound the pseudo-dimension of the set of functions fu for [0, 1]mh, where fu A, b) is the size of the tree B&C builds when it applies the CG cut defined by u at the root. To do so, we take advantage of structure exhibited by the class of dual functions, each of which is defined by a fixed IP (c. b) and measures tree size as
We assume that constraints generated in the same order across instances; Appendix for discussion.
5

---

a function of the parameters u. In other words, each dual function fČ [0. - R is defined as (") = (c, A. b). Our main result in this section is a proof that the dual functions are
well-structured (Lemma 3.2 which then allows us to apply a result by Balcan et al. [8] to bound Pdim((fu= u [0, ||Th [) (Theorem 3.3). Proving that the dual functions are well-structured is challenging because they are volatile: slightly perturbing can cause the tree size to shift from constant to exponential in n, as we prove in the following theorem. The full proof is in Appendix C
Theorem 3.1. For any integer 71, there exists an integer progrum (c, A, b) with two constraints and at1, then applying the CG cut defined by u at the roor 2n I u[1] u[2] < 1, then applying the CG cut defined by u the root causes B&C build tree of size at least 2
variables such that if S u[1] - ud2] < 2n
causes B&C to terminate immediately. Meanwhile, if n+1
Proof sketch. Without loss of generality, assume that n is odd. Consider an IP with constraints [[x[1]+ +.... xfn]) I n, -2(x[[1] +... x(n)) -nn x E {0. 1)", and any objective. This IP is infeasible because is odd. Jeroslow (22) proved that without the of cutting planes or heuristics, B&C will build tree of size 2 before it terminates. We prove that when =+1 the CG cut halfspace defined by u = (u [1] u(2]) has an empty intersection with the feasible region of the IP, causing B&C terminate immediately. On the other hand, we show that if n+1
-n,
2 S u[1] w/2]- < 2n
2n I u[1] - u[2] < 1, then the CG cut halfspace defined by u contains the feasible region of
the IP, and thus leaves the feasible region unchanged. In this case, due to Jeroslow [22], applying this
CG cut at the root will cause B&C to build tree of size at least 2 1)/2 before it terminates.
This theorem shows that the dual tree-size functions can be extremely sensitive to perturbations in the CG cut parameters. However, we are able to prove that the dual functions are piecewise-constan
Lemma 3.2. For any IP (c, A, b). there are O(1AI|,,1 - [|b]], +n) hyperplanes that partition [0, 1)m into regions where in any one region R, the dual function fč,A, (u) is constant for all u E R.
Proof. Let a1...., a, E 1T be the columns of A. Let A, = || and B = =|[b|] for any
b] E [-B, For each integer k [- A,). E [0, 11mh u a; E [-A,, A.] and bubb]
have | a. = kj + k S u" a, < K + There are Ei= 24 + 0(1 + n) such halfspaces, plus an additional 2B + halfspaces of the form Kn+1 I u²b < ko+1 + 1 for each kn+1 E {- .... B). In any region R defined by the intersection of these halfspaces, the vector (Lu" ai......,. [u" a. uu b]) is constant for all u E R, and thus so is the resulting cut.
Combined with the main result of Balcan et al. 81, this lemma implies the following bound. Theorem 3.3. Let Fa.9 denote the set of all functions for u E [0. defined on the domain of
IPs (c.A, b) with |A]l, I a and [|b|]] < B. Then, Pdim(Fa..
Om log (m((m)( + B + n))).
This theorem implies that Ō(K2m/E?) samples sufficient to ensure that with high probability, for every CG cut, the average size of the tree B&C builds upon applying the cutting plane is within c of the expected size of the tree it builds (the Ô notation suppresses logarithmic terms).
3.2 Learning a sequence of cuts
We now determine the sample complexity of making w sequential CG cuts at the root. The first cut is defined by m parameters U₁ [0, 1) for each of the m constraints. Its application leads to the addition of the row |uf A a < " b) to the constraint matrix. The next cut then be defined by m + 1 parameters U2 E [0. 1] |=+1 since there are now m + 1 constraints. Continuing in this fashion, the with cut is be defined by m + w
parameters u. E [0, 1 1|m+=-1, Let fuy.....u.. (c, A, b) be the size of the tree B&C builds when it applies the CG cut defined by un then applies the CG cut defined
by u2 to the new IP, and so on, all at the root of the search tree.
As in Section 3.1 we bound the pseudo-dimension of the functions fui....u.. by analyzing the structure of the dual functions fč,A,b' b. which measure tree size as a function of the parameters U1 Ui...., ww Specifically, fč,A,: [0, 11m x ... x [0, 1|m+w-1 + R, where fa uw) =
fun fun..... u. Ac.. The analysis in this section is more complex because the 8th cut (with s

---

{2...., W)) depends not only on the parameters u, but also on Ui..... uz-1- We prove that the dual functions are again saccewsse-constann defined by multivariate polynomials rather than hyperplanes. The full proof is in Appendix
but in this case, the boundaries between pieces are
Lemma 3.4. For any IP (c, A, b), there are O(w2" ||AlI,, + 2n |[bi] + nuc) multivariate polyno- mials in S w² + maw variables of degree I w that partition [0, 1 x x... x [0. 1 into regions where in any one region R. fe,A,b (u.,..... uw
constant for all (wI,..., Uw) E R.
Proof sketch. Let 01 an E R be the columns of A. For t1 E [0, "0... the E [0, 1| define a. E [0, 1|"h ...... a. [0. m for each i [n]] such that o is the ith column of the constraint matrix after applying cuts u1....; U Similarly, define be to be the constraint vector after applying the first 1 cuts. More precisely, we have the recurrence relation
a a;
6a b
aj
a
b"
b
u a
u
T
b
for 8 2..... W. We prove that u1 a
2--1 ||a:l1]] For each integer k; in this < k; + 1. The boundaries of these surfaces are defined by polynomials over u. in < ms + x variables with degree S 8. Counting the total number of such hypersurfaces yields the lemma statement.
E [-2-1 |
interval, |u a: = h2 - h; S u a.
We now use this structure to provide a
bound. The full proof is in Appendix C
Theorem 3.5. Let Fa.ß denote the set of all functions fui... for un [0, 1]mh. ...., Uw [0, 1j defined the domain of integer programs (c b) with ||A||], S and [[b]] S B. Then, Pdim(Fo..) Omm?² log(mw(( + B + n)))-
Proof sketch. The space of 0/1 classifiers induced by the set of degree < w multivariate polynomials in w² + mw variables has VC dimension O((w² + mww) log w) 3 However, we more carefully
examine the structure of the polynomials considered in Lemma 3.4 to give an improved VC dimension
bound of + mw. For each j = L..... m define ü [j]]).... Uw recursively as
ü [i] = u1bl [s]
[i] = L. +
u. [m + Eubbi
for s = 2,..., w
8=1
The space of polynomials induced by the sth cut is contained in span (1, ü. [1]..... ü, [m]]. The intuition for this is as follows: consider the additional term added by the sth cut to the constraint matrix, that is, u az. The first m coordinates [u,[1], [l...., u. [m]) interact only with a,-so u, [i] collects coefficient of a, [i]. Each subsequent coordinate u. [m + f] interacts with all coordinates of àj arising from the first cuts. The term that collects a coefficient of [5] is precisely u, [m + E] times the sum of all terms from the first cuts with a coefficient of a, [j]. Using standard facts about the VC dimension of vector spaces and their duals in conjunction with Lemma 3.4 and the framework of Balcan et al. g yields the theorem statement.
The sample complexity (defined in Section 2.2 of learning W sequential cuts is thus 0 2
3.3 Learning waves of simultaneous cuts
We now determine the sample complexity of making w sequential waves of cuts at the root, each wave consisting of A simultaneous CG cuts. Given vectors u ......, uf E [0, 11"h, uz...., ub e (c, A, b) be the size of the
[0, 1|m+h ..... w ....... u E [0, 1] 1]m=++(w--1), let Sui.... .f.............. u! tree B&C builds when it applies the CG cuts defined by ui..... u then applies the CG cuts defined by uz..... u to the new IP, and so on, all at the root of the search tree. The full proof of the following theorem is in Appendix C and follows from the observation that w waves of & simultaneous cuts can be viewed as making kw sequential cuts with the restriction that cuts within each wave assign nonzero weight only to constraints from previous waves.
7

---

Theorem 3.6. Let Fa.ß be the set of all functions Juu............u...... for u!.....,u E [0, "..,.... ww....
u E |0, 1]m+t((-11) defined on the domain of integer programs (c, Ac, with |All,,1 I a and [|b]] S B. Then, Pdim(Fa.9) O(mk2 w/ log mkww(a + n))).
This result implies that the sample complexity of learning W waves of & cuts is O u² ////// fe²)
3.4 Data-dependent guarantees
So far, our guarantees have depended on the maximum possible norms of the constraint matrix and vector in the domain of IPs under consideration. The uniform convergence result in Section (..2 for Fa.g only holds for distributions over A and with norms bounded by a and 3. respectively. In Appendix C.I we show how to convert these into more broadly applicable data-dependent guarantees that leverage properties of the distribution over IPs. These guarantees hold without assumptions on the distribution's support, and depend on E [max, || [ and E (max,, [|b||]]] (where the expectation is over N samples), thus giving a sharper sample complexity guarantee that is tuned to the distribution.
4 Learning cut selection policies
In Section 3] we studied the sample complexity of learning waves of specific cut parameters. In this section, we bound the sample complexity of learning cut-selection policies at the root, that is, functions that take as input an IP and output a candidate cut. Using scoring rules is a more nuanced way of choosing cuts since it allows for the cut parameters to depend on the input IP.
Formally, let I. be the set of IPs with constraints (the number of variables is always fixed n) and let Hm be the set of all hyperplanes in R A scoring rule is a function score Um (Hm x Im) >> Ryo. The real value score(a x S B, (c, A, b)) measure of the quality of the cutting plane ax T x < B for the IP (c, b). Examples include the scoring rules discussed in Section 2.1
Suppose score score, are d different scoring rules. We now bound the sample complexity of learning combination of these scoring rules that guarantee a low expected tree size. Our high- level proof technique is the same as in the previous section: we establish that the dual tree-size functions are piecewise structured, and then apply the general framework of Balcan et al. [ to obtain pseudo-dimension bounds.
Theorem 4.1. Let C be a set of cutting-plane parameters such that for every IP (c, A, b). there is a decomposition of C into S r regions such that the cuts generated by any two vectors in the same region are the same. Let scorel.... scorea be d scoring rules. For μ Rd, let f A, b) be the size of the tree B&C builds when it chooses cut from C to maximize sco]sccr(e(: (c. A. b))
+ p middsscored(: (c, A, b)). Then, Pdim (dim({pp= :p E [Rd]) = (ddoog(d))
Proof. Fix an integer program (c, Ac b). Let uI...., Ur C be representative cut parameters for each of the r regions. Consider the hyperplanes Σi= [[i]score; = Σ [4li]score;(u for each s * E (1....,r) r (suppressing the dependence on c, A, b). These (r hyperplanes partition Rd into regions such that as μ varies in given region, the cut chosen from C is invariant. The desired
bound follows from the main result of Balcan et al. g
Theorem can be directly instantiated with the class of CG cuts. Combining Lemma 3.2 with the basic combinatorial fact that & hyperplanes partition Rd into at most kn regions, we get that the pseudo-dimension of {frz 1 E IR4) defined on IPs with ||A||],1 S a and [|b]] I B is Odm (o((a(a + 3 + n))). Instantiating Theorem 4.1 with the set of all sequences of w CG cuts requires the following extension of scoring rules to sequences of cutting planes. A sequential scoring rule is a function that takes as input an IP (c, A, b) and a sequence of cutting planes hy...., hw. where each cut lives in one higher dimension than the previous. It measures the quality of this sequence of cutting planes when applied one after the other to the original IP. Every scoring rule score can be naturally extended to sequential scoring rule score defined by score (1,,.. ... hws (c", Ao, bo)) EiS score(h (c', A', b')). where (c', A b¹) is the IP after applying cuts h1...., 14-11-
Corollary 4.2. Let C = [0, 1m x .... 10, mj denote the set of possible sequences of w Chvátal-Gone Goottyy cut parameters. Let score,..... scorea C x Im X ... Im+w-1 + R
8

---

be d sequential scoring rules and let fulc, b) be as in Theorem 4.1 for the class C. Then, Pdim m f E R= = ((mmw² log(dw(( + 3 + n))).
we showed that there are (w22 a + 2 + nw) multivariate polynomials that belong family of polynomials 9 with VCdim S + mww (g* denotes the dual of 9) that partition C. into regions such that resulting sequence of cuts is invariant in each region.
Proof. In Lemma 3.4 and Theorem 3.5
By Claim 3.5 by Balcan et al. [8] the number of regions is O(w2"a a + 2 3 + nw) VCdim(g")
O(w2 2 3 + mw) --w The corollary then follows from Theorem 4.1
These results bound the sample complexity of learning cut-selection policies based on scoring rules, which allow the cuts B&C that selects depend on the input IP.
Sample complexity of generic tree search
In this section, we study the sample complexity of selecting high-performing parameters for generic tree-based algorithms, which are generalization of B&C. This abstraction allows us to provide guarantees for simultaneously optimizing key aspects of tree search beyond cut selection, including node selection and branching variable selection. We also generalize the previous sections by allowing actions (such cut selection) to be taken at any stage of the tree bearch-not, just at the root.
Tree search algorithms take place over series of i. rounds (analogous to the B&B tree-size cap in the previous sections). There is a sequence of steps that the algorithm takes on each round. For example, in B&C, these steps include node selection, cut selection, and variable selection. The specific action the algorithm takes during each step (for example, which node to select, which cut to include, or which variable to branch on) typically depends on scoring rule. This scoring rule weights each possible action and the algorithm performs the action with the highest weight. These actions (deterministically) transition the algorithm from one state to another. This high-level description of tree search is summarized by Algorithm For each step j E [t]. the number of possible actions is T, E N. There is a scoring rule scorej, where score, (k, s) E R is the weight associated with the action &s E [T}] when the algorithm is in the state
Algorithm 1 Tree search
Input: Problem instance, t scoring rules score score,, number of rounds k.
$1,1 f- Initial state of algorithm
2: for each round E [nc] do
3: for each step j E [t] do
4: Perform the action k E [T}] that maximizes score, (8i.g k)
5: 85,j+1 f- New state of algorithm
6: $;+1,1 + 8i,++1
> State at beginning of next round equals state at end of this round
Output: Incumbent solution in state Sx,441, if one exists.
There are often several scoring rules one could use, and it is not clear which to use in which scenarios. As in Section 4 we provide guarantees for learning combinations of these scoring rules for the particular application at hand. More formally, for each step j E [t], rather than just single scoring rule score, as in Step there are d, scoring rules scorej,1, ..,....,,,,,; Given parameters 14 = ( [d,)) E Rdd,, the algorithm takes the action i: E [T,] that maximizes Ee 14 (k: There is distribution D over inputs x Algorithm 1 For example, when this framework instantiated for branch-and-cut, x is an integer program (c, A, b). There is utility function (z)) [-H, H) that measures the utility of the algorithm parameterized by = (Mi..... 14:) on input x. For example, this utility function might measure the size of the search tree that the algorithm builds. We assume that this utility function is mnaal-stat-ccossantt
Definition 5.1. Let μ (pI...., M2) and μí (u/...., 14)) be two parameter vectors. Suppose that we run Algorithm| on input x once using the scoring rule score, = Σ My [i]soree,, and once using the scoring rule score, Σie 14, sioore. Suppose that on each run, we obtain the same final state sx,+11 The utility function is final-state state-constant if fz(z) (x).

---

We provide a sample complexity bound for learning the parameters μ.. The full proof is in Appendix Theorem 5.2. Let d Ej= d2 denote the total number tunable parameters of search. Then,
Pdim ((R:))R)) =0(dn) =0 log T; + d
Proof sketch. We prove that there is set of hyperplanes splitting the parameter space into regions such that if tree search uses any parameter setting from a single region, will always take the same sequence of actions (including node, variable, and cut selection). The main subtlety is induction argument to count these hyperplanes that depends on the current step of the tree-search algorithm. C
In the context of integer programming, Theorem 5.2 only recovers the main result of Balcan et al. [5] for learning variable selection policies, but also yields a more general bound that simultaneously incorporates cutting plane selection, variable selection, and node selection. In B&C, the first action of each round is to select a node, Since there are at most 2 -I nodes, Ti S 2n-1 1. The second action is choose cutting plane. As in Theorem 4. let C. be family of cutting planes such that for every IP (c, A, b). there is a decomposition of the parameter space into < r regions such that the cuts generated by any two parameters in the same region are the same. So T2 < The last action is to choose a variable to branch on at that node, so T'3 n. Applying Theorem [.2 Pdim(1Jy : μ E R= = (den + de log r + dolog d). Ignoring Ti and T2, thereby only learning the variable selection policy, recovers the Odd log n + d dllog d) bound of Balcan et al. [5]
Conclusions and future research
We provided the first provable guarantees for using machine learning to configure cutting planes and cut-selection policies. We analyzed the sample complexity of learning cutting planes from the popular family of Goomoyy (CG) cuts. We then provided sample complexity guarantees for learning parameterized cut-selection policies, which allow the wranch-and-cut algorithm to adaptively apply cuts as it builds the search tree. We showed that this analysis can be generalized to simultaneously capture various key aspects of tree search beyond cut selection, such node and variable selection.
This paper opens up variety questions for future research. For example, which other cut families can we learn over with low sample complexity? Section 3 focused on learning within the family of CG cuts (Sections 4 and 5 applied more generally). There are many other families, such as Gomory mixed-integer cuts and an interesting direction for future research (and would call for new techniques). In addition, can we machine learning to design improved scoring rules and heuristics for cut selection? The bounds we provide in Section Happly to any choice of scoring rules, no matter how simple or complex. Is it possible to obtain even better bounds by taking into account the complexity of the scoring rules? Finally, the bounds in this paper are worst case, but a great direction for future research is to develop data-dependent bounds that improve based on the structure of the input distribution.
cuts, and sample complexity analysis of these is
Acknowledgements
This material is based on work supported by the National Science Foundation under grants IIS- 1618714, 171-471,,57, IIS-1901403, 173355, CCF-1535967, CCF-1910321, SES-1919453, the ARO under award W91 I INF2010081, DARPA under cooperative agreement HRO011 12020003, an AWS Machine Learning Research Award, an Amazon Research Award, a Bloomberg Research Grant, and Microsoft Research Faculty Fellowship.
References
[1] Tobias Achterberg. Constraint Integer Programming, PhD thesis, Technische Universität Berlin, 2007.
[2] Alejandro Marcos Alvarez, Quentin Louveaux, and Louis Wehenkel. machine learning-based approximation of strong branching. INFORMS Journal on Computing, 29(1):185-195 2017.
10

---

[3] Martin Anthony and Peter Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 2009.
[4] Egon Balas, Scbastián Ceria, and Gérard Coruééjos. Mixed 0-1 programming by lift-and- project in a branch-and-cut framework. Management Science, 42(9):1229- -226, 1996.
[5]
Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch. In International Conference on Machine Learning (ICML), 2018.
[6] Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Learning optimize compu- tational resources: Frugal training with generalization guarantees. In AAAI Conference on Artificial Intelligence, 2020.
[7] Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Refined bounds for algorithm configuration: The edge of dual class approximability. In International Conference on Machine Learning (ICML), 2020.
[8] Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm design. In Annual Symposium Theory of Computing (STOC), 2021.
[9] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: methodological tour d' d'horizon. European Journal of Operational Research, 2020.
[10] Vašek Chvátal. Edmonds polytopes and hierarchy of combinatorial problems. Discrete mathematics, 4(4):305- 1973.
[11] Michele Conforti, Gérard Cornuéjols, Giacomo Zambelli, et al. Integer programming, volume 271. Springer, 2014.
[12] Gérard Cornuéjols and Yanjun Li. Elementary closures for integer programs. Operations Research Letters, 28(1):1-8, 2001.
[13] Giovanni Di Liberto, Serdar Kadioglu, Kevin Leo, and Yuri Malitsky. Dash: Dynamic approach for switching heuristics. European Journal of Operational Research, 248(3):943-953 2016.
[14] Richard Dudley, Universal Donsker classes and metric entropy. The Annals of Probability, 15 (4):1306-1326, 1987.
[15] Aaron Ferber, Bryan Wilder, Bistra Dilkina, and Milind Tambe. MIPaal.: Mixed integer program layer. In AAAI Conference on Artificial Intelligence, 2020.
[16] Gerald Gamrath, Daniel Anderson, Ksenia Bestuzheva, Wei-Kun Chen, Leon Eifler, Maxime Gasse, Patrick Gemander, Ambros Gleixner, Leona Gottwald, Katrin Halbig, Gregor Hendel, Christopher Hojny, Thorsten Koch, Pierre Le Bodic, Stephen J. Maher, Frederic Matter, Matthias Miltenberger, Erik Mühmer, Benjamin Müller, Mare F. Pfetsch, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Christine Tawfik, Stefan Vigerske, Fabian Wegscheider, Dieter Weninger, and Jakob Witzig. The SCIP Optimization Suite 7.0. Technical report, Optimization Online, March 2020. URL html
[17] Ralph F. Gomory. Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society, 64(5):275 278, 1958.
[18] Rishi Gupta and Tim Roughgarden. PAC approach application-specife algorithm selection. SIAM Journal on Computing, 46(3):992- 2017.
[19] He He, Hal Daume III, and Jason M Eisner. Learning to search in branch and bound algorithms.
In Annual Conference on Neural Information Processing Systems (NeurIPS), 2014.
[20] Zeren Huang, Kerong Wang, Furui Liu, Hui-ling Zhen, Weinan Zhang, Mingxuan Yuan, Jianye Hao, Yong Yu, and Jun Wang. Learning to select cuts for efficient mixed-ine inteeer programming. arXiv preprint 21Xx:2105.13645 2021.

---

[21] Frank Hutter, Holger H Hoos, Kevin Leyton-Brown and Thomas Stützle. ParamILS: An automatic algorithm configuration framework. Journal of Artificial Intelligence Research, 36 (1):267-306, 2009. ISSN 1076-9757.
[22] Robert G Jeroslow. Trivial integer programs unsolvable by branch-and-bound. Muthematical Programming, 6(1):105-109 1974.
[23] Serdar Kadioglu, Yuri Malitsky, Meinolf Sellmann, and Kevin Tierney. CLAC--istanne-speee algorithm configuration. In European Conference Artificial Intelligence (ECAI), 2010.
[24] Elias Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. In AAAI Conference Artificial Intelligence, 2016.
[25] Elias Khalil, Bistra Dilkina, George Nemhauser, Shabbir Ahmed, and Yufen Shao. Learning to heuristies in tree search. In International Joint Conference Artificial Intelligence (IJCAI), 2017.
[26] Robert Kleinherg, Kevin Leyton-Brown, and Brendan Lucier. Efficiency through procrastination: Approximately optimal algorithm configuration with runtime guarantees. International Joint Conference on Artificial Intelligence (IJCAI), 2017.
[27] Robert Kleinberg, Kevin Lcyton-Brown, Brendan Lucier, and Devon Graham. Procrastinating with confidence: Near-optimal, anytime, adaptive algorithm configuration. Annual Conference on Neural Information Processing Systems (NeurIPS), 2019.
[28] Vladimir Koltchinskii. Rademacher penalties and structural risk minimization. IEEE Transac- tions on Information Theory, 47555:1902-1191 2001.
[29] Michail G Lagoudakis and Michael Littman. Learning to select branching rules in the DPLL procedure for satisfiability. Electronic Notes in Discrete Mathematics, 0:344-35,, 2001.
[30] Kevin Leyton-Browe Brown, Mark Pearson, and Yoav Shoham. Towards universal test suite for combinatorial auction algorithms. In ACM Conference on Electronic Commerce (ACM-EC), pages 66-76, Minneapolis, MN, 2000.
[31] Kevin Leyton-Brown, Eugene Nudelman, and Yoav Shoham. Empirical hardness models: Methodology and case study on combinatorial auctions. Journal of the ACM, 56(4): 2009. ISSN 0004-5411.
[32] Jia Hui Liang, Vijay Ganesh, Pascal Poupart, and Krzysztof Czarnecki. Learning rate based branching heuristic for sat solvers. In International Conference on Theory and Applications of Satisfiability Testing, pages 123-140. Springer, 2016.
[33] Andrea Lodi and Giulia Zarpellon. On learning and branching: survey. TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, 25(2):207-236, 2017.
[34] David Pollard. Convergence of Stochastic Processes. Springer, 1984.
[35] Ashish Sabharwal, Horst Samulowitz, and Chandra Reddy. Guiding combinatorial optimization with UCT. In International Conference Al and OR Techniques in Constraini Programming for Combinatorial Optimization Problems. Springer, 2012.
[36] Tuomas Sandholm. Vary-large-seee generalized combinatorial aulti-attribute auctions: Lessons from conducting $60 billion of sourcing. In Zvika Neeman, Alvin Roth, and Nir Vulkan, editors, Handbook of Market Design. Oxford University Press, 2013.
[37] Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Reinforcement learning for integer program- ming: Learning to cut. International Conference on Muchine Learning (ICML., 2020.
[38] Gellért Weisz, András György, and Csaba Szepesvári. LEAPSANDBOUNDS: A method for approximately optimal algorithm configuration. In International Conference on Machine Learning (ICML), 2018.
12

---

[39] Gellért Weisz, Andrés György, and Csaba Szepesvári. CAPSANDRUNS: An improved method for upproximately optimal algorithm configuration. International Conference on Machine Learning (ICML), 2019.
[40] Franz Wesselmann and Uwe Suhl. Implementing cutting plane management and selection techniques. Technical report, University of Paderborn, 2012.
[41] Wei Xia and Roland Yap. Learning robust search strategies using a bandit-based approach, In AAAI Conference Artificial Intelligence, 2018.
[42] Lin Xu, Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown. Brown. Satzilla: portfolio-based algorithm selection for SAT. Journal of Artificial Intelligence Research, 32(1):565-606, 2008.
[43] Lin Xu, Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown. Hydra-MIP: Automated algorithm configuration and selection for mixed integer programming. In RCRA workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion at the International Joint Conference on Artificial Intelligence (IJCAI), 2011.
[44] Kaan Yilmaz and Neil Yorke-Smine Learning efficient search approximation in mixed integer branch and bound. arXiv preprint 2000020007,,3948, 2020.
13


Reviews:
[{"review_id": "wrjb5hUEu-n", "reviewer": "Reviewer_4fY3", "summary": "This paper studies the sample complexity of cutting plane selection in branch-and-cut algorithms for integer programming problems. The authors study a handful of different settings, with the goal of characterizing the intrinsic difficulty of learning: (i) the tree size upon adding a single cut at the root, (ii) the tree size upon adding a sequence of cuts at the root, (iii) the tree size upon adding a series of waves of cuts at the root, and (iv) the score of cuts according to a set of predefined scoring rules. Finally, the authors generalize the results to bound the sample complexity of generic tree search policies with sequential operations that can be scored.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is nicely written, tackles an interesting problem, and covers a nice range of related, but still distinct, settings. I view it as a worthy addition to the literature, though I am not particularly well-suited to evaluate the learning aspects of the work (i.e. its novelty or deepness).\n\nI have two questions/comments for the authors:\n1.This is nitpicky, but: [10], as cited on L136, restricts attention to bounded polyhedron, whereas the authors do not make the same assumption.\n2. How much of this machinery is specialized for integer programming as opposed to mixed-integer programming? I would be interested to hear the authors thoughts, though I do not feel that a lengthy discussion is needed in the paper itself.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "WO6C5t0u_mC", "reviewer": "Reviewer_i38d", "summary": "The paper focuses on the sample complexity of learning to select Chvatal-Gomory cuts for integer linear programming. We assume that there is an unknown distribution that generates ILP instances. CG cuts are parametrized by a set of weights, one per constraint. How large should the set of training instances be for one to accurately estimate the \"goodness\" of a given parametrization? This is the main question tackled here.\n\nUsing the data-driven algorithm design framework of Balcan et al. [8], this paper shows that three flavors of the learning problem can be analyzed effectively. The main contribution is to show that there is structure to the cut generation process as its parameters vary; the space of possible cuts can be partitioned, the form of the boundaries that determine the partition is identified, and the behavior of the cut generation is constant within each region. These can be plugged into a very general PAC learning bound from Balcan et al. [8].\n\nAdditionally, the sample complexity of generic tree search is analyzed. It is shown that variable, node, and cut selection can be parameterized simultaneously, each with its own additive scoring function, and sample complexity bounds can be derived accordingly. This result generalizes a previous branching-only bound from Balcan et al. [5].\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Clarity: The paper is very well-written and easy to read. Proofs are either concise or sketched in the main text, which I appreciate.  \n\nOriginality: The sample complexity of learning to generate CG cuts is a new problem as far as I know. Deriving the partitions of the parameter spaces do involve some careful analysis.\n\nQuality: The paper is expertly executed. I have checked the proofs to the extent that I am capable, and identified one potential mistake which is likely inconsequential:\n\nIn line 203, you say $\\sum_{i=1}^{n}{2A_i} \\in O(\\lVert A \\rVert_{1,1})$. I suspect this should be $O(n\\lVert A \\rVert_{1,1})$: consider the case where all column norms are equal, then summing them up gives $2n \\lVert A \\rVert_{1,1}$.\n\nIf you ignore logarithmic factors in the sample complexity bound of line 210, this missing factor of $n$ is ignored anyways, so even if I were right about this, it is maybe not a big issue. I'd like the authors to comment on this.\n\nSignificance: There's a basic issue with the set of results in section 3. The values of the parameter vector depend on the index of the constraint, i.e., $u[1]$ corresponds to the first constraint, etc. Now consider two identical ILP instances with the constraints permuted. The same parameter vector can potentially produce a different cut. A practical scenario for this is a graph optimization problem, say Max. Independent Set (MIS), where each linear constraint expresses independence along an edge of the graph; there is no intrinsic ordering to the edges and thus to the constraints. This is to say that unlike the scoring rules in section 4, the parameters in section 3 make little sense unless you make strong assumptions on the distribution of instances, e.g., if all instances have the exact same constraints but a random objective function, which makes the ordering argument irrelevant.\n\nI am not 100% sure of it, but I think section 4 does not suffer from this issue, as the scoring rules take pre-generated cuts as input.\n\nMore broadly though, while the technical work involved in deriving the sample complexity bounds in this paper is solid, I don't see what the theory tells us about the practice: the sample complexity bounds often require a large number of instances (e.g., line 210, quadratic in the maximum search tree size), and there is no clear path to a practical empirical risk minimization procedure that exploits the partition of the parameter space. I would be interested in hearing what the authors think about this.\n\nMinor:\n- Line 318: \"which allow the cuts B&C that selects\" --> \"which allow the cuts that B&C selects\"\n- This paper might be relevant to your literature review: Baltean-Lugojan, Radu, et al. Scoring positive semidefinite cutting planes for quadratic optimization via trained neural networks. Working paper., 2019, http://www. optimization-online. org/DB_HTML/2018/11/6943. html, 2019.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "LDf8QepKLFV", "reviewer": "Reviewer_U5ky", "summary": "Combinatorial optimization solvers often add cutting planes during solving, which are additional constraints in the problem that accelerate solving. These cutting planes have a major impact on the size of the final branch-and-bound tree, and therefore of the speed of the overall solving, but their impact is badly understood theoretically. At minimum, it is empirically understood that the size of the branch-and-bound tree is a complicated and sensitive function of the parameters of the cutting planes that were added during solving: a slightly different cutting plane might have been much more, or much less, effective.\n\nIn this paper the authors look at the problem of trying to learn these functions that relate the size of the branch-and-bound tree (a measure of solving performance) as a function of the instance data (A, b, c) when cuts with given parameters u_1, ..., u_k are added to the problem. They compute an order of magnitude of samples required to learn well this function, both for a single cut, a sequence of cuts, or rounds of sequences of cuts (as are used in practice). They also compute the number of samples required for the generalized problem of predicting tree size as a function of the instance data (A, b, c) for an algorithm that would pick the cut parameters to maximize a convex combination of scores, for given algorithm hyperparameters (the convex weights.) Finally, they do the same for more general algorithms that would pick an action, during solving, by maximizing a convex combination of scores, such as when doing node selection or variable selection.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think the paper is overall interesting. Although branch-and-cut is the main algorithm used by combinatorial optimization solvers, very little theory has been developed for it, mostly because it is devilishly difficult. The current paper develops some theory related to a more tangential aspect (how hard is it to learn the function mapping cuts, or scoring weights, to the tree size?), but which might be useful for cut selection. In some sense only the initial results of the paper (Theorem 3.1, Lemma 3.2, Lemma 3.4) really seem to have to do with cutting planes per se; the rest is more a consequence of generic results about learning discrete functions, like the tree size, as a function of continuous parameters. Nonetheless the results are not trivial and are certainly original.\n\nOn the criticisms side, I think there could be ways for the presentation in Section 4 to be improved.\n1) I think the authors should really separate better the paragraph starting at line 298 in two, at line 301. I found the lack of break confusing: the text switches from discussion Theorem 4.1 to moving on to the next result without a breath in between.\n2) I think the authors should explain better in Theorem 4.1 what is the main result of Balcan et al. (2021) (Theorem 3.3?) and how it gets invoked in the proof, since the setup and notation of that second paper is quite different from this one. Right now I find the current proof a bit too hand-wavey for my taste, for what is ultimately (with Theorem 5.2) the most interesting result of the paper.\n3) My third question is perhaps a bit more philosophical, but is there a good reason why the bound of Theorem 4.1 seems to have no relationship at all with the scoring functions? One might have thought that more complex scoring functions would have led to tree sizes that are more sensitive to their input, and therefore needing more samples to learn, but your bound seems independent of their complexity. Perhaps a little high level explanation would be welcome in the text.\n\nOtherwise, I think the literature review section could be improved. There is a lot of applied papers missing, mostly from more recent years - the list is far from being up to date, both for variable selection, node selection and cut selection. For cut selection there is the recent Huang et al. (2021); for node selection there is Yilmaz and Yorke-Smith (2021). For variable selection (the most studied problem) there is quite a bit missing out, probably at least 10 papers or so since 2017-2018. Conversely, I am not sure I understand the relevance of the paragraph discussing Ferber et al. (2020), except that the method uses cutting planes - this has not really much to do with branch-and-cut?\n\nI also think the tone is sometimes a bit too grandiose in the abstract and the paper. \"In this paper we prove the first guarantees for learning high-performing cut-selection policies tailored to the instance distribution at hand using samples\" makes it sound like the authors have a procedure with guarantees to produce high-quality cuts - this is not the case. Or in sentences like, \"we bound the sample complexity of learning high-performing cutting planes\" - I don't think they bound at all the sample complexity of learning the (optimal) planes, they bound the sample complexity of learning a metric, the tree size. This is different in my mind. Now, I do agree that the results of the paper might be useful for deriving such procedures-with-guarantees, for example by optimization of the empirical mean performance over instances (empirical risk minimization), but this is not discussed in the paper, and there would be more work needed to get there. In fact, I think the paper does in that respect an underwhelming job of explaining why these results are interesting, and on that aspect better explaining how they could be useful for cutting plane algorithms would be useful.\n\nAnother more minor comment: in Section 3 (and elsewhere in the paper), the authors discuss \"waves of cuts\". I am personally much more used to hear about \"rounds\" of cuts, which I think (perhaps incorrectly) is the more standard term in the combinatorial optimization community. To help readers, perhaps it would be valuable to switch to this terminology? Unless there is a distinction I did not quite grasp between the two concepts.\n\nOverall, my recommendation would be acceptance of the paper, with the criticisms I described above having been addressed.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As I mentioned, although I like in general the contributions, I found the tone sometimes a bit too bombastic in the claim of its breath. On a positive note however, they do discuss how their results are mostly focused on Gomory fractional cuts and not other families.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "BaibT0FMh3U", "reviewer": "Reviewer_D3H9", "summary": "Linear integer programming is an incredibly important algorithmic tool that is used widely in practice.  In general the problem is NP-hard and so we have to resort to heuristics. These heuristics often use the branch-and-cut framework: we branch on \"guesses\" on variables and we cut by adding valid inequalities that tightens the linear relaxation of the integer program.\n\nWhen dealing with such heuristics, an obvious question arises: which cut should I add and on which variable should I branch? The goal here is to limit  the size of the search tree and therefore getting a good running time. There has been a growing amount of experimental work on using ML algorithms to guide this choice.  \n\nThe paper under submission considers this problem from a more theoretical perspective. The main results bound the sample complexity for finding \"good\" cuts complementing and generalizing a prior work that studied this question for variable selection.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper studies an important problem and give original new contributions.  The paper is also written extremely well and is a pleasure to read.  In what follows, I detail some of the contributions of the paper and comment on their strengths and weaknesses.\n\nThe first question that the authors study is the following. Suppose you have an (unknown) distribution over m-constraint IPs. You would like to find the best Chvatal-Gomory (CG) cut u in the following sense. If I add u to the IP then I would like to have the smallest search tree in expectation over the randomly chosen IP (from the distribution). More specifically, the authors study the sample complexity of u and show that it is near linear in m under reasonable norm bounds on the coefficients of the IP instances.  The proofs of this is not hard and uses a connection to pseudo-dimension used in prior work. The key insight is the observation that for a fixed IP the number of Chvatal-Gomory cuts of interest is  exponential.  The authors also generalize this to when you add several cuts to the root of the search tree.\n\nThe  strength of the first line of results is that it give new insights to a classic and very natural family of cuts (Chvatal-Gomory cuts). The weaknesses are that (1) the results do not tell us much about when we can find a good cut efficiently; and, as the author points out, (2) the current cut does not depend on the actual IP only on the distribution which is quite unnatural.  It would be good if the authors further explain when this setting is natural and also to comment on the efficiency issue.\n\nIndeed, many solvers uses different scoring rules (that depend on the IP) to select the cuts to add. This is the second part of the paper where the authors analyze the sample complexity of learning such scores. The statement of this result is interesting. The techniques to get it are not striking: basically they show that a good combination of d scoring rules is learnable. Assuming the coefficients in front of these scoring rules don't have huge bit complexity, this follows since then the number of options is say poly(n)^d (or even exp(n)^d if we allow polynomial bit complexity in our coefficients). Now the authors have to work  a little more since they don't make such an assumption.  \n\nThe authors also generalize this to a more generalize tree search model in which they are able to recover and generalize prior work that only considered the sample complexity of variable selection.\n\nOverall, I see this as a nice paper that is interesting. It touches on a very interesting problem where we can expect ML to lead to huge speedups. It is unclear how the the sample complexity of the problems considered here will inform such improvements and it would be great if the authors would comment more on this. Overall, I'd recommend the paper to be accepted.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do wish the authors would have discussed more why the sample complexity is important for cut selection. Perhaps it is a necessity but it is not sufficient (the sample complexity of exponentially many functions is low but we can't try all). As aforementioned, it would also have been good if the authors would have been given a concrete examples where we would expect to have a distribution of IPs and select our cuts depending on this distribution and not the instance.\n", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper shows sampling bounds for the problem of identifying good cuts in branch-and-bound search using cutting planes. The reviewers appreciated the importance of the problem and the contribution of the paper. Some reviewers were concerned that sampling bounds by themselves do not provide efficient algorithms for finding good cuts, but these concerns were mostly resolved during the rebuttal phase.
Decision: Accept (Spotlight)