Learning Cut Generating Functions for Integer Programming

Summary

The paper is concerned with the interplay of learning theory and the branch-and-cut algorithm for solving mixed-integer programs (MIPs). Concretely the authors analyse the problem of cut selection. In general, cut selection asks for a given (class of) MIPs: What cut(s) should be added to the lp relaxation, to speed up the branch-and-bound algorithm as much as possible? The authors limit the scope of this board question to: How should one parameterize a concrete cut-generating function, to generate a single cut, which, when added to the problem at the root node, minimizes the number of branch-and-bound nodes the solver has to create? For the selection of a cut generating function, the authors list three criteria: 1: There should be an efficient way, to compute the cutting planes 2: One should be able to prove concrete sample complexity bounds 3: One should be able to demonstrate that the cutting planes are “significantly better in practice than classical cuts” The authors then proof sample complexity bounds for three different settings. 1) One wants to find the parameters for the Gomory and Johnson [2003] cut generating function (which generates cuts from a single row of the simplex tableau) minimizing the expected tree size for instances drawn from $D$. 2) One wants to find the parameters for a subfamily of cut generating functions studied by Basu and Sankaranarayan [2019] (which generate cuts from k many rows of the simplex tableau) again minimizing the expected tree size for instances drawn from $D$. 3) One wants to train a neural network to choose a good instance (not distribution) dependent cut generating function. In their numerical experiments, the authors investigate the effect of the cut generating functions on some generated knapsack and partition problems. The goal is to find evidence for better performance of the chosen cut generating functions when compared to classical (here GMI only) cuts. For 1-d knapsack, the cut generating function is shown to clearly outperform GMI cuts in the chosen setting. For all other instances, GMI performs worse than at least one cut generating function, but the difference is smaller, especially for the packing instances.

Strengths

The paper is well-structured and easy to read. The provided code allows for the reproducibility of nearly all experiments (only for knapsack_50 I get “index 0 is out of bounds for axis 0 with size 0” and no results, even if I run the code to regenerate the instances).

Weaknesses

The main weakness I see is the little empirical evidence for some strong claims about the Gomory and Johnson [2003] cut generating functions. See e.g. line 220 and 251: “and they result in significantly smaller tree sizes compared to traditional cutting planes”. This statement seems over the top. 1) the numerical experiments do not always indicate “significant” 2) the only tested classical baseline are GMI cuts, which are by far not the only class of cuts doing heavy lifting in modern branch-and-cut solvers 3) for the instances on which the impact is high (1-d Knapsack), I think the combination of setting and instance class, does not allow general claims, see below. L 316: “Instances were generated using the distribution proposed by Chvátal in Chvátal [1980], also used in Balcan et al. [2021b].” -> this is not correct. The authors use the same parameters as Balcan et al., but they are at best related to Chvátal instances. Chvátal explicitly designs instances, which are provably hard to solve for certain branch-and-bound algorithms. To achieve this, all constraint coefficients $a_{ij}$ are sampled from $[1, 10^{(n/2)}]$ and $b_j = floor(\sum (a_i / 2))$. Balcan et al. sample a_ij from a uniform normal distribution $N(50, 2)$. This leads to extremely similar a_ij (so quite far from Chvátals distribution) values and makes the instances extremely easy in practice. For 1-dimensional knapsack the original constraint of the problem formulation is tight. When turning on primal heuristics (which are turned off by the authors, but not by Balcan et al.) Gurobi solves all instances at the root node, before even solving the relaxation. From my perspective, there is little to learn from experiments on these types of instances (1-d knapsack). I am well aware, that the authors focus on theoretical aspects of machine learning and cut selections, but when explicitly listing “3) we should be able to demonstrate that these new cutting planes are significantly better in practice than classical cuts” (line 109) as one of three requirements for the cut generating functions, I expect stronger empirical evidence.

Questions

Additional and minor remarks: - L 6: “optimal cutting planes”. “Optimal” is very global and strict. Maybe “good” - L 24: “small representative sample”. Representative seems subjective - L 36: “we understand many of their theoretical properties”. “We” sounds ambiguous here. Maybe “many theoretical properties are understood” - L 53: “with several excellent insights”. “Excellent” is quite subjective - L 144: Z^n should be Z^k - Figure 1: The use of the label “y” for the y-Axis is confusing to me - Figure 1: For r = 1 the graph has a red circle, indicating it is not defined here. The same should hold for r=0? - Figure 1: The font seems unnecessarily small - L 296: If “their” in “A direct applications of their main theorem” refers to Cheng et al. [2024] from line 278, I feel like the reference is too far away, for the reader to parse “their” in the context of Cheng et al. - L 314: The two types of instances under consideration are quite similar (in referenced Tang 2020: “A knapsack problem is a binary packing problem”.) I think it might make sense to mention their similarity and the fact, that one is integer and one is binary - Table 1: For $d$-dimensional knapsack, there are $d$ constraints significantly different from the remaining $n$. Are these constraints considered first, for k-row? Does this explain why e.g. 2-row is best for 2-d knapsack? - Small and capital letter inconsistency in references. E.g. 352 & 358: “cambridge university press” and “Cambridge University Press”

Rating

5

Confidence

2

Soundness

2

Presentation

3

Contribution

2

Limitations

The author's discussion of their limitations is fine, apart from the part about the numerical experiments (see weaknesses).

Summary

This paper studies the learning of generic classes of cut generating functions, which can be used as an algorithmic tool for solving integer programming problems. The paper presents a handful of cut generating function families, studies the learning complexity of these functions, and presents a computational study of those CGF families on standard integer programming problems.

Strengths

The setting is of clear interest to the integer programming (IP) community. I cannot vouch for the novelty or correctness of the learning-theoretic content of the paper, but the IP content is crisp and clean, and the high-level idea and computational setup all make sense to me.

Weaknesses

I feel like there is some connective tissue missing from the paper, particularly joining the computational study with the rest of the paper. Section 5 seems like an interesting connection to draw, but does not appear in the computational study and feels a bit disjointed from the rest of the paper. And while the paper spends much of its effort to show that the cut generating functions _can_ be learned, the computational study is relatively rudimentary and does not really attempt to develop very sophisticated techniques to actually learn the CGFs in practice (to be clear, this is a reasonable tradeoff to make for a theoretical paper).

Questions

None.

Rating

7

Confidence

2

Soundness

3

Presentation

4

Contribution

3

Limitations

Yes.

Summary

This work presents sample complexity results for learning parameters for certain classes of cut generating functions, along with some numerical experiments. These are functions that determine coefficients of cutting planes to help solve mixed-integer programming problems, and some of the most effective cutting planes in practice (e.g. GMI cuts) can be expressed as cut generating functions. More specifically, this paper proves pseudo-dimension bounds on an established class of one-dimensional cut generating functions, and on a class of k-dimensional functions, both of which generalize GMI cuts. This latter function can be (non-trivially) computed efficiently. Furthermore, the authors provide pseudo-dimension bounds for these functions for the case where the parameters are learned by a neural network. Finally, the paper provides numerical experiments to highlight the learnability of parameters for these families of cuts on small instances.

Strengths

This work adds an interesting and novel learning-theoretical perspective to the cut generating function literature. Making general cut generating functions practical has always been challenging, and this paper suggests potential in learning them in a principled and theoretically grounded fashion. While we are still far from being able to use cut generating functions in the way that the paper promotes, this is a valuable step that advances the field further and I believe that this can inform future learning-based cut generation methods. The paper is overall written in a clear way. I checked the proofs at a high level but could not do so in detail since my familiarity with learning theory is limited. The computational results, while focused on small cases, show good potential for learning-based methods.

Weaknesses

None of the weaknesses that I see are particularly major. I would have liked to see further experiments on more realistic scenarios, but I understand that we can derive insights from a very focused experimental setup and the theoretical contributions are the main focus of this paper. I leave specific issues for the Questions section below.

Questions

These are all minor comments. 1. It would be nice to add the geometrical interpretation of the parameters of the functions to provide a quicker understanding for the reader. It takes a little while by looking at the functions and the examples (which are helpful) to understand, and for me it was easier to understand some of the proofs after I understood what those parameters were doing. You can for example add them with Figure 2 in the Appendix. 2. I am not sure I can visualize the k-dimensional function very well. Would you be able to explain what motivates this particular function, and perhaps include 3d examples for the case where k = 2 (like you did with k = 1)? 3. Is the definition of tree size here the worst-case tree size across variable and node selection? If relevant, could you add a precise definition of tree size to the paper? 4. Could you add to the paper why these cut generating functions are extreme? I believe those come from previous work (e.g. the 1-row one has two slopes)? 5. I am confused as to how you have 5-row cuts and 10-row cuts for knapsack with 2 and 3 rows. If I missed something, please add the explanation to the paper. 6. This question is mainly out of curiosity (though could be interesting to discuss in the paper if you have a good answer): I see that increasing the number of rows sometimes help, but generally do not seem to be too helpful. It may be more difficult to find a good multi-row cut with more rows but a fixed number of samples. Do you have any sense on how the quality of your cuts would improve with more samples? 7. Please fix the citation types (those missing parenthesis).

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

There is not much discussion on limitations, though the paper is mostly theoretical. Perhaps the paper could discuss some more what these results could lead to in future work, and limitations of interpreting these small-scale experiments.