Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts
Authors: Nina Balcan
Siddharth Prasad
Tuomas Sandholm
Ellen Vitercik
Venue: NeurIPS 2022 Accept (2022)
Keywords: Gomory mixed integer cuts
automated algorithm configuration
integer programming
tree search
branch-and-bound
branch-and-cut
cutting planes
sample complexity
generalization guarantees
data-driven algorithm design

Abstract: The incorporation of cutting planes within the branch-and-bound algorithm, known as branch-and-cut, forms the backbone of modern integer programming solvers. These solvers are the foremost method for solving discrete optimization problems and thus have a vast array of applications in machine learning, operations research, and many other fields. Choosing cutting planes effectively is a major research topic in the theory and practice of integer programming. We conduct a novel structural analysis of branch-and-cut that pins down how every step of the algorithm is affected by changes in the parameters defining the cutting planes added to the input integer program. Our main application of this analysis is to derive sample complexity guarantees for using machine learning to determine which cutting planes to apply during branch-and-cut. These guarantees apply to infinite families of cutting planes, such as the family of Gomory mixed integer cuts, which are responsible for the main breakthrough speedups of integer programming solvers. We exploit geometric and combinatorial structure of branch-and-cut in our analysis, which provides a key missing piece for the recent generalization theory of branch-and-cut.

Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts
Maria-Florina Balcan
Siddharth Prasad
Tuomas Sandholm
School of Computer Science
Computer Science Department
Computer Science Department Carnegie Mellon University Optimized Markets, Inc. Strategic Machine, Inc.
Carnegie Mellon University
Carnegie Mellon University
ninamf danamf@cs.co cmu. edu
sprasad28cs. cmu edu
Strategy Robot, Inc. sandholm@cs cmu edu
Ellen Vitercik
Management Science and Engineering Department Computer Science Department
Stanford University
vitercik@sttanff edu
Abstract
The incorporation of cutting planes within the branch-and-bould -ooud-boudddd algorithm, known as mrunch-nddcuus forms the backbone modern integer programming solvers. These solvers the foremost method for solving discrete optimization problems and have a vast array of applications machine learning, operations research, and many other fields. Choosing cutting planes effectively in the theory and practice of integer programming. We conduct a novel structural analysis of branch-and-cut that pins down how every step of the algorithm is affected by changes in the parameters defining the cutting planes added to an integer program. Our main application of this analysis is derive sample complexity guarantees for using machine learning to determine which cutting planes to apply during andch-and-cut. These guarantees apply to infinite families of cutting planes, such as the family of Gomory mixed integer cuts, which are responsible for the main breakthrough speedups of integer programming solvers. We exploit geometric and combinatorial structure of branch-and-cut in our analysis, which provides a key missing piece for the recent generalization theory of branch-and-cut.
major research topic
Introduction
Integer programming (IP) solvers the most widely-used tools for solving discrete optimization problems. They have many applications in machine learning, operations research, and other fields, in- cluding MAP inference (34), combinatorial auctions (52). NLP 37 neural network verification [17).
interpretable classification [61], training of optimal decision trees and optimal clustering 48
Under the hood, IP solvers use the tree-search algorithm branch-an and-bound [41] augmented with cutting planes, known as branch-and-cur (B&C). A cutting plane is a linear constraint that is added to the linear programming (LP) relaxation at any node of the search tree. With a carefully selected cut, the I.P guidance can more efficiently lead B&C to the optimal integral solution. Cutting planes, specifically the family of Gomory mixed integer responsible for breakthrough speedups of modern IP solvers 15] 21
(GMI) which study in this paper,
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Average tree size
21000
Average tree size
36600
20000
36400
19000
36200
18000
36000
17000
35800
0.00 0.25 0.50 0.75 1.00 Parameter
0.00
0.25 0.50 0.75 1.00 Parameter μ
(a) Facility location with 40 locations and 40 clients; (b) Facility location with 80 locations, 80 clients, and sampled by perturbing a base facility location IP.
random Euclidean distance costs.
Figure I: These figures illustrate the need for distribution-dependenn policies for choosing cuts. We plot the average number of nodes B&C expands as function of parameter fs that controls a policy to add GMI cuts, detailed in Appendix A In each figure, we draw a training set of facility location IPs from two different distributions. In Figure Tal define the distribution by starting with uniformly random facility location instance and perturbing its costs. In Figure [b] the costs are more structured: the facilities are located along a line and the clients have uniformly random locations. In Figure [al smaller value of ja leads to small search trees, but in Figure Tb a larger value of ju is preferable.
Successfully employing cutting planes can challenging because there are infinitely many cuts to choose from and there are still many open questions about which cuts to employ when. A growing body of research has studied the use of machine learning for tunigg various aspects of IP
51 52 67) recently including cut 53 55 We analyze a machine learning setting where there is an unknown distribution over for-for example, a distribution over shipping company's routing problems. The learner receives a training set of IPs sampled from this distribution which it uses to learn cut parameters with strong average performance over the training set (leading, for example, to small search trees). Figure T Iillustrates that tuning cut parameters according to the instance distribution at hand can have large impact on B&C's performance, and that for one distribution, the best parameters can be very different-in fact opposite-thal the best parameters for another distribution.
solvers [e.g.. 2 8 12 24
29
33 35
36 38
40
42
44
45
selection [10 I1 30
We provide sample complexity bounds for this procedure, which bound the number of training instances sufficient to ensure that if a set of cut parameters leads to strong average performance future IPs from the same
over the training set, it will also lead to strong expected performance distribution. These guarantees apply no matter what procedure is used to optimize the cut parameters over the training set optimal suboptimal, automated or manual.
significant body of research has recently provided sample complexity bounds for automated algorithm configuration, further illustrating the importance of this line of research [e.g.. (57 g
11
However, these works have been unable to analyze Gomory mixed integer (GMI) cuts 226] which are perhaps the most important family of cutting planes in integer programming. They
16 25 28
dominate most other families of cutting planes (23 and are directly responsible for the realization that a B&C framework is necessary for the speeds now achievable by modern IP solvers [4]. Prior research has been unable to handle GMI cuts because there are an uncountably infinite number of different GMI cuts that one could add, whereas prior research cutting planes was only able to handle cutting plane families of finite effective size 10 IT.. The current work closes this gap.
The key challenge is that an infinitesimal change to any GMI cut can completely change the entire course of B&C because cut added at the root remains in the LP relaxations stored in each node all the way to the leaves. At its core, our analysis therefore involves understanding an intricate interplay between the continuous and discrete components our problem. The first, continuous component requires us to characterize how an L.P' solution changes as function of its constraints. The optimum will move continuously through space until it jumps from one vertex of the polytope to another. We use this characterization to analyze how the B&C tree-a discrete, combinatorial object-varies as function of its LP guidance, which allows us to prove our sample complexity bound.
1.1 Our contributions
In order to prove our sample complexity bound for GMI cuts, we analyze how the B&C tree varies as function of the cut parameters any IP. We prove that the set of all possible cuts can be partitioned

---

(a) LP optimum closed form
(b) Invariant
(c) Invariant I.P
(d) Invariant B&C exccution
branching
integrality
(Lemma
(Lemma
(Lemma
(Theorem 4.4)
Figure 2: Our B&C analysis involves successive refinements to our partition of the parameter space.
into a finite number of regions such that within any one region, B&C builds the exact same search tree. Moreover, the boundaries between regions are defined by low-degree polynomials. The simplicity of this function allows us to prove our sample complexity bound. The buildup to this result consists of three main contributions, each of which we believe may be of independent interest:
1. Our first main contribution (Section addresses fundamental question in linear programming: how does an LP's solution change when new constraints are added? As the constraints vary, the solution will jump from vertex vertex of the LP polytope. We prove that can partition the set of all possible constraint vectors into a finite number of regions such that within any one region, the LP's solution has clean closed form. Moreover, we prove that the boundaries defining this partition have a specific form, defined by degree-2 polynomials.
We build on this result in our second main contribution (Section 4) a novel analysis of how the entire B&C search tree changes builds this search tree by iteratively subdividing its feasible set via a process called branching on variables: in one subdivision, the constraint z2 S le is enforced and in the other x; some variable and integer (k: is chosen according to the LP relaxation solution, as described in Section 2). Upon constructing subdivision S, it checks whether the I.P relaxation restricted to S is integral. If not, it further subdivides S, unless the LP relaxation's 's solution is worse than the best integral solution found thus far, in which case it stops searching in S- process called fathoming or pruming S. Each subdivision is stored as a node in B&C's search tree. Our analysis of how the B&C search changes as a function of the cuts added has four steps, illustrated by Figure A
function of the cuts added the root. At high level, B&C
for
(a) Section First, use our result from Section 3 to show that the cut parameter space can partitioned into regions such that any one region, the LP optimal solution at any node of the B&C search tree has clean closed form, illustrated in Figure 2a
(b) Section 4.2] We this result show that each region can be further partitioned (as illustrated in Figure 2 such that no matter what cut we employ in any one region, all of the branching decisions that B&C makes are fixed. Intuitively, this is because the branching decisions depend on the LP relaxation, which has a closed-form solution in any one region.
Next, we show that each region from Figure 2b can be further partitioned into regions (illustrated Figure(cc) where in any one region, for every node in the B&C tree, the integrality of that node's LP relaxation is invariant no matter what cut in that region we use. (d) Section 4.4 Finally, we show that each of these regions can be further subdivided into regions (as in Figure 2d where the nodes that B&C fathoms are fixed, so the tree it builds is fixed.
(c) Section 4.3
This result allows us to prove sample complexity bounds for learning nigh-performing cutting planes from the class of GMI cuts, our third main contribution (Section 5). Our key technical insight that the GMI cutting plane coefficients can be viewed as mapping that embeds our polynomial partition from the previous step (Figure ( into the space of GMI cut parameters. We prove that the resulting embedding does not distort the polynomial hypersurfaces too much: the embedded hypersurfaces are still polynomial, with only slightly larger degree.
1.2 Related research
Learning to cut. Several papers have studied how to use machine learning for cut selection from whereas our goal is to provide theoretical guarantees. Towards this end, this paper helps develop a theory of generalization for cutting plane selection. This line of inquiry began with paper by Balcan et al. [10), who studied Chvátal-Gomory (CG) cuts [8] 27
an applied perspective (30 53 55

---

for (pure) integer programs (IPs). Later work [I]] provided a unifying compleco analysis of tunable tree-search algorithms when there is finite set of actions the algorithm can take at any given node. All prior research on generalization guarantees for integer programming 6 [0] fits this framework. the context of single-variable branching [6] the number of possible branching decisions at any node is equal to the number of variables. In the context of CG cuts, Balcan et al.
[00] showed that there are only finitely many distinct cuts at any node. These analyses followed by making pairwise comparisons between actions and understanding in what region of the parameter space one action would be chosen over another. Since there were only a finite number actions, there were only a finite number of pairwise comparisons. This approach cannot work in our setting due to the uncountably infinite number of GMI cuts. Tackling a continuum of cutting planes requires novel techniques that we develop in this paper in particular structural analysis of B&C that is significantly more involved than the finite-action setting.
Sensitivity analysis of IPs and LPs. A related line of research studied the sensitivity of LPs, and to lesser extent IPs, to changes in their parameters [e.g.. 20 43 46). This paper fits in to this line of research as we study how the solution to an LP varies as new rows are added.
2 Notation and branch-and-cut background
Integer and linear programs. An integer program (IP) is defined by an objective vector E R"," constraint matrix m and constraint vector b E 2m, with the form
max(c" x: Ax & b, x 2 0, x E }
(1)
The linear programming (LP) relaxation is formed by removing the integrality constraints:
max(c"' x Ax S b, 2 0}. We denote the optimal solution to ( by zip and its LP-relaxation optimal solution by iip. Let x = c² zip- If a is a set of constraints, we let <ip(() denote the optimum of (I) subject to these additional constraints (similarly define <Tp((r and (o))
Polyhedra and polytopes. A set P C Rn is a polyhedron if there exists an integer m, A E RR and b Th such that p {ıx R Ax < b). P is rational polyhedron if there exists A E nxx" and b E nd such that P = fo E R² Ax < b}. A bounded polyhedron is called a polytope. The feasible regions of all IPs considered in this paper are assumed be rational polytopes of full dimension. Let P = fx E IR" a'æ < b, E M] be a nonempty polyhedron. We assume the representation of P irredundant, that is, fxr E II" a'r S b,, E M \ {it} + P for all j E M. For any I C M, the set F2 = {x E I² a x = b,, E a'x < b i E M \ (T] is afcc of P. Conversely, if F is a nonempty face of P. then F F, for some I C M. Faces of dimension 1 are called edges and faces of dimension O are called vertices. A detailed reference on the polyhedral theory used our arguments can be found in Conforti et al. 19).
Given a set of constraints a, let (a)) denote the polyhedron that is the intersection of P with all inequalities in o.
Cutting planes. A cutting plane is constraint a x S 8. Let P be the feasible region of the LP relaxation of (1) and Pi P T be the IP's feasible set. cut is valid if it is satisfied by every integer point in Pi: a x:
for all x E Pi. A valid cut separates a point x E P Pi if a > B. We refer to a cut both by its parameters (at, 3) E g=+1 and the halfspace a x < 3 R".
An important family of valid cuts that we study in this paper is the set of Gomory mixed integer (GMI) cuts. For decades, general-purpose cutting planes were thought to be unwieldy and useless for solving IPs quickly in practice. However, seminal paper by Balas et al. [4] completely reversed this sentiment by showing that GMI cuts added throughout the B&C tree led to massive speedups. Today, GMI cuts one of the most important components of state-of-the- IP solvers.
Definition 2.1 (Gomory mixed integer cut). Suppose the feasible region of the IP is in equality form Ax = b, x 2 O (which can be achieved by adding slack variables). For u E Rmm, let f;
'This assumption is not restrictive one. The Minkowski Weyl theorem states that any polyhedron can be decomposed as the sum of a polytope and its recession cone. All results in this paper can be derived for rational polyhedra by considering the corresponding polytope in the Minkowski- Weyl decomposition.

---

denote the fractional part of (u" A); and let fo denote the fractional part of u u That is, (u"A), = (Lu" Al); + fo and uub b- = [u" b] + fo. The Gomory mixed integer (GMI) cut parameterized by
fo
E fa SA
Σ (1- fo- 1- fo ffi
The form of the GMI cut is obtained via slightly more nuanced rounding procedure than the one used to obtain the CG cut |u AJ S [u"b]. GMI cuts strictly dominate CG cuts. More details about GMI cuts can be found in the tutorial by Cornuéjols [22].
Branch-and-cut. We provide high-level overview of B&C (Nemhauser and Wolsey 49 for
example, provide more details). Given an IP, B&C searches the IP's feasible region by building a binary search tree. B&C solves the LP relaxation of the imput IP and then adds any number of cutting planes. It stores this information at the tree's root. Let [i (.ī+[)),--. " (n)) be the solution to the LP relaxation with the addition of the cutting planes. B&C next uses a variable selection policy to choose a variable 2i to branch on. This means that it splits the IP's feasible region in two: one set where x, S |m[p[(] [ and the other where T; 2 [x[p[(] [1]. The left child of the root now corresponds to the IP with feasible region defined by the first subset and the right child likewise corresponds to the second subset. B&C then chooses a leaf using a node selection policy and recurses, adding any number of cutting planes, branching on a variable, and on. B&C fathoms node-whiee means that it will never branch on that node-if 1) the LP relaxation at the node is infeasible, 2) the optimal solution to the LP relaxation is integral, or 3) the optimal solution to the LP relaxation is no better than the best integral solution found thus far. Eventually, B&C will fathom every Icaf, at which point has found the globally optimal integral solution. We assume there is bound we allow B&C to build before we terminate, as is common in prior research [6]
the size of the tree
31 38 39).
Every step of B&&C-includig node and variable selection and the choice of whether or not to depends crucially on guidance from LP relaxations. Tighter LP relaxations provide more valuable LP guidance, highlighting the importance of cuts. To give an example, this is true of the product scoring rule M. a popular variable selection policy that our results apply to.
Definition 2.2. Let wip be the solution to the LP relaxation at a node and z c² cdppp. The product scoring rule branches on the variable E [n]] that maximizes: max[= - zTp(;; S (ttp( 10-6)-----0 max[2(p = 2 [e]p) 10
Polynomial arrangements in Euclidean space. Let E R(yn.... yk|] be polynomial of degree at most d. The polynomial partitions R into connected components that belong to either IR \ (1i,,..,, .))) ) p(y)...... y& = 0} or {(v)...., m/k) p(y)...., Me) = 0}. When we discuss the connected components of _ induced by p. we include connected components both these sets. We make this distinction because previous work on sample complexity for data-driven algorithm design oftentimes only needed consider the connected components of the former set. The number
of connected components in both sets is ((d)) 47 54 56
3 Linear programming sensitivity
Our main result in this section addresses fundamental question in linear programming: how an LP's optimal solution affected by the addition of new constraints? Later in this paper, we use this result to prove sample complexity bounds for optimizing over the canonical family of GMI cuts.
More formally, fixing an LP with m constraints and variables, if xtp(("' x S 3) E IR" denotes the new LP optimum when the constraint ax a: S /3 is added, we pin down a precise characterization of (a x S (3) function of and B. We show that "[p(a=" x: < 3) has a piece-wise closed form: there are surfaces partitioning I such that within each connected component induced by these surfaces, -[p(( (a x S 3) has a closed form. While the geometric intuition used to establish this piece-wise structure relies the basic property that optimal solutions to LPs are achieved at vertices, the surfaces defining the regions are perhaps surprisingly nonlinear: they are defined by multivariate 2 polynomials in ax B. In Appendix B.I we illustrate these surfaces for an example LP.
The proof requires us to: (1) track the set of edges of the I.P polytope intersected by the new constraint, and once those edges are fixed, (2) track which edge yields the vertex with the highest objective.
5

---

Let M = [m] denote the set of m constraints. For E S M, let Ag E R| and bg E R
denote the restrictions of and b to E. For a E R", 3 E R. and S M with |E| AE E RR*x* denote the matrix obtained by adding row vector to Ag and let A E.a. E R be the matrix Aga with the ith column replaced by (bg,
1, let
Theorem 3.1. Let (c, A, b) be an LP with optimal solution Tip. There are most m" hyperplanes
and m² degree-2 polynomial hypersurfaces partitioning Rn+1 into connected components such that for each component C, either: (1) xip((' O x - B) = Lip. or (2) there is a set of constraints E C M
with E = n 1 such that pip(a" x S 3) = det A //to( for all (a. (3) E ECC
Proof. First, if o x S 3 does not separate Tip, then xip(a" S B) =ip. The set of all such cuts is the halfspace given by {(ax, 3) E R=+1 of Lip S 8). All other cuts separate tip and thus pass through P = fa E R" Ax S b, x 2 0}. and the new LP optimum is achieved at a vertex created by the cut. We consider the new vertices formed by the cut, which lie on edges of P. Each edge e of P can be identified with a subset E C M of size n - 1 such that the edge is the set of all points æ such that a. x = by for all E E and a. x I b; for all i M \ E where a; is the ith row of A. If we drop the inequality constraints defining the edge, the equality constraints define a line in R The intersection of the cut axx S B and this line is the solution to the system of n linear equations in n variables: Agæ = bE, a T x = B. By Cramer's s rule, the unique solution æ = (II,... : (n) to this system is given by x; = (e the edge of the polytope, we stipulate that it satisfies the inequality constraints in M \ E. That is,
de)(A To ensure that the intersection point lies on
n
det det(A'g, S b; agj
det (AF,))
for every E M \ E (if ax 3 satisfy any of these constraints, it must be that det(AE..) ) + O, which guarantees that AzT by, a² x 3 has unique solution). Multiplying through by det(Ar,,) shows that this constraint is halfspace in Ra+1, since (AE,a) and det(A (a,,), are linear in or and B. The collection of all the hyperplanes defining the boundaries of these halfspaces over all edges of P induces a partition of R=* into connected components such that for all (a,, 3) within a given component, the (nonempty) set of edges of P that the hyperplane a x = 3 intersects is invariant.
Now, consider single connected component, denoted by C' for brevity. Let eI....,e, Cg denote the edges intersected by cuts in C, and let Ei...., Eg C M denote the sets of constraints that are binding each of these edges, respectively. For each pair ep, Eq. consider the surface
del (el( del(A
del del(A',,...))
Σ C: det(AFrg.a)
(3)
Clearing the (nonzero) denominators shows this is degree-2 polynomial hypersurface in or, B in
R=+1, This hypersurface is the set of all (ax, 3) for which the LP objective values achieved at the vertices on edges ey and eg are equal. The collection of these surfaces for each p, q partitions C into further connected components. Within each component C", the edge containing the vertex that maximizes the objective is invariant. If this edge corresponds binding constraints E, ptp((" x S
(3) has the closed form "ip(a''s x S [) = det (A'r,,,,,))) det(AE, for all (a,, 3) E C". We now
count the number of surfaces in our decomposition. P has at most (,m))) A m= edges, and for each edge E, Equation (2) defines at most |M > E < m hyperplanes for total of at most m"
hyperplanes. Equation (3) defines a degree-2 polynomial hypersurface for every pair of edges, of
which there are at most 177" S 22
In Appendix B.2 we generalize Theorem 3.1 to understand "[p function of any K constraints.
In this case, we show that the piecewise structure is given by degree-2K multivariate polynomials.
4 Structure and sensitivity of branch-and-cut
We now use Theorem 3.1 to answer a fundamental question about B&C: what is the structure of the B&C tree as function of cuts at the root? Answering this question brings one step closer toward

---

providing sample complexity guarantees for GMI cuts. Said another way, we derive conditions on 01, 02 E R", 31, B2 E R. such that B&C behaves identically on the two IPs
max(c" AAx - b, b, & 31, æ E Øgo) and max(c"x: x Ax S b, a x S B2, x E 1201-
We prove that the set of all cuts can be partitioned into a finite number of regions where by employing cuts from any one region, the B&C tree remains exactly the same. We also prove that the boundaries between regions are defined by low-degree polynomials. Figure 2 is a schematic diagram of our proof, which breaks the analysis of B&C into four main steps. Each step successively refines the partition obtained in the previous step, and uses the properties established in the previous step to single cut added to the root and extend to multiple cuts in Appendix C.2 The full proofs from this section are in Appendix C
analyze the next stage of B&C. We focus
We use the following notation in this section. Given an IP, let [max ||a: be the maximum magnitude coordinate of any LP-feasible solution, rounded up. By Cramer's rule and Hadamard's ||Alllc.... However, can be much smaller. For example, if A
inequality, T S a" n²n where contains row with only positive entries, then T S | Let BC == {az[i] S E, ar 2 fossess,slll which contains the set of all possible branching constraints. Let A, and b denote A and b with
the constraints in C BC added. For E C M J let Ag, E R E xn and bg E R El denote the restrictions of A and b, to E. For a E RR"," , 3 Rax= denote the matrix obtained by adding row vector to A Ag and let A E, E Raxa be the
and E S MU with |E] = n 1, let Ag, E
matrix Ag with the ith column replaced by (bg,a.8)T.
4.1 Step 1: Understanding how the cut affects the LP optimum at any node of the B&C tree
Theorem 3.1 gives a (piecewise) closed form for the LP optimum aip(a x S (3) at the root of the B&C tree as a function of coefficients (ax, 3) E R2+1 determining the cut. The first step is to extend this result to get handle on the LP optimum at any node of any B&C tree. Suppose C BC is set of branching constraints (any node of any B&C tree can be identified with some o C BC). We refine the partition of space obtained in Theorem 3.1 so that within given region of the new partition, x(p(a' T x & B,o) has a closed form for all o. This is illustrated by Figure 2a
Lemma 4.1. For any IP A, there are most (m + 2n 7 hyperplanes and at most (m + 2n) degree-2 polynomial hypersurfaces partitioning 12+ into connected components such that for each component and every a C BC, either: (1) zip( (ap x S B, x (a) and
det(AAr 2[pla" x S (, = (0) or (2) there is a set of constraints E S M U with E = n 1 such
that aap(aTa s 3, = det(A
for all ()) E EC
4.2 Step 2: Conditions for branching decisions be identical
We next refine the decomposition obtained in Lemma 4.1 so that the branching constraints added at each step of B&C are invariant within a region, as in Figure 2b For concreteness, we analyze the product scoring rule (Def. 2.2 used by the leading open-soure solver SCIP [14). The high-level intuition is that we zoom in on a connected component in the partition of Lemma 4. Within this component, we may express "ip (a" S 3, r)) explicitly in terms of a, 1, for all o. This allows us to unravel the branching rule and derive conditions for invariance.
Lemma 4.2. For any IP (c, A. b). there are most 3(m + 2n)""3" hyperplanes, 3(m + 22) 3n d 2 polynomial hypersurfaces, and (m + 2n )o degree-5 polynomial hypersurfaces parti- tioning g=+1 into connected components such that within each component, the branching constraints used at every step of B&C are invariant.
Proof sketch. If we are at a node of B&C represented by a, the new branching constraints after expanding that node are of the form v; < ai x < 3, [i]] and x; 2 "ip(a" x S 3, [i]]] Lemma 4.1 gives closed forms for the hagtt-hand-sidss of these two constraints, allowing us to control the rounding aspect of the constraints. The rest of the proof a careful analysis of the product scoring rule which allows to derive conditions ensuring that the branching variable is invariant.
L
7

---

4.3 Step 3: When do nodes have an integral LP optimum?
We now move to the most critical phase of first reason node might be fathomed is if the LP relaxation of the IP at that node has an integral solution. We derive conditions that ensure that nearby cuts have the same effect on the integrality of the IP at any node in the search tree. Recall Pi = P n Z" is the set of integer points in P.
and-cut:
deciding when fathom node. The
Lemma 4.3. For any IP (c, b), there are at most 3(m + 2n)"" hyperplanes, 3(m + ) degree-2 2 polynomial hypersurfaces, and (m + 2n 18m fm degree-5 polynomial hypersurfaces par- titioning Iu+t1 into connected components such that for each component C' and each o S BC, 1 æip (a x
S 3.0 E =Z"] is invariant for all (a, () C.
Proof sketch. For all a, a E PI, and E [n]] consider the surface zip(a x S []] = mi By Lemma 4.1 this surface is a hyperplane. If xfip(a" S 3) E Z" for some (a, 3) in a connected
component induced by these hyperplanes. "ip(a" x S r) = कj for some क E Pi(a) S Pi which means that "ip(a" x S 3) = 21 E 2n for all (a, 3) in that component.
Lemma is illustrated by Figure 2c Next, suppose for moment that B&C fathoms node if and only if either the LP is infeasible or the LP optimal solution is integral- is, the "bounding" of B&C is suppressed. In this case, the tree built by B&C is invariant within each component of the partition in Lemma 4.3 Equipped with this observation, we now analyze the full behavior of B&C.
4.4 Step 4: Pruning nodes with weak LP bounds
In this final step, we analyze the most important aspect of B&C: pruning nodes when the LP objective value is smaller than the best-known integral solution. Using the tools we have developed so far, expressing the question "is the LP value at a node smaller than the best-known integral solution?" becomes a simple matter of hyperplanes and halfspaces. This final step is illustrated by Figure 2d
Theorem 4.4. Given an IP (c. A), there is set of at most (114 (m + 2n)3n² " polynomial hypersurfaces of degree < 5 partitioning B=+1 into connected components such that the B&C tree built after adding the cul a²
T x S 3 at the root is invariant over all (ox, B) within a given component.
Proof sketch. Let Q1, ... Qi, I, Qi Qig I2, +i denote the nodes of the B&C tree in order of exploration, under the assumption that a node is pruned if and only either the LP at that node is infeasible or the LP optimal solution is integral. Here, a node is identified by the list of branching constraints added to the input IP. Nodes labeled by Q are either infeasible or have fractional LP optimal solutions. Nodes labeled by I have integral LP optimal solutions and candidates for the incumbent integral solution at the point they are encountered. By Lemma 4.3 this ordered list of nodes is invariant over any connected component of our partition.
Given an node index f, let I(E denote the incumbent node with the highest objective value en- countered up until the fth node searched by B&C, and let zT(()) denote its objective value. For each node Qi, let oe denote the branching constraints added to arrive at node Qe. The hyperplane =[p(a" x S 3,02) = =(T(()) (which is hyperplane due Lemma 4.1 induces two regions. In one region, =ip(a xx S 0z) S 2{{(E)) and so the subtree rooted at Qe is pruned. In the other region, 2ip(a" x < 3, 3,0z)= 2(1())). and Qe is branched further. Therefore, within each component induced by all such hyperplanes for all É, the set of nodes that are pruned is invariant. Combined with the surfaces established in Lemma(4.3 these hyperplanes partition R B=+1 into components such that as (a, B) varies within a given component, the B&C tree is invariant.
5 Sample complexity bounds for Gomory mixed integer cuts
In this section, we show how the results from Section 4 can be used to provide sample complexity bounds for GMI cuts (Definition 2.1. parameterized by u E U S R We assume there is an unknown, application-speeife distribution D over IPs. The learner receives a training sei S ~ D of N IPs sampled from this distribution. A sample complexity guarantee bounds the number of samples N sufficient to ensure that for any parameter setting u E U4 the B&C tree size on average over S is close to the expected tree size. More formally, let Iu (c, A, b) be the size of the tree
8

---

B&C builds given the input (c, A, b) after applying the cut defined by u at the root. Given > 0 and 8 (0,1). a sample complexity guarantee bounds the number of samples N sufficient to ensure that with probability 1 6 over the draw S DD, for every parameter setting E U, IN Elc.A.bEES (c,c, A,b) - Elgg (c, A. b)]l S c. To derive our sample complexity guarantee, we use the notion of pseudo-dimension [50]. Let G = {gu u E U.) The pseulo-dimension of g. denoted Pdim(g), is the largest integer N for which there exist N IPs (CI, A1, bi), (eN, AN, bx) and N thresholds ri,...., - E IR such that for every binary vector (01...., .N) E {0, 1 there exists Iu E G such that gu (c, A,, b.) 2 ri if and only if 0; 1. The number of samples sufficient to ensure an error of & and confidence of - 6 is N = O दe (Pdim(() + log })) [50]. Equivalently, for given number of samples N, the error-term is at most / (Pdim(G) + log (og(1/))//N.
So far, a, 3 have been parameters that do not depend on the input instance c, A, b. Suppose now that they do: a, B are functions of c, A, b and parameter vector u (as they are for GMI cuts). Despite the structure established in the previous section, if ax 3 can depend on (c, A, b) in arbitrary ways, one cannot even hope for a finite sample complexity, illustrated by the following impossibility result. The full proofs of all results from this section are Appendix D
Theorem 5.1. There exist functions Ale.A,b : U + _ and Bc,,,b : - + R such that Pdim (1 u E U}) = oc, where U any set with [2]] = [R]
However, in the case of GMI cuts (Def. 2. by u are highly structured. Combining this structure with our analysis of B&C allows us to derive polynomial sample complexity bounds. We assume that u E [-U; U|" for some U > 0.
show that the cutting plane coefficients parameterized
Let a [-U, + IR denote the function taking GMI cut parameters u to the corresponding vector of coefficients determining the resulting cutting plane, and let B [-U, U1 R denote the offset of the resulting cutting plane. So (after multiplying through by 1 - fu),
a = -
[i(1 [:(1
- (1(1--o)
fo)
f fo f fo
fo(1 - fi)
and B(u) - fo(1- (So and Sa are functions of u. but suppress this dependence for readability).
To understand the structure of B&C as a function of GMI cut parameters, we study the preimages of components C C R=+1 under the GMI coefficient maps [-U, U| - RR""" B [-U, U1m - R. (as in Theorem 4.4) is such that B&C (as a function of a. () is invariant over C. then B&C (as function of GMI parameter u.) is invariant over D D= fu
If C 12++1
(a<(z). (()) E C). Our key
structural insight for GMI cuts is that if C' is the intersection of degree-d polynomial hypersurfaces in R=+1, then D is the intersection of degree-2d 22 polynomial hypersurfaces in [-U, UT We provide the high-level intuition for this result below-the formal statements and proofs are in Appendix D
Consider some degree-d polynomial p in variables .i..... Mn++1 that defines C, which can be written as ETgm++1).ITIS \T Iher Vi for some coefficients \r E R. where T E [n + 1] means that T is a multiset of [n + 1]. Evaluating at (ox()),
we get
fo(1 fo). Next, substitute f. u" a; - u² a.J and fo = u²bb (-b--uT) bJ. Restricted to u such that the floor terms round down to some fixed integers, the above expression is polynomial in u of degree < 2d. We run this procedure for every polynomial determining C, for every connected component C in the partition of n established in Theorem 4.4 derive our main structural result for GMI cuts.
Eirisa Ar ILTTTS,(--) fa(1 fo) II.ET,,, fo - fi) IIeern(++1) fo(
[-ū, For any IP (c. A, b), there are at most O(nU² ||Al|| [[b]]]) hyperplanes and 20(2)) + 2m)0 degree- 10 polynomial hypersurfaces partitioning [-U, U\ into connected components such that the B&C tree built after adding the GMI cul defined by u is invariant over all u within a single component.
Lemma 5.2. Consider the family of GMI cuts parameterized by
Bounding Pdim(fgu u E ") is direct application of the main theorem of Balcan et al.
(9 along with standard results bounding the VC dimension of polynomial boundaries (.
Theorem 5.3. The sreudo-dimension of the class of tree-size functions {gu. E [-U, U|"} on the
domain of IPs with ||A||, < and [[b|], < b is O (m log(abl:) + mnz log(m + n1) + mn' logt).
We generalize the analysis of this section to multiple GMI cuts at the root of the B&C tree in Appendix [ We show that if K GMI cuts are sequentially applied at the root, the resulting partition of the parameter space is induced by polynomials of degree O(K2).

---

6 Conclusions
In this paper, we investigated fundamental questions about integer programming: given an integer program, what is the structure of the branch-and-cu tree as a function of a set of additional feasible constraints? Through detailed geometric and combinatorial analysis of how additional constraints affect the LP relaxation's 's optimal solution, we showed that the branch-and-cut tree is piecewise constant and precisely bounded the number of pieces. We showed that the structural insights that we developed could be used to prove sample complexity bounds for learning GMI cuts, one of the most important classes of general- purpose cutting planes integer programming.
This paper opens up a variety of directions for future research. Our sensitivity analyses in Sections 3 and[4ar are fairly general and a promising direction is explore applications to other important topics in integer programming such as column generation and lifting. Another important direction is to further develop algorithmic approaches for choosing GMI (and other) cutting planes. Currently, solvers employ a subset of GMI cuts derived from the optimal simplex tableau due to computational efficiency-it would be interesting to see if the theory developed in this paper could expand the possibilities for efficient cutting plane generation.
Acknowledgments and Disclosure of Funding
This material is based on work supported by the National Science Foundation under grants CCF- 1733556, CCF-1910321, I1S-1901403, and SES- 1919499,,,,, the ARO under award W91 1NF2010081, the Defense Advanced Research Projects Agency under cooperative agreement HR001 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. A machine learning- -base approximation of strong branching. INFORMS Journal on Computing, 29(1):185-195, 2017.
[3] Martin Anthony and Peter Bartlett. Neural Network Learning: Cambridge University Press, 2009.
Theoretical Foundations.
[4] Egon Balas, Sebastian Ceria, Gérard Comuéjols, and N Natraj. Gomory cuts revisited. Opera- tions Research Letters, 19(1):1-9, 1996.
[5] Maria-Florina Balcan. Data-driven algorithm design. In Tim Roughgarden, editor, Beyond Worst Case Analysis of Algorithms. Cambridge University Press, 2020.
[6] Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitereik. Learning branch. In International Conference on Machine Learning (ICMI.), 2018.
[7] Maria-Florina Balcan, Travis Dick, and Colin White. Data-driven clustering via parameterized Lloyd's families. In Annual Conference on Neural Information Processing Systems (NeurIPS), 2018.
[8] Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Refined bounds for algorithm configuration: The knife-edge of dual class approximability. In International Conference Machine Learning (ICML), 2020.
[9] Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data is sufficient learn high-performing algorithms? Generalization guarantees for data-driven algorithm design. In Annual Symposium on Theory of Computing (STOC), 2021.
[10] Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. Sample complexity of tree search configuration: Cutting planes and beyond. Annual Conference on Neural Information Processing Systems (NeurIPS), 2021.
10

---

[11] Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. Improved sample complexity bounds for Franch-and-ee In International Conference on Principles and Practice of Constraint Programming (CP), 2022.
[12] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: methodological tour d' horizio.. European Journal of Operational Research, 2020.
[13] Dimitris Bertsimas and Jack Dunn. Optimal classification trees. Machine Learning, 106(7): 1082-1082, 2017.
[14] Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doormmalen, Leon Fifler, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, Leona Gottwald, Christoph Graczyk, Katrin Halbig, Alexander Hoen, Christopher Hojny, Rolf van der Hulst, Thorsten Koch, Marco Lübbecke, Stephen J. Maher, Frederic Matter, Erik Mühmer, Benjamin Müller, Marc E. Pfetsch, Daniel Rehfeldt, Steffan Schlein, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Boro Sofranac, Mark Turner, Stefan Vigerske, Fabian Wegscheider, Philipp Wellner, Dieter Weninger, and Jakob Witzig. The SCIP Optimization Suite 8.0. Technical report, Optimization Online, December 2021. URL http://wwww.oiiiiziiii. onl ine org 2tgg/DBBHHHLL2221/2////72 html
[15] Robert Bixby, Mary Fenelon, Zonghao Gu, Ed Rothberg, and Roland Wunderling. MIP: Theory and practice clossng the gap. In IFIP Conference System Modeling and Optimization, pages 19-49. 49. Springer, 1999.
[16] Avrim Blum, Chen Dan, and Saeed Seddighin. Learning complexity of simulated annealing. In International conference on artificial intelligence and statistics, pages 1540-1548, PMLR, 2021.
[17] Rudy Bunel, Ilker Turkaslan, Philip H.S. Torr, Pushmeet Kohli, and M. Pawan Kumar. A unified view of piecewise linear neural network verification. In Annual Conference on Neural Information Processing Systems (NeurIPS), 2018.
[18] Vašck Chvátal. Edmonds polytopes and hierarchy of combinatorial problems. Discrete mathematics, 4(4):305-337, 1973.
[19] Michele Conforti, Gérard Cornuéjols, Giacomo Zambelli, et al. Integer programming, volume 271. Springer, 2014.
[20] William Cook, Albertus MH Gerards, Alexander Schrijver, and Éva Tardos. Sensitivity theorems in integer linear programming. Mathematical Programming, 34(3):251-266 1986.
[21] Gérard Coruúéols. Revival of the Gomory cuts in the 1990's. Annals of Operations Research, 149(1):63-66, 2007.
[22] Gérard Cornuéjols. Valid inequalities for mixed integer linear programs. Mathematical Pro- gramming, 1 (1((1):3-44 2008.
[23] Gérard Cornuéjols and Yanjun Li. Elementary closures for integer programs. Operations Research Letters, 28(1):1-8, 2001.
[24] 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.
[25] Vikas Garg and Adam Kalai. Supervising unsupervised learning. Annual Conference on Neural Information Processing Systems (NeurIPS), 2018.
(26) Ralph Gomory. An algorithm for the mixed integer problem. resreport RM-2597, The Rand Corporation, 1960.
[27] Ralph E. Gomory. Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society, 64(5):275 278, 1958.

---

[28] Rishi Gupta and Tim Roughgarden. A PAC approach to iopiication-spccifi algorithm selection. SIAM Journal on Computing, 46(3):992-1017, 2017.
[29]
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.
[30] Zeren Huang, Kerong Wang, Furui Liu, Hui-Ling Zhen, Weinan Zhang, Mingxuan Yuan, Jianye Hao, Yong Yu, and Jun Wang. Learning select cuts for efficient mixed-integer programming. Pattern Recognition, 123: 108353, 2022.
[31] Frank Hutter, Holger H Hoos, Kevin Leyton- -roow,, and Thomas Stützle. ParamILS: An automatic algorithm configuration framework. Journal of Artificial Intelligence Research, 36 (1):267-306, 2009. ISSN 1076-9757.
[32] Robert G Jeroslow. Trivial integer programs unsolvable by branch-and-bound. Mathematical Programming, 6(1):105-109 109, 1974.
[33] Serdar Kadioglu, Yuri Malitsky, Meinolf Sellmann, and Kevin Tiemny. instanceecccc-eeiiffeee algorithm configuration. In European Conference on Artificial Intelligence (ECAI), 2010.
[34] Jörg Hendrik Kappes, Markus Speth, Gerhard Reinelt, and Christoph Schnörr. Towards efficient and exact map-inference for large scale discrete computer vision problems via combinatorial optimization. In Conference Computer Vision and Pattern Recognition (CVPR), pages 7752-1758, IEEE, 2013.
[35] Elias Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. AAAI Conference on Artificial Intelligence, 2016.
[36] Elias Khalil, Bistra Dilkina, George Nemhauser, Shabbir Ahmed, and Yufen Shao. Learning to run heuristies in tree search. In International Joint Conference on Artificial Intelligence (IJCAI), 2017.
[37] Daniel Khashabi, Tushar Khot, Ashish Sabharwal, Peter Clark, Oren Etzioni, and Dan Roth. Question answering via integer programming over semi-structured knowledge. In International Joint Conference Artificial Intelligence (IJCAI), 2016.
[38] Robert Kleinberg, Kevin Leyton- -Brow,, and Brendan Lucier. Efficiency through procrastination: Approximately optimal algorithm configuration with runtime guarantees. In International Joint Conference on Artificial Intelligence (IJCAI), 2017.
[39] Robert Kleinberg, Kevin Leyton-Brove Broww, Brendan Lucier, and Devon Graham. Procrastinating with confidence: Near-optimal, anytime, adaptive algorithm configuration. Annual Conference on Neural Information Processing Systems (NeurIPS), 2019.
[40] Michail G Lagoudakis and Michael L Littman. Learning to select branching rules in the DPLL procedure for satisfiability. Electronic Notes in Discrete Mathematics, 9:344-359, 2001.
[41] Ailsa H Land and Alison G Doig. An automatic method of solving discrete programming problems. Econometrica, pages 497-520, 1960.
[42] Kevin Leyton-Brown Eugene Nudelman, and Yoav Shoham. Empirical hardness models: Methodology and case study on combinatorial auctions. Journal of the ACM, 56(4):1-52, 2009. ISSN 0004-5411.
[43] Wu Li. The sharp lipschitz constants for feasible and optimal solutions of a perturbed linear program. Linear algebra and its applications, 187:15-40, 1993.
[44] Jia Hui Liang, Vijay Ganesh, Pascal Poupart, and Krzysztof Czamecki. Learning rate based branching heuristic for sat solvers. In International Conference on Theory and Applications of Satisfiability Testing, pages 123-140. Springer, 2016.
[45] 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.
12

---

[46] Olvi L Mangasarian and T-H Shiau. Lipschitz continuity of solutions of linear inequalities, programs and complementarity problems. SIAM Journal on Control and Optimization, 25(3): 583-595, 1987.
[47] John Milnor. On the Betti numbers of real varieties. Proceedings of the American Mathematical Society, 15(2):275-280, 1964.
[48] Atsushi Miyauchi, Tomohiro Sonobe, and Noriyoshi Sukegawa. Exact clustering via integer programming and maximum satisfiability. In AAAI Conference on Artificial Intelligence, 2018.
[49] George Nemhauser and Laurence Wolsey. Integer and Combinatorial Optimization. John Wiley Sons, 1999.
[50] David Pollard. Convergence of Stochastic Processes. Springer, 1984.
[51] Ashish Sabharwal, Horst Samulowitz, and Chandra Reddy. Guiding combinatorial optimization with UCT. International Conference on and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Springer, 2012.
[52] Tuomas Sandholm. Very-large generalized combinatorial multi-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.
[53] Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Reinforcement learning for integer program- ming: Learning cut. International Conference Machine Learning (ICML), 2020.
[54] René Thom. Sur I'homologie des varietes algebriques reelles. Differrntial and combinatorial topology, pages 255-265. Princeton University Press, 1965.
[55] Mark Turner, Thorsten Koch, Felipe Serrano, and Michael Winkler. Adaptive cut selection in mixed-integer linear programming. arXiv preprint arXiv:2202. 2022.
[56] Hugh E Warren. Lower bounds for approximation by nonlinear manifolds. Transactions of the American Mathematical Society, 133(1):167-178, 1968.
[57] 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.
[58] Wei Xia and Roland Yap. Learning robust search strategies using a bandit-based approach. In AAAI Conference on Artificial Intelligence, 2018.
[59] Lin Xu, Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown. Satzilla: portfolio-based algorithm selection for SAT. Journal of Artificial Intelligence Research, 32(1):565-606, 2008.
[60] 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.
[61] Jiaming Zeng, Berk Ustun, and Cynthia Rudin. Interpretable classification models for recidivism prediction. Journal of the Royal Statistical Society: Series A (Statistics in Society), 180(3): 689-722, 2017.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 6
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
13

---

(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you'le 'e using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "l4gWGQCkVX", "reviewer": "Reviewer_zTZn", "summary": "The paper develops a theoretical framework to investigate the geometric structure incurred by Gomory Mixed Integer (GMI) cuts and its implications for learning. More precisely, the authors first show the closed form of the optimal LP solutions obtained when adding a GMI cut, also demonstrating that the cut parameters lie in a countable number of connected degree-2 polynomial hypersurfaces.  Based on this result, they establish (surprising) conditions for which two or more sets of distinct GMI cuts would result in the same branch-and-cut tree. Finally, given a particular instance distribution, they leverage the previous structural results to derive the sample complexity associated with GMI, i.e., that the expected tree size over a training set of instances is sufficiently close to the expected average. ", "questions": "1. Are all the cuts in a partition required? That is, can we obtain the same branch-and-cut trees if we omit some of them?\n\n2. What would be the challenges in adding cuts throughout the search procedure, and not only at the root node? Would the sample complexity still be a valid bound?", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- Very strong theoretical results, advance our understanding and provide further geometric insights into GMI cuts \n\nWeaknesses\n- Perhaps some of the results could be formalized more carefully\n- There is little insight into how the theory translates into actual learning. It would be interesting to incorporate a discussion of the practical elements of the approach and the sample complexity\n\nMajor Comments\n\nOverall, I believe the paper provides a very strong theoretical contribution to the extensive body of work associated with GMI cuts, which are key to the solution approach in modern mathematical programming solvers. In particular, I found the result stating that GMI cuts could be partitioned into sets with similar branch-and-cut trees quite surprising; in hindsight, that makes sense given the \"discreteness\" associated with the dual description of rational polyhedra. The paper also reads very well, with an interesting way of writing more on the informal side. However, that also brings a few concerns.\n\n(i) [Rigour.] While I believe the results are sound, I felt that the proofs (or general statements) were written in a sometimes informal way and lacked a bit of discussion or explicit statements of boundary conditions. My apologies if I sound \"picky\" here, but for some illustrative examples...\n\n(a) the authors state multiple times that, when adding a cut, the optimum would \"jump\" or \"change\" from one vertex to another in the LP; however, adding a cut changes the polytope itself, so it is not clear what \"LP\" this refers to. \n\n(b) I am sure results still hold, but what if the LP does not have any extreme points  (e.g., empty or unbounded); I felt it is missing some assumptions (e.g., full rank of A?) to ensure this would not happen (unless I missed something obvious?). Theorem 3.1 is easy to understand (essentially a nice application of Cramer's rule), but the description was a bit hand-wavey; would it be more formal to state that the proof essentially enumerates the basis of the LP considering that the cut is part of the basis or not, as opposed to just using the geometric intuition in the argument? \n\n(c) In the proof of Lemma 4.1: \"we assume that the B&C tree takes some special form denoting an invalid cut\" - my apologies as this was a bit unclear to me, it would be great if the authors could clarify...\n\n(ii) [Learning.] Until I reached Section 5, I was under the impression that I was reading a (very high-quality) paper in the Mathematical Programming journal. The learning element (here implied by the sample complexity theory) seems secondary because there is little intuition about its practical aspects. There are some hints in the conclusion that the theory opens doors for new cut generation mechanisms, which I agree with, but how does that actually impact learning the parameters? It seems that the motivation of the Intro and the actual results are somewhat disjoint. I would suggest authors add more comments on what Theorem 5.3 means when learning parameters (e.g., when would \"too many samples\" be needed), considering the broader audience of the conference.\n\n\nMinor notes\n- Text sometimes alternates between \"piecewise\" and \"piece-wise\"", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RW1hC4wA9mw", "reviewer": "Reviewer_H9iB", "summary": "The paper proves a number of results regarding the sample complexity\nof gomory mixed integer cuts.\n", "questions": "None.", "limitations": "It would help if the paper included some experiments.", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nA number of interesting results are proved, some of which do not seem\nexpected.\n\nWeaknesses:\nSeveral key aspects of the paper are left for the appendix, and in\ntotal the submission in 30 pages. Also, the lack of experiments in the\nmain text is problematic.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PICheQ5u-zl", "reviewer": "Reviewer_JLsy", "summary": "The authors analyze the sample complexity bounds required for learning to select from the infinite family of GMI cutting planes. The authors demonstrate that there are finitely many distinct outcomes of the branch and cut procedure by determining how the cuts impact the result at any branch and bound node, determine when the branch and cut algorithm results in the same result due to branching, node fathoming, and integral optima at intermediate nodes. After bounding this uniqueness, the authors determine the sample complexity for learning to select GMI cuts. Overall, this work builds on previous work of sample complexity in branch and bound which is mainly concerned with bounding the number of distinct predictive algorithms by analyzing the impact of different decisions in the branch and bound solver. Generally, these approaches rely on the same principle of bounding the number of distinct outcomes that the algorithm can have and then drawing conclusions of sample complexity on top of this bound.", "questions": "How easy is it to generalize this method to other types of cuts, or even other types of cut-based branching such as multi-variable branching?\n\nIs it possible to generalize these results to settings like bilevel optimization or solving Stackelberg games?\n", "limitations": "The authors adequately address the limitations of their approach and any ethical considerations", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main strength is that this work theoretically analyzes the requirements for any algorithm to determine a high-quality gutting plane procedure. The approach itself is interesting and tackles a new component of branch and bound. The approach additionally paves the way for future work on other aspects of optimization solvers that rely on selecting from an infinite family of objects as previous work was concerned with decisions such as variable selection where only a finite number of decisions are possible. Additionally, the paper is very well and clearly written and would be a good contribution to the area of theoretically analyzing learning algorithms meant to improve optimization procedures. \n\nThe main area for improvement would be to provide a general framework for other cutting plane algorithms such as where there are many latent constraints that are iteratively generated. Such situations arise in settings like bilevel optimization or game theory, where the solving process iteratively generates solutions to the internal level or adversary strategy respectively to compute the top level solution based on the performance with respect to the current known second level solution set. These second level solutions generally become cuts in the overall problem. Another setting which would be interesting for analysis is in determining a methodology for helping understand unknown categories of cuts that have yet to be devised. In these settings, a novel cut family is proposed which helps the reformulated problem solve much faster. It would be helpful to know how much benefit is possible from devising the ideal family of cuts for a given problem.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6nxYpdIK22", "reviewer": "Reviewer_3NW3", "summary": "This paper applies learning theory to provide sample complexity bounds for GMI cuts.\n\nThe paper is very dense, and the literature is updated and exhaustive.\n\nThe main results of this paper are the three lemmas and the theorem presented in Section 4, which permit to the author to express their sample complexity bounds for GMI cuts given in Section 5. The authors convey the main idea in the introduction, given the main background on B&C in Section 2, and then the results are very interesting, and the proofs are very technical. \n\nFor a reader who is not an expert of this topic, it is difficult to follow the paper without consulting the material in the appendix (which is 15 pages long).\n", "questions": "- How do you think we could exploit your results to implement more efficient B&C algorithms based on GMI? Could you expand the final comments on your conclusions?\n\n", "limitations": "We see no limitations in this paper.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "STRENGTHS: the topic of this paper is very technical and hard to follow without a strong theoretical background, but we think this paper is laying the foundation of learnability principles for branch-and-cut algorithms in general, and for Gomory Mixed Integer cuts, specifically.\n\nWEAKNESS: We think the paper suffers the 9-page limit imposed by the conference venue. Given that the appendix, which is very useful for understanding the contributions, is another 15 pages long, the paper should be sent directly to a journal (e.g., the new \"Transactions on Machine Learning Research\", https://www.jmlr.org/tmlr/).", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept