Learning Large Neighborhood Search Policy for Integer Programming
Authors: Yaoxin Wu
Wen Song
Zhiguang Cao
Jie Zhang
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Deep Reinforcement Learning
Integer Programming
Large Neighborhood Search

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.

Learning Large Neighborhood Search Policy for Integer Programming
Yaoxin Wu
Wen Song*
SCALE@NTU Corp Lab
Shandong University
Nanyang Technological University, Singapore wuyaoxinEntu. www.inntttuuuuuuaa....em 5g
Qingdao, China wensong@email sdu. edu.
Zhiguang Cao
Jie Zhang
Singapore Institute of Manufacturing Technology STAR, Singapore zhiguangcao@@uutlook.c com
Nanyang Technological University Singapore zhangj @ntu. edu.sg
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 represent all subsets by factorizing them into binary decisions
this challenge, on each variable. We then design a neural network to learn policies for each variable in parallel, trained by customized actor-critic algorithm. We evaluate the proposed method on four representative IP problems. Results show that it can find better solutions than SCIP much less time, and significantly outperform other LNS baselines with the same runtime. Moreover, these advantages notably persist when the policies generalize larger problems. Further experiments with Gurobi also reveal that our method can outperform this state-of-the-an commercial solver within the same time limit.
Introduction
Combinatorial optimization problems (COPs) have been widely studied computer science and operations research, which cover numerous real-world tasks in many fields such communication. transportation and manufacturing [l. 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, is common in practice that similar instances with shared structure are frequently solved, and differ only in data that normally follows distribution B]. 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 the algorithm on class of problems.
Recently, a number of works apply deep (reinforcement) learning to automatically design heuristic algorithms, either in constructive improving fashion. Different from construction heuristics that sequentially extend partial solutions to complete ones [ 6 7 g 9 10 [1] learning improvement heuristics can often deliver high solution quality by iteratively reoptimizing initial solution using
Wen Song is the corresponding author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

local operations 12 13 In this line, some methods are developed under the Large Neighborhood Search (LNS) framework [5] 16]. which is a powerful improving paradigm find near-optimal solutions for COPs.
However, the above methods are restricted to specific problem types, and cannot generalize those from different domains. This motivates the studies of learning to directly solve Integer Programs (IPs), which very powerful and flexible in modelling a wide range of COPs. The standard approach to solve IPs is branch-and-bound (B&B) [7.. 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 [8] 19 20). Nevertheless, these methods are generally limited small instances and require sufficient interface access to the internal solving process of the solvers.
This paper mainly tackle the issue that how improve 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 series of smaller sub-IPs. Moreover. complex interface to the solver's s internal logic is not required. However, the above RL task is challenging, mainly because the action space, i.c., 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 variable should be destroyed. In doing so, we make it possible to learn a policy to select any subser from large discrete action spaces (at least 2 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 customized actor-critic algorithm.
A recent work 21 also attempts 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 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.
2 Related work
In this section, we briefly review existing works related to ours. We first describe two main streams of learning based methods 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 few works attempt learn heuristies 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. [4] 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 Tiemny [5] 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-basee 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. contrast, this paper aims to solve general IP problems with high-level LNS framework and raise its performance by learning better policies.
2

---

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. [1]] learn to explore nodes in B&B tree by imitating an oracle. Gasse et al. 20 train GNN model to predict the strong branching rule by
imitation learning. Khalil et al. [9 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 interfacing with inner process of solvers This is also noted in [2I] 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 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-Amold et al. [27] and Chandak et al. (28) update the action representation by solving continuous control problems as alleviate learning complexity via generalization. Other similar works can be found [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 much larger (at least 2000). 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.
Preliminaries
Integer Program (IP) is typically defined as arg min fu T Al S b; 0; Z"), where is a vector of n decision variables; μ E R" denotes the vector of objective coefficiens;; the incidence matrix A x and right-hand-sidde (RHS) vector 6 E R" 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 reopti- mizes a solution by the destroy and repair operator until certain termination condition is reached
32. Specifically, the former one breaks part of the solution 2y at step 4, then the latter one fixes the broken solution derive the next solution 11+1- The destroy and repair operator together define the solution neighborhood N (zz), i.c., solution candidates that can be accessed at time step t. Compared typical local search heuristics, LNS more effective in exploring the solution space, since 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.
4 Methodology
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.
4.1 MDP formulation
Most of existing works learn LNS for specific problems [15] [6], which rely on extra domain knowledge and hinder their applicability to other COPs. In this paper, we apply LNS to general IP
Nevertheless, our method can also work with solvers enhanced by the above methods repair operators.
3

---

Static
Update dymamii festures
dh Vartable featcres
Destroy opecaior
min,ur) + ( + M Ma
Sample
a,1d, + Fa282 B1x + BiaKa b,
3 4
SOLVER (Repair operiaad
Incidence matrix A
02 022 + Kg 22 I b2
mi
as + 0az dgyKs AscK4 I by
de
IP formilation
Constraint features
formulation
State Az
GNN based Policy
Environment
Variable to optimize
Current solution value
Reoptimized solution value
An example of LNS solving an instance with 4 variables and 3 constraints. Given the current state characterized by static and dynamic features, the RL agent (destroy operator) selects subset of variables from the current solution be reoptimized. Then this action influences the environment, through which a sub-IP is formulated and solved by the repair operator (i.e., solver). As feedbacks, the new solution updates the state and a reward is provided to the agent. The above process is repeated until reaching the time limit.
Figure 1:
problems, in which RL is employed learn policy that each step, selects variable subset from the solution to be reoptimized. We formulate this sequential decision problem as a discrete-time MDP. Specifically, regard the destroy operator as the agent and the remainder in LNS the environment. In one episode of solving an IP instance, the MDP can be described as follows:
States. A state 8t E S at each LNS step needs to not only reflect the instance information but also the dynamic solving status. For the former, we represent by static features of variables and constraints, along with the incidence matrix in instance. The latter is represented by dynamic features, including the current solution z; and dynamic statistics of incumbent solutions up to step t. Specifically, both the current and incumbent solution f are defined the initial solution ro-
Actions. each state 8t, an action of the agent is to select a variable subset a 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 are optimized with the others equaling to their current values in It. Accordingly, the next state S141 is deterministically attained by updating 9; with the new solution:
Zt+1 arg min(u a|AA S b; 2 0; 2"; x" 24, Vx a'}.
(1)
Rewards. The reward function is defined r; r(st, ax) 1u (ar, xt+1), which is the change of the objective value. Given the step limit 7 of the interaction between the agent and environment, the return (i.e., cumulative rewards) from step t of the episode is R. = 'r_ ~ with the discount factor 7 E [o, 1]. The goal of RL is to maximize the expected return [ over all episodes, i.e., the expected improvement over initial solutions, by learning policy.
Policy. The stochastic policy æ represents conditional probability distribution all possible variable subsets given state. Starting from sp, it iteratively picks an action aj based on the sate s, at each step f, until reaching the step limit T.
An example of the proposed LNS framework solving an IP instance is illustrated Figure I in which the GNN based policy network has the potential to process instances of any size via sharing parameters across all variables.
4.2 Action factorization
Given the vector of decision variables in an IP instance, we gather all its elements in a set X= {== ,ي²
Accordingly, we define the action space A (ala C X), which contains all possible variable subsets. Thus our RL task is learning a policy to select a, E A for reoptimization at
..",,, ,.",...,,""
each step of LNS. and the cardinality of o, (i.e., (a. ) reflects the destroy degree on the solution. Apparently, the size of the combinatorial space A is 2", 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. [1] assumes the action space as the subspace of A that merely contains equal-sized variable subsets, that is, A= {azlaz E A, |a=| = 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 each dimension (i.e., variable). Specifically, we denote of E {x², } as the elementary action for variable x² at step t. It means that x' is either selected for reoptimization, such representation, any variable subset can also be expressed as 0+ = U i= ai 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:
not selected and thus fixed its value in the current solution. With
π T (t) = I x (a/lse))
(2)
which expresses TT (acls))) the probability of selecting an action, the product of probabilities of selecting its elements. Since (are(arr0) (0) (0) (a](s)) = 1, vi E {L...., n), it is casy to verify that the sum of probabilities of all actions in A still equals to 1, i.e., A = 1. Based on this factorization, we can apply RL algorithms to train policies n² for each variable x'. In the following subsections, we first parametrize the policy π by a GNN тa, and then train it by a customized actor-critic algorithm.
4.3 Policy parametrization
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 variables. Based on Equation ( 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 s by a bipartite graph 9 (V,C, A), where V {u1. ... Un denotes variable nodes with features V E RRnxd. C [c1, Cm } denotes constraint nodes with features C E Rmxde; A E mR denotes the adjacency matrix with azz being the weight (or feature) of the edge between nodes C, and v, 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 To(ac) St) by a graph convolutional network (GCN), GNN 39 40 The architecture of our design is illustrated in
variant broadly used in various tasks [38 Appendix A. with the graph convolution layer expressed as below:
1(++1) = (k) + a (LN (AV
(3)
((++1)= = (()) + (IN A (ATC(tt ,0...... K
where (A(A)) w!(k) E dd are trainable weight matrices in the k-th layer; (+)) (v(+) ...,, (.( and (4)) [c] -...
(k) 1 are node embeddings for variables and constraints respectively in k-th
5

---

layer; LN and of-) 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 and ((o) with da dimensions (d,, = 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 {v? J and {c ym jj= We finally process the former by multi-layer perceptron (MLP) with a single-value output activated by Sigmoid. In this way, the output value can represent the probability of variable being selected, i.c., x x'(a((s)) = To a (s)) MLP(v ), Vi {I...., ra}. such that we can conduct Bernoulli sampling accordingly on each variable and attain the subset. this paper, we structure the MLP by two hidden layers, which have 256 and 128 dimensions respectively and are activated by Tanh.
4.4 Training algorithm
Actor-critic is one of the policy gradient methods developed from REINFORCE [4]] It parametrizes state-value or action-valus value function as a critic network to estimate the expected return. In this paper, adopt Q-actor-critic with Qu (s, a) Q(, a) EE| [ 8, a, = a), where w 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:
I(w) = EDD(( (++1))))0)))))))))))))))))))))) +r+ (w(ss, (t))
(4)
L(O)= = ED QQ a.) log To (aels))))
(5)
where the experience replay buffer D contains transitions (st, as, S141, ac+1), which are collected during solving a batch of instances. (Qu(Se+ a(+1) + Tt is the one-step temporal-diffee diffeeeeffee (TD) target to update the critic.
The above Q-actor-critic not directly applicable to the primitive high-dimensional action spaces in our IP problems. To learn the factorized policies we designed in Section (.2 one way is customize it by training an actor and critic on each dimension, and updating the parameters via the loss functions:
[(w)= = -Eol, 1 Σn (7Qu
Qu
i.(0) = -Eol - 1=1
at) ~
Qu (og(mo(a()s))))
(7)
where the parameter-sharing Q. used across all dimensions as the actor To. i.e., Qu at)
Q'(s,, af), Vi E n1.....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:
{()) EDlep EDIQu((e, or) Σ" 1=1 log(mo
where the critic Qu is structured in the same manner as except that: 1) we add a binary value to the raw features of each variable of to indicate whether it is selected; 2) 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 range [e, 1 e]. e <0.5. It helps avoid always 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 MLP based semi-shared network similar to the one in [26], which indicates that the fully-shared one (ours) is more suitable for problems. More details are given in Appendix A.3.

---

Experimental results
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
Instance generation. We generate SC instances with 1000 columns and 5000 rows following the
procedure in [42]. MIS instances are generated following 44] where we use the Erdós-Rényí random
graphs with 1500 nodes and set the affinity number to 4. CA instances with 2000 items and 4000
MC instances are generated according to Barabasi-Albee 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
bids are generated according to arbitrary relationships in
Table 1: Average sizes of problem instances.
Training
Generalization
Num,
SC
MIS
CA
MC
SC2
MIS;
CA2
MC2
SC,
MIS,
CA2
MC2
Variables
1000
1500
4000
2975
2000
3000
8000
5975
4000
6000
16000
11975
Constraints
5000
5939
2674
4950
5000
11932
5357
9950
5000
23917
10699
19950
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 problem structure. For the dynamic features, we record for each variable its value the current solution and incumbent, of LNS. Specially, at the step = O, the average incumbent values are naturally attained from the initial solution, i.c., 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 the constraint nodes and edges, respectively. Detailed description of the above features are available in Appendix A.4.
well as its average value in all incumbents to represent the solving status
Hyperparameters. We use the state-of tiite-of-the-att 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) ES-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 c=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== and the batch size B-TM/U. We set the discount factor >=0.99 for all problems, and use Adam optimizer with learning rate x 10-4, To show the applicability of our method other solvers, have also performed experiments where Gurobi 47 used as the repair solver, which will be discussed in Section 5.3
5.1 Comparative analysis
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 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 (1I, which randomly groups variables into disjoint equal-sized subsets and reoptimizes them in order.
FT-LNS:
the best-perforning LNS version in 21, which applies forward training, an imitation learning algorithm, to mimic the best demonstrations collected from multiple R-LNS runs.
hhtps://ittubbcoo///XX11111 -ooicy
7

---

Table 2: Comparison with SCIP and LNS baselines.
SC
MIS
CA
MC
Methods
Obj Obj.1.Si..5 %
Gap%i
Std.
Gap%
Obj.
Gap
Obj Stid. %
Gap%
SCIP
567.66 + 8.76
3.62
-681.02 +: 1.14
0.29
-110181 + 2.03
2.98
-852.57 +: 1.22
4.37
SCIP"
552.82 1: 8.69
0.91
-681.76
1.06
0.18
-111511 + 1.85
1.85
-861.10 +: 1.26
3.41
SCIP"
550.68
0.53
-682.46
1.02
0.07
-112638
1.68
0.82
-863.63
1.32
3.13
U-LNS
568.60 + 12.17
5.99
-681.38
0.95
0.23
-103717 = 1.22
8.67
-869.20
1.53
2.50
R-LNS
560.54 = 8.07
2.38
-682.20 + 0.93
0.11
-109550 = 1.62
3.44
-882.18 + 1.27
1.05
FT-LNN
364.00 + 8.03
3.02
-681.82 2222222222- + 0.93
0.17
-107370
+ 2.03
5.45
867.05
+ 1.64
2.75
Ours
551.50 8.59
0.68
-682.52
0.98
0.06
-112666 = 1.72
0.77
-889.6
1.32
0.27
and the method run with 500s and 1000s.
Table 3: Generalization to large instances.
SC2
MISa
CA2
MC₂
Methods
Otd.1
Gap%
Obj Otd.iSid.%%
Gap%
Std...
Gap%
Obj.1Sid.. %
Gap%
SCIP
303.18 + 8.62
6.80
-1323.99 90 + 0.81
3.22
-205542 + 2.87
7.14
-1691.48
1.18
6.22
SCIP"
298.12 + 8.08
5.04
-1357.04
1.34
0.80
-214654 = 1.44
3.02
-1706.45 = 1.26
5.39
SCIP""
295.70 7.89
4.21
-1361.98
1.06
0.44
-217271 = 1.93
1.84
-1714.71
1.02
4.93
U-LNS
303.36 1: 8.24
6.90
-1364.66
0.69
0.24
-197453 1: 1.86
10.79
-1769.00
1.03
1.92
R-LNS
300.84 +: 7.74
6.06
-1339.00
= 0.81
2.12
-204145 = 1.57
7.77
-1767.09
-1.00
2.03
FT-LNS
303.52 + 7.86
6.98
-1345.58
= 0.86
1.63
-212264
+ 1.35
4.10
-1700.58
1.64
5.72
Ours
297.90 1: 8.20
4.98
-1367.78
0.68
0.01
-216006
1: 1.15
2.40
-1803.71
0.92
0.00
SC4
MISa
CA₁
MC²
Methods
Std.1
Gap%
Obj
Gap%
Obd.
Gap%
Obj-1Std
Gap%
SCIP
179.88 + 6.35
6.37
26622.56 + 0.58
3.05
-372291 + 1.22
13.44
-3392.02
0.86
5.45
SCIP*
177.44 6.64
4.91
26652.56
0.58
3.05
-372291
1.22
13.44
-3392.94
0.82
5.43
SCIP"
175.38 1 6.98
3.68
-2673.64
1.54
2.28
-372291 1: 1.22
13.44
-3394.42
0.81
5.39
U-LNS
196.60 + 10.13
16.25
26653.42 + 0.63
3.02
-419973 + 1.11
1.41
-3522.67
0.80
1.81
R-LNS
188.02 + 7.13
11.24
2683.30
+ 0.59
1.93
-427478
+: 0.95
0.61
-3521.90
0.82
1.83
FE-LNS
179.40 1 8.47
6.04
-2684.99 94 1 0.81
1.87
424052
1 0.96
1.41
-3525
0.83
1.74
Ours
176.84 + 7.42
4.57
-2735.86
0.50
0.00
-428052
+ 0.12
0.49
-3587.72
0.76
0.00
Following [11]. 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 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 basclines 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 be solved optimally, we measure the primal gap [19] to reflect the difference between the solution 2 of a method to the best one x² found by all methods. We compute |p J μ x" 1/max 8). | T xx' 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 high- quality solutions in 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 basclines 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. 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.
8

---

Table 4: Generalization to large instances (500s).
SC₂
MIS²
CA2
MC²
Methods
Obj.=Stdd.%
Gap%
Obj. %6
Gap%
Obj.#Sttd.5 %
Gap%
Obj.::Std.9 %
Gap%
SCIP"
295.70
7.89
4.48
-1361.98 + 1.06
0.56
-217271
1.93
1.59
-1714.71 + 1.02
5.44
U-LNS
302.94
8.15
7.04
-1368.58 = 0.72
0.05
-200256
2.08
9.28
-1777.98 + 1.01
1.95
R-LNS
298.24 = 7.43
5.39
-1362.04 = 0.71
0.52
-207937
= 1.44
5.81
-1776.44
+ 1.02
2.04
FT-LNS
303,34 1 7.97
7.18
-1345.60
1 0.83
1,76
-213464
1 1.21
3.30
-1767.81
1 1.04
2.51
Ours
295.36
7.81
4.36
-1368.68
+ 0.65
0.04
-218920
+ 2.13
0.85
-1813.02
+ 0.91
0.02
SC4
MIS+
CA4
MC²
Methods
Std.1
Gap%
Std.1
Gap%
Obd.1Stt..
Gap
Obj.1Stt.99 %
Gap%
SCIP"
175.38 + 6.99
5.21
-2673.64 + 1.54
2.41
-372291 + 1.22
14.98
-3394,42 + 0.81
6.04
U-LNS
185.62 1 8.19
11.26
-2737.24
1 0.54
0.09
-426480 1 0.93
2.60
-3556.69
1 0,80
1.55
R-LNS
172.96 - 6.43
3.73
-2736.60
0.52
0.11
-431786
1.03
1.39
-3554.98 + 0.80
1.59
FT-LNS
175.20 + 6.59
5.11
-2655.00
0.81
1.97
.431234
0.91
1.52
-3526.24
0.79
6.10
Ours
172.38 7.14
3.36
-2738.24
0.50
0.04
-437880
0.72
0.00
-3612.52
+ 0.74
0.00
5.2
Generalization analysis
Training deep models that perform well on larger problems is a desirable property for solving IPs, since practical problems are often large-scale. Here evaluate such generalization performance instances with the average sizes listed in Table 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 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 three LNS baselines on SC2, CA2 and SC₁, while our method can still deliver better results on all problems. Compared to SCIP with 1000s, our method is inferior on SC2, CA2 and SC₁ 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 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., MIS+, CAa and MC,, It suggests that as the problem size becomes larger, LNS could 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 basclines, showing that is more efficient in improving the solution. In summary, LNS policies learned on small instances generalize well to larger ones, with a persistent advantage over other methods.
5.3 Experiments with Gurobi
Our LNS framework 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 7=50 with Is 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 much as that for training. To save space, only show results of two instance groups for each problem Table 5 Despite the shorter runtime, we find that Gurobi (100s) generally attains lower objective values than SCIP (200s), showing a better performance to solve IP
'Specially, we observe that MIS is fairly easy for Gurobi (76 out of 100 instances can be solved optimally with average 40s). Thus, evaluate this problem with less time limit and show the results in Appendix A.6.

---

Table 5: Results with Gurobi. The left part shows the results of inference on the testing set in SC, CA and MC; the right part shows the results of generalization to larger instances in SC2. CA2 and MC
CA
SC2
MC₂
Methods Obj +.dd.% Gap% Obj
Gap% Obj.+Std. Gap% Obj Std Gap% +Std% Gap% Std.= GapSi
Gurohi 554.94 1 8.34 1.15 111166 1 1.96 1.10 863.91 1. 3.77 3,31 302.52 1. 7.73 2.43 -14271 1. 1.52 3.63 -1652.33 1 3,63 5.1
U-LNS 562.08 = 8,16 2.46 -110402 + 1.67 2.21 -862.39 = 1.75 3:45 301.48 + 7.62 2.07 -218986 + 1.42 151 -1733.57 + 1.22 1.21
R-LNS 563.98 =: 8.29 2.81 -110230 + 1.56 2.36 -860.22 = 1.96 3.72 302.86 + 7.41 2.56 -219462 + 1.16 1.29 -1723.75 + 1.32 1.77
FI-LNS 564.14 +: 8.37 2.84 -110141
+: 1.56 2.53 -866.22 +: 1.65 3.03 348.50 1 9.05 -29919 +: 1.39 7.26 -1726.07 4: 1.19 1.64
Ours 551.88 8,31 0.59 -111787 1. 2.60 1.00 -888.97 1: 1.55 0.50 297.70
1. 7.40 0.80 -222346 1.35 0.00 -1752.98
1. 1.21 0.11
problems. Hence, the LNS baselines lose their advantages over the solver several problems, e.g.. SC, CA and SC2. In contrast, our method outperforms Gurobi across all problems, showing good performance 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.
5.4 Testing on MIPLIB
The mixed integer programming library (MIPLIB) [8
contains real-world COPs from various domains. Since the instances in MIPLIB are severely diverse in problem types, structures and sizes, it is not 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
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.
Conclusions and future work
We propose 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 parameter-sharing GNN to learn policies for each variable, and train 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 practical view, our method could be a choice when new IP problems are produced with little expertise, 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.
Acknowledgments
This research was conducted at Singtel Cognitive and Artificial Intelligence Lab for Enterprises ISCALE@NTU) which is 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: (1701 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 62420089964 188. Zhiguang Cao supported by the National Natural Science Foundation China under Grant 61803104.
10

---

References
[1] Vangelis Th Paschos. Applications of combinatorial optimization. John Wiley & Sons, 2013.
[2] Christos H Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: algorithms and complexity. Courier Corporation, 1998.
[3] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d' d'horizon. European Journal of Operational Research, 290(2):405 2020.
[4] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Proceedings of the 29th Conference on Neural Information Processing Systems (NIPS), pages 2692-2700, 2015,
[5] Irwan Bello and Hicu Pham. Neural combinatorial optimization with reinforcement learning.
In the 5th International Conference Learning Representations (ICLR), 2017.
[6] Hanjun Dai, Elias Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial op- timization algorithms over graphs. In Proceedings of the 31st Conference on Neural Information 2017.
Processing Systems (NIPS), pages
[7] Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn solve routing problems! In the 7th International Conference on Learning Representations (ICLR), 2019.
[8] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Multi-decoder attention model with embedding glimpse for solving vehicle routing problems. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, page 12042-12049, 2021.
[9] Jingwen Li, Yining Ma, Ruize Gao, Zhiguang Cao, Andrew Lim, Wen Song, and Jie Zhang Deep reinforcement learning for solving the heterogeneous capacitated vehicle routing problem. IEEE Transactions on Cybernetics, 2021.
[10] Jingwen Li, Liang Xin, Zhiguang Cao, Andrew Lim, Wen Song, and Jie Zhang. Heterogeneous attentions for solving pickup and delivery problem via deep reinforcement learning. IEEE Transactions on Intelligent Transportation Systems, 2021.
[11] Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Chi Xu. Learning to dispatch for job shop scheduling via deep reinforcement learning. In Proceedings of the 34th Advances in Neural Information Processing Systems (NIPS), pages 1621 2020.
[12] Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. Proceedings of the 33rd Conference on Neural Information Processing Systems (NIPS), pages 6278 6289, 2019.
[13] Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuristics for solving routing problems. IEEE Transactions on Neural Networks and Learning Systems, 2021.
[14] Hao Lu, Xingwen Zhang, and Shuang Yang. A learning-base iterative method for solving vehicle routing problems. In the 8th International Conference on Learning Representations (ICLR), 2020.
[15] André Hottung and Kevin Tierney. Neural large neighborhood search for the capacitated vehicle routing problem. In Proceedings of the 24th European Conference on Artificial Intelligence (ECAI), 2020.
[16] Lei Gao, Mingxiang Chen, Qichang Chen, Ganzhong Luo, Nuoyi Zhu, and Zhixin Liu. Learn to design the heuristics for vehicle routing problem. arXiv preprint arXiv:2002.085: 2003.00329 2020.
[17] Ailsa Land and Alison G Doig. An automatic method for solving discrete programming problems. In 50 Years of Integer Programming 1958-2008, pages 105-132. Springer, 2010.
[18] He He, Hal Daume III, and Jason M Eisner. Learning to search in branch and bound algorithms. In Proceedings of the 27th Conference on Neural Information Processing Systems (NIPS), pages 3293-3301, 2014.
11

---

[19] Elias B Khalil, Bistra Dilkina, George L Nemhauser, Shabbir Ahmed, and Yufen Shao. Learning to run heuristies tree search. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAT), pages 659-666, 2017.
[20] Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. In Proceedings of the 33rd Conference on Neural Information Processing Systems (NIPS), 2019.
[21] Jialin Song, Ravi Lanka, Yisong Yue, and Bistra Dilkina. A general large neighborhood search framework for solving integer linear programs. In Proceedings of the 34th Conference on Neural Information Processing Systems (NIPS), 2020.
[22] Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Reinforcement learning for integer program- ming: Learning to cut. In International Conference on Machine Learning (ICML), pages 9367-9376, 2020.
[23] Jian-Ya Ya Ding, Chao Zhang, Lei Shen, Shengyin Li, Bing Wang, Yinghui Xu, and Le Song. Accelerating primal solution findings for mixed integer programs based on solution prediction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 1452-1459,
2020.
[24] Vinod Nair. Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O' O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, al. Solving mixed integer programs using neural networks. arXiv preprint arXiv: 2020.
[25] Jason Pazis and Ronald Parr. Generalized value functions for large action sets. In Proceedings of the 28th International Conference on Machine Learning (ICML), pages 1185-1192, 2011.
[26] Arash Tavakoli, Fabio Pardo, and Petar Kormushev. Action branching architectures for deep reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[27] Gabriel Dulac-Aroldd, Richard Evans, Hado van Hasselt, Peter Sunehag, and Timothy Lillicrap. Deep reinforcement learning in large discrete action spaces. arXiv preprint arXiv: 1512.0777, 2015.
[28] Yash Chandak, Georgios Theocharous, James Kostas, Scott Jordan, and Philip Thomas. Learning action representations for reinforcement learning. In Proceedings of the 36th International Conference on Muchine Leurning (ICML), pages 941-950, 2019.
[29] Yunhao Tang and Shipra Agrawal. Discretizing continuous action space for on-policy opti- mization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5981- 2020.
[30] Thomas Hubert, Julian Schrittwieser, loannis Antonoglou, Mohammadamin Barekatain, Simon Schmitt, and David Silver. Learning and planning in complex action spaces. arXiv preprint arXiv:2104.06300
2021.
[31] OpenAl: Marcin Andrychowicz. Bowen Baker, Maciek Chociej, Rafal Jozefowicz, Bob Mc- Grew, Jakub Pachocki, Arthur Petron, Matthias Plappert, Glenn Powell, Alex Ray, et Learning dexterous in-hand manipulation. The International Journal of Robotics Research, 39(1):3-20, 2020.
[32] David Pisinger and Stefan Ropke. Large neighborhood search. In Handbook of metaheuristics, pages 399-419. Springer, 2010.
[33] Stefan Ropke and David Pisinger. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation science, 40(4):455 472, 2006.
[34] Eric Prescott-Gagnon Guy Desaulniers, and Louis-Martin Rousseau. A branch-and -riice- based large neighborhood search algorithm for the vehicle routing problem with time windows. Networks: An International Journal, 190-)2190-24,, 2009.
12

---

[35] Lactitia Matignon, Guillaume J Laurent, and Nadine Le Fort-Piat. Independent reinforce- ment learners cooperative markov games: survey regarding coordination problems. The Knowledge Engineering Review, 27(1):1-31, 2012.
[36] Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.0122 012611, 2018.
[37] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32( 24, 2012.
[38] Thomas N. Kipf and Max Welling. Semi-superviee classification with graph convolutional networks. the 5th International Conference on Learning Representations (ICLR), 2017.
[39] David Duvenaud, Dougal Maclaurin, Jorge Aguilera-Iparree Iparraguiree, Rafael G6mmzz-oobarre Timothy Hirzel, Alán learning molecular fingerprints. Proceedings of the 29th Conference on Neural Information Processing Systems (NIPS), pages 2224-2232, 2015.
and Ryan P Adams. Convolutional networks on graphs for
[40] Liang Yao, Chengsheng Mao, and Yuan Luo. Graph convolutional networks for text classi- fication. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 7370-7377, 7377, 2019.
[41] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforce- ment learning. Machine learning, 8(3-4):229-256, 1992.
[42] Egon Balas and Andrew Ho. Set covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study. In Combinatorial Optimization, pages 37-60. Springer, 1980.
[43] David Bergman, Andre A Cire, Willem-Jan Van Hoeve, and John Hooker. Decision diagrams for optimization. Springer, 2016.
[44] Kevin Leyton-Brown, Mark Pearson, and Yoav Shoham. Towards a universal test suite for combinatorial auction algorithms. In Proceedings of the 2nd ACM conference on Electronic commerce, pages 66-76, 2000.
[45] Réka Albert and Albert-László Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002.
[46] Tobias Achterberg. Seip: solving constraint integer programs. Mathematical Programming Computation, 1(1):1-41, 2009.
[47] LLC Gurobi Optimization. Gurobi optimizer reference manual, 2021. URL http: // www gurobi. com
[48]
Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg, Michael Bastubbe, Timo Berthold, Philipp M. Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, Marco Lübbecke, Hans D. Mittelmann, Derya Ozyurt, Ted K. Ralphs, Domenico Salvagnin, and Yuji
Shinano. MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library. Mathematical Programming Computation, 2021. doi: 10.10077/11532--00-0000999 URL https://do1. org/ 10. 1007 82222222222220001444
13


Reviews:
[{"review_id": "ktpU0ePo9tG", "reviewer": "Reviewer_WJkM", "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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Post-rebuttal comments: I thank the authors for providing detailed answers to my questions. I will keep my score.\n\nOriginality: 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. \n\nThis recent workshop paper [1] also applies RL to LNS. I think the authors should add it to the related discussion.\n\n[1]: Neural Large Neighborhood Search, Ravichandra Addanki, Vinod Nair, Mohammad Alizadeh, https://openreview.net/forum?id=xEQhKANoVW \n\nQuality: For an empirical paper, the authors did a good job of providing thorough analyses in the following aspects. \n1. The problem instances are diverse and contain real-world problems in MIPLIB.\n2. Two different solvers, SCIP and Gurobi, are used to show the generality of the proposed method.\n3. 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.\n\nI have some questions regarding some details of the experiments. \n1. 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?\n2. Does the time limit include all runtime, such as model inference, or only include solver invocation time?\n3. How many random seeds did you use for the RL results?\n\nClarity: This paper is clear and easy to read. Good job!\n\nSignificance: 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequately addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "R3XgzNPTzPG", "reviewer": "Reviewer_r59Z", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is at times difficult to read. I would request that the authors attempt to polish the presentation.\n\nI 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).\n\n* L41: What does \"externals\" mean here?\n* L108: IP is _not_ a subset of COP, it is in fact much more general.\n* L137: \"latter\" seemingly refers to the incidence matrix, which does not make sense in context.\n* 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?\n* L182: \"parametrize\"\n* 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)?\n* 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.\n* 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.\n* Table 1: \"Constrains\"\n* L349: MIPLIB contains many instances which are not COPs.\n* L356: If you have produced a new best solution for a MIPLIB instance, you should submit it upstream!", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "QBSCOtF6Uu0", "reviewer": "Reviewer_WFms", "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.\n\n===== updated post rebuttal ====\n\nThe 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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "=========== Originality ============\n\nThough 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.\n\n=========== Quality ============\n\nThe 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). \n\n=========== Clarity ============\n\nOverall, 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.\n\n=========== Significance ============\n\nThe 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. \n\n=========== Technical questions ============\n\nI have a few tech questions:\n\n1. 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?\n\n2. 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.\n\n3. 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)?\n\n3. 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)?\n\n4. 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.\n\n\n5. 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?\n\n6. 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?\n\n7. 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?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have discussed their limitations in the conclusion section.", "review_text": "", "extra_scores": {"ethical_concerns": "No clear ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "5hZy9M7a0vY", "reviewer": "Reviewer_Tvg1", "summary": "The last few years have seen numerous projects leveraging ML/RL to\nspeedup the optimization of ILP problems. Many of these attempts fall\nunder 2 categories:\n  * RL driven branch-and-bound. By integrating a policy deeply inside\nan ILP solver to drive the branch&bound process, these approaches have\nthe ability to extract a rich set of features from the solver and can\nleverage them to inform the decisions made by the policy. The work of\nGasse et al. (Exact combinatorial optimization with graph convolution\nneural networks)  is an example of such an approach.\n* Large Neighborhood Search. This technique has been applied with\nsuccess to speedup the optimization of integer programs, in particular\nin the work of Song et al. (A general large neighborhood search\nframework for solving integer linear programs). This approach is\neasier to implement since it doesn't require a deep integration into\nan ILP solver (it merely calls one to solve subproblems).\n\nThis paper proposes a hybrid of the two approaches. It leverages a\nneural network architecture similar to the Gasse GCN as well as the\nfeaturization introduced by Gasse to build and inform a policy that\ndrives the large neighborhood search pioneered by Song et al. It also\noffers some novel aspects, including a customized actor critic\nalgorithm to train the policy.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nThe work makes 3 novel contributions:\n* 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.\n* 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. \n* It introduces a novel variation of the actor critic algorithm to train the policy.\n\nThe paper appears technically sound, and the approach is extensively compared against the SCIP solver\nand the results of Song et al. The authors demonstrate that the combination\nof (i) their actor critic based training (ii) a richer set of features\nand (iii) the GCN based architecture outperforms Song et al and the\nSCIP solver. I would have liked to see an evaluation against Gasse et\nal. as well as an ablation study to get a sense of the relative\nimportance of these 3 factors. This might also help figure out whether\nthe approach of Gasse or that of Song is the most promising overall.\n\nThe previous experiments were repeated, but this time using the Gurobi\nsolver. Again the hybrid approach came up on top. Since the extended\nset of features provided by the SCIP solver are not available when\nusing the Gurobi solver, it seems that the richer featurization made\navailable by SCIP is not critical to the outcome. This is somewhat\ncounter intuitive, so any insights you have about why that is would\nenrich the paper.\n\nLast but not least, RL based approaches can be sensitive to initial\nconditions. I'd love to see how much variance you get when\ninitializing your policy with different random weights.\n\nOverall, 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

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)