Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The paper focuses on scheduling primal heuristics in an exact MIP solver to find feasible and fast solutions rather than finding the expensive global optimal. An exact MIP solver has a variety of primal heuristics implemented during the branch-and-bound algorithm. This paper aims to propose a data-driven and generic approach to improve the primal heuristics scheduling in the B&B algorithm. They formalized the problem as an MIP, and the goal here is to find the order of the heuristics and their iterations. Paper proposes a greedy heuristic inspired by Streeter’s algorithm to compute different parameter configurations. It is claimed that the heuristic is constructed by learning from data about the duration and success of two kinds of heuristics that call for two sets of training instances. In the data collection phase, the objective is to collect the heuristics performances on each node of the search tree. For this purpose, they used strategies that will result in running just one B&B execution for each instance. It is asserted that authors have solutions at a less expensive cost in comparison to the baseline SCIP and SMAC in terms of primal integral. Based on results the average primal integral is reduced by up to 49% on two classes of instances.
main_review: 1. The problem statement is interesting, but the contributions made do not seem much strong. This is because the heuristic they are proposing is very simple, and the methodology authors have implemented is a variation of Streeter’s approach, so I don’t see significant contributions in the scientific area.
2. The structure of the paper looks good, but it is better to have a more in-depth literature review in the related works section.
3. The approach is asserted to be data-driven, but I don't think it is because no explanation exists about instance structures or features in order to create a data-driven approach. Also, authors are just using a homogeneous set of instances which means not many diversities exist in the set of problems.
4. The result can be hard to reproduce and this is because of:
    - The randomly generated instances in which there is no explanation in the paper.
    - Not enough information about the cross-validation method is mentioned for line 278.
    - Among that large number of used instances, 121 instances are available.
5. In Line 154, authors mentioned a fact without any reference. I mean it’s mentioned that “the SMAC schedule can get very expensive quickly”, but how we can find information about this fact without any reference.
6. In line 170, it is mentioned that "we allow every heuristic to be included in the schedule at most once", and this seems that the approach is simplified version of Streeter's and it defines fixed parameters for scheduling.
7. The shadow mode and the sandbox environment used in the data collection phase do not seem to be real data. This can be because in practice no sandbox environment will be used, and in the shadow mode, the state of the current heuristic can have an impact on the next heuristic.
8. In line 277, they claimed they have implemented “a more exhaustive testing framework than the commonly used benchmark methodology”. The reader does not know what is the commonly used benchmark methodology without any references.
9. In the result section, in line 296, they have talked about the dominance of their approach in “the number of incumbents found by the heuristics” in comparison to SCIP, and I wish I could see the exact difference as a table in appendices.
10. For tables, it is preferred to have statistical plots to show the comparisons more clearly. 
11. Comparing SMAC with the greedy approaches results in table 1, the average of primal integral for greedy schedules is dominating the SMAC in just 11 out of 25 cases, and this is not much significant improvement.
12. For table 2, it is recommended to include SMAC results in order to compare the other performance metrics. 
13. Line 312, what does enough machines mean here? This can make the evaluation biased. 
	
Minor comments:
    1. In the introduction section, (line 22) they mentioned “classical ML techniques” in the literature, but in the cited papers I found some neural network related papers and I guess are they are not using classical machine learning. So, the term “classical” should be removed.
    2. The y-axis of the left plot in Figure 3 is mentioned to be “in percent”, but it’s not. So “in percent” term should be removed.
    3. Every single table and plot should be self-explained, but in Table 1 the number of instance headers is not mentioned which makes the table hard to understand.
    4. In line 142, one extra closing parenthesis in the mathematical description.
    5. For the formulation in lines 204 and 205, I couldn’t find any definition of “c” variable in the text, and I guess it’s cost. Also, the same happened for “A” variable.
    6. In line 248, “It is both related to the effort spent by the heuristic and its likelihood of success.”, they have talked about just one work limit, not two.
    7. Typos:
        ◦ line 275, 291 and 350, typo in “Furtheremore”
        ◦ line 286 “partitial”
        ◦ line 297 “heurisitcs”
        ◦ line 323 “stricly”
        ◦ line 337 “improvment”
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers integrating data driven approaches into the design of mixed integer programming (MIP) solvers.  In particular, the problem of scheduling primal heuristics is the main focus.  A MIP solver may use various primal heuristics - efficient techniques for generating feasible integer solutions - at various nodes of the branch and bound tree.  Generating good feasible solutions can speed up the solution process and some primal heuristics may work better for certain classes of problems than others.  Thus it makes sense to use data driven/learning approaches to tailor the choice of primal heuristics to run.

This paper proposes a learning approach to generating a fixed heuristic schedule (i.e. the learned schedule does not depend on the current instance being solved by the MIP solver).  The schedule must specify the order to run the heuristics and (roughly) how long to run each.  Finding the learned schedule is formulated as an MIQP.  A greedy approach to construct the schedule and a heuristic for data collection (which is needed to avoid running B&B multiple times) are proposed.  The effectiveness of these heuristics are demonstrated empirically on two types of benchmark problems (generalized independent set and fixed charge multicommodity flow), with the main metric of interest being the primal integral.  The proposed method shows a significant improvement over standard heuristic schedules (those used by SCIP) and the hyperparameter tuning method SMAC (which can also be used to set the heuristic schedule).  The downside of SMAC compared to the proposed methods is that SMAC has a high computational cost for the learning stage.


main_review: Improving MIP solvers using data driven approaches is a relevant problem and has seen some recent interest (along with other data driven approaches to algorithm design).  This paper focuses on the primal aspect of MIP solving and shows promising results

The main weakness of this paper is the lack of theory.  In addition to studying this problem from the perspective of learning theory (which the authors make a note of in the conclusion), it would also be interesting to see further justification for the greedy approach to designing the schedule and the data collection procedure.  Does the proposed greedy algorithm (Algorithm 1 in the Appendix) have a constant approximation ratio?  Can it be made more formal that the data collection procedure (Section 5) is unbiased?

Overall, the strengths of this paper outweigh the weaknesses, so I would vote to accept this paper.

-------------------------------------

Edit after rebuttal period

Thanks to the authors for responding to my comments, my overall (positive) opinion is unchanged.
limitations_and_societal_impact: There is discussion of the limitations of the work, and I do not see any issues in terms of negative societal impact stemming directly from this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Branch-and-bound (B&B) algorithms systematically enumerate all solutions of a combinatorial optimization problem. In order to prune the enumeration tree early, these algorithms periodically solve problem relaxations and execute problem heuristics, thus generating upper and lower bounds on the value of an optimum solution. Usually, the better the bounds are, the smaller the enumeration tree is.

In general, we have at our disposal several heuristics that may be run at certain re-occuring points during the excecution of the B&B algorithm. Each heuristic may be run for a given number of iterations, with more iterations increasing the chance of successfully improving the bound at the expense of computation time. Classically, a B&B algorithm would include simple fixed decision rules that govern the execution of the heuristics. It is, however, understood that a more sophisticated decision framework potentially improves the overall running time of the algorithm. 

Hence, the authors wish to learn when -- and for how many iterations -- best to execute the problem heuristics in the case that the B&B is used to solve a mixed-integer linear program (MILP). To that aim, they:

1. derive a formal model for the heuristic scheduling problem, 
2. formulate a learning problem as a mixed-integer quadratic program (MIQP), 
3. propose a heuristic greedy heuristic for the learning problem (the MIQP is too difficult to solve exactly)
4. propose a scheme to effiently collect training data from B&B runs (B&B runs are very expensive)
5. seem to use the training data and the training problem to derive a fixed schedule (see comments below) that schedules the heuristics based on the index of a node in the enumeration (B&B) tree
main_review: The paper certainly covers an interesting and potentially high-impact topic, as having fewer parameters to optimize is something that every MILP expert is very happy about. It is clearly geared towards applications with little theoretical contribution. The general idea -- learning parameters for MILP solvers -- has been seen before, but a successful execution seems to be difficult so far. This is because -- in my experience -- (a) even the B&B trees of near identical instances of the same problem may bear little to no ressemblence and (b) decisions that are superb in one B&B tree may prove disastrous in another seemingly very similar B&B tree. Hence, to me a big challenge seems to be to derive meaningful features from a B&B tree that generalize well.

Having said that, the feature used for generalization here seems to be the index of a node in the B&B tree. Aside for the general experiments which seem to largely favor the author's approach, there is no argument why this measure should be a good feature for distinguishing B&B nodes with different characteristics. In my view, the index is a measure of how far into the procedure a node was processed and the important question is whether a good choice of heuristics is merely a function of this progress. The answer could also depend on the traversal strategy, since for BFS traversal, the node index corrolates to the depth of the node in the tree, whereas it could correspond to any random position in the tree for best-first or DFS traversals. 

I am not entirely sure if I have understood correctly how the generalization works and I would like the authors' opinion on the above concern.  If my reasoning is correct, however, I would propose the following two ways to provide strong indications of the quality of a good generalization:

- Could you check how your proposed schedule performs against pure random schedule? 

- Generally, we cannot expect to understand learned models due to their complexity. In this particular case, however, the learned schedule should be interpretable. In fact, what does a schedule produced by your algorithm look like? Do we see trends like 
 + a preference for certain heuristics in early or late nodes of the tree,
 + a progress over a (largely) contiguous sequence of heuristics over time,
 + the number of iterations being proportional to the node index,
 + a corrolation of heuristics and the number of iterations (i.e., if the same heuristic appears twice in the schedule, does it have a similar number of iterations?)
 + ...
 
 Further researching this point could also become a strong point of this work since it would enable us to understand when and maybe why certain heuristics should be used. 
 
 I feel those two points would be reasonable sanity checks of the approach.
 
limitations_and_societal_impact: I feel an argument why the selected features will lead to a good generalization is missing.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Modern MIP solvers run multiple heuristics throughout its branch-and-bound tree using a fixed order. This paper introduces the problem of learning a schedule of heuristics, that is, the order and computational effort spent by each heuristic, with the goal of reducing the solving time of a MIP solver given a distribution of instances to train on. The learning task is formalized as a Mixed-Integer Quadratic Program but solved with a greedy heuristic. The paper also discusses an efficient approach to collect training data. Computational experiments are done on the Generalized Independent Set Problem and the Fixed Charge Multicommodity Network Flow Problem, using only diving and LNS heuristics, and they show that this learning method significantly improves upon SCIP with tuned hyperparameters, and produces similar or slightly better results than a schedule produced by the hyperparameter tuning tool SMAC.
main_review: This is overall a very good paper that I believe advances the state-of-the-art in learning for MIP solvers, an important area to enable us to better solve discrete optimization problems. The idea of learning the schedule of heuristics is interesting and novel as far as I am aware. Both the proposed learning task and the greedy learning method are simple and clean, which is appropriate for the scope of this paper, and it opens the door for future exploration of more sophisticated methods. The paper is overall well-written and does a good job at relating it to previous work. I particularly like the example plots that help the reader understand the context.

The computational setup is sound and adopts good practices for MIP computational research, such as using a tuned version of the MIP solver as a baseline and random seeds to account for inherent MIP solver variability. They also do a fair amount of cross-validation for the random graph instances. The final computational results show that this approach works well overall. They are not particularly striking especially compared to SMAC, but still represent significant improvements in the context of MIP solvers. Perhaps one aspect that feels missing from the paper are ablation experiments that could give us more insight on which components of this approach are important (e.g. does the ordering matter more than number of iterations?), but I believe this paper is good enough for NeurIPS without them, although there is one ablation experiment below in particular that I would like to suggest.

Overall I recommend this paper for acceptance, though I have a few requests:

1. In Section 3, the paper says: "The loop is terminated if a heuristic finds a new incumbent solution." This is used to explain that a good ordering can reduce solve time. However, in the function SCIPprimalHeuristics in solve.c in SCIP 7.0.1, I see that the heuristics are interrupted only if a feasible solution that cuts off the current node is found, otherwise it seems to continue. Please correct me if I an incorrect, but if this is the case, then the statement above would not be correct and overstate the value of choosing a good ordering. It is still valuable because you want to be able to cut off nodes early (which could happen fairly often, not just at infeasible nodes but also when finding a feasible solution that meets the local dual bound), but otherwise if you have a node where no heuristic is able to do that, then does the ordering really matter? Or is the benefit here solely to be able to cut off nodes with primal heuristics? In any case, I would like to ask the authors to double-check whether the statement about heuristics cited above is correct. If not, this should be corrected and clarified in the paper. It is fine if a better ordering is meant to produce earlier node cut offs, but this should be clear in the paper.

2. The notion of using the number of iterations needed to find any feasible solution instead of an incumbent or high-quality solution is counter-intuitive to me. I would be interested in a clarifying discussion on this in the paper. There are a few situations where I would expect considering the quality of the solution important, such as the case where feasibility is easy (i.e. when most heuristics should find a feasible solution early) and the case with improvement heuristics where a starting feasible solution is given. For example, for GISP, a schedule where a trivial heuristic that sets all variables to zero is the first one is always an optimal schedule. This does not happen in your case because you use diving and LNS heuristics, but I suspect that your approach is not robust to this type of behavior. I imagine that the dependency on the node is relevant here (e.g. the incumbent solution passed to the improvement heuristic might not be feasible for a particular node), but I could use some clarification as to why the cases above are not problematic. Could you add a discussion on this to the paper, and if possible, an ablation experiment in the appendix showing your attempt at rewarding for improving incumbents? In addition (and this is only out of curiosity, not a request), have you tried making your reward dependent on the quality of the feasible solution (and/or node cut off) rather than it just improving the incumbent?

3. Section 5 appears to be too vague. What is the special version of the MIP solver that collects multiple reward signals? How is the shadow mode improved from previous work? It is fine if the discussion is done in the appendix, but the description of how these challenges were overcome needs to be complete.


Writing notes:

- Many citations throughout the text are supposed to be parenthetical citations but are not.
- Section 2: It is worth to briefly define "incumbent" and its distinction to "feasible solution", since that is important later in the paper.
- Section 3: I suggest briefly mentioning here that the average iteration cost can be taken into account as described in Section 4, since this is an immediate concern that one might have when reading this section.


Typos:

- Line 143: Missing period before "Section 5".
- Line 275: "Furtheremore".
- Line 291: "Furtheremore".
- Line 323: "stricly".
- Line 337: "improvment".
- Table 2 caption: "Statictics"
- Formulation in Appendix B.4: In constraint (9), there is an extra ")" and extra space before $\mathcal{H}$. In constraint (12), $s_n$ should be $s_N$.
- Line 564 (Appendix): "unifromly".
- Line 567 (Appendix): "insatnces".
limitations_and_societal_impact: Societal impact was not discussed, but this is not particularly relevant.
review_title: null

Meta-review: Three of the reviewers felt this is a good paper and should be published.  One reviewer was negative and thought the paper had several shrotcommings.  

In this case, I feel this interest in the work outweighs the concerns. 
Decision: Accept (Poster)