Learning Cut Generating Functions for Integer Programming

We greatly appreciate your thorough review and the thoughtful feedback. Regarding the experimental evidence, we acknowledge that our paper focuses primarily on theoretical aspects, and thus, the experimental section is somewhat preliminary. First, we agree that it was poor scholarship on our part to call our distribution the Chvátal distribution. Our distribution is indeed the same as what was done in the Balcan paper. We will reword to something like "what Balcan et al call the Chvátal distribution".

However, we believe that even these basic experiments lend support to our claim that some of the CGFs we consider can result in significantly smaller tree sizes compared to some traditional cutting planes. Our reasoning is as follows:

1. Even though the 1D knapsack problem is very simple, this does not detract from the theoretical interest of the result. Specifically, when using only branch-and-bound for certain specific distributions (such as the "Chvátal distribution" considered here), there are indeed some CGFs that perform significantly better than GMI cuts.

2. Even if we disregard the 1D knapsack results, we believe the other experiments on multidimensional knapsacks and packing problems also give some support to our claim:

   • Regardless of the problem type or the number of rows used to generate cutting planes, we selected a parameter from only 121 random candidate CGF parameters, and for one-row cuts, we only considered the simple case of $p = q = 2$, resulting in only two parameters. Despite this, some CGFs performed better, which demonstrates the potential of CGFs.
   • In the last column, we provided the "best 1-row cut" for the one-dimensional CGF, obtained by enumerating and selecting the best 1D CGF for each instance. We believe this result shows significant improvement over GMI cuts, even for the packing problem settings. While this method is not really "learning," we believe it does demonstrate the potential of CGFs. Also, for this method, in Section 5 we proved the learnability and rigorous sample complexity for solving the problem of "selecting good CGFs for each instance" using neural networks, which may provide some insights to practitioners to develop some neural network based instance-specific selection methods.

3. We compare with GMI cuts because this is considered a "gold standard" in evaluating cutting planes in IP computational literature. While there are indeed several other cutting plane families that are used in modern solvers, the first test for any new family of cutting planes (from a practical perspective) is usually to see how well they do in comparison to GMIs. They are arguably the most important and popular general purpose cutting planes, adopted by commercial solvers for almost thirty years now (Conforti et al., 2014). Additionally, GMI cutting planes are generated by an extreme CGF (Section 2.1 has the corresponding CGF definition). Given that the main focus of the paper is on the theory developed, we wanted to keep the message of our experimental section crisp and streamlined. Comparisons with GMI seemed like a good way to achieve this.

We do agree that perhaps our choice of wording in the experimental section (and in references to it) is overenthusiastic. We will reword and tone down some of the language. The reason behind our excitement is that we have not seen such promising results with CGFs in the computational IP literature. We concede that some of instances are not the most challenging ones for modern solvers. Nevertheless, we do not know of any published (or folklore) cases of instances where CGFs have previously been demonstrated to have such stark improvements over GMI cuts. And this is even more true for the Gomory-Johnson family of CGFs. While there are some computational results showing some promise with CGFs coming from lattice-free sets and their liftings, to the best of our knowledge, the Gomory-Johnson families have not been shown to do better than GMIs (beyond some artifical instances) in any previous study. Observing an improvement with these CGFs that was quite a contrast from previous computational experience was the basis for our enthusiastic wording. One reason could indeed be the choice of instances. Nevertheless, we think another reason is that previous work focused more on the gap closed at the root, as opposed to the overall tree size. We hope that our preliminary results convinces the community to revisit these CGFs, especially with the view to investigate their effect on the overall tree sizes (both theoretically and practically). We will also expand our computational investigation to look at other families of instances to see if the improvement in tree size is as dramatic as we observed on these knapsack instances.

To summarize, our hope with the experimental section is to "whet the IP community's appetite" and rejuvenate its interest in CGFs. We believe they can be useful, and using learning techniques may be a good way to unlock their true potential.

Some responses to your more detailed questions:

• Z^n should be Z^k

  It should be $\mathbb{Z}^n$ since $\mathbf{r}^1,...,\mathbf{r}^n \in \mathbb{R}^k$ are vectors.

• Figure 1: For $r=1$ ... should hold for $r=0$?

  The plots in Figure 1 are on the interval $[0,1)$, so $r = 1$ is not included, which is necessary because the generating function of Chvátal-Gomory cut, $\text{CG}_f(r)$, is not continuous at $r \in \mathbb{Z}$. However, $r = 0$ is defined, and by periodicity, for these functions, the value at $r = 1$ is the same as the value at $r = 0$.

• Table 1: For $d$-dimensional ..., 2-row is best for 2-d knapsack?

  Yes, this is a very insightful point. We share the same intuition. Indeed, for $k$-row cuts, we selected the first $k$ rows from the simplex tableau to generate a cut, so it makes sense that the 2-row cut works best for the 2D knapsack problem.

We will address the other minor remarks in the final version of the paper.

Thank you very much for the thoughtful and encouraging review. Section 5 is meant to illustrate that our analysis extends to the setting where one wishes to select cutting planes tailored to instances using, say, a neural network mapping from instances to cutting planes. This was done in a more general algorithm design setting by Cheng et al (2024), but the analysis can be easily adapted to CGFs. This can potentially lead to stronger gains since the CGFs are tailored to specific isntances, as opposed to using the same CGF for all instances.

Thank you very much for the insightful review and providing detailed feedback. Regarding your questions:

1. This is an good point. The two families of cut-generating functions considered in this paper are indeed parametrized geometrically. We will include additional explanations and figures to clarify this further.

2. The $k$-dimensional cut-generating function in this paper is a subfamily of those studied by Basu and Sankaranarayanan (2019). Specifically, it is the trivial lifting of the gauge function of a family of maximal $(\mathbf{f} + \mathbb{Z}^k)$-free simplices, defined as $\mathbf{f} + \lbrace \mathbf{x} \in \mathbb{R}^k : \sum_{i=1}^{k} \mu_i \mathbf{x}_i \leq 0, \mathbf{x}_1 \geq -1, \dots, \mathbf{x}_k \geq -1 \rbrace$, parametrized by $\mu$ restricted to the standard $k$-dimensional simplex. We indeed have some 3D-printed models of these generating functions, as shown in our global response (see the attached PDF). We will include these figures in the paper.

3. Our main results are based on the piecewise structural results of the branch-and-cut tree size studied by Balcan et al. (2022), so we adhere to the same methods and assumptions for building branch-and-cut trees as in their paper. Therefore, the results apply to product scoring policy or lexicographic policy for variable selection and depth-first search policy for node selection. Using the same technique, one can prove similar results for other selection policies, such as the best-bound policy for node selection. We will clarify this further in the paper.

4. Gomory and Johnson (2003) proved that the one-dimensional cut-generating functions (CGFs) considered in this paper are extreme. For $k$-dimensional CGFs, they are minimal valid functions as they are the trivial lifting of the gauge function of maximal $(\mathbf{f} + \mathbb{Z}^k)$-free convex sets with the covering property (Basu et al., 2013; Conforti et al., 2014; Averkov and Basu, 2015). Then, these $k$-dimensional CGFs are extreme by the $(k+1)$-slope theorem (Basu et al., 2011). We will include these explanations in the appendix of the paper.

5. There are some trivial constraints for those $0/1$ knapsack problems restricting the decision variables to be no larger than 1. We do not explicitly handle these upper bounds differently, and consequently, they contribute to the simplex tableaux.

6. This is a very interesting and important question. There are two related issues here. One is the classical bias-variance/bias-complexity/overfitting-underfitting tradeoff in any statistical method such as ours. The second issue is the difficulty in finding the optimal solution to the ERM problem $\min_{{\mu}} \frac{1}{N}\sum_{i=1}^N T^k(I_i, {\mu})$, where $T^k(I_i,{\mu})$ is the branch-and-cut tree size of the instance $I_i$ after adding a cutting plane induced by a $k$-dimensional CGF parameterized by ${\mu}$ (i.e., $k$ is the number of rows used to generate the cutting plane).

   Increasing the number of rows reduces the bias of the model, i.e., we expect the overall expected error to go down with the optimal choice of parameters ${\mu}$ (for minimizing the overall expected error). However, it increases the variance/complexity of the learning procedure. As you point out, if we fix the number of samples, increasing the number of rows leads to weaker guarantees on the expected error of the learned parameters, i.e., the ERM solution ${\hat\mu}$. Sample complexity tracks this trade-off quantitatively: it tells us how the sample size should grow if we increase the complexity of our model (i.e., increase the number of rows $k$ used to generate the cutting plane), if we wish to keep the same error and high probability guarantees.

   From an empirical perspective of solving the ERM problem, the phenomenon you mentioned is the following. In the experiments of this paper, regardless of the value of $k$, we uniformly sampled a constant number of CGF parameters on the $k$-dimensional standard simplex and chose the best one. Therefore, for higher dimensions, the probability is lower that some of these randomly sampled points are good enough to solve the ERM problem. In this setting, increasing the number of sampled candidate parameters as $k$ increases is a reasonable way to improve the performance of the $k$-dimensional CGF. However, the number of candidate parameters might grow exponentially with $k$ for a provable guarantee. We have not theoretically or computationally explored this dependence.

   Therefore, with more IP instance samples, we might consider moving away from this simple yet robust enumeration method and adopting heuristic algorithms to solve the ERM problem. For instance, as suggested by Cheng et al. (2024) in their paper that also involves the optimization of a similar ERM problem, we could use some reinforcement learning (RL) algorithms, treating the CGF parameters as continuous actions in the RL setting, to find a relatively good parameter setting.

7. Thank you for catching this. We will fix the citation types in the paper.