Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors propose an actor-critic reinforcement learning algorithm to learn policies for large neighborhood search (LNS). A central innovation is action factorization to tackle the high-dimensional action space. Extensive empirical evaluations are provided, covering different solver integrations (SCIP and Gurobi) as well as generalizations to larger problem instances.

main_review: Post-rebuttal comments: I thank the authors for providing detailed answers to my questions. I will keep my score.

Originality: The main idea is straightforward given the MDP formulation of LNS. Two innovations come in the form of defining factorized action spaces and the model architecture design to reflect the factorization. They are relatively small novelties but the empirical results show their efficacy. 

This recent workshop paper [1] also applies RL to LNS. I think the authors should add it to the related discussion.

[1]: Neural Large Neighborhood Search, Ravichandra Addanki, Vinod Nair, Mohammad Alizadeh, https://openreview.net/forum?id=xEQhKANoVW 

Quality: For an empirical paper, the authors did a good job of providing thorough analyses in the following aspects. 
1. The problem instances are diverse and contain real-world problems in MIPLIB.
2. Two different solvers, SCIP and Gurobi, are used to show the generality of the proposed method.
3. I particularly like the generalization analysis. Integer programming solving typically needs good anytime performance, thus models able to generalize to larger instances are needed, which is a weakness of the previous imitation learning approach.

I have some questions regarding some details of the experiments. 
1. On line 276, different step limits are used to train policies for different problems. On line 304, it is mentioned that a 200s time limit is used. Given the time limit for repair is 2 seconds. Does that mean, for example for SC problems, the solving terminates before reaching the 200s time limit?
2. Does the time limit include all runtime, such as model inference, or only include solver invocation time?
3. How many random seeds did you use for the RL results?

Clarity: This paper is clear and easy to read. Good job!

Significance: As the learning for LNS starts getting popular, this paper is a nice addition focusing on applying RL. It is relevant to the learning-to-optimize community at NeurIPS. It is likely that future works will build on it.

limitations_and_societal_impact: Adequately addressed.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The last few years have seen numerous projects leveraging ML/RL to
speedup the optimization of ILP problems. Many of these attempts fall
under 2 categories:
  * RL driven branch-and-bound. By integrating a policy deeply inside
an ILP solver to drive the branch&bound process, these approaches have
the ability to extract a rich set of features from the solver and can
leverage them to inform the decisions made by the policy. The work of
Gasse et al. (Exact combinatorial optimization with graph convolution
neural networks)  is an example of such an approach.
* Large Neighborhood Search. This technique has been applied with
success to speedup the optimization of integer programs, in particular
in the work of Song et al. (A general large neighborhood search
framework for solving integer linear programs). This approach is
easier to implement since it doesn't require a deep integration into
an ILP solver (it merely calls one to solve subproblems).

This paper proposes a hybrid of the two approaches. It leverages a
neural network architecture similar to the Gasse GCN as well as the
featurization introduced by Gasse to build and inform a policy that
drives the large neighborhood search pioneered by Song et al. It also
offers some novel aspects, including a customized actor critic
algorithm to train the policy.
main_review: The paper is well written and easy to follow. It is organized clearly, and makes it easy for the reader to follow the approach taken, and provides all the relevant technical information needed to reproduce the results. It also cites all the relevant related work. 

The work makes 3 novel contributions:
* It bridges the gaps between two approaches to the field of RL driven ILP solver that have remained on parallel paths until now. The first approach modifies the branch&bound algorithm of existing ILP solvers and drives it using a trained policy. It requires a deep integration with the ILP solver, which is complex to implement but enables the extraction of a rich set of input features to inform the policy. The second approach relies on the large neighborhood search approach to generate small subproblems that can be solved quickly by an existing ILP solver. The ILP solver is used as a black box the solver which makes the implementation easier. This is an interesting idea since it has the potential to bring the best of both worlds to the table. I would be surprise if this didn't inspire other researchers to follow up in this direction.
* Inspired by previous work, it decomposes the actions into sub-actions (one per variable of the ILP) which are taken individually. The sub-actions are taken by individual policies which share parameters. The number of decisions the combined policy only needs to grow linearly with the number of variables and constraints of the ILP under consideration even through the action space grows exponentially in the size of the ILP. This is significant for two reasons: (i) and unlike previous work on ILP, this paper can leverage the entire action space and (ii) As far as I know, this is the first time that an action factorization scheme is successfully attempted on such a large action space, and could have numerous applications beyond ILP. 
* It introduces a novel variation of the actor critic algorithm to train the policy.

The paper appears technically sound, and the approach is extensively compared against the SCIP solver
and the results of Song et al. The authors demonstrate that the combination
of (i) their actor critic based training (ii) a richer set of features
and (iii) the GCN based architecture outperforms Song et al and the
SCIP solver. I would have liked to see an evaluation against Gasse et
al. as well as an ablation study to get a sense of the relative
importance of these 3 factors. This might also help figure out whether
the approach of Gasse or that of Song is the most promising overall.

The previous experiments were repeated, but this time using the Gurobi
solver. Again the hybrid approach came up on top. Since the extended
set of features provided by the SCIP solver are not available when
using the Gurobi solver, it seems that the richer featurization made
available by SCIP is not critical to the outcome. This is somewhat
counter intuitive, so any insights you have about why that is would
enrich the paper.

Last but not least, RL based approaches can be sensitive to initial
conditions. I'd love to see how much variance you get when
initializing your policy with different random weights.

Overall, this work makes solid albeit incremental progress in each of the 3 directions outlined above. If the authors can address my concerns I would gladly increase the score of my review.

limitations_and_societal_impact: The paper is candid about the limitations of the work: it lists them in section 6 and provides some ideas to overcome them in follow up work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes to augment large neighborhood search (LNS) method in integer programming solver (e.g., SCIP) with a learning component. in particular, the paper provides a MDP formulation, parameterization and RL training pipeline for the problem. The paper also shows significant empirical performance gains compared to other baseline methods.

===== updated post rebuttal ====

The authors have addressed most of my technical concerns in details. I would like to see such clarifications shown in the final draft of the paper should it be accepted. I would like to stick with my original evaluation.
main_review: =========== Originality ============

Though using learning for LNS has been touched on by a number of prior work, as discussed in the paper, this paper seems to be one of the first applications to show empirical progress of using RL for improving integer programming subroutines. Though idea-wise, applying RL to such problems is not extremely novel, the paper shows much solidity in overcoming the technical challenge of applying RL.

=========== Quality ============

The paper has relatively strong quality in terms of the technical challenge the proposed approach overcomes. Purely based on the comparative tables shown in Table 1-4, the new method enjoys strong empirical gains compared all other baselines (including 'static' baselines such as SCIP, as well as learned baselines). 

=========== Clarity ============

Overall, the paper is clearly written. The logic is clear and technical details are spelled out rather comprehensively. However, I do have a few technical details that need clarifying from the authors.

=========== Significance ============

The paper demonstrates some empirical success in applying RL to LNS. This bears some significance to the learning-to-optimize community, both in terms of the new approach it proposes, as well as the new domain (LNS) that the method applies. 

=========== Technical questions ============

I have a few tech questions:

1. From the paper, the MDP runs for T steps, where T is between 50 and 100. How is this value chosen in practice? Do we set a larger T for more difficult problems?

2. In addition to the step limit T, there is a time limit of 2s for each step (see line 295). If I understand correctly, this 2s time limit is for the computational time it takes to approximately solve the sub-problem, in order for the MDP to transition? Do the authors find the learning and MDP transition to be greatly impacted by the 2s time limit? In other words, when the time limit is larger, at each step the solver can solve the sub-problem more optimally and hence induce a different MDP transition dynamics.

3. From above, does this mean that if T=100, then the overall time constraint is 2*100=200s? What's the connection between this and the overall time limit of 200s (see line 306)?

3. Related to the above question, I am a bit confused about the relationship between the running of LNS and the overall solving procedure. SCIP by default uses a combination of LNS, B&B, cutting planes and other primal heuristics to solve a problem. Do the authors run LNS alongside other methods (e.g. B&B and cutting planes) when doing the training and evaluation? If so, then it seems that the MDP transition function should also depend on other components of the solver such as B&B, because they can also impact the statistics and hence states of the MDP. In that case, do we specify a time budget for the LNS and an overall budget for the whole solver (and hence a time limit for other components of the solver)?

4. Do training and evaluation phase have the same behavior? In other words, do we train the LNS RL agent under a 'cleaner' setup, where all other components of the solver are turned off, while at evaluation phase, we run LNS alongside other components? This is the approach taken by the cutting plane method by Tang et al, 2020 where at training time they train the RL agent on a pure cutting plane problem, while at evaluation phase they combine the agent with other methods to jointly solve problems.


5. Is the evaluation pipeline different from how LNS is typically used in a full IP solver? I think SCIP documentation says that primal heuristics such as LNS are run every once in a while, to plunge deep into the search tree and obtain good primal solutions. On the other hand, in the paper, the evaluation seems to rely mainly on primal heuristics, i.e., the LNS is run fairly frequently. Can the authors comment on this?

6. How are validation instances used exactly? Do you run RL training on the training instances, and early stop based on performance metrics on the validation instances?

7. Comparing results for the MC instances in Table 2 and Table 3, it seems that the RL agent achieves even 'better' performance on large instances measured by the gap. Table 3 shows that RL achieves 0% gap while on the training instances in Table 2, the gap is nonzero. Is this a surprising result? RL achieves zero gaps on large instances, is it because RL finds the best solution among all other baselines, and the gap metric as defined in the paper is effectively zero?
limitations_and_societal_impact: The authors have discussed their limitations in the conclusion section.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents a reinforcement learning based approach for tuning a heuristic method for integer programming solvers. It derives the method, then validates its performance computationally.
main_review: The paper is at times difficult to read. I would request that the authors attempt to polish the presentation.

I cannot assess the quality of proposed RL method, or the novelty with respect to the literature on heuristic learning. Instead, I will focus on the computational experiments. Here, the results seem promising, though I have a few questions about the methodology, as well as a concern with the baseline used (detailed below).

* L41: What does "externals" mean here?
* L108: IP is _not_ a subset of COP, it is in fact much more general.
* L137: "latter" seemingly refers to the incidence matrix, which does not make sense in context.
* L139: What if you do not have an initial solution? Often for COPs and IPs producing feasible solutions is very difficult. How does your method accomodate this, if at all?
* L182: "parametrize"
* Is a single model used throughout the computational section for each set of experiments? Or are different models trained for each problem class (SC, MIS, CA, MC, MIPLIB)?
* The usage of SCIP and Gurobi with default settings is a bit of a strawman. These solvers are configured to prove optimality quickly, while LNS is aimed solely at producing primal solutions. As such, the solvers will spend significant times improving the dual bound through cuts, presolve, etc. This renders wall time comparisons unfair to the solvers. A more fair comparison would configure the solvers to focus on the primal bound, using their respective "emphasis" parameters.
* L299: It would be good to compare also against the best dual bound available to get a sense of whether the produced solutions are close to optimal. You can get these dual bounds from SCIP or Gurobi. Without such a comparison, it is difficult to gauge how much improvement is offered by the new method.
* Table 1: "Constrains"
* L349: MIPLIB contains many instances which are not COPs.
* L356: If you have produced a new best solution for a MIPLIB instance, you should submit it upstream!
limitations_and_societal_impact: N/A
review_title: null

Meta-review: All reviewers agree that this paper applies RL (Q-actor-critic method) to learn Large Neighborhood Search policy for integer linear programming (ILP) and achieves strong performance compared to default policies in popular ILP solvers (SCIP and Gurobi) in multiple domains (SC, MIS, CA and MC) that have been widely used in previous works. Some of its proposed algorithm is novel (e.g., training an independent policy for each variable, new network architecture design), the presentation is clear, and experiments are well-designed and convincing, showing the final performance the community cares (i.e., the quality of the solution given fixed wall clock time). The authors also address many of the reviewers' concerns in the rebuttal, by including comparison with Gasse et al and different setting of the ILP solvers, further solidifying the work. 

Overall, I happily accept the work. It can be a strong contribution to the learning-to-optimize community and I would highly encourage the authors to open source the code. 
Decision: Accept (Spotlight)