Cutting planes are crucial in solving mixed integer linear programs (MILP) as they facilitate bound improvements on the optimal solution. Modern MILP solvers rely on a variety of separators to generate a diverse set of cutting planes by invoking the separators frequently during the solving process. This work identifies that MILP solvers can be drastically accelerated by appropriately selecting separators to activate. As the combinatorial separator selection space imposes challenges for machine learning, we learn to separate by proposing a novel data-driven strategy to restrict the selection space and a learning-guided algorithm on the restricted space. Our method predicts instance-aware separator configurations which can dynamically adapt during the solve, effectively accelerating the open source MILP solver SCIP by improving the relative solve time up to 72% and 37% on synthetic and real-world MILP benchmarks. Our work complements recent work on learning to select cutting planes and highlights the importance of separator management.
Paper
Similar papers
Peer review
Summary
The authors use machine learning to decide how and when to toggle the on/off switches for different cutting plane families provided by SCIP, the fastest open-source MIP solver. Their learning algorithm outperforms the default setting of SCIP on various benchmark sets.
Strengths
The techniques used to deal with the high dimensional combinatorial space of possible configurations are interesting. The results are promising and yield speedups over SCIP default on established benchmark sets. The interactions between different cut families is not an extremely well understood topic. It is nice to know that machine learning can help decide what families to activate, and when.
Weaknesses
Ultimately I don’t think the proposed methodology is too novel, since it boils down to learning how to set on-off toggles for a variety of cut families. I acknowledge that this toggling is a critical component of tuning MIP solvers, but since this paper doesn’t mention what cut families ended up being selected and most useful for the different problem instances, I believe it leaves the most interesting question of what separator families worked best for which problems on the table. So methodologically this paper doesn’t seem too different from an array of previous algorithm configuration papers for MIP (e.g. Hydra-MIP by Xu, Hutter, Hoos, Leyton-Brown) that aim to tune parameters of a MIP solver from past data, but without any deeper principled investigation of what the parameters are actually doing. Hypothetically, it could be the case that turning off SCIP’s Gomory cut generation helps out for a class of MIPS, but maybe if the actual Gomory cut generation was tweaked performance would improve. Learning to toggle does not yield any such insights, as far as I can tell.
Questions
The title/phrase “learning to separate” slightly misleading. The *separation problem* refers to the specific problem of generating a cut (from some class of cuts) that cuts off the LP optimum. The authors here are not concerned with that problem, rather they are concerned with the on/off toggle for a particular family of cuts that is being generated via SCIP’s separation routines. The authors discuss generalization guarantees but do not cite or compare to any prior work on such theoretical guarantees for cutting planes/integer programming/tree search. It might be worth mentioning how this compares to that work and where it is different (ostensibly “learning to toggle” falls into some of the frameworks studied previously). As mentioned previously, one of the most interesting questions that is completely missing: what cut families ended up being selected and working well for the different problem instances? To me this would be the most interesting set of conclusions, since it is well known that MIP solvers need to be tuned to yield improved performance. The question of what cuts work best for what problems is much more elusive. Overall, I would be much more in favor of acceptance if there was some discussion about this aspect. Presumably this question is already answered by the experiments the authors ran, and including some observations here would be great. Given that the authors are controlling granular on/off parameters (and not fundamentally modifying the underlying algorithms), why not compare to a state-of-the-art solver like Gurobi or CPLEX, which are free for academic use and significantly faster than SCIP?
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
4 excellent
Presentation
3 good
Contribution
2 fair
Limitations
N/A
Summary
The paper proposes a pipeline for a learning-enhanced cut separation management in modern MIP solvers (specifically, in the academic solver SCIP). To pick a promising subset of the large number of possible settings, the authors derive a data-driven and theoretically motivated method to focus on specific configurations that are expected to perform well. The actual policy on how cut separators are used during a MIP solving run are then learned over the restricted configuration space. The experimental results show significant solve-time improvements for a variety of benchmark MIP classes and test sets; this holds both when learning within MIP subclasses and when learning within heterogeneous benchmark sets such as MIPLIB. The presented work has the potential to replace current fixed, heuristic solver settings for cutting plane separation by carefully learned policies that often yield large speed-ups, which in turn can increase the size of problem instances that can be solved to optimality, and therefore represents a very notable advancement in data-driven MIP solving techniques. -- update: I have read and acknowledged all other reviews and the authors rebuttals, see discussion. --
Strengths
Besides the impressive empirical results, the theoretical justification/motiviation for the configuration pre-selection is a strength of this work. Moreover, although the work spans quite many different and subtle aspects of the intricate workings of MIP solvers and employs different machine learning techniques, the authors did an excellent job in condensing their work into an understandable and well-written main paper; the supplementary material, while containing the technical proofs, is largely additional information that well complements the main paper but is mostly not necessary to follow the main paper.
Weaknesses
It appears to have become common practice to submit papers to NeurIPS (and ICML) whose actual, main content is put in a separate "Supplementary Material" document whose length far exceeds that of the supposed main paper. This paper is only a partial exception -- the main paper provides enough information and details to stand on its own except for the most technical bits, which can then be found in the very long Appendix (supplementary document; three times as long as the main paper) along with a host of additional information. Thus, it may be considered a weakness of the paper to have such a long Appendix, because this format bears the danger of the formally most important parts of the work (proofs; algorithm details and specific setups) not being reviewed thoroughly due to the short review period and high review load of reviewers at these conferences. I cannot exclude myself from this -- I simply did not have the time to rigorously check all the details in the long supplementary document, and therefore cannot give a definitive answer regarding the proofs' correctness beyond "believing" everything appears to be well in order. In this regard, I cannot help but wonder if a full journal paper would not be the better way to publish results that simply do not fit into the 9-page limit. But, again, I have seen papers that exploit the main paper/supplementary material split in a much worse way; for the present work, it actually hardly bothered me because the main paper is nearly self-sufficient. Nevertheless, if I have to point to a weakness, this aspect is what stands out to me.
Questions
- there are several (minor) typos throughout paper and supplementary document (e.g., no comma after "e.g.", "c.f." or "v.s." instead of "cf." and "vs.", "constraint" <-> "constrained" (caption of Fig.2), "contrary" <-> "contrast" (l.193), "included A" <-> "included in A" (l. 239), "which we provide comparision" <-> "for which we provide comparison" (l. 311), "U Stuhl" (ref. [47] -- what's the first name?)) - some wordings are a bit inaccurate (at least when not having seen the supplementary document yet, i.e., when reading just the first paper): * l.19: "lower bound" -- this implies that the problem is a minimization problem, which is not specified here (only in the supplement). Maybe clarify, or use "dual bound"? * l. 66 and again later: The product-sign (\prod , large Pi) should be a *Cartesian* product-sign * Prop. 1 is referred to as "lemma" in the paragraph preceding it. * Sect. 3.2: "network" kind of drops out of nowhere -- please clarify a bit here that neural networks are used for the discussed task * in Tab. 1 and 3 at least: "higher the better" only applies to the median; for standard deviation, lower is better! * is the reported standard deviation given in percent deviation from the default or as percent variation from the median values? how often, if at all, does reconfiguration actually slow down the solver? what are the mean/average deviations from default? - it would be good to clarify in the main paper that the separation rounds after which configuration updates occur are specified in advance; this only becomes clear in the supplementary document, so reading the main paper, one wonders how this is decided and/or if it is part of the learning procedure to decide when to update configurations. Also, are there cases in which the MIP solver terminates before the number k of updates has been performed? - have you tried reverting to the default configuration as the last update? - which LP solver was used by SCIP to solve the relaxations? SoPlex? - were all MIPs solved in single-thread mode?
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.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
4 excellent
Contribution
4 excellent
Limitations
Limitations have been appropriately addressed (at least in the supplementary material).
Summary
This paper studies learning to manage separators to improve MILP solvers. Specifically, it learns a policy to determine which separators to use to generate cutting planes. The task is well formulated and experiments on many datasets demonstrate the effectiveness of the proposed model.
Strengths
1. The paper is well written. Especially the problem is well formulated. 2. The paper identifies the opportunity of managing separators to improve MILP solvers. 3. Experiments on many datasets demonstrate the effectiveness.
Weaknesses
In general, I think this paper is an OK work, but it is just borderline to the NeurIPS bar, so I only give borderline accept. There have been many works that study different parts of branch-and-bound, e.g., cut selection and node selection. Replacing one of the solving stages to a learning method, which leads to improvements compared with heuristic rules, is unsurprising. However, in real applications, it would be impossible to replace every part to learned models because of the memory limitation. Whether the studied part is critical enough in branch-and-bound is an important question. Therefore, separator configuration may not be in a trend of the research community, and thus the impact of the proposed method may be limited. I would give some suggestions in improving the work. First, the authors can compare the focused task, i.e., separator configuration, with other solving stages to demonstrate its significance. Or the authors can compare the resource usage to show the proposed method is lightweight enough so that it can be used jointly with other methods. Or the authors can try to merge the proposed framework with existing work and conduct enough ablation study. Summarily, the authors should denonstrate the real usefulness of the proposed method beyond only its performance.
Questions
See Weakness.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
2 fair
Limitations
N/A
Summary
This paper uses machine learning to decide which families of cutting planes should be applied in each of a finite number of rounds when a discrete mathematical optimization problem is solved by an MILP solver. The authors conduct experiments on the SCIP solver, in which they show that their selection of separators (generators of different families of cutting planes) is able to solve problems faster than the default configurations of SCIP.
Strengths
Within the mathematical optimization community, it is known that many people have looked at this problem but few obtained good results, which shows in the limited number of direct references shown by the authors. The results are certainly motivating, and the authors managed to analyze their work across a representative number of datasets. ***** Following the rebuttal, I still have concerns about the significance of the work, which are similar to the ones presented in reviewer wvgK's review. For that reason, I cannot be more enthusiastic than a borderline accept for this paper.
Weaknesses
I tend to consider the selection of separators a special case of what was done in prior work, in which the cuts themselves were selected. By using a setting in which their work is not comparable to prior ML studies on this topic, I am left wondering if what is proposed in this paper indeed leads to a better approach than the ones already known. The paper explains very little about MILP, to the point that it fells like the application is an afterthought. While the appendix generously makes up for that, a reader unfamiliar with MILP might read the entire paper and not understand much about the application considered. In fact, for a span of approximately 3 pages (Line 56 in Page 2 to Line 175 in Page 5) there is very little that is specific to the application to MILP solvers. In great part that is because of using a language that is very different. I would not say that this is an issue of using ML instead of MILP terminology because I also got lost with the abstractions used, such as when the authors say "single configuration update" to mean that the same separators would be used in every round. This abstractness of the language left me with many questions about what exactly was done (see Questions). For someone with a greater interest in MILP as myself, I find it difficult to translate what the authors did to the application. As a consequence, I would have a hard time trying to reproduce their work if I wanted to.
Questions
1) Can you compare your work with prior cut selection approaches? 2) In plain terms, what exactly is the subset of configurations A and how is it pre-selected? 3) What is the relevance of Propositions 1 and 2 in the context of MILP? 4) How exactly are the separator nodes S used in the representation of the instances? 5) How exactly do you consider instances in which neither SCIP nor skip with your separator selection were able to solve? Figure 1: The letter b is used both as the RHS of the set of constraints as well as the RHS of the next cut generated; also using A and a with different meanings (constraint LHS and cut LHS) does not seem advisable. Equation 2: Why is the term on the left repeated at the end of the equation? Is this a typo?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
1 poor
Contribution
2 fair
Limitations
Although the authors do not explicitly acknowledge this, their focus on runtime for solving problems to optimality means that their approach is of little help precisely for the case in which it would be needed the most: problems in those benchmarks for which the provable optimal solution is not known. It is also unclear what happens in the case of the problems that do not finishing running on time: my guess is that timeout is counted equally as bad, although it would make more sense to look for the best solution found or the remaining optimality gap.
I thank the authors for their detailed responses to all comments by the other reviewers and myself. Especially the additional insights summarized in the general response will be a valuable addition to the paper. A quick (?) follow-up question regarding the interpretability analysis in GR1: Besides identifying known results/what was known to work well for specific instance classes, did you observe something "unexpected" or "unexplained"? For example, did some family of cuts consistently appear in selected configurations for an instance class for which it is not known that or why these cuts would be useful? If so, this may warrant a closer (theoretical) inspection of the problem-cut pair in future work, so possibly, L2Sep could also serve as a driver of improved polyhedral understanding fof some problems. Overall, I am strongly in favor of accepting this paper, and will increase my score. I very much hope that the other reviewers see the merits of this work and raise their scores at least into acceptance territory as well.
Thank you for your feedback!
We are very thankful to the reviewer for recommending acceptance of our work! Regarding the reviewer’s followup question, we do observe some intriguing unexpected scenarios from the visualizations. For Independent Set (see Rebuttal PDF Fig. 2), L2Sep deactivates all separators with a frequency of 20% at the 2nd config. update, whereas all selected configurations at the 1st update activate a substantial amount of separators. It is an interesting question to investigate why it is better to *deactivate all* separators for a certain subset of Independent Set instances at *later* separation rounds. For Maximum Cut, OddCycle [1, 2] and ZeroHalf [3] are known to be effective in the literature. Interestingly, none of the selected configurations activate ZeroHalf for both config. updates; OddCycle is also completely deactivated for the 1st update, but is activated with a frequency of 14% at the 2nd update. Meanwhile, we observe that Disjunctive, FlowCover, and Aggregation separators are more frequently selected. We will provide the visualization in the Appendix. In summary, we agree with the reviewer that L2Sep could also serve as a driver of improved (theoretical) polyhedral understanding of some problems. We further believe that L2Sep can be helpful to seed investigations (empirical and theoretical) for nonstandard, newly-proposed problems (e.g. NN Verification) where few analyses exists. We thank the reviewer again for the time taken throughout the process to thoroughly review our work! *[1] Boros, Endre, Yves Crama, and Peter L. Hammer. "Chvátal cuts and odd cycle inequalities in quadratic 0–1 optimization." SIAM Journal on Discrete Mathematics 5.2 (1992): 163-177.* *[2] Jünger, Michael, and Sven Mallach. "Exact facetial odd-cycle separation for maximum cut and binary quadratic optimization." INFORMS Journal on Computing 33.4 (2021): 1419-1430.* *[3] Caprara, Alberto, and Matteo Fischetti. "{0, 1/2}-Chvátal-Gomory cuts." Mathematical Programming 74 (1996): 221-235.*
I greatly appreciate the authors' amazingly thorough response. The qualitative results are very interesting, and it is especially fascinating to me that the L2Sep method "discovers" classical knowledge. Coupled with this, I find the message that L2Sep meaningfully shows when and where to toggle specific cut families to be significant and interesting, given that the "when to cut" question is equally not-well-understood as the "how to cut" question, and has received significantly less study. My initial score of 4 was probably too harsh, and I would be happy to raise my score to a 6/7. I do think the title change proposed by the authors would be appropriate.
Thank you for your feedback and suggestions!
We are thankful to the reviewer for taking a careful look at our rebuttal and taking the time to revise their assessment. We're happy that our rebuttal alleviated the reviewer's main concerns, and we will make the title change in the updated paper. Thank you again for your detailed feedback and suggestions throughout the whole process!
I appreciate the response from the authors. I did not see a comment regarding Figure 1, but I hope that this gets correct. In revising my score, I am counting on the word of authors that a final version would be more informative about the application (MILP), and I also second reviewer wvgK's recommendation that the paper title should be changed to better reflect what the paper does.
Authors' Further Response to Reviewer LDTP
We're thankful that the reviewer took the time to revise their assessment! We will incorporate more information about MILP and make the title change in the final version. We did not provide a comment on Fig. 1 due to the character limit of our initial response, but we will update a and b to $\nu$ and $\omega$ in the Figure (e.g. $\nu_{11}^\intercal x \leq \omega_{11}$). Thank you for your suggestions! Regarding the reviewer’s concern on the significance of our work (similar to the ones in reviewer wvgK's review), we invite the reviewer to elaborate on their concern more explicitly, so that we can use this discussion period to further address. As we are delighted that our response addressed reviewer wvgK’s concern, we thought of sending you a summary of the significance of our work. We hope this message will help the reviewer LDTP in contextualizing our work’s significance. - **Task**: we agree with reviewer TfAQ and wvgK’s response that it is important to understand “when to cut”, which is much less explored (though equally crucial) as the “how to cut” question. Separator configuration and the associated cut generation play a vital role in the B&C process; properly configuring separators can accelerate MILP solvers by 25%-70% (also, see our response to reviewer JiCg *“The Immediate and Multi-step Effect of Separator Configuration in the B&C Process”*). We are excited about our work’s potential to inspire more future studies on this “when to cut” question. - **Interpretability**: from [GR1], our learning method L2Sep automatically discovers known facts from literature regarding the efficacy of difference separators for each MILP class (where the existing literature has spent decades of efforts to initially discover these facts). L2Sep can potentially speed up the knowledge discovery process by suggesting efficient MILP class-separator family pairs for future theoretical inspection. - **Method**: different from prior cut selection works, we propose a data-driven subspace restriction algorithm followed by a learning method to configure separators. Our work integrates empirical methodology with theoretical justification, bridging gaps in the existing learning for MILP literature that has been predominantly empirical; our theory directly informs our empirical subspace restriction algorithm, whereas prior theoretical works on parameter configuration cannot (see our response to reviewer wvgK for details). - **Performance**: our learning method L2Sep for separator configuration is able to accelerate multiple MILP solvers (SCIP, Gurobi [GR2]) under different objectives (time improvement, gap improvement [GR3]) on various datasets (standard, large-scale [our paper]), demonstrating effectiveness of our method in accelerating MILP solvers. We would like to thank the reviewer again! We really appreciate your detailed feedback on the paper presentation and your other insightful suggestions.
Thanks for the response and sory for the late reply. Increasing my score from 5 to 6.
I appreciate the authors' efforts in responding to my concerns and I'm sorry for the late reply. I have read the authors' response and other reviewers' comments. I can understand the importance of the task better now, which has addressed my main concern. I have raised my score from 5 to 6. Still, though the authors provide a comparison of efficiency between the proposed method and other B&C parts (e.g., cut selection, branching), I think the paper will be stronger if direct comparisons of end-to-end performances can be conduct.
Thank you! Please see authors’ further response.
We really appreciate that the reviewer takes a careful look at our rebuttal and and other reviewers’ comments. Thank you for taking the time to provide valuable feedback and revise the assessment! We provide our further responses regarding “the direct comparison of end-to-end performances” below. If our answers do not align with the reviewer intention, we would appreciate that the reviewer explain their suggestion in more details. The bottom line is that subtle differences in the emerging related works result in challenges in directly comparing without adapting and extending implementations (it is not as easy as re-running the authors’ code), not to mention that some implementations are not available. We thus offer comparisons based on reported improvement metrics for overlapping benchmarks. **What we are able to say about performance comparison:** - **Cutting:** In Sec. 4.3 of our main paper, we contextualize our performance for separator configuration with prior cut selection works on comparable datasets, where L2Sep achieves a 37.5% time improvement on NNV and 12.9% on MIPLIB (a larger subset), whereas prior cut selection works report 11.67% on NNV and 3% & 1% on MIPLIB (two smaller subsets). - **Branching:** A recent work [4] compares a few learned branching rules with SCIP default on the Ecole datasets, and report the best time improvements of 36.4% (Comb. Auc.), 34.1% (Indep. Set), and 57.4% (Fac. Loc.) from SCIP default (see Table 2 in their Appendix). In contrast, our method L2Sep achieves 66.2% (Comb. Auc.), 72.4% (Indep. Set) and 29.4% (Fac. Loc.) on larger and more heterogeneous Ecole instances. **Challenges in direct comparisons:** It is challenging to directly compare with prior learning works due to differences in experimental setup. For example, [1,2] focuses on the comparing different cutting plane selection strategies (including learning) on a synthetic environment that consider pure cutting plane iterations (without branch-and-bound) on Tang et al. instances. That is, they do not consider improvement relative to a full B&C solver (e.g., SCIP). Another recent work [3] is restricted to solving only the root node of B&C. In addition, prior works also consider different performance metrics (e.g. reversed Integrality-gap-closed integral), since they do not fully solve the B&C. Our work compares with the full B&C solver (SCIP and Gurobi), solves the full B&C tree, and considers the performance metrics of relative time or optimality gap improvement. The reviewer comment does highlight an emerging research gap, however, to unify and rigorously relate the emerging works in this area! We hope our response align the reviewer’s intended suggestion. We would like to thank again for the reviewer’s suggestions during the rebuttal period! *[1] Tang, Yunhao, Shipra Agrawal, and Yuri Faenza. "Reinforcement learning for integer programming: Learning to cut." International conference on machine learning. PMLR, 2020.* *[2] Paulus, Max B., et al. "Learning to cut by looking ahead: Cutting plane selection via imitation learning." International conference on machine learning. PMLR, 2022.* *[3] Wang, Zhihai, et al. ‘Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Model’. The Eleventh International Conference on Learning Representations, 2023.* *[4] Scavuzzo, Lara, et al. "Learning to branch with tree mdps." Advances in Neural Information Processing Systems 35 (2022): 18514-18526.*
Thanks for the further response. I would like to keep my score, 6 weak accept.
Thanks for your further response. The performance comparison demonstrates the advances of the proposed method to some extend, and I understand the challenges in more direct comparisons. Since the idea of using learning method to replace parts of solvers is not that novel, and the advantage of the proposed method to previous ones is not sufficiently demonstrated, I would like to keep my score, 6 weak accept.
Decision
Accept (poster)