Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper applies learning theory to provide sample complexity bounds for GMI cuts.

The paper is very dense, and the literature is updated and exhaustive.

The 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. 

For 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).

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.

WEAKNESS: 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/).
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?


limitations: We see no limitations in this paper.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper proves a number of results regarding the sample complexity
of gomory mixed integer cuts.

strengths_and_weaknesses: Strengths:
A number of interesting results are proved, some of which do not seem
expected.

Weaknesses:
Several key aspects of the paper are left for the appendix, and in
total the submission in 30 pages. Also, the lack of experiments in the
main text is problematic.

questions: None.
limitations: It would help if the paper included some experiments.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.
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. 

The 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.

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?

Is it possible to generalize these results to settings like bilevel optimization or solving Stackelberg games?

limitations: The authors adequately address the limitations of their approach and any ethical considerations
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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. 
strengths_and_weaknesses: Strengths
- Very strong theoretical results, advance our understanding and provide further geometric insights into GMI cuts 

Weaknesses
- Perhaps some of the results could be formalized more carefully
- 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

Major Comments

Overall, 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.

(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...

(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. 

(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? 

(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...

(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.


Minor notes
- Text sometimes alternates between "piecewise" and "piece-wise"
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?

2. 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
review_title: null

Meta-review: metareview: There is general agreement that this is a strong paper that should be accepted. I agree with the discussion. Nothing much to add.
confidence: Certain
Decision: Accept