Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts

Integer programming (IP) solvers are the most widely-used tools for solving discrete optimization problems. They have numerous applications in machine learning, operations research, and many other fields, including MAP inference [22], combinatorial auctions [33], natural language processing [23], neural network verification [11], interpretable classification [37], training of optimal decision trees [9], and optimal clustering [30], among many others.

Under the hood, IP solvers use the tree-search algorithm branch-and-bound [26] augmented with cutting planes, known as branch-and-cut (B&C). A cutting plane is a linear constraint that is added to the LP relaxation at any node of the search tree. With a carefully selected cutting plane, the LP guidance can more efficiently lead B&C to the globally optimal integral solution. Cutting planes, specifically the family of Gomory mixed integer cuts which we study in this paper, are responsible for breakthrough speedups of modern IP solvers [14].

Successfully employing cutting planes can be 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 cut selection [34, 8, 7, 19]. In this paper, we analyze a machine learning setting where there is an unknown distribution over IPs—for example, a distribution over a 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). 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 over the training set, it will also lead to strong expected performance on future IPs from the same distribution. These guarantees apply no matter what procedure is used to optimize the cut parameters over the training set—optimal or suboptimal, automated or manual. We prove these guarantees by analyzing how the B&C tree varies as a function of the cut parameters on any IP. By bounding the “intrinsic complexity” of this function, we are able to provide our sample complexity bounds.

Figures 1 and 2 illustrate the need for distribution-dependent policies for choosing cutting planes. We plot the average number of nodes expanded by B&C as a function of a parameter $\mu$ that controls its cut-selection policy, as we detail in Appendix A. In each figure, we draw a training set of facility location integer programs from two different distributions. In Figure 1, we define the distribution by starting with a uniformly random facility location instance and perturbing its costs. In Figure 2, the costs are more structured: the facilities are located along a line and the clients have uniformly random locations. In Figure 1, a smaller value of $\mu$ leads to small search trees, but in Figure 2, a larger value of $\mu$ is preferable. These figures illustrate that tuning cut parameters according to the instance distribution at hand can have a large impact on the performance of B&C, and that for one instance distribution, the best parameters for cut evaluation can be very different—in fact opposite—than the optimal parameters for another instance distribution.

The key challenge we face in developing a theory for cutting planes is that a cut added at the root remains in the LP relaxations stored in each node all the way to the leaves, thereby impacting the LP guidance that B&C uses to search throughout the whole tree. Tiny changes to any cut can thus completely change the entire course of B&C. At its core, our analysis therefore involves understanding an intricate interplay between the continuous and discrete components of our problem. The first, continuous component requires us to characterize how the solution the LP relaxation changes as a function of its constraints. This optimal solution will move continuously through space until it jumps from one vertex of the LP tableau to another. We then use this characterization to analyze how the B&C tree—a discrete, combinatorial object—varies as a function of its LP guidance.

Our main result in this section characterizes how an LP’s optimal solution is affected by the addition of one or more new constraints. In particular, fixing an LP with $m$ constraints and $n$ variables, if $\bm{x}^{*}_{\mathsf{LP}}(\bm{\alpha}^{T}\bm{x}\leq\beta)\in\mathbb{R}^{n}$ denotes the new LP optimum when the constraint $\bm{\alpha}^{T}\bm{x}\leq\beta$ is added, we pin down a precise characterization of $\bm{x}^{*}_{\mathsf{LP}}(\bm{\alpha}^{T}\bm{x}\leq\beta)$ as a function of $\bm{\alpha}$ and $\beta$. We show that $\bm{x}^{*}_{\mathsf{LP}}(\bm{\alpha}^{T}\bm{x}\leq\beta)$ has a piece-wise closed form: there are surfaces partitioning $\mathbb{R}^{n+1}$ such that within each connected component induced by these surfaces, $\bm{x}^{*}_{\mathsf{LP}}(\bm{\alpha}^{T}\bm{x}\leq\beta)$ has a closed form. While the geometric intuition used to establish this piece-wise structure relies on 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 degree-$2$ polynomials in $\bm{\alpha},\beta$. In Appendix B.1 we illustrate these surfaces for an example two-variable LP.

There are two main steps of our proof: (1) tracking the set of edges of the LP polytope intersected by the new constraint, and once that set of edges is fixed, (2) tracking which edge yields the vertex with the highest objective value.

Let $M=[m]$ denote the set of $m$ constraints. For $E\subseteq M$, let $A_{E}\in\mathbb{R}^{|E|\times n}$ and $\bm{b}_{E}\in\mathbb{R}^{|E|}$ denote the restrictions of $A$ and $\bm{b}$ to $E$. For $\bm{\alpha}\in\mathbb{R}^{n}$, $\beta\in\mathbb{R}$, and $E\subseteq M$ with $|E|=n-1$, let $A_{E,\bm{\alpha}}\in\mathbb{R}^{n\times n}$ denote the matrix obtained by adding row vector $\bm{\alpha}$ to $A_{E}$ and let $A^{i}_{E,\bm{\alpha},\beta}\in\mathbb{R}^{n\times n}$ be the matrix $A_{E,\bm{\alpha}}$ with the $i$th column replaced by $(\bm{b}_{E},\beta)^{T}$.

In Appendix B.2, we generalize Theorem 3.1 to understand $\bm{x}^{*}_{\mathsf{LP}}$ as a function of any $K$ constraints. In this case, we show that the piecewise structure is given by degree-$2K$ multivariate polynomials.

We now use Theorem 3.1 to answer a fundamental question about B&C: how does the B&C tree change when cuts are added at the root? Said another way, what is the structure of the B&C tree as a function of the set of cuts? We prove that the set of all possible 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. Moreover, we prove that the boundaries between regions are defined by constant-degree polynomials. As in the previous section, we focus on a single cut added to the root of the B&C tree. We provide an extension to multiple cuts in Appendix C.2.

We outline the main steps of our analysis:

1. 1.

   In Lemma 4.2 we use Theorem 3.1 to understand how the LP optimum at any node in the B&C tree behaves as a function of cuts added at the root.

2. 2.

   In Lemma 4.3, we analyze how the branching decisions of B&C are impacted by variations in the cuts.

3. 3.

   In Lemma 4.4, we analyze how cuts affect which nodes are fathomed due to the integrality of the LP relaxation.

4. 4.

   In Theorem 4.5, we analyze how the LP estimates based on cuts can lead to pruning nodes of the B&C tree, which gives us a complete description of when two cutting planes lead to the same B&C tree.

The full proofs from this section are in Appendix C.

Given an IP, let $\tau=\lceil\max_{\bm{x}\in\pazocal{P}}\left\lVert\bm{x}\right\rVert_{\infty}\rceil$ be the maximum magnitude coordinate of any LP-feasible solution, rounded up. The set of all possible branching constraints is contained in $\pazocal{B}\pazocal{C}:=\{\bm{x}[i]\leq\ell,\bm{x}[i]\geq\ell\}_{0\leq\ell\leq\tau,i\in[n]}$ which is a set of size $2n(\tau+1)$. Naïvely, there are at most $2^{2n(\tau+1)}$ subsets of branching constraints, but the following observation allows us to greatly reduce the number of sets we consider.

By Cramer’s rule, $\tau\leq|\det(\widetilde{A})|$, where $\widetilde{A}$ is any square submatrix of $A$. This is at most $a^{n}n^{n/2}$ by Hadamard’s inequality, where $a$ is the maximum absolute value of any entry of $A$. However, $\tau$ can be much smaller in various cases. For example, if $A$ contains even one row with only positive entries, then $\tau\leq\left\lVert\bm{b}\right\rVert_{\infty}$.

We will use the following notation in the remainder of this section. Let $A_{\sigma}$ and $\bm{b}_{\sigma}$ denote the augmented constraint matrix and vector when the constraints in $\sigma\subseteq\pazocal{B}\pazocal{C}$ are added. For $E\subseteq M\cup\sigma$, let $A_{E,\sigma}\in\mathbb{R}^{|E|\times n}$ and $\bm{b}_{E}\in\mathbb{R}^{|E|}$ denote the restrictions of $A_{\sigma}$ and $\bm{b}_{\sigma}$ to $E$. For $\bm{\alpha}\in\mathbb{R}^{n},\beta\in\mathbb{R}$ and $E\subseteq M\cup\sigma$ with $|E|=n-1$, let $A_{E,\bm{\alpha},\sigma}\in\mathbb{R}^{n\times n}$ denote the matrix obtained by adding row vector $\bm{\alpha}$ to $A_{E,\sigma}$ and let $A^{i}_{E,\bm{\alpha},\beta,\sigma}\in\mathbb{R}^{n\times n}$ be the matrix $A_{E,\bm{\alpha},\sigma}$ with the $i$th column replaced by $(\bm{b}_{E,\sigma},\beta)^{T}$.

Next, we refine the decomposition obtained in Lemma 4.2 so that the branching constraints added at each step of B&C are invariant within a region. Our results apply to the product scoring rule (Def. 2.2), which is used, for example, by the leading open-source solver SCIP [10].

We now move to the most critical phase of branch-and-cut: deciding when to fathom a node. One reason a 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 original IP at any node in the search tree. Recall that $\pazocal{P}_{\mathsf{I}}=\pazocal{P}\cap\mathbb{Z}^{n}$ is the set of integer points in $\pazocal{P}$. Let $\pazocal{V}\subseteq\mathbb{R}^{n+1}$ denote the set of all valid cuts for the input IP $(\bm{c},A,\bm{b})$. The set $\pazocal{V}$ is a polyhedron since it can be expressed as

and $\pazocal{P}_{\mathsf{I}}$ is finite as $\pazocal{P}$ is bounded. For cuts outside $\pazocal{V}$, we assume the B&C tree takes some special form denoting an invalid cut. Our goal now is to decompose $\pazocal{V}$ into connected components such that $\mathbf{1}\left[\bm{x}_{\mathsf{LP}}^{*}(\bm{\alpha}^{T}\bm{x}\leq\beta,\sigma)\in\mathbb{Z}^{n}\right]$ is invariant for all $(\bm{\alpha},\beta)$ in each component.

Suppose for a moment that a node is fathomed by B&C if and only if either the LP at that node is infeasible, or the LP optimal solution is integral—that is, the “bounding” of B&C is suppressed. In this case, the partition of $\mathbb{R}^{n+1}$ obtained in Lemma 4.4 guarantees that the tree built by branch-and-cut is invariant within each connected component. Indeed, since the branching constraints at every node are invariant, and for every $\sigma$ the integrality of $\bm{x}^{*}_{\mathsf{LP}}(\bm{\alpha}^{T}\bm{x}\leq\beta,\sigma)$ is invariant, the (bounding-suppressed) B&C tree (and the order in which it is built) is invariant within each connected component in our decomposition. Equipped with this observation, we now analyze the full behavior of B&C.

In this section, we show how the results from the previous section can be used to provide sample complexity bounds for configuring B&C. Our results will apply to families of cuts parameterized by vectors $\bm{u}$ from a set $\pazocal{U}$, such as the family of GMI cuts from Definition 2.1. We assume there is an unknown, application-specific distribution $\pazocal{D}$ over IPs. The learner receives a training set $\pazocal{S}\sim\pazocal{D}^{N}$ 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 $\bm{u}\in\pazocal{U}$, the B&C tree size on average over the training set $\pazocal{S}$ is close to the expected B&C tree size. More formally, let $g_{\bm{u}}(\bm{c},A,\bm{b})$ be the size of the tree B&C builds given the input $(\bm{c},A,\bm{b})$ after applying the cut defined by $\bm{u}$ at the root. Given $\epsilon>0$ and $\delta\in(0,1)$, a sample complexity guarantee bounds the number of samples $N$ sufficient to ensure that with probability $1-\delta$ over the draw $\pazocal{S}\sim\pazocal{D}^{N}$, for every parameter setting $\bm{u}\in\pazocal{U}$,

To derive our sample complexity guarantee, we use the notion of pseudo-dimension [32]. Let $\pazocal{G}=\{g_{\bm{u}}:\bm{u}\in\pazocal{U}\}$. The pseudo-dimension of $\pazocal{G}$, denoted $\textnormal{Pdim}(\pazocal{G})$, is the largest integer $N$ for which there exist $N$ IPs $(\bm{c}_{1},A_{1},\bm{b}_{1}),\dots,(\bm{c}_{N},A_{N},\bm{b}_{N})$ and $N$ thresholds $r_{1},\dots,r_{N}\in\mathbb{R}$ such that for every binary vector $(\sigma_{1},\dots,\sigma_{N})\in\{0,1\}^{N}$, there exists $g_{\bm{u}}\in\pazocal{G}$ such that $g_{\bm{u}}(\bm{c}_{i},A_{i},\bm{b}_{i})\geq r_{i}$ if and only if $\sigma_{i}=1$. The number of samples sufficient to ensure that Equation (8) holds is $N=O(\frac{\kappa^{2}}{\epsilon^{2}}(\textnormal{Pdim}(\pazocal{G})+\log\frac{1}{\delta}))$ [32]. Equivalently, for a given number of samples $N$, the left-hand-side of Equation (8) can be bounded by $\kappa\sqrt{\frac{1}{N}(\textnormal{Pdim}(\pazocal{G})+\log\frac{1}{\delta})}$.

So far, $\bm{\alpha},\beta$ are parameters that do not depend on the input instance $\bm{c},A,\bm{b}$. Suppose now that they do: $\bm{\alpha},\beta$ are functions of $\bm{c},A,\bm{b}$ and a parameter vector $\bm{u}$ (as they are for GMI cuts). Despite the structure established in the previous section, if $\bm{\alpha},\beta$ can depend on $(\bm{c},A,\bm{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 in Appendix D.

However, in the case of GMI cuts, we show that the cutting plane coefficients parameterized by $\bm{u}$ are highly structured. Combining this structure with our analysis of B&C allows us to derive polynomial sample complexity bounds.

Let $\bm{\alpha}:[-U,U]^{m}\to\mathbb{R}^{n}$ denote the function taking GMI cut parameters $\bm{u}$ to the corresponding vector of coefficients determining the resulting cutting plane, and let $\beta:[-U,U]^{m}\to\mathbb{R}$ denote the offset of the resulting cutting plane. So (after multiplying through by $1-f_{0}$),

and $\beta(\bm{u})=f_{0}(1-f_{0})$ (of course $f_{0}$ and each $f_{i}$ are functions of $\bm{u}$, but we suppress this dependence for readability).

The next lemma allows us to transfer the polynomial partition of $\mathbb{R}^{n+1}$ from Theorem 4.5 to a polynomial partition of $[-U,U]^{m}$, incurring only a factor $2$ increase in degree.

Applying Lemma 5.3 to every polynomial hypersurface in the partition of $\mathbb{R}^{n+1}$ established in Theorem 4.5 yields our main structural result for GMI cuts.

Bounding the pseudo-dimension of the class of tree-size functions $\{g_{\bm{u}}:\bm{u}\in[-U,U]^{m}\}$ is a direct application of the main theorem of Balcan et al. [6] along with standard results bounding the VC dimension of polynomial boundaries [2].

We generalize the analysis of this section to multiple GMI cuts at the root of the B&C tree in Appendix D. The analysis there is more involved since GMI cuts can be applied in sequence, re-solving the LP relaxation after each cut. In particular, GMI cuts applied in sequence have one more parameter than the next, so the hyperplane defined by each GMI cut depends (polynomially) on the parameters defining all GMI cuts before it. 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(K^{2})$.

In this paper, we investigated fundamental questions about linear and integer programs: given an integer program, how many possible branch-and-cut trees are there if one or more additional feasible constraints can be added? Even more specifically, what is the structure of the branch-and-cut tree as a function of a set of additional constraints? Through a detailed geometric and combinatorial analysis of how additional constraints affect the LP relaxation’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 understandings that we developed could be used to prove sample complexity bounds for configuring branch-and-cut.