Improving Learning to Branch via Reinforcement Learning
Authors: Haoran Sun
Wenbo Chen
Hui Li
Le Song
Venue:  (2021)
Keywords: Mixed Integer Programming
Branching and Bound
Strong Branching
Reinforcement Learning
Evolution Strategy
Novelty Search

Abstract: Branch-and-Bound~(B\&B) is a general and widely used algorithm paradigm for solving Mixed Integer Programming~(MIP). 
Recently there is a surge of interest in designing learning-based branching policies as a fast approximation of strong branching, a human-designed heuristic. In this work, we argue strong branching is not a good expert to imitate for its poor decision quality when turning off its side effects in solving linear programming. To obtain more effective and non-myopic policies than a local heuristic, we formulate the branching process in MIP as reinforcement learning~(RL) and design a policy characterization for the B\&B process to improve our agent by novelty search evolutionary strategy. Across a range of NP-hard problems, our trained RL agent significantly outperforms expert-designed branching rules and the state-of-the-art learning-based branching methods in terms of both speed and effectiveness. Our results suggest that with carefully designed policy networks and learning algorithms, reinforcement learning has the potential to advance algorithms for solving MIPs.

Under review conference paper at ICLR 2021
IMPROVING LEARNING TO BRANCH VIA REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Branch-and-Bound (B&B) is general and widely used algorithm paradigm for solv- ing Mixed Integer Programming (MIP). Recently there is a surge interest in designing learning- based branching policies fast approximation of strong branching, human- designed heuristic. In this work, we argue that strong branching is not a good expert to imitate for its poor decision quality when turning off its side effects in solving branch lin- ear programming. To obtain more effective and non-myopic policies than a local heuristic, we formulate the branching process MIP as reinforcement learning (RL) and design novel set representation and distance function for the B&B process associated with a pol- icy. Based on such representation, we develop a novelty search evolutionary strategy for optimizing the policy. Across range of NP-hard problems, our trained RL agent signifi- cantly outperforms expert-designed branching rules and the state-of-the learning- based branching methods in terms of both speed and effectiveness. Our results suggest that with carefully designed policy networks and learning algorithms, reinforcement learning has the potential to advance algorithms for solving MIPs.
1 INTRODUCTION
Mixed Integer Programming (MIP) has been applied widely in many real-world problems, such schedul- ing (Barnhart et al. 2003) and transportation (Melo & Wolsey 2012). Branch and Bound (B&B) is a general and widely used paradigm for solving MIP problems (Wolsey & Nemhauser 1999). B&B recursively par- titions the solution space into a search tree and compute relaxation bounds along the way to prune subtrees that provably not contain
optimal solution. This iterative process requires sequential decision mak- ings: node selection: selecting the next solution space to evaluate, variable selection: selecting the variable by which partition the solution space (Achterberg & Berthold 2009). In this work, focus learning a variable selection strategy, which is the core of the B&B algorithm (Achterberg & Wunderling (013))
Very often, instances from the same MIP problem family are solved repeatedly in industry, which gives rise to the opportunity for learning to improve the variable selection policy (Bengio et al. (020)). Based on the human- designed heuristics, Di Liberto et al. (2016) learn classifier that dynamically ly selects an existing rule to perform variable selection; Balcan et al. (2018) consider a weighted score of multiple heuristics and analyse the sample complexity of finding such good weight. The first step towards learning variable selection policy was taken by Khalil et al. (2016), who learn instance customized policy in an online fashion, as well as Alvarez et al. (2017) and Hansknecht et al. (2018) who learn a branching rule offline on a collection of similar instances. Those methods need extensively feature engineering and require strong domain knowledge in MIP. To avoid that, Gasse et al. (2019) propose a graph convolutional neural network approach to obtain competitive performance, only requiring raw features provided by the solver. In each case, the branching policy is learned by imitating the decision of strong branching as it consistently leads to the smallest B&B trees empirically (Achterberg et al. 2005).

---

Under review conference paper at ICLR 2021
In this work, we argue that strong branching is not a good expert imitate. The excellent performance (the smallest B&B tree) of strong branching relies mostly on the information obtained in solving branch linear programming (LP) rather than the decision it makes. This factor prevents learning good policy by imitating only the decision made by strong branching. To obtain more effective and non-myopic policies,i.e. minimizing the total solving nodes rather than maximizing the immediate duality gap gap, we use reinforce- ment learning (RL) and model the variable selection process as Markov Decision Process (MDP). Though the MDP formulation for MIP has been mentioned in the previous works (Gasse et al. 2019 Etheve et al., 2020 the advantage of RL has not been demonstrated clearly in literature.
The challenges of using RL are multi-fold. First, the state space is a complex search tree, which can in- volve hundreds thousands of nodes (with linear program on each node) and evolve over time. In the meanwhile, the objective of MIP is to solve problems faster. Hence a trade-off between decision quality and computation time is required when representing the state and designing a policy based on this state rep- resentation. Second, learning a branching policy by RL requires rolling out on a distribution of instances. Moreover, for each instance, the solving trajectory could contain thousands of steps and actions can have long-lasting effects. These result in a large variance in gradient estimation. Third, each step of variable selection can have hundreds of candidates. The large action set makes the exploration in MIP very hard.
In this work, we address these challenges by designing a policy network inspired by primal-dual iteration and employing a novelty search evolutionary strategy (NS-ES) to improve the policy. For ffficiency-effettveeee trade-off, the primal-dual policy ignores the redundant information and makes high-quality decisions on the fly. For reducing variance, the ES algorithm is an attractive choice as its gradient estimation is independent of the trajectory length (Salimans et al., 2017). For exploration, we introduce a new representation of the B&B solving process employed by novelty search (Conti et al. 2018) to encourage visiting new states.
We evaluate our RL trained agent over range of problems (namely, set covering, maximum independent set, capacitated facility location). The experiments show that our approach significantly outperforms state- of-the-art art numan-designa
heuristics (Achterberg & Berthold 2009) well as imitation based learning methods (Khalil et al. 2016 Gasse et al.) 2019)) In the ablation study, we compare our primal-dual policy net with GCN (Gasse al.) 2019). novelty based ES with vanilla ES (Salimans al. 2017). The results confirm that both our policy network and the novelty search evolutionary strategy are indispensable for the success of the RL agent. In summary, our main contributions the followings:
We point out the overestimation of the decision quality of strong branching and suggest that methods other than imitating strong branching are needed to find better variable selection policy.
We model the variable selection process as MDP and design novel policy net based on primal-dual iteration over reduced LP relaxation.
We introduce a novel set representation and optimal transport distance for the branching process associated with a policy, based on which we train our RL agent using novelty search evolution strategy and obtain substantial improvements in empirical evaluation.
2 BACKGROUND
Mixed Integer Programming, MIP is an optimization problem, which is typically formulated as
minxeR" (o"x: Ax < b, l < x u, xj E VjeJ}
(1)
where Rd is the objective vector, A E Rm is the constraint coefficient matrix, b Rm is the constraint vector, e, u E IR" are the variable bounds. The set J C {1, nn is an index set for integer variables. We denote the feasible region of x as X.
2

---

Under review conference paper at ICLR 2021
Linear Programming Relaxation. LP relaxation is an important building block for solving MIP problems, where the integer constraints are removed:
minxeR* (c Ax < b. x u..
LP based B&B is the most successful method in solving MIP. A typical LP
Branch and Bound.
Algorithm 1: Branch and Bound Input: A MIP P in form Equation An optimal solution set x" and optimal value ex
based B&B algorithm for solving MIP looks as Algo- rithm T Achterberg et al. 2005).
Output:
It consists of two major decisions: node selection, in line 3, and variable selection, in line In this paper. we will focus on the variable selection. Given a LP relaxation and its optimal solution å, the variable se- lection means selecting an index j. Then, branching 3 Select and pop LP relaxation Q E S
Initialize the problem set S == {PLp). where
PLP is in form Equation 2 Set
x² 0,
oC:
2 If = Φ. exit by returning x" and and
splits the current problem into two subproblems, each
a Solve Q with optimal solution E and optimal value ;;
representing the original I.P relaxation with new con-
straint v S [ for Q, and x;y 2 [&y] for Q re- spectively. This procedure
If c", go to 2;
be visualized by a bi-
6 If f E X, set x² = c* é, go to 2;
nary tree, which is commonly called search tree. We 7 Select variable j. split into two subproblems give simple visualization in Section A.I
Q and QJ. add them to S and go 3:
Evolution Strategy. Evolution Strategies (ES) is a class of black box optimization algorithm (Rechenberg 1978). In this work, we refer to the definition in Natural Evolution Strategies (NES) (Wierstra al. 2008
NES represents the population as a distribution of parameter vectors 0 characterized by parameters Φ (
NES optimizes & maximize the expectation of fitness f(0) over the population Eg-p. [(0) In recent work, SalimanSs et al.] (2017) outlines a version of NES applied to standard RL benchmark problems, where 0 parameterizes the policy Te. (0,, a) parameterizes Gaussian distribution (0) (O0,,, a² and
[0) is the cumulative reward R(0) over a full agent interaction. At every iteration, [Salimans et al. (017)
apply n additive Gaussian noises the current parameter and update the population
1 no
Be+1 = 8g + a
f(0, + tG)G
(3)
To encourage exploration, Conti et al. (018)) propose Novelty Search Evolution Strategy (NS-ES). In NS- ES. the fitness function f(0) (N (R))))(() is selected as a combination of domain specific novelty
score N and cumulative reward R, where À is the balancing weight.
3 WHY IMITATING STRONG BRANCHING IS NOT GOOD
Strong branching is a human-designes heuristic, which solves all possible branch LPs Q+ Q, ahead of branching. As strong branching usually produces the smallest B&B search trees (Achterberg) 2009), many learning-bas based variable selection policy are trained by mimicking strong branching (Gasse et al. 2019 Khalil al. 2016 Alvarez et al. 2017 Hansknecht al., 2018). However, we claim that strong branching is not a good expert: the reason strong branching can produce small search tree is the reduction obtained solving branch L.P, rather than its decision quality. Specifically, (i) Strong branching can check lines 5, 6 in Algorithm add the subproblem into the problem set S. (ii) Strong branching can strengthen other LP relaxations in the problem set S via domain propagation (Rodosek et al. 1999) and conflict analysis (Achterberg) 2007). For example, if strong branching finds x1 2 1 and x2 2 can be pruned during solving branch LP, then any other LP relaxations containing æ > 1 can be strengthened by adding x2 0. These two reductions
[ before branching. If the pruning condition is satisfied, strong branching does not need to
3

---

Under review conference paper at ICLR 2021
the direct consequence of solving branch LP, and they can not be learned by variable selection policy. (ii) Strong branching activates primal heuristics (Berthold 2006) after solving LPs.
To examine the decision quality of strong branching, we employ vanilla full strong branching (Gamrath et al. 2020), which takes the same decision as full strong branching, while the side-effect of solving branch
LP is switched off. Experiments Section 5.2 show that vanilla full strong branching has poor decision
quality. Hence, imitating strong branching is not wise choice for learning variable selection policy.
4 METHOD
Due line 5 in Algorithm 1 a good variable selection policy can significantly improve solving efficiency. To illustrate how to improve variable selection policy, we organize this section in three parts. First, we present our formulation of the variable selection process as RL problem. Next, we introduce the LP relaxation based state representation and the primal-dual based policy network. Then, we introduce our branching process representation and the corresponding NS-ES training algorithm.
4.1 RL FORMULATION
Let the B&B algorithm and problem distribution D be the environment. The sequential decision making of variable selection can be formulated Markov decision process. We specify state space S, action space A, transition and reward as follows
State Space. At iteration i, node selection policy will pop out a LP relaxation PLP from the problem set S. We set the representation the state to s, = (PL,,J.S) where J is the index set of integer variables. Action Space. At iteration f, the action space is the index set of non-fixed integer variables determined by the relaxation: A(st) = {j E J:: JJ:l. < U,
Transition. Given state 8, and action ae, the new state is determined by the node selection policy.
Reward. As our target is solving the problem faster, we set the reward r. = -1 with discount 7 = 1.
Maximizing the cumulative reward encourages the agent solving problems with less steps.
commercial solver, the solving process much more complicated than the B&B stated in Algorithm T For example, between line 3 and line 4, primal heuristics could be used to detect feasible solutions, and cutting planes could be applied to strengthen the LP relaxation. These components in solver introduce more randomness transition, but our formulation still valid.
4.2 PRIMAL DUAL POLICY NET
Reduced LP. In the solving process, the variable bounds keep changing due to branching. Thus, we obtain our reduced LP relaxation by the following two steps: 1) remove fixed variables 2j. where E = Uy and plug their values into the constraints; remove trivial constraints, where maxesx E, A.j S by. the view of primal-dual iteration, the LP relaxation has Lagrangian form:
min max c' x + (Ax-Ol s.t. 2xx
(4)
where variables and constraints naturally form bipartite graph. In the primal-dual iteration over Equation fixed variables and trivial constraints always pass zero and have no interaction with other variables.
PD policy net. We parameterize our policy network ao(a, (s:) primal-dual iteration over the reduced LP relaxation by message passing
Y, - fe Yú, Ai me (xx))) x, + Pv (x Ex,,=a. Aij my (Y.))
(5)
4

---

Under review conference paper at ICLR 2021
3/2
3/2
5/2
W (6,, b)) =
5/2
7/2
3/2
W (0, ba)
1/2
3/2
5/2
1/2
r(b b2)
1/2
1/4
0
1/4
1(61,
1/2
1/1
1/4
Figure 1: (left) three policies T1, T2 and Ta produce three sets of polytopes b1. b2 and by respectively for the same problem Q, (right) example cost matrix W and transportation matrix r.
where fc, fv two-hidden-layers neural networks, me, my one hidden layer neural networks, Ag is the entry in the reduced constraint matrix A and X, Y are the embedding for variables and constraints initialized by PLP and J. As mentioned above, the original primal-dual iterations only occurs the reduced LP hence, our message passing in Equation 5 is defined only on the reduced graph. For efficiency, we do not include problem set S, which makes it partial observable MDP {Astrom [965). After two iterations of Equation [] the variable embedding X is passed to a two-hidden-laye neural network score function fs and the output is the final score for each variable. Since the state reduction and message passing are both inspired by primal-dual duul iteration, we call it PD policy. A more detailed discussion and comparison with GCN (Gasse al. 2019) can be found at section A.2.2
4.3 SET REPRESENTATION FOR POLICY AND OPTIMAL TRANSPORT DISTANCE
We train the RL agent using evolution strategy similar to NSR-ES (Conti et al. 2018) and we need to define the novelty score for B&B process. In the general B&B algorithm, the solving process can be represented by a search tree, where each leaf is solved subproblem. Given a branch policy and instance Q, we define our representation b(T, Q) = {R,, ... R₂ } as the collection of leaf subproblems on the complete search tree Focusing MIP, a subproblem R2 is LP relaxation which can be represented by its feasible region, a polytope. For example, in Figure [ 61. b2 and by are the set polytopes produced by three different policies 71, T2 and Is respectively. And bj {A1, B1) } is set of two polytopes (leaf subproblems), by {A2, B2, C2] } is set of three polytopes, and by- = [Ag. B3
} is set of two polytopes. For computational efficiency, we ignore the constraints and only consider variable bounds such that every polytope a box.
For each polytope R2 (leaf subproblem), we define the weight function w(-) and distance function d(:,.) between two polytopes R2 and Ry
w(R)) = #(x fx= E R2 x is a feasible solution for Q}.
d(R,, R,) 19: 9; 111 where 9: and gj the center of mass for R. and R3 respectively.
12, d(A,(A,, A2) - Then we can map the representation b= [81,.- } to simplex p(b) E A H by normalizing the weights p(Rt) = w(R))/ -= w w(Rt),
For example, in Figure I we have w(Ai)
and compute cost matrix W., d( R(, R2) (See Figure for examples). Then, D between two representations as the Wasserstein distance (or optimal transport distance) (Villani 2008
define the metric
Peyré al. 2019):
D(b,, b2) = min Wyy s.t. r1 = p(b1), I = p(b2)
(6)
2.
á meaning by is closer to dj than b2- Hence the corresponding policy ma is closer to I than n2. Here, provide concrete method to measure
For example, in Figure| the distance D(b,, b2) = D(b,, by) = 3
2
5

---

Under review conference paper at ICLR 2021
the distance between two solving processes. is also provides framework for general B&B algorithm. We can choose weight function w and distance function d depending on the property of the solution space and compute the distance between two B&B solving processes.
4.4 NOVELTY SEARCH EVOLUTIONARY STRATEGY
Equipped with metric D between representations, we can define the novelty score following Conti et al. (2018). Given a policy memory M (a collection of older policies) and an instance Q sampled from the problem distribution D, novelty score is computed
(6, Q, M)
Σ
D(b(To. Q), Q)) ())
(7)
TYENNN(M,0)
where &N, 0) is the k nearest neighbor of Ty in M. Back Algorithm 1 B&B algorithm recursively splits the feasible region and obtains set of polytopes when finishing solving an instance. Notice that polytope in the set representation is invariant with the generating order, i.e. branching z then 22 will give the same polytope with branching Z2 then I1. As result, metrie D and novelty score N is mostly determined by the pruning behavior during the solving process. Put everything together, we summarize the training algorithm in section A.3
5 EXPERIMENTS
We now present comparative experiments against two competing machine learning approaches and three SCIP's branching rules to assess the value of our RL agent, as well as an ablation study to validate our choice of policy representation and training algorithm.
5.1
SETUP
Benchmarks: We consider three classes of instances, Set Covering (Balas & Ho 1980). Maximum Indepen- dent Set (Albert & Barabási 2002) and Capacitated facility location (Cornuéjols et al., 199T), those are not only challenging for state-of-hheart solvers, but also representative for problems encountered in practice. For each class, we set up a backbone based on which we randomly generate the dataset as many real-world problems also share the same backbone. For example, logisties company frequently solves instances on very similar transportation networks with different customer demands. We generate set covering instances using 1000 columns. We train on instances with 500 rows and evaluate on instances with 500 rows (test), 1000 rows (medium transfer), 1500 rows (hard transfer). We train maximum independent set on graphs with 400 nodes and evaluate on graphs with 400 nodes (test), 1000 nodes (medium transfer), and 1500 nodes (hard transfer). We generate capacitated facility location with 100 facilities. We train on instances with 40 customers (test) and evaluate on instances with 40 customers (test), 200 customers (medium transfer), and 400 customers (hard transfer). More details are provided in the section A.4
Settings:
Throughout all experiments, we use SCIP 7.0.1 as the backend solver, with a time limit of hour. For SCIP parameters, we have two settings: clean and default. The clean setting switches off other SCIP components, such as estimate node selection, cutting plane and primal heuristics. This way, the evaluation eliminates the interference from other components of the solver to variable selection policy. Under the clean setting, the solving nodes reflect the decision quality of variable selection policies only. So, we compare the decision quality of different methods under the clean setting. The default setting of SCIP will turn on all components inside SCIP, which is tuned for solving real problems. So, We compare the ability to solve challenging problems of different methods under the default setting.
Baselines: We compare against: Reliability Pseudocost Branch (RPB) (Achterberg & Berthold 2009), the human-designed state-of-the-art branching rule, which computes strong branching in the beginning and
6

---

Under review conference paper at ICLR 2021
Table 1:
Policy evaluation on test instances. Wins are counted by the number of times a method results in least number of solving nodes. The time Tavg is reported in seconds.
Method
T lrrg
Nav
Wins
Tayg
Navg
Wins
T Tavg
Navg
Wins
FSB 99.73
367
na/100
19.19
140
na/ 100
27.16
964
na/100
RPB
12.64
763
na/100
3.06
250
na/100
21.39
1449
na/100
VFS
1935.35
737
5/ 7.
244.14 14
1304
0/100
173.50
1848
31/100
SVM
21.19
856
1/100
10.83
498
1/100
29.64
2096
17/100
GCN
10.37
575
28/100
1.56
418
2/100
26.31
1752
13/100
7.91
399
66/100
1.26
200
97/100
20.85
1640
39/100
Set Covering
Independent Set
Facility Location
gradually switches to simpler heuristics; Full Strong Branching (FSB), full version of strong branching: Vanilla Full Strong Branching (VFS), strong branching with branch LP information muted (Gamrath et al. 2020;; and two recent machine learning policies support vector machine (SVM) rank approach (Khalil et al. 2016) and GCN approach (Gasse et al. 2019) We denote our method as RL, which is the primal-dual net trained by NS-ES.
Metrics To minimize the expected solving cost, metrics are selected as the average solving times (Tavg) for all instances and average solving nodes (Navg) for instances solved by all methods. Since MIP instances could vary a lot in difficulty, we count the number of times each method leads the performance over the number of times each method solves the instance within timelimit (Wins) third robust metric.
Implementation. The detail of implementation is provided in section A.2
5.2 DECISION QUALITY
We evaluate the variable selection quality by solving 100 test instances under clean setting. Since we are comparing the decision quality, we say method wins in this experiment if it results in the least number of solving nodes. As FSB and RPB benefit lot from branching LP information (section 3), we do not include them when counting Wins. Table. [hhows our RL agent leads the win times on all datasets and the average solving nodes on set covering, and independent set are significantly better than other methods.
5.3 GENERALIZATION TO LARGER INSTANCES
It is very important for RL. agents transfer larger unseen instances training on large instances is very expensive in the real world. We investigate the generalization ability of our RL agent by solving 100 transfer instances under default setting. To meet the needs in practice, we say a method wins in this experiment if results in the fastest solving time. As VFS is not able to solve any transfer instance in time limit, we do not list its results in Table. We can see, except for RPB and SVM having comparable performance on hard set covering and hard facility location, respectively, the RL agent leads the performance. In set covering (hard) and maximum independent set (hard), we do not compute the average number of nodes for full strong branching as it solves too limited instances.
5.4 IMPROVEMENT ANALYSIS
Having seen the improvements brought by RL, we would like to ask what kind of decisions our agent learns. We answer this question in aspects: finding lower primal bound e and obtaining higher dual value that
The source code has been released in Gasse al. 2019
7

---

Under review conference paper at ICLR 2021
Table 2: Policy evaluation on transfer instances. Wins are counted by the number times a method results in fastest solving time. The time Tavg is reported in seconds.
Method
T azy
New we
Wins
Tavg
Nav Medium
Wins
Twn
Navz
Wins
FSB
1806
0/85
2835
95
0/57
506
208
3/100
RPB
360
10422
6/100
228
1354
8/100
311
562
4/100
SVM
1003
10170
0/92
1353
2687
8/81
1079
17/100
GCN
351
8789
7/100
1654
9292
0/76
332
1231
7/100
RL
295
7687
87/100
148
1374
84/100
258
1032
69/100
Hard
FSB
3361
0/15
3566
na
0/3
1046
101
0/90
RPB
1608
15043
30/80
1743
1618
21/82
763
281
5/99
SVM
2928
14058
0/30
3243
3850
0/20
606
623
37/100
GCN
1979
15043
0/71
2973
2114
0/26
891
865
5/97
1628
12555
50/80
1497
1648
62/79
624
650
53/100
Set Covering
Independent Set
Facility Location
30
30
GCN
SVM
VFS
primal bound
20
10
10
10
20
30
10
20
30
0
10
20
30
0
10
20
30
number branch constraints
number of branch constraints
number of branch constraints
number of branch constraints
Figure 2: Primal bounds versus the depth in search tree (number of branch constraints) they found
allows pruning in line 5 Algorithm 1
We compare our RL. agent with GCN, SVM, VFC 100 maximum independent set test instances under clean setting.
We first examine primal bound c" Figure 2 plots the feasible solutions found during the solving process. A point (ni, y) means we find a feasible solution e* in a subproblem containing n branch constraints. Figure shows that RL agent is able detect small c" at the early stage. Hence, it can prune more subproblems and solve the MIP faster. On the contrary, VFS fails to detect feasible solutions efficiently. One reason is, traditionally, strong branching or other human-desiin -dennndd heuristics are mainly on the purpose of obtaining higher č. Our result suggests a new possibility for researchers to find variable selection method good detecting feasible solutions.
Then, we check local dual value b. To eliminate the influence in primal bound c* changing, we initialize Cops with the optimal value like Khalil al.) (2016). We plot the curve of average width versus the depth in Figure 3 The area under the curve equals the average number of solving nodes, and we report it the legend. Also, as e" is fixed, the width versus depth plot characterizes how many branches are needed increase the local dual value è to et selection policy closes the gap faster. VFS performs better under this setting than in Figure 2 while still beat by learning based methods, Figure shows that although RL agent has the worst width in the beginning, it has the lowest peak and leads the overall performance. This means our RL agent successfully employs non-myopic policy maximize č in the long term.
to close subproblem. A smaller width indicates the variable
8

---

Under review conference paper at ICLR 2021
17.5
RL-166
-150
15.0
GCN=199
SVM-327
-175
average Wtth
12.5
VFS=239
averoge rewards
225
10.0
7.5
277
PD NSES
-325
GON ES GCN_NSES
-350
0
10
20
30
40
50
depth
frames (xle8)
Figure 3: Average width versus depth
Figure 4: Comparison of RL agents
5.5 ABLATION STUDY
We present ablation study of our method maximum independent set problem by comparing four types RL agents: (1) PD policy + ES; (2) PD policy NS-ES; (3) GCN + ES; (4) GCN + NS-ES. We sample validation set in and plot the average number of solving nodes under clean setting on the validation set during the training process for five random seeds. All agents are initialized by imitation learning. The results are plotted in Figure 4 All curves obtain higher rewards shows that RL improves the variable selection policy. (1) and (2) having larger rewards than (3) and (4) shows that PD policy can obtain more improvement than GCN. Also, (2) and (4) having larger rewards than (I) and (3) shows that novelty
V 200 instances
search helps to find better policies. The results suggest that RL improves learning to branch and both PD policy, NS-ES are indispensable in the success of RI. agent.
DISCUSSION
In this work, we point out the overestimation the decision quality strong branching. The evidence in Table shows VFS performs poor on synthetic dataset under clean setting. An interesting phenomenon is that GCN can easily beat VFS after imitation learning (or our policy can obtain similar result). One possible explanation is that the primal-dual message passing structure naturally learns the good decisions and ignores the noise brought by strong branching. Another possible reason is the biased sampling. To keep the diversity of the samples, Gasse et al. (2019) employs mixed policy of RPB and VFS to sample the training data. VFS probably performs good on most of the states while has poor decision quality when trapped in some regions. As result, VFS has poor overall performance. Fortunately, using the mixing policy as the behavior policy helps to escape from these regions hence, the collected data have good decision quality. More studies needed before can give confident answer for this question.
7 CONCLUSION
We present NS-ES framework to automatically learn the variable selection policy for MIP. Central to approach is the primal-dual policy network and the set representation of the B&B process. We demonstrate RL agent makes high-quality variable selection across different problems types and sizes. Our results suggest that with carefully designed policy networks and learning algorithms, reinforcement learning has the potential to advance algorithms for solving MIP.
9

---

Under review conference paper at ICLR 2021
REFERENCES
Tobias Achterberg. Conflict analysis in mixed integer programming. Discrete Optimizationn4():. 2007.
Tobias Achterberg. Scip: solving constraint integer programs. Mathematical Programming Computation (1): 2009.
Tobias Achterberg and Timo Berthold. Hybrid branching. International Conference on Al and OR Techniques in Constriant Programming for Combinatorial Optimization Problems pp. Springer, 2009.
Tobias Achterberg and Roland Wunderling. Mixed integer programming: Analyzing 12 years of progress.
In Facets of combinatorial optimization pp. Springer, 2013.
Tobias Achterberg, Thorsten Koch, and Alexander Martin. Branching rules revisited. Operations Research (et)ers33(1): 2005.
Réka Albert and Alsert-László Barabási. Statistical mechanics of complex networks. Reviews of modern p1y) 2002.
Alejandro Marcos Alvarez, Quentin Louveaux, and Louis Wehenkel. machine learning- based approxima- tion of strong branching. INFORMS Journal ())) 2017.
Karl Astrom. Optimal control markov processes with incomplete state information. Journal of mathe- matical analysis and applications10(1)) 1965.
Egon Balas and Andrew Ho. Set covering algorithms using cutting planes, heuristics, and subgradient optimization: computational study. In Combinatorial Optimization pp. Springer, 1980.
Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch. arXiv preprint arXiv: 10150, 2018.
Cynthia Barnhart, Amy M Cohn, Ellis Johnson, Diego Klabjan, George L Nemhauser, and Pamela Vance. Airline crew scheduling. In Handbook of transportation science pp. Springer, 2003.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d' horizon. European Journal of Operational Research, 2020.
Timo Berthold. Primal heuristics for mixed integer programs. 2006.
Edoardo Conti, Vashisht Madhavan, Felipe Petroski Such, Joel Lehman, Kenneth Stanley, and Jeff Clune. Improving exploration in evolution strategies for deep reinforcement learning via population of novelty- seeking agents. In Advances in neural information processing systems pp. 2018.
Gérard Cornuéjols, Ranjani Sridharan, and Jean-Michel Thizy. A comparison heuristics and relaxations for the capacitated plant location problem. European journal of operational research50(3). 1991.
Giovanni Di Liberto, Serdar Kadioglu, Kevin Leo, and Yuri Malitsky. Dash: Dynamic approach for switch- ing heuristies. European Journal of Operational Research248(3), 2016.
Marc Etheve, Zacharie Ales, Côme Bissuel, Olivier Juan, and Saña Kedad-Sidhoum. Reinforcement learning for variable selection in branch and bound algorithm. arXiv preprint 20Xiv:2005.10026 2020.
Gerald Gamrath, Daniel Anderson, Ksenia Bestuzheva, Wei-Kun Chen, Leon Eifler, Maxime Gasse, Patrick Gemander, Ambros Gleixner, Leona Gottwald, Katrin Halbig, al. The seip optimization suite 7.0. 2020.
10

---

Under review conference paper at ICLR 2021
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. In Advances in Neural Information Processing Systems pp. 2019.
Christoph Hansknecht, Imke Joormann, and Scbastian Stiller. Cuts, primal heuristics, and learning to branch for the time-dependent traveling salesman problem. arXiv preprint arXiv:1805.01415. 2018.
Elias Boutros Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning branch in mixed integer programming. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
Rafael A Melo and Laurence A Wolsey. Mip formulations and heuristics for two-level production- transportation problems. Computers & Operations Research39 2012.
Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport: With applications to data science. Foundations and Trends in Machine Learning (egumingg1((-6)))) 1(5-6); 2019.
Ingo Rechenberg. Evolutionsstrategien.. In Simulaationsseethdden in der Medizin und Biologie pp. Springer, 1978.
Robert Rodosek, Mark G Wallace, and Mozafar T Hajian. A new approach to integrating mixed integer programming and constraint logicprogramming, Annals of Operations research86: 1999.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies as scalable alternative to reinforcement learning. arXiv preprint arXiv: / 703.03364, 2017.
Cédric Villani. Optimal transport: old and new, volume 338. Springer Science & Business Media, 2008.
Minjie Wang, Lingfan Yu, Da Zheng, Quan Gan, Yu Gai, Zihao Ye, Mufei Li, Jinjing Zhou, Qi Huang, Chao Ma. et al. Deep graph library: Towards efficient and scalable deep learning on graphs. arXiv preprint arXiv: 1eee::99900001 0035, 2019.
Daan Wierstra, Tom Schaul, Jan Peters, and Juergen Schmidhuber. Natural evolution strategies. In 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence) pp- IEEE, 2008
Laurence A Wolsey and George L Nemhauser. Integer and combinatorial optimization, volume 55. John Wiley & Sons, 1999.
11

---

Under review conference paper at ICLR 2021
A APPENDIX
A.1 BRANCH AND BOUND
Here we gives a simple illustration B&B algorithm in Figure 5 represents the feasible region of the LP relaxation and the red arrow represents the objective vector. We first solve the LP relaxation and obtain the solution as the red point. Noticing it is not feasible for MIP, we branch the LP relaxation into two subproblems. In (a) we select to split variable to split variable T2- The subproblems obtained after branching are displayed by the shaded purple regions. After finishing solve these two MIPs, obtain the search trees & and fz2. We can that wise selection of variable 22 can solve the problem faster.
Given the LP relaxation, the polytope
and in (b) select
K2
24
(1.2) X/
$
2
1.
14
(x,2y) (3.2)
Infeasible
(xp 12) (3.2) infeasble
(a) split 21 and search tree
(b) split r2 and search tree
Figure Illustration of splitting in B&B and the corresponding search tree
A.2
IMPLEMENTATION
A.2.1
HARDWARF
All the experiments were run at Ubuntu 18.04 machine with Intel(R) Xeon(R) Silver 4116 CPU @ 2.10GHz, 256 GB Memory and Nvidia RTX 2080Ti graphic cards.
A.2.2 PD POLICY
Comparison. PD policy is similar to the GCN in Gasse et al. (2019) but has two major differences. First, we use dynamic reduced graph where fixed variables and trivial constraints are removed due to the variable bounds changing during the solving process while Gasse et al. (2019) do not consider it. The reduced graph can not only save computation, but also give more accurate description the solving state by ignoring the redundant information. The ablation in Section 5.5 shows it is indispensable in the success of RL. Second, we use a simple matrix multiplication in our PD policy while [aasse et al. (2019) use a complicated edge embedding in GCN. In some sense, GCN can be our success reveals that message passing on the I.P relaxation is the true helpful structure.
overparameterized version of method. And
detail. We implement
primal dual policy net using dgl (Wang al. 2019) with hidden dimension h = 64 and ReLU activation. The feature X for variable is a 17 dimension vector and feature Y for constraint is dimension vector. We list the detail of feature in Table.
12

---

Under review conference paper at ICLR 2021
Tensor Name
Description
type
a one-hot encoding for (binary, integer, implicit, continuous)
coef
objective coefficient
lb
variable lower bound
ub
variable upper bound
at-lb
indicator whether solution value equals lower bound
X
at-ub
indicator whether solution value equals upper bound
sol-frac
solution value fractionality
basis-status
one-hot encoding for simplex basis status (lower, basic, upper, zero)
red
reduced cost
age
normalized LP age
sol-val
solution value
obj-sim
cosine similarity with objective
bias
bias value
Y
is-tight
lightness indicator in LP solution
dualsol-val
dual solution value
age
normalized LP age
Table 3: Feature X for variable and feature Y for constraint
A.2.3 BASELINE
FSB. We use the implementation in SCIP
Gamrath et al, (2020)
VFS. We use the implementation in SCIP
Gamrath et (2020)
RPB. We use the implementation in SCIP Gamrath et al.
2020
GCN. We tried implement GCN in dgl (Wang original implementation in Gasse et al. 2019). Hence, we still use the implementation in Gasse et al. (2019)
2019)
however, it significantly slower than the
SVM. We use the implementation in Gasse et al. 2019
A.3 TRAINING
We have two settings clean, default. In experiments, always train and test under the same setting.
Imitation Learning. We initialize our PD policy using imitation learning similar to Gasse et al. (2019). The difference is only use 10000 training samples, 2000 validation samples and 10 training epochs as warm start. In our setting, a policy from scratch can hardly solve an instance in a reasonable time, hence a warm start is necessary.
Novelty Search Evolution Strategy. We improve our RL agent using Algorithm 2 The parameters are set le 4, o le 2, = 40, V 200, 0.25, 3 0.99. T 1000, I
10.
13

---

Under review conference paper at ICLR 2021
Algorithm 2: Evolutionary Strategy with Novelty Score.
Input:
Learning rate a, Noise std Ø, number of workers n, Validation size V, Batch size M, Initial weight X, Weight decay rate 3, Iterations T, Parameter 0. Policy memory M, Instance distribution D. Neighborhood size k.
Output: Best parameter Ohest
Sample validation instances Q1.-.. Qv D
2 Set Riest \ E R(Ub, Qÿ). Best Bu
3 for 1=0 to T do
Sample instances PL, ... PMM D
Sample 61.-.. Cn NO0, I) and compute i 0, oc.
Set M (0 "0, }
for i= to n do
Compute R.
1 Σ m=1 R(0; Pm)
Compute N; m ΣM N(O; Pm; M) end 10
m
Set 02+1 = 0c + a 1 Ei= X N₁c; + (1 x) R24
no
Compute R((+1)= = Eド=ı R(0++1, Qi)
if R(++1) > Rise then
13
Set Rosst = R(++1), Obest 0,41, X = 33x end
14
end
A.4 DATA SET
Set Covering. We generate weighted set covering problem following Balas & Ho 1980). The problem is formulated as the following ILP.
min
WSSS
SES
subject to
Xg 2 1, Ve EU
S:EES
Is E [), VS ES
where 24 is the universe of elements, the universe the sets, w is a weight vector. For any e e U and S E S. E S with probability 0.05. And guarantee that for any it is contained by at least two sets in S. Fach wy uniformly sampled from integer from to 100.
We first generate it as our backbone. Then, every time we want to generate a new problem with m elements, we let Uo (C401, 6402. cm add new e, into 5 S following the pipeline mentioned above.
covering problem with Uo fer,... "aa..""aaaa c200) and So {Si, (.. S1000) and set
14

---

Under review conference paper at ICLR 2021
We generate maximum independent set problem using Barabasi-Albert (Al- bert & Barabási, 2002 graphs. The problem is formulated as the following ILP.
Maximum Independent Set.
TV
subject to
Iu Fe I 1, Vewv E Ty E (0, 11, V V
where V is the set of vertices and E is the set of edges. We generate the BA graph using a preferential attachment with affinity coefficient 4.
We first generate BA graph Go with 350 nodes. Then, every time we want generate new problem with n variables, we expand Go using preferential attachment.
Capacitated Facility Location. We generate the capacitated facility location problem following Cornuéjols et al. (1991). The problem with m customers and n facilities is formulated as the following MIP.
min
Cijdjut Uij
+
fix
i=1
i=1
subject to
Vij 1, Vj
1,...
di3ii S Witi, Vi 1...,7
j=l
Mij 2 0, Vi 1,... n and ,
2; E {0, 1},
where 1 indicates facility i is open, and x; 0 otherwise; Si is the fixed cost if facility i is open; dj is the demand for customer j: Cij the transportation cost between facility j and customer i; Viy the fraction of the demand of customer filled by facility i. Following Cornuéjols et al. (1991). where first sample the location of facility and customers on a dimension map. Then cıj is determined by the Euclidean distance between facility i and customer j and other parameters are sampled from the distribtuion given in Cornuéjols et al. 1991).
We first generate the location of 100 facilities and 40 customers backbone. Then, every time want to generate a new problem with m customers, we generate new m 40 locations for customers and follow the pipeline mentioned above.
A.5 EXPERIMENTS BENCIIMARK FROM GASSE AL
We are mostly interested in improving the variable selection policy on similar problems hence, we generate our benchmark based on backbone. The backbone allows the instances share some common structures such that there exists good policy for the given distribution of problems. Our experiments show that NS-ES is able to learn good policies on this purpose. However, method more random distribution. Here, conduct experiments (2019). We employ the same instance generator and SCIP setting as Gasse et al. (2019). For each category, evaluate the policy on 20 instances with 5 random seeds. We report the average solving time Tavg and shifted geometric mean solving time Tgeu on all instances, average solving nodes Navy and shifted geometric mean solving nodes N instances solved by all instances, and Wins for the times methods leads
also interesting to check the performance of
benchmark from Gasse al.
15

---

Under review conference paper at ICLR 2021
Table 4: Policy evaluation on benchmark from Gasse et al. (2019)
Fasy
Medium
Hard
Method
Tang
T 2co
Nag
N
Wins
T lng
T gco
Navg
Nge
Wins
T
T gco
Naz
N
Wins
VFS
155.74
74.84
249
122
0/100
10.94
9.57
0/100
121.3
7351
2413
0/100
2406 2038
50702
46487
9/56
SVM
14.16
11.49
348
166
0/100
220.8
108.1
6786
2522
0/100
3140
3029
55052
52059
0/34
GCN
8.84
7.97
282
132
5/100
88.5
53.1
4614
1844
44/
100
2311
1971 39735
37699
52/70
RL
7.54
6.38
275
133
95/100
96.4
51.5
4761
1872
56/
100
2611
2248
39802
36863
9/51
Set Covering
VFS
103.32
81.77
121
84
0/100
RPB
3.39
3.10
29
0/100
20.2
19.3
1036
732
0/100
243
167
43147
9074
5/100
SVM
3.09
2.71
125
78
0/100
30.9
26.3
1189
867
0/100
420
272
17171
10933
0/100
GCN
2.26
2.15
106
69
29/100
15.0
13.1
964
694
46/100
219
138
13046
7661
29/100
RL
2.16
2.00
107
68
71/100
14.3
12.8
876
665
54/100
212
132
12700
7531
66/100
Conbinatorial Auction
VFS
298.52
94.18
399
122
(1/00
RPB
50.84
29.18
341
25
13/100
219.9
165.5
371
151
13/100
863
624
245
109
19/97
SVM
84.06
33.71
571
115
3/100
209.3
146.9
606
343
16/100
1365
1029
513
334
1/91
GCN
71.60
27.39
684
109
21/100
196.8
133.0
586
344
28/100
876
573
483
309
48/95
56.43
25.00
109
63/100
191.9
136.7
577
43/100
807
583
527
367
29/95
Capacitated Facility Location
VFS
385.68
144.61
205
50
0/100
RPB
11.68
10.24
270
21
15/100
185.3
143.8
5687
2437
7/100
2809
2365
8374
7294
4/38
SVM
20.67
10.78
431
39
1/100
723.5
306.8
8692
2595
2/100
3330
3159
12991
10807
0/14
GCN
10.92
8.96
0/100
161.6
11110
2563
50/100
2422
1500
3236
2607
37/43
RL
10.38
7.64
305
38
84/100
240.9
104.4
9767
2082
41/100
3039
2439
9241
5936
8/23
Maximum Independent Set
over the number of instance solving to optimal. As VFS is too slow to solve challenge instances, only report its performance on easy instances.
We that, in Table 4 the improvement from RL method is less than that in the main text. Intuitively, the randomly generated instances have less shared structure and leave less room for RL to improve the policy. How can we improve branch policies for randomly generated problems is still question needs more explorations in the future.
16


Reviews:
[{"review_id": "qgkzOViWyPH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n### Summary\n\nThe paper proposes a model for *variable selection* in *Mixed Integer Programming (MIP)* solvers. While this problem is clearly a sequential decision making task, modeling it as an MDP is challenging. As a result, existing works use other approaches such as ranking or imitation learning. This paper overcomes these challenges by introducing a new problem representation. \n\nAdditionally, the paper makes an interesting observation: It demonstrate the problem with mimicking an existing heuristic. This approach has been used in recent works on learning to branch. \n\n### Strong points\n\n- Introducing the MDP formulation is a significant and timely contribution\n- The writing and presentation is very good\n- The observation about imitating strong branching can spark follow-up investigation\n- The empirical results are promising\n\n### Aspects to improve\n\n- The benchmarks and results do not match those reported in *(Gasse et al., 2019)*. This makes it difficult to compare the results of the two papers. I suggest adding experiments using those instances in the appendix. \n\n### Recommendation\n\nThis paper introduces a new direction in the area of *learning to branch in MIP solvers*.  The empirical evaluation suggests promise for the proposed method. The paper has potential for follow-up work. I recommend accepting the paper. \n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "QN95cZ5R_m", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a method of choosing variables for branching in branch and bound approaches to MIP solving. The approach is based on reinforcement learning.\n\nThe paper presents an adequate overview of previous approaches to the problem. There is not a lot of detail about how these approaches work but the overview of the techniques given allows the reader to see how the proposed approach differs from this earlier work and motivates the technique.\n\nThe MDP formulation used appears not to be novel, but the paper presents a novel way to use reinforcement learning to find good strategies.\n\nThe paper makes a clear argument about why simply choosing the same variable as strong branch would is not the best variable selection strategy. This is supported by later experimental results. I am not sufficiently close to the field to know whether this is a novel argument or accepted fact. In any case, it seems worth stating here as it illustrates a significant fault with many existing alternative approaches.\n\nThere are quite a lot of decisions made in the design of the algorithm. While it is clear what has been done, I am unclear on why many of these choices have been made. For example, what is it about NS-ES that makes the authors think it is suited to this task? Is there some feature of the problem that means this is an appropriate method? Ditto the novelty metric. Is is clear how to compute the metric, but there is a lack of argument or intution on why this is an appropriate way to measure the distance between two sets of polytopes.\n\nThe benchmarks used in the testing are sensible. It is always easy to raise questions about whether testing could be on a larger set of problems, but those presented here seem suitable for a conference paper. The competing methods evaluated against are appropriate and fair. The setting does not seem biased towards any of the methods.\n\nThe novel approach appears significantly to beat other learning approaches on two of the problem types. The new approach seems about the same as the other approaches on the facility location problems. It would be interesting to understand what it is about this problem that gives different results.\n\nIn table 1, wins are defined by number of nodes visited. In table 2, the time taken is used instead. Either method could be justified, but to change between experiments without good justification looks dubious.\n\nA side benefit of the paper is that it results in determining branching rules which seem to perform well while not (intentionally) imitating strong branching. There is some investigation of why this is and why the technique works. Further research could build on this and the result may lead to further work on manually constructed branching rules.\n\nThere is a discussion section in the appendices. This seems very odd.\n\nThe paper is very well written - the language is easy to understand and the arguments being made are clear.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "40wl26qkWMz", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary\n\nThe authors present a way of achieving high-quality variable-selection decisions inside a branch-and-bound algorithm for MIP Solving. The learning happens via evolutionary search with a bias for novelty which the authors introduce.\n\n### Reasons for score\n\nThe authors show a significant application performance improvement compared to existing learning aproaches, and visualization/ablations showring where the improvements may be coming from. The paper is readable.\n\n\n### Pros \n\n1. Clear and readable\n1. The experimentation is exhaustive: different MIP Solving settings (e.g. \"clean and default\") and unseen test set problem-instance sizes generalization in the size dimension.\n1. Visualization to try to understand where the improvement is coming from.\n1. Ablations of novelty component inside search and learning architecture\n\n### Cons/Clarifications\n\n1. I don't feel confident that the evidence presented that strong-branching decisions are bad, because of the non-diverse and small sized data distribution -- section 5.2 Table 1 -- I would feel more confident if the data were 300 randomly sampled instances from MIPLIB *if you don't get timeouts in your evaluation then it isn't large enough to be interesting application-wise)\n1. the reward described may not work well when training on instances large enough that take lots of steps to solve\n1. the PD policy net is a graph neural network specialized for bipartite graphs with single-scalar-attributed edges, and its receptive field is 1 hop per layer, so 2 hops for the architecture used in the paper, which raise the question: how does the diameter (or average variable-variable distance) of the data distribution compare to that?\n1. I don't really know if the novelty score will scale well to large MIP instances, or if it is defined for infeasible MIPs. (The network could still be trained on small feasible MIPs).\n\n### Other questions\n\n1. Figure 2 shows that the primal bound improves with the RL network, can we know why/how this is happening? Having a better dual bound could lead to pruning based on that and thus having a better primal bound.\n\n### Typos\n\nfounded -> found in page 7 section 5.4 https://pasttenses.com/find-past-tense\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "0KMpy3Y9kpk", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "###############################################################################\n\nSummary\n\nThe paper presents a novel method for learning branching strategies within branch-and-bound solvers, which consists in a graph-convolutional network (GCN) combined with a novelty-search evolutionary strategy (NS-ES) for training, and a new representation of B&B trees for computing novelty scores. The paper claims this new method provides a significant improvement over state-of-the-art branching strategies, either based on expert-designed rules or on imitation learning of strong branching.\n\n###############################################################################\n\nPros and cons\n\nPros:\n - the idea of learning branching strategies using reinforcement learning instead of imitation learning makes a lot of sense and seems like a promising direction to follow\n - the proposed representation of B&B trees is original\n - the presented results seem promising\n\nCons:\n - the experimental setup followed in the paper is questionable\n - the presented experimental results are inconsistent with the literature, which I find suspicious\n - the overall method description comprises several blind spots and fallacious arguments\n\n###############################################################################\n\nRecommendation\n\nWhile I like the idea pursued in the paper, and I believe the proposed method might be promising, the paper is mostly experimental, and is not sound enough on that side. I therefore recommend rejection of the paper.\n\nFirst, I found the reported experimental results suspicious. The paper is mostly based on the work from Gasse et al., reuses the same code, (almost) the same problem benchmarks, and some portions of text which are identical. This is fine, but then why did the authors conduct experiments only on 3 out of the 4 available benchmarks ? And why are the results inconsistent with those reported in the original paper ? In the presented experiment the SVM model consistently performs better than the GCN model in terms of number of nodes. Why is it so, if literally the same code has been reused, as mentioned in the appendix ? This alone raises serious doubt in my mind about the validity of the reported numbers. At the very least the authors must provide an explanation for that. Also, Figure 4 indicates that a pre-trained GCN model results in a tree size of 350 on independent set problems, which does not coincide with the number 418 reported in Table 1.\n\nSecond, the experimental setup itself is questionable. The authors consider two setups for the SCIP solver, \"clean\", with depth-first-search node selection and all other functions disabled (whatever that means), and \"default\". No explanation is given as to why those two setups are considered. Some experiments are conducted under the \"clean\" setup (Table 1, Figure 2 and 3), other are made under the \"default\" setup (Table 2), and for some experiments this information is missing (Figure 4). What is the purpose of the \"clean\" setup ? It is known that node selection and branching strategies do interact with each other, and all the evaluated branching methods were proposed in the context of a default, state-of-the-art solver. Why then comparing such methods in the \"clean\" setting ? What is the justification here ? Also, the paper lacks a proper ablation study. How much of the reported improvements come from the policy model ? From the RL training ? From the proposed novelty measure ? \n\nThird, I found several arguments to be fallacious. The authors claim their method results in non-myopic policies, without defining what they mean by that. Assuming they mean the policies have access to non-local information, they later on contradict this claim, by acknowledging that the proposed model only processes the local node's LP-based information. The authors also argue that imitating strong branching (SB) is not a good idea, as it results in small trees not because of its branching decisions, but because of side-effects. To back-up their claim, the authors present numbers showing that, once those side effects are removed, the SB tree size is much higher. But in the same table, the GCN model trained to imitate SB results in trees much smaller than the expert (418 vs 1304 on independent set), which again is suspicious, and most importantly contradicts the original claim of the authors. Given those numbers, imitating SB looks like a good idea.\n\nFinally, the proposed method comprises blind spots. The authors present their model as a primal-dual iteration policy, for what looks like a simplified GCN architecture for the one from Gasse et al. The same structure (bipartite graph) and the same features are used. The authors present a Lagrangian dual LP formulation in Equation 4, however I do not see the connection to the proposed model. How is the proposed model a primal-dual iteration policy ? The authors then present what is I believe the most original contribution of the paper, a distance metric for branch-and-bound trees. However, again I found the description of the method rather sloppy. Counting the number of integral points inside a polytope is a hard problem in itself. Is the counting performed over box relaxations only ? If so, how can the proposed representation process MILPs with unbounded variables ? This seems to be a strong limitation to me, which at least deserves a discussion.\n\n###############################################################################\n\nQuestions to authors\n\nI would appreciate if the authors could clarify why they conduct some of their experiments in the \"clean\" setting, why they don't report results on the complete benchmark from Gasse et al., and also comment on the performance of SVM vs GCN, which contradicts what is reported in Gasse et al.\n\n###############################################################################\n\nFinal recommendation\n\nI thank the authors for their detailed response. The authors have clarified some technical details and blind spots of their methods, have fixed their evaluation metric which was wrongfully comparing tree sizes on solved and unsolved instances, and have presented an additional experiment in the appendix on the original benchmark from Gasse et al. These changes are going in the right direction. However, I remain concerned about the experimental setup in the paper, and therefore my final recommendation is still rejection.\n\nFirst, I still find suspicious that the main experiment in the paper is conducted on only 3 (modified) benchmarks out of the 4 proposed in Gasse et al. The authors claim they did not run experiments on the 4th benchmark due limited computational resources, but at the same time they present complete results on the 4 original benchmarks in the appendix. Therefore I believe the explanation given by the authors is fallacious. Results on the 4th (modified) benchmark, and even better, on other additional benchmarks, would be much more convincing and alleviate any doubt about cherry-picking.\n\nSecond, I am not convinced by the argument the authors present to justify their two solver settings: clean and default. I do agree that challenging problems should be solved under the default setting, however I do not see why decision quality should be measured using the clean setting. Decision quality matters in the default setting as well, and one could argue it matters in the default setting only, if the final goal is to improve the solving time of the solver on challenging problems. Moreover, if the authors want to use the tree size as a mean to measure branching decision quality, they must also provide the optimal solution value to the solver at the beginning of the solving process, in order to deactivate side-effects from pruning. See G. Gamrath and C. Schubert, 2018, \"Measuring the Impact of Branching Rules for Mixed-Integer Programming\".\n\nLast, the method proposed by the authors seems to be effective only in the specific benchmark they propose. In the additional experiments they present in the appendix (Table 4), their method does not convincingly improve over the original method from Gasse et al., as the performance gains on the Easy training instances degrade rapidly as one moves away towards the more challenging Hard instances. The very name of the paper, \"Improving Learning to Branch via Reinforcement Learning\", seems to claim that reinforcement learning improves existing learning to branch methods. However, the improvement observed by the authors is very specific to the \"backbone\" setting they propose, and does not seem to translate to the original benchmarks of the methods they compare to. The authors justify their choice of benchmarks saying \"we focus on a more realistic industrial setting\", but I am unsure whether the hypothesis of a \"backbone graph\" is particularly realistic in industrial applications. I do not think the original benchmark from Gasse et al. is particularly realistic either, however I would not give more or less value to either one of the two. As such, I believe it is crucial that the authors report experimental results on both benchmarks in the main body, and provide a discussion as to why RL seems to bring improvement in the restricted \"backbone graph\" benchmarks, but not in the original ones which have more variability. This, in my opinion, would have a much higher scientific value than simply presenting both a new method and a new benchmark, while disregarding how the method performs on previous benchmarks from the literature.\n\nIn light of the changes made by the authors I am willing to raise my rating, however I still recommend rejection for ICLR.\n\n###############################################################################\n\nAdditional feedback\n\np.2 §2: a linear programming -> a linear program\n\np.2 §2: efficiency-effectiveness trade-off -> What do you mean by efficient and effective ? What is the difference ? Do you mean the decision quality / computation time trade-off ?\n\np.2 §3: ignores the redundant information and makes high-quality decisions on the fly -> This is quite vague. How does your policy achieve that ? What redundant information are you talking about ? What is the efficiency-effectiveness trade-off ?\n\np.2 §3: For exploration, we introduce a new representation of the B&B solving process -> How is this new representation related to exploration ? I am missing the argument here.\n\np.2 §5: set covering, maximum independent set, capacitated facility location -> In Gasse et al. 2019, to which you compare as a baseline, there is a fourth benchmark, combinatorial auctions. I must say that not reporting experiments on this complete benchmark is suspicious, as I do not see a reason for not doing it.\n\np.2 §4: primal-dual policy -> Where does this name come from ? Why is your policy primal-dual ?\n\np.2 §5: the long-term overestimation of strong branching -> What does that mean ?\n\np.2 §5: based on primal-dual iteration over reduced LP relaxation -> What does that mean ?\n\np.3 §2: in line 2 -> line 3 I believe\n\np.3 §2: visulization -> visualization\n\np.3 Equation 3: I am not sure I understand this formula. I suppose that $\\phi_t=(\\theta_t,\\sigma_t)$ ? Then $\\sigma_t$ is never updated, but only $\\theta_t$ is ? What is $\\epsilon_i$ here ? I suggest that you clarify the meaning of this equation, which I could understand only after reading Wierstra et al. 2014, Natural Evolution Strategies. Making it explicit what it corresponds to (expected gradient $\\frac{\\delta R(\\theta)}{\\delta \\theta}$ over the population) would greatly help the reader. At the very minimum, all terms should be defined properly.\n\np.3 §4: if strong branching finds [...] -> I hardly understand that sentence. Do you mean that strong branching will induce additional domain propagation (Achterberg 2007, Constraint Integer Programming, §2.3) ?\n\np.4 §2: we set the reward $r_t = -1$ with discount $\\gamma = 1$ -> Maximizing such a reward is equivalent to minimizing the B&B tree size. And as a result it aligns with your evaluation metric (nodes). This should be mentioned, again, for clarity.\n\np.4 Section 4.2: Primal Dual POlicy Net -> I don't really understand this primal-dual thing, given that you use the same features as in Gasse et al. (Table 3) and just replace their GCN model by a simpler, underparameterized version (A.2.2).\n\np.4 Equation 4: I do not see the point of introducing a Lagrangian relaxation here. Neither Equation (4) nor $\\lambda$ are ever used or referred to in the text.\n\np.4 §4: $f_\\mathcal{C}, f_\\mathcal{C}$ -> $f_\\mathcal{C}, f_\\mathcal{V}$\n\np.4 §4: one layer -> one hidden layer ?\n\np.4 §4: For efficiency, we do not include problem set $S$, which makes it a partial observable MDP -> Then your model only has access to local information, and as such results in myopic policies, which contradict one of your initial claims. Myopic by definition means your vision is limited, which is the case here if your model can not observe the full state of the solver but only the local LP.  Unless you mean something else with \"myopic\", which does not have a formal definition in the paper. I think you confuse myopic policies with greedy policies.\n\np.5 §1: as the collection of those leaf subproblems -> Which leaf subproblems ? The leaves of the complete B&B tree ? The partial tree ?\n\np.5 §2: $w(R_i):= \\dots$ -> I understand $Q$ is the original MILP, while $R_i$ is a box. $Q$ restricted to $R_i$ is therefore a regular MILP as well (the local MILP). Counting the number of feasible solutions for a MILP is I believe an NP-hard problem. How do the authors afford to do that ? Do you mean that you look for integral solutions within $R_i$ ? A second comment here: What if some variables in Q are unbounded ? Your weight function does not seem to handle that case...\n\np.5 §2: the feasible solution -> a feasible solution ?\n\np.5 §3: Notice that a polytope in the set representation is invariant with the generating order [...] -> This sentence is ambiguous, and is simply not true. Branching on $x_1$ then $x_2$, depending on whether it is the left child or the right child which is subsequently branched on, does not yield the same collection of polytopes.\n\np.5 §3: pruning behavior -> What is meant here by pruning behavior ? Node selection ? A common procedure to compare branching strategies, is to removes potential side-effects from node selection by providing the algorithm with the optimal objective value from the start. See, e.g., Gamrath and Schubert, 2017, Measuring the impact of branching rules for mixed-integer programming. In this scenario where the goal of B&B is just to close the dual gap, the branching strategy remains a major component of B&B.  This seems to contradict your point here, that your novelty measure is both relevant for branching, while it is mostly driven by the pruning behavior.\n\np.6 §3: we have two settings -> Why having those two settings ? What is the point of the \"clean\" setting ? Also, I think you mean depth-first-search, not deep-first-search.\n\np.6 §7: under clean setting -> Why under that setting ? Would the \"default\" setting be more representative for evaluating the performance of branching strategies ? It is known that branching interacts a lot with node selection, which you arbitrarily changed here to depth-first-search. Is there a reason for that ?\n\np.7 Table 1: I suggest that you group FSB and RPB together, since they can not be compared to the other methods in terms of number of nodes (unfair node counting). Also, the RPB $N_avg$ value should not be bolted, since RPB can not be compared to here in terms of nodes.\n\np.7 §1: under the default setting -> Why do you suddenly switch to the \"default\" setting ?\n\np.7 Table 2: Those numbers are very doubtful. Why does the GCN model result here in larger trees than the SVM model, while the opposite is observed in Gasse et al. ? This should, at the very least, be discussed.\n\np.7 §3: founded -> found\n\np.8 §2: Then, we check dual value $\\hat{c}$ -> If you want to assess the capacity of each strategy for closing the dual gap, why not simply reporting the evolution of $\\hat{c}$ over time ?\n\np.8 §2: our RL agent successfully employs a non-myopic policy to maximize $\\hat{c}$ in the long term -> I do not see that from the curves... I only see that the tree size is smaller, and distributed differently that with the other methods.\n\np.8 Section 5.5: This ablation study is missing a key ingredient: what is the performance of the PD model, trained via imitation learning ? Which part of your improvements comes from your PD model ? Which part comes from RL ?\n\np.8 Figure 4: Why don't those numbers align with those in Table 1 ? Is the ablation study conducted in the \"clean\" setting ? Why do all curves in Figure 4 start at 350 nodes, when the optimal GCN model in Table 1 is at 418 nodes ?\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper describes an RL technique to learn how to branch in discrete optimization.  This advances the state of the art in comparison to previous imitation learning techniques.  However, the reviewers and a public reader raised concerns about the validity of the experiments due to several inconsistencies and differences with previous work that might suggest some cherry picking.  This is too bad since the reviewers really liked the work, but it is important to make sure that the experimental evaluation is done fairly.  I read the paper and I share the concerns regarding the experimental methodology.  Hence the experimental evaluation needs to be revised before publication.
Decision: Reject