Learning Large Neighborhood Search Policy for Integer Programming
Year: 2021

Abstract:
We propose a deep reinforcement learning (RL) method to learn large neighborhood search (LNS) policy for integer programming (IP). The RL policy is trained as the destroy operator to select a subset of variables at each step, which is reoptimized by an IP solver as the repair operator. However, the combinatorial number of variable subsets prevents direct application of typical RL algorithms. To tackle this challenge, we represent all subsets by factorizing them into binary decisions on each variable. We then design a neural network to learn policies for each variable in parallel, trained by a customized actor-critic algorithm. We evaluate the proposed method on four representative IP problems. Results show that it can find better solutions than SCIP in much less time, and significantly outperform other LNS baselines with the same runtime. Moreover, these advantages notably persist when the policies generalize to larger problems. Further experiments with Gurobi also reveal that our method can outperform this state-of-the-art commercial solver within the same time limit.

heading: 1 Introduction
text: Combinatorial optimization problems (COPs) have been widely studied in computer science and operations research, which cover numerous real-world tasks in many fields such as communication, transportation and manufacturing [1]. Most COPs are very difficult to solve efficiently due to their NP-hardness. The performance of classic methods, including exact and heuristic algorithms [2], is generally limited by hand-crafted policies that are costly to design, since considerable trial-and-error and domain knowledge are needed. On the other hand, it is common in practice that similar instances with shared structure are frequently solved, and differ only in data that normally follows a distribution [3]. This provides a chance for machine learning to automatically generate heuristics or policies. In doing so, the learned alternatives are expected to save massive manual work in algorithm design, and raise the performance of the algorithm on a class of problems.
Recently, a number of works apply deep (reinforcement) learning to automatically design heuristic algorithms, either in constructive or improving fashion. Different from construction heuristics that sequentially extend partial solutions to complete ones [4, 5, 6, 7, 8, 9, 10, 11], learning improvement heuristics can often deliver high solution quality by iteratively reoptimizing an initial solution using
∗Wen Song is the corresponding author.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
local operations [12, 13, 14]. In this line, some methods are developed under the Large Neighborhood Search (LNS) framework [15, 16], which is a powerful improving paradigm to find near-optimal solutions for COPs.
However, the above methods are restricted to specific problem types, and cannot generalize to those from different domains. This motivates the studies of learning to directly solve Integer Programs (IPs), which is very powerful and flexible in modelling a wide range of COPs. The standard approach to solve IPs is branch-and-bound (B&B) [17], which lies at the core of common solvers such as SCIP, Gurobi, and CPLEX. Thus, most of existing methods improve the performance of a solver on a distribution of instances, by training models for critical search decisions in B&B such as variable and node selection [18, 19, 20]. Nevertheless, these methods are generally limited to small instances and require sufficient interface access to the internal solving process of the solvers.
This paper mainly tackle the issue that how to improve a solver from externals such that it can find high-quality solutions more quickly? In specific, we propose a high-level, learning based LNS method to solve general IP problems. Based on deep reinforcement learning (RL), we train a policy network as the destroy operator in LNS, which decides a subset of variables in the current solution for reoptimization. Then we use a solver as the repair operator, which solves sub-IPs to reoptimize the destroyed variables. Despite being heuristic, our method can effectively handle the large-scale IP by solving a series of smaller sub-IPs. Moreover, complex interface to the solver’s internal logic is not required. However, the above RL task is challenging, mainly because the action space, i.e., number of variable subsets at each LNS step, is exponentially large. To resolve this issue, we represent all the subsets by factorizing them into binary decisions on each variable, i.e., whether a variable should be destroyed. In doing so, we make it possible to learn a policy to select any subset from large discrete action spaces (at least 21000 candidates in our experiments). To this end, we design a Graph Neural Network (GNN) based policy network that enables learning policies for each variable in parallel, and train it by a customized actor-critic algorithm.
A recent work [21] also attempts to learn LNS policy to solve IP problems, and we generalize this framework to enable learning more flexible and powerful LNS algorithms. One limitation of [21] is that it hypothesizes a constant cardinality of the destroyed variable subset at each LNS step, which is a predefined hyperparameter. However, the number and choice of optimized variables at each step should be adaptive according to instance information and solving status, which is achieved in our method. In doing so, the LNS policies trained by our method significantly outperform those trained by the method in [21].
We evaluate our method on four NP-hard benchmark problems with SCIP as the repair solver. Extensive results show that our method generally delivers better solutions than SCIP with mere 1/2 or 1/5 of runtime, and significantly outperforms LNS baselines with the same runtime. These advantages notably persist when the trained policies are directly applied to much larger problems. We also apply our LNS framework to Gurobi, which shows superiority over the solver itself and other baselines.

heading: 2 Related work
text: In this section, we briefly review existing works related to ours. We first describe two main streams of learning based methods to solve COPs, and then introduce the literature that study RL with large discrete action space, which is also an essential issue we confront in this paper.
Learning to solve specific COPs. Quite a few works attempt to learn heuristics to solve certain types of COPs. Compared to construction ones, methods that learn improvement heuristics can often deliver smaller optimality gap, by training policies to iteratively improve the solution. Chen and Tian [12] propose to learn how to locally rewrite a solution; Wu et al. [13] train policies to pick the next solution in local moves; Lu et al. [14] learn to select local operators to reform a solution. These methods are generally limited by simple local operations. A few methods learn more powerful operators under the LNS framework. Hottung and Tierney [15] train an attention model to repair the solution every time it is broken by a predefined destroy operator. Similarly, Gao et al. [16] combine GNN and Recurrent Neural Network to learn a reinsertion operator to repair sequence-based solution. However, all the above methods are limited to specific problem types, e.g., the LNS methods in [15, 16] are designed only for routing problems. In contrast, this paper aims to solve general IP problems with a high-level LNS framework and raise its performance by learning better policies.
Learning to solve IP problems. Most of learning based methods for IPs aim to improve inner policies of B&B algorithm. For example, He et al. [18] learn to explore nodes in B&B tree by imitating an oracle. Gasse et al. [20] train a GNN model to predict the strong branching rule by imitation learning. Khalil et al. [19] predict the use of primal heuristics by logistic regression. Other components of B&B are also considered to improve its practical performance, such as learning to select cutting planes by Tang et al. [22], predicting local branching at root node by Ding et al. [23] or refining the primal heuristic and branching rule concurrently by Nair et al. [24]. Different from these works, we employ RL to improve practical performance of IP solvers especially for large-scale problems, without much engineering effort on interfacing with inner process of solvers.2 This is also noted in [21], which proposes to combine learning and LNS to solve IPs. However, a major drawback of this method is that the subsets of destroyed variables are assumed to be fixed-sized, which limits its performance. In contrast, our LNS framework allows picking variable subsets in a more adaptive way, and thus empowers learning broader classes of policies.
RL with large action spaces. Learning with large-sized, high-dimensional discrete action spaces is still intricate in current RL research. In this direction, Pazis and Parr [25] use binary format to encode all actions, and learn value functions for each bit. Tavakoli et al. [26] design neural networks with branches to decide on each component of the action. Besides, Dulac-Arnold et al. [27] and Chandak et al. [28] update the action representation by solving continuous control problems so as to alleviate learning complexity via generalization. Other similar works can be found in [29, 30, 31]. However, we note that all these methods are generally designed for tasks with (discretized) continuous action spaces, which are relatively low-dimensional and small-sized (at most 1025 as in [26]). In contrast, action spaces in our scenario are much larger (at least 21000). In this paper, we propose to factorize the action space into binary actions on each dimension, and train the individual policies in parallel through parameter sharing.

heading: 3 Preliminaries
text: Integer Program (IP) is typically defined as argminx{µ⊤x|Ax ≤ b;x ≥ 0;x ∈ Zn}, where x is a vector of n decision variables; µ ∈ Rn denotes the vector of objective coefficients; the incidence matrix A ∈ Rm×n and right-hand-side (RHS) vector b ∈ Rm together define m linear constraints. With the above formulation, the size of an IP problem is generally reflected by the number of variables (n) and constraints (m).
Large Neighborhood Search (LNS) is a type of improvement heuristics, which iteratively reoptimizes a solution by the destroy and repair operator until certain termination condition is reached [32]. Specifically, the former one breaks part of the solution xt at step t, then the latter one fixes the broken solution to derive the next solution xt+1. The destroy and repair operator together define the solution neighborhood N (xt), i.e., solution candidates that can be accessed at time step t. Compared to typical local search heuristics, LNS is more effective in exploring the solution space, since a larger neighborhood is considered at each step [32]. Most of existing LNS methods rely on problem specific operators, e.g., removal and reinsertion for solutions with sequential structure [33, 34]. Instead, we propose a RL based LNS for general IP problems, with the learned destroy operator to select variables for reoptimization at each step.

heading: 4 Methodology
text: In this section, we first formulate our LNS framework as a Markov Decision Process (MDP). Then, we present the factorized representation of the large-scale action space, and parametrize the policy by a specialized GNN. Finally, we introduce a customized actor-critic algorithm to train our policy network for deciding the variable subset.

heading: 4.1 MDP formulation
text: Most of existing works learn LNS for specific problems [15, 16], which rely on extra domain knowledge and hinder their applicability to other COPs. In this paper, we apply LNS to general IP
2Nevertheless, our method can also work with solvers enhanced by the above methods as repair operators.
problems, in which RL is employed to learn a policy that at each step, selects a variable subset from the solution to be reoptimized. We formulate this sequential decision problem as a discrete-time MDP. Specifically, we regard the destroy operator as the agent and the remainder in LNS as the environment. In one episode of solving an IP instance, the MDP can be described as follows:
States. A state st ∈ S at each LNS step needs to not only reflect the instance information but also the dynamic solving status. For the former, we represent it by static features of variables and constraints, along with the incidence matrix in an instance. The latter is represented by dynamic features, including the current solution xt and dynamic statistics of incumbent solutions up to step t. Specifically, both the current and incumbent solution at t = 0 are defined as the initial solution x0.
Actions. At each state st, an action of the agent is to select a variable subset at from all candidate subsets A for reoptimization. Transition. The repair operator (i.e., an IP solver) solves the sub-IP, where only the variables in action at are optimized with the others equaling to their current values in xt. Accordingly, the next state st+1 is deterministically attained by updating st with the new solution:
xt+1 = argmin x
{µ⊤x|Ax ≤ b;x ≥ 0;x ∈ Zn;xi = xit,∀xi /∈ at}. (1)
Rewards. The reward function is defined as rt = r(st, at) = µ⊤(xt − xt+1), which is the change of the objective value. Given the step limit T of the interaction between the agent and environment, the return (i.e., cumulative rewards) from step t of the episode is Rt = ∑T k=t γ
k−trk, with the discount factor γ ∈ [0, 1]. The goal of RL is to maximize the expected return E[R1] over all episodes, i.e., the expected improvement over initial solutions, by learning a policy.
Policy. The stochastic policy π represents a conditional probability distribution over all possible variable subsets given a state. Starting from s0, it iteratively picks an action at based on the sate st at each step t, until reaching the step limit T .
An example of the proposed LNS framework solving an IP instance is illustrated in Figure 1, in which the GNN based policy network has the potential to process instances of any size via sharing parameters across all variables.

heading: 4.2 Action factorization
text: Given the vector of decision variables x in an IP instance, we gather all its elements in a set X = {x1, x2, . . . , xn}. Accordingly, we define the action space A = {a|a ⊆ X}, which contains all possible variable subsets. Thus our RL task is learning a policy to select at ∈ A for reoptimization at each step t of LNS, and the cardinality of at (i.e., |at|) reflects the destroy degree on the solution. Apparently, the size of the combinatorial space A is 2n, which grows exponentially with the number
of variables n. This prevents the application of general RL algorithms on large-scale problems, since they require an explicit representation of all actions and exploration over such huge action space.
As a special case under our LNS framework, Song et al. [21] assumes the action space as the subspace of A that merely contains equal-sized variable subsets, that is, Az = {az|az ∈ A, |az| = z}. In doing so, they instead learn classifying variables into groups of equal size, to optimize each iteratively. Despite the good performance on some COPs, such action representation with the fixed destroy degree makes the LNS search inflexible and thus limits the class of policies that can be learned. Also, the issue of large action space still exists, since the patterns to group variables could be combinatorial.
To involve larger action space and in the meanwhile keep the learning tractable, we factorize the combinatorial action space A into elementary actions on each dimension (i.e., variable). Specifically, we denote ait ∈ {xi, ∅} as the elementary action for variable xi at step t. It means that xi is either selected for reoptimization, or not selected and thus fixed as its value in the current solution. With such representation, any variable subset can also be expressed as at = ⋃n i=1 a i t. Therefore, our task can be converted into learning policies for binary decisions on each variable. This enables exploration of large action space by traversing binary action spaces, the number of which grows linearly with the number of variables. To this end, we factorize the original policy as below:
π(at|st) = ∏n
i=1 πi(ait|st), (2)
which expresses π(at|st), the probability of selecting an action, as the product of probabilities of selecting its elements. Since ∑ ait∈{xi,∅}
πi(ait|st) = 1, ∀ i ∈ {1, . . . , n}, it is easy to verify that the sum of probabilities of all actions in A still equals to 1, i.e., ∑ at∈Aπ(at|st) = 1. Based on this factorization, we can apply RL algorithms to train policies πi for each variable xi. In the following subsections, we first parametrize the policy π by a GNN πθ, and then train it by a customized actor-critic algorithm.

heading: 4.3 Policy parametrization
text: Policy networks in deep RL algorithms are generally designed to map states to probabilities of selecting each action. In our case, the complexity of directly training such policy networks could exponentially increase with the growing number of variables. Based on Equation (2), an ad hoc way to reduce the complexity is training individual policies for each dimension. However, the IP problems in our study comprise a high volume of variables, and it is unmanageable to train and store this many networks. Learning disjoint policies without coordination could also suffer from convergence problem as shown in [35]. Another possible paradigm could be constructing a semi-shared network, in which all dimensions share a base network and derive outputs from separate sub-networks. Following a similar idea, Tavakoli et al. [26] design a network with branches for deep Q-learning algorithms. However, it is not suitable for IP problems, since the number of sub-networks is only predefined for single problem size, without the generalization ability to different-sized instances.
To circumvent the above issues, we design a GNN based policy network to share parameters across all dimensions, and also enable generalization to any problem size [36, 37]. To this end, we first describe the state st by a bipartite graph G = (V, C,A), where V = {v1, · · · , vn} denotes variable nodes with features V ∈ Rn×dv ; C = {c1, · · · , cm} denotes constraint nodes with features C ∈ Rm×dc ; A ∈ Rm×n denotes the adjacency matrix with aji being the weight (or feature) of the edge between nodes cj and vi, which is practically the incidence matrix A in an IP instance. This state representation is similar to the one in [20], which depicts the status in B&B tree search to learn branching policy. We extend its usage outside the solver to reflect the solving process in our LNS framework.
Then, we parametrize the policy as πθ(at|st) by a graph convolutional network (GCN), a GNN variant broadly used in various tasks [38, 39, 40]. The architecture of our design is illustrated in Appendix A.1, with the graph convolution layer expressed as below:
C(k+1) = C(k) + σ ( LN ( AV(k)W (k)v )) ,
V(k+1) = V(k) + σ ( LN ( A⊤C(k+1)W (k)c )) , k = 0, . . . ,K
(3)
where W (k)v ,W (k) c ∈ Rdh×dh are trainable weight matrices in the k-th layer; V(k) = [v(k)1 · · ·v (k) n ]⊤ and C(k) = [c(k)1 · · · c (k) m ]⊤ are node embeddings for variables and constraints respectively in k-th
layer; LN and σ(·) denote layer normalization and Tanh activation function respectively. In particular, we linearly project raw features of variables and constraints into the initial node embeddings V(0) and C(0) with dh dimensions (dh = 128), and keep this dimension through all layers. After K iterations of convolution (K = 2), the embeddings for the two clusters of heterogeneous nodes are advanced as {vKi }ni=1 and {cKj }mj=1. We finally process the former by a multi-layer perceptron (MLP) with a single-value output activated by Sigmoid. In this way, the output value can represent the probability of a variable being selected, i.e., πi(ait|st) = πθ(ait|st) = MLP(vKi ),∀ i ∈ {1, . . . , n}, such that we can conduct Bernoulli sampling accordingly on each variable and attain the subset. In this paper, we structure the MLP by two hidden layers, which have 256 and 128 dimensions respectively and are activated by Tanh.

heading: 4.4 Training algorithm
text: Actor-critic is one of the policy gradient methods developed from REINFORCE [41]. It parametrizes state-value or action-value function as a critic network to estimate the expected return. In this paper, we adopt Q-actor-critic with Qω(s, a) ≈ Q(s, a) = E[Rt|st = s, at = a], where ω is the parameter set to be learned. In doing so, Qω (i.e., the critic) can be updated through bootstrapping and leveraged in the training of the policy network (i.e., the actor). Specifically, the loss functions for the critic and the actor are defined as follows:
L(ω) = ED[(γQω(st+1, at+1) + rt −Qω(st, at))2], (4)
L(θ) = ED[Qω(st, at) log πθ(at|st)], (5)
where the experience replay buffer D contains transitions (st, at, rt, st+1, at+1), which are collected during solving a batch of instances. γQω(st+1, at+1) + rt is the one-step temporal-difference (TD) target to update the critic.
The above Q-actor-critic is not directly applicable to the primitive high-dimensional action spaces in our IP problems. To learn the factorized policies we designed in Section 4.2, one way is to customize it by training an actor and critic on each dimension, and updating the parameters via the loss functions:
L̃(ω) = ED[ 1
n ∑n i=1 (γQω(st+1, a i t+1) + rt −Qω(st, ait))2], (6)
L̃(θ) = ED[ 1
n ∑n i=1 Qω(st, a i t) log(πθ(a i t|st))], (7)
where the parameter-sharing Qω is used across all dimensions as the actor πθ, i.e., Qω(st, ait) = Qi(st, a i t),∀ i ∈ {1, . . . , n}. However, our experiments show that the critic trained by bootstrapping on each elementary action delivers inferior performance, which is similar to the finding in [26]. Intuitively, this may stem from excessive action-value regressions with one single neural network. To circumvent this issue, we keep the global TD learning in Equation (4) and adjust elementary policies by the Q value of the state-action pair (st, at), such that:
L̃(θ) = ED[Qω(st, at) ∑n
i=1 log(πθ(a
i t|st))], (8)
where the critic Qω is structured in the same manner as πθ, except that: 1) we add a binary value to the raw features of each variable ait to indicate whether it is selected; 2) we use MLP to process the graph embedding, which aggregates the embeddings of variables by mean-pooling, to output a real value that represents the Q value.
Clipping & masking. To enhance exploration, we clip the probabilities of being selected for each variable in a range [ϵ, 1− ϵ], ϵ <0.5. It helps avoid always or never traversing some variables with extreme probabilities. We also do not consider empty or universal sets of variables, which lead to unsuitable sub-IPs. Though the chance to select these two sets are low, we mask them by resampling.
Details of the training algorithm are given in Appendix A.2. Besides the policy network we designed in Section 4.3, we also adopt this algorithm to train a MLP based semi-shared network similar to the one in [26], which indicates that the fully-shared one (ours) is more suitable for IP problems. More details are given in Appendix A.3.

heading: 5 Experimental results
text: We perform experiments in this section on four NP-hard benchmark problems: Set Covering (SC), Maximal Independent Set (MIS), Combinatorial Auction (CA) and Maximum Cut (MC), which are widely used in existing works. Our code is available.3
Instance generation. We generate SC instances with 1000 columns and 5000 rows following the procedure in [42]. MIS instances are generated following [43], where we use the Erdős-Rényi random graphs with 1500 nodes and set the affinity number to 4. CA instances with 2000 items and 4000 bids are generated according to arbitrary relationships in [44]. MC instances are generated according to Barabasi-Albert random graph models [45], with average degree 4, and we adopt graphs of 500 nodes. For each problem type, we generate 100, 20, 50 instances for training, validation, and testing. In addition, we double and quadruple the number of variables and generate 50 larger and even larger instances respectively for each problem, to verify the generalization performance. We name the instance groups and display their average sizes in Table 1.
Features. To represent an instance, we extract static features of variables and constraints, along with the incidence matrix after presolving by the solver at the root node of B&B. In this way, redundant information could be removed and the extracted features could be more clear and compact in reflecting the problem structure. For the dynamic features, we record for each variable its value in the current solution and incumbent, as well as its average value in all incumbents to represent the solving status of LNS. Specially, at the step t = 0, the average incumbent values are naturally attained from the initial solution, i.e., the incumbent at the root node. Note that in practice, we concatenate the static and dynamic features for each variable, and attach them (V) to variable nodes in the bipartite graph. The features of constraints (C) and the incidence matrix (A) are attached to the constraint nodes and edges, respectively. Detailed description of the above features are available in Appendix A.4.
Hyperparameters. We use the state-of-the-art open source IP solver SCIP (v6.0.1) [46] as the repair operator, which also serves as a major baseline. We run all experiments on an Intel(R) Xeon(R) E5-2698 v4 2.20GHz CPU. For each problem, we train 200 iterations, during each we randomly draw M=10 instances. We set the training step limit T=50, 50, 70, 100 for SC, MIS, CA and MC respectively. The time limit for repair at each step is 2 seconds, unless stated otherwise. We use ϵ=0.2 for probability clipping. For the Q-actor-critic algorithm, we set the length of the experience replay TM , the number of updating the network U=4 and the batch size B=TM/U . We set the discount factor γ=0.99 for all problems, and use Adam optimizer with learning rate 1× 10−4. To show the applicability of our method on other solvers, we have also performed experiments where Gurobi [47] is used as the repair solver, which will be discussed in Section 5.3.

heading: 5.1 Comparative analysis
text: Baselines. We compare our method with four baselines:
• SCIP with default settings.
• U-LNS: a LNS version which uniformly samples a subset size, then fills it by uniformly sampling variables. We compare with it to show that our method can learn useful subset selection policies.
• R-LNS: a LNS version with hand-crafted rule proposed in [21], which randomly groups variables into disjoint equal-sized subsets and reoptimizes them in order.
• FT-LNS: the best-performing LNS version in [21], which applies forward training, an imitation learning algorithm, to mimic the best demonstrations collected from multiple R-LNS runs.
3https://github.com/WXY1427/Learn-LNS-policy
Following [21], we tune the group number of R-LNS (and FT-LNS since it imitates R-LNS) from 2 to 5, and apply the best one to each problem. To train FT-LNS, we collect 10 demonstrations for each instance, and tune the step limit to 20 for SC, MIS, CA and 50 for MC, which perform the best. Same as our method, all LNS baselines also use SCIP as the repair operator with 2s time limit. To compare solution quality, we use the average objective value and standard deviation over the 50 testing instances as metrics. Also, since all problems are too large to be solved optimally, we measure the primal gap [19] to reflect the difference between the solution x̃ of a method to the best one x∗ found by all methods. We compute |µ⊤x̃− µ⊤x∗|/max{|µ⊤x̃|, |µ⊤x∗|} · 100% for each instance, then average the gaps for all 50 ones. Below we report the results on testing instances of the same sizes as in training.
In this paper, we aim to improve an IP solver from externals to enable more efficient search of highquality solutions in a broad range of COPs. To this end, we compare all methods for time-bounded optimization with the same 200s time limit, and further allow SCIP to run for longer time, i.e., 500s and 1000s. The results are gathered in Table 2. As shown, our method significantly outperforms all baselines on all problems with the same 200s time limit. It is notable that FT-LNS is inferior to R-LNS which yields demos for its imitation learning. The reason might be that FT-LNS only mimics the random demos of short (training) step limits, and hence lacks the ability of generalizing to longer steps. This limitation might hinder its application since in practice, IP problems are often solved in an anytime manner with flexible time/step limits. In contrast, our method avoids this myopic issue by RL training. In Appendix A.5, we also show that FT-LNS can outperform R-LNS with the same number of LNS steps as in training. Another key observation from Table 2 is that with longer time limits, SCIP is able to find better solutions than the three LNS baselines on SC, MIS and CA. However, our method still surpasses SCIP (500s) on all problems and SCIP (1000s) on MIS, CA and MC.

heading: 5.2 Generalization analysis
text: Training deep models that perform well on larger problems is a desirable property for solving IPs, since practical problems are often large-scale. Here we evaluate such generalization performance on instances with the average sizes listed in Table 1. We run our method and baselines on these instances with the same time limits as those in the experiments for comparative analysis. For our method and FT-LNS, we directly apply the policies trained in Section 5.1.
All results are displayed in Table 3. It is revealed that with the same 200s time limit, while the LNS baselines only outperform SCIP on specific problems, our LNS policies trained on small instances are consistently superior to all baselines, showing a stronger generalization ability. Also, our method delivers much smaller gaps, e.g., at least 38.35% smaller than that of SCIP (200s), which are more prominent than the results in Section 5.1. It indicates that our policies are more efficient in improving SCIP for larger instances solely by generalization. When SCIP runs with 500s, it surpasses all three LNS baselines on SC2, CA2 and SC4, while our method can still deliver better results on all problems. Compared to SCIP with 1000s, our method is inferior on SC2, CA2 and SC4 but apparently better on the remaining 5 instance groups.
We further test all methods with 500s time limit except SCIP, which is allowed to run with 1000s. All results are gathered in Table 4. It is revealed that our method still has clear advantages over others on all problems, and consistently outperforms SCIP with mere 1/2 runtime. We find that LNS baselines can outperform SCIP on some problems, especially the three largest ones, i.e., MIS4, CA4 and MC4. It suggests that as the problem size becomes larger, LNS could be more effective to deliver high-quality solutions by solving successive sub-IPs which have much lower complexity than the original problem. On the other hand, our method outperforms all LNS baselines, showing that it is more efficient in improving the solution. In summary, our LNS policies learned on small instances generalize well to larger ones, with a persistent advantage over other methods.

heading: 5.3 Experiments with Gurobi
text: Our LNS framework is generally applicable to any IP solver. Here we evaluate its performance by leveraging Gurobi (v9.0.3) [47] as the repair operator. Gurobi is a commercial solver and offers less interfaces to the internal solving process. Thus, we condense the static features of variables to mere objective coefficients, and attain the initial solution by running the solver with 2s time limit. During training, we set the step limit T=50 with 1s time limit for Gurobi at each step. For FT-LNS, we use the same 1s time limit, and tune the group number to 2 in all problems for its best performance. The remaining settings are the same as those with SCIP. During testing, we let all methods run with 100s time limit, roughly twice as much as that for training. To save space, we only show results of two instance groups for each problem in Table 5.4 Despite the shorter runtime, we find that Gurobi (100s) generally attains lower objective values than SCIP (200s), showing a better performance to solve IP
4Specially, we observe that MIS is fairly easy for Gurobi (76 out of 100 instances can be solved optimally with average 40s). Thus, we evaluate this problem with less time limit and show the results in Appendix A.6.
problems. Hence, the LNS baselines lose their advantages over the solver on several problems, e.g., SC, CA and SC2. In contrast, our method outperforms Gurobi across all problems, showing good performance on instances of both training and generalization sizes. Moreover, our method can be well applied to much larger instances and we provide this evaluation in Appendix A.7.

heading: 5.4 Testing on MIPLIB
text: The mixed integer programming library (MIPLIB) [48] contains real-world COPs from various domains. Since the instances in MIPLIB are severely diverse in problem types, structures and sizes, it is not a very suitable testing set to directly apply learning based models and thus seldom used in the related works. We evaluate our method (with Gurobi as the repair solver) on this realistic dataset, in the style of active search on each instance [5, 6], and compare it to SCIP and Gurobi. Results show that: 1) with the same 1000s time limit, our method is superior to both solvers on 24/35 instances and comparable to them on 9/35 instances; 2) our method with 1000s time limit outperforms both solvers with 3600s time limit on 13/35 instances; 3) for an open instance, we find a better solution than the best known one. More details are provided in Appendix A.8.

heading: 6 Conclusions and future work
text: We propose a deep RL method to learn LNS policy for solving IP problems in bounded time. To tackle the issue of large action space, we apply action factorization to represent all potential variable subsets. On top of it, we design a parameter-sharing GNN to learn policies for each variable, and train it by a customized actor-critic algorithm. Results show that our method outperforms SCIP with much less time, and significantly surpasses LNS baselines with the same time. The learned policies also generalize well to larger problems. Furthermore, the evaluation of our method with Gurobi reveals that it can effectively improve this leading commercial solver. For limitations, since we mainly aim to refine off-the-shelf solvers for general IP problems, it is not sufficient to conclude that our method can transcend specialized and highly-optimized algorithms in different domains. In a practical view, our method could be a choice when new IP problems are produced with little expertise, or extensive dependence on domain knowledge is expected to be avoided. Also, our LNS policies are more suitable to improve solvers for large-scale problems in bounded time, but cannot provide optimality guarantee. For future work, we will apply our method to other (mixed) IP problems, and extend it by combining with other learning techniques for IPs, such as learning to branch.

heading: Acknowledgments
text: This research was conducted at Singtel Cognitive and Artificial Intelligence Lab for Enterprises (SCALE@NTU), which is a collaboration between Singapore Telecommunications Limited (Singtel) and Nanyang Technological University (NTU) that is supported by A*STAR under its Industry Alignment Fund (LOA Award number: I1701E0013). Wen Song was supported by the National Natural Science Foundation of China under Grant 62102228, and the Young Scholar Future Plan of Shandong University under Grant 62420089964188. Zhiguang Cao was supported by the National Natural Science Foundation of China under Grant 61803104.

Review summaries:
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.

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. 

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.