BTBS-LNS: Binarized-Tightening, Branch and Search on Learning LNS Policies for MIP
Authors: Hao Yuan
Wenli Ouyang
Changwen Zhang
Yong Sun
Liming Gong
Junchi Yan
Venue: ICLR 2025 Poster (2025)
Keywords: Large neighborhood search
Reinforcement learning
Bound tightening
Primary area: optimization

Abstract: Learning to solve large-scale Mixed Integer Program (MIP) problems is an emerging research topic, and policy learning-based Large Neighborhood Search (LNS) has been a popular paradigm. However, the explored space of LNS policy is often limited even in the training phase, making the learned policy sometimes wrongly fix some potentially important variables early in the search, leading to local optimum in some cases. Moreover, many methods only assume binary variables to deal with. We present a practical approach, termed Binarized-Tightening Branch-and-Search for Large Neighborhood Search (BTBS-LNS). It comprises three key techniques: 1) the ``Binarized Tightening" technique for integer variables to handle their wide range by binary encoding and bound tightening; 2) an attention-based tripartite graph to capture global correlations among variables and constraints for an MIP instance; 3) an extra branching network as a global view, to identify and optimize wrongly-fixed backdoor variables at each search step. Experiments show its superior performance over the open-source solver SCIP and LNS baselines. Moreover, it performs competitively with, and sometimes better than the commercial solver Gurobi (v9.5.0), especially on the MIPLIB2017 benchmark chosen by Hans Mittelmann, where our method can deliver 10\% better primal gaps compared with Gurobi in a 300s cut-off time.

Published as a conference paper at ICLR 2025
BTBS-LNS: BINARIZED-TIGHTEENE BRANCH AND SEARCH ON LEARNING LNS POLICIES FOR MIP
Hao Yuan', Wenli Ouyang'; Changwen Zhang', Yong Sun', Liming Gong' Junchi Yan
AI Lab, Lenovo Research
School of Artificial Intelligence & Department of Computer Science and Engineering & MoE Lab of AI, Shanghai Jiao Tong University
{yuanhac4, ouyangwl1, zhangew5, sunyong4, gonglm3 (engglm)eeeeeee @eeeovo.e...........m... com. yanjunchiesjtu.eda
ABSTRACT
Learning to solve large-scale Mixed Integer Program (MIP) problems is an emerg- ing research topic, and policy learning-based Large Neighborhood Search (LNS) has been a popular paradigm. However, the explored space of LNS policy is often limited even in the training phase, making the learned policy sometimes wrongly fix some potentially important variables early in the search, leading to local optimum in some cases. Moreover, many methods only assume binary vari- ables to deal with. We present practical approach, termed Binarized- Tighhtinn- Seunchandd-eaachh for Large Neighborhood Search (BTBS-LNS). comprises three key techniques: 1) the "Binarized Tightening" technique for integer vari- ables to handle their wide range by binary encoding and bound tightening; 2) an attention-based tripartite graph to capture global correlations among variables and constraints for an MIP instance; 3) an extra branching network as global view, to identify and optimize wrongly-fixe ffxeed backdoor variables each search step. Ex- periments show its superior performance over the open-source solver SCIP and LNS baselines. Moreover, it performs competitively with, and sometimes bet- ter than the commercial solver Gurobi (v9.5.0), especially on the MIPLIB2017 7 benchmark chosen by Hans Mittelmann, where method can deliver 10% bet- ter primal gaps compared with Gurobi in a 300s cut-off time.
INTRODUCTION AND RELATED WORK
Mixed-integer programming (MIP) is well-established optimization problem. In many cases, fea- sible or even optimal solutions are required under strong time limits, and thus efficiently finding high-quality solutions is of great importance. Recently, machine learning for combinatorial opti- mization has been an emerging topic (Bengio et al. [022]) with prominent success in different tasks, e.g. graph matching (Yan et al. 2020), and ML4MIP is also emerging field (Zhang et al. 2023)
solving methods were proposed to deal with specific MIP prob- lems, including construction methods (Ma al. 2019 Xing & Tu 2020 Fu al.) 2021 Zhang
A variety of deep learning-
jet al. 2020; Khalil et al. 2017;; Xin et al.] 2021 and iterative-hased refinements (Wu et al. 2021b
Chen & Tian 2019 Lu et al. 2019 Li et al. 2020). While they cannot be directly applied
wider scope of MIP problems, and thus learning the solving policies for general MIP problems has
also been intensively studied, in which the primal heuristics catch more attention, including Large
Neighborhood Search (LNS) (Wu et al. 2021a Song et al. 2020; Nair et al., 2020a) and Local Branching (LB) (Liu al. 2022). This paper focuses on LNS for solving general MIP problems the powerful yet expensive iteration- based heuristics (Hendel) 2022)..
Traditional LNS methods usually explore a complex neighborhood by predefined heuristics (Gen- dreau et al., 2010), in which the heuristic selection is a long-standing challenging task, especially for general MIP problems, which may require heavy efforts design valid heuristics. Learning-
based methods provide possible direction. Both Imitation Learning (IL) (Song et al. 2020) and
"Corresponding author.

---

Published as a conference paper at ICLR 2025
Table 1: Comparison of our method to existing works, and it achieves the SOTA performance.
References
Applicability
Appreach
Addressing Local Optima
Training
Huang et al.
20236
Binary
LNS
Adaptive Noighburhood Size
Contrastive Leaminng Regression e RL
Binary
Local Branching
based Branching
3000
Rinary
Song 6i an
A120
Binary
LNS
Iniiation & RL
Hondel
General MIP
(Heuristic in B&R)
ALNS
Adaptive Control for
Multiple Heuristics
Multi-anme Bandit
Sommerd al
2021
General MIP
LNS
Adapiive Naghhbrrhoo Sioe
Insiationn
BTBS-LNS
General MIP
Branching
lop LNS
Stop-wise Global Information
Imitation (Branching)
RL (LNS)
Reinforcement Learning (RL) (Wa et al., 2021a Nair et al. 2020a) showed effectiveness in learning decomposition- LNS policies. However, there are still some challenges. The performance of the learned policies may significantly degrade when applied to general integers due to the vast scale of candidate values (compared to binary variables), leading to a large complexity in optimization. Moreover, the learned policies may be trapped in local optimum for complicated cases.
In this paper, we propose a Brnarized-Tighteningg Branch and Search-based LNS approach (BTBS- LNS) for general MIP problems. Specifically, we design the "Binarized Tightening" algorithm to deal with the optimization for general integer variables, where we first binarize the general integer variables and express them with the resulting bit sequence, and then tighten the bound of original variables w.r.t. the LNS decision along with the current solution. In this way. the variable bounds can controlled complexity. Based our binarization formu-
be tightened and explored effectively lation, we further employed an ceauttion-based tripartite graph (Ding et al. 2020) to encode the MIP instances and improved the attention architecture by removing the softmax normalization, which allows us to fully preserve the raw weights between neighboring nodes. Meanwhile, to enhance ex- ploration and optimize some wrongly-fixe backdoor variables (Williams et al., 2003) Khalil al.] 2022) by the learned LNS policy, we leverage extra branching network at each step, providing branching decisions at the global view to help escape local optimum. In a nutshell, this paper can be characterized by the following bullets, which we believe are common building blocks:
1) Bound Tightening for MIP. We propose a new "Binarized Tightening" scheme for general MIP problems with an efficient embodiment of variable encoding and bound tightening techniques.
2) Combining global information step by step with LNS. To assist the learned policy in escaping the local optimum efficiently, we devise an extra variable branching mechanism to select and opti- mize the LNS wrongly fixed backdoor variables, by contrast with the global optimum. The hybrid branch and search policy greatly enhance exploration and show efficiency.
3) Problem encoding with improved attention architecture. We employ an iisention-based tripar- tite graph to encode MIP problems and capture correlations using an improved attention approach, which demonstrates empirical effectiveness.
4) Strong empirical results. Experiments seven MIP problems show that method con- sistently outperforms the LNS baselines and open-source SCIP (Gamrath et al.] 2020). On MI- PLIB2017 benchmark chosen by Hans Mittelmann, it even achieves superior performance over Gurobi, purely taking SCIP as the baseline solver. It can further boost Gurobi when taking Gurobi as the baseline solver (see Appendix(A.4]
We summarize the key related works in Table I and elaborate on more details in Appendix A.I
2 PRELIMINARIES
Mixed Integer Program (MIP) is in general defined as:
min s.t.
C T x Ax b x;
(1)
B; E EZ 2 20 EC (0,
where x E RR is a vector of n decision variables; E RD denotes the vector of objective coefficients.
Ax < b denotes the overall m linear constraints, where A E mmxx represents the incidence
A hroader context that gnes beyond the immediate LNS observations, e.g, contrast with global optimum. e hhpps:/ppato..ssuu wwwplatooossu..uuue aww.cdd/hennchhhmm
2

---

Published as a conference paper at ICLR 2025
solution
feasible solution
ub
Tighten
Update current roluton
Neighborhood Search
Sub- MIP
MIP solver
c.aggec Input MIP
Graph Representation
LNS dedisions
Optimized x
Static
Branch
wrong decisions
Encodl
Branching Policy
general Integers
Update
variable to optimiza
Current solution
Variable
re-optimized solution
Figure 1: Overview of BTBS-LNS. First, we propose "Binarize Tightening" handle general in- teger variables. The Binarize mechanism can binary-encode the variables and split them into sub- optimization bits. With the bit-wise decision by LNS, the variable bounds can be refined by bound tightening. Second, we devise branching network on top of LNS to select wrongly fixed backdoor variables at global view, which may help efficiently escape local optimum in some cases.
matrix, with b E IRm. For general MIP instances, the index set of n variables . == {1, n) can be partitioned into three sets, binary variable set B, general integer variable set and continuous variable set C. MIP presents greater challenges compared to integer programming (Wu et al. 202 the continuous variables may require distinct optimization policies with integer variables.
Large Neighborhood Search (LNS) is powerful yet expensive heuristic (Gendreau el al. 2010) takes the best solution so far x" as input and searches for the local optimum in neighborhood:
x = =ar min {c' x] xx=
where N-)) is predefined neighborhood the search scope at each step, and x' denotes the opti- mized solution within N(x*)) ), obtained by destroying and re-optimization from the current solution.
Compared to local search heuristics, LNS can be more effective by using broader neighborhood. However, the selection of neighborhood function N(.) is nontrivial. Heuristic methods mainly rely on problem-specific operators, e.g., 2-opt (Flood 1956 in TSP, which call for considerable trial- and-error and domain knowledge (Papadimitriou & ltzi 1998). The currently popular learning- based approaches mainly focus on binary variables and may be trapped in local optimum due to the learning complexity. In this paper, we propose a binarized-tightening branch-and-search LNS approach. designed address general MIP problems. It may efficiently escape local optimum when the LNS decisions are unreliable in some scenarios.
METHODOLOGY
3.1 OVERVIEW
Fig. presents the overview of our approach. The input is a MIP instance, with its initial fea- sible solution Xy generated by baseline solver. General integer variables first encoded into binary substitute variables, and the instance is subsequently represented as a tripartite graph (Ding al. 2020). which is then fed into the large neighborhood search network, selecting the variable subsets that may need to be optimized at each step, with the remaining variables fixed or bound- tightened (see Sec. 3.2 and (33). Additionally, we devise an extra branching network select some wrongly-fixed backdoor variables by the learned LNS policy, help escape local optimum. With the sequential decisions of the branch and search policy and the resulting tightened variable bounds, an off- the-shelf solver, e.g. SCIP, is applied to obtain the optimized feasible solution X Iterations continue until the time limit is reached, and the optimized solutions can be obtained.
In general, the neighborhood search policy and branching policy trained sequentially, where the training details are described in Sec. [3. and Sec. Sec.B.44 respectively. They optimize the current solution from different views and may remedy the local search drawbacks in some cases.
Sec.3.33
3

---

Published as a conference paper at ICLR 2025
3.2 THE BINARIZED TIGHTENING SCHEME
Variables in general MIP instances can be divided into three categories: binary, general integer (with arbitrary large value), and continuous variables. Previous studies mainly focused on the binary vari- ables (0/1). Limited values greatly simplify the optimization, making it easier deal with compared to the general integer variables, and some learning frameworks have proved their effectiveness (Wu jet al., 2021a; Song et al. 2020). this paper, we concentrated on more general MIP problems, especially for general integer variables.
intuitive method is to directly migrate some efficient binary LNS approaches, e.g., Wu et al. (202Ta), to general integers. In this way, different types of variables are equally treated. At each step, we fix some of the variables (no matter what type the variable belongs to), and solve the sub-MIP with bascline solver e.g. SCIP (Gamrath et al., 2020) or Gurobi G (020)). However, empirical results revealed that the simplified generalized LNS approach (e.g., RL-LNS (Wu et al,, 2021a)) is much slower and significantly underperforms the MIP solvers, e.g., Gurobi. (see Table
and Fig. 3 for detail comparison.)
To address these challenges, propose the so-called "Binarized Tightening" scheme for MIP. The idea is confine the variables within a narrow range around the current solution, rather than directly fixing them, balance exploration and exploitation. It shares simi- lar insights with local search, which relies on the current best solution to guide the search, thus avoiding blind search throughout the en- tire solution space. Specifically, we repre- sent each general integer variable with d = [logz (ub 16)1 binary variables at decreas- ing magnitude, where ub and lb are the upper and lower bounds of the original variable, re- spectively. The subsequent optimization is ap- plied to the substitute binary variables, indicat-
Algorithm Bound tightening Integer variable x;
Require: Initial lower, upper bound of z,; lb, ub; Current solution value: I; p;
Binary LNS decision for rz: a for un- bounded variables, and ş = 1, 1.2,... d} for others.
Ensure: Tightened 1b, ub
1: if x; unbounded then if l6 existed and at = 0 then
2:
3:
ub = 2p lb else if ub existed and of then
4:
5:
= 2p ub
6: end if
7: else
8:
d = [log2 (ub [b)
9:
for = 0: d do
ing whether the current solution is reliable or not. In this way, we transform the LNS for the original variable into multiple decisions on substitution variables. Note that the unbounded variables where wh or lb does not exist, will not
if faa,, = 0 then
lb max(lb, p 1/2(ub Ib)):
12:
ub = (ub. p + (2ubb - 1b));
13:
else
14:
break;
be encoded and will remain a single variable.
15:
end if
The decision for each substitute variable can be
16: end for
obtained from the LNS policy (see See. 3.3
17:
end if
where 0 means the variable indicates reliability
at the current encoded bit, and 1 means it still needs exploration. We design a bound-tightening scheme to fully use the bit-wise decisions in Alg. (see Appendix.[A.9 for example). Specifically, let at represent the decision for the jth substitute variable of variable at step f. Decisions af,; for all') j are checked, and the upper and lower bounds will be tightened around the current solution whenever of, = 0, as in Line 11 12 Therefore, more fixed substitute variables can contribute to tighter bounds. In our embodiment, variables that sit far from both bounds can have a significantly wider exploration scope than close-to-bout variables, as they showed no explicit "preference" on either bound direction, which is significantly different from Nair al.) (2020b) (see Appendix I for detailed discussion). Tightening either bound when the current solution sits precisely at the midpoint of variable bounds, may contribute to performance degradation, which conceptually drives us to design the bound tightening scheme, tightening the bounds the far side iteratively.
In addition, as for unbounded variables, meticulous analysis MIPLIB2017 benchmark (Gleixner et al., 2021) revealed that all unbounded variables within the instances are characterized by un- bounded in only one direction, which means that either lb or ub will exist for all general integer variables (otherwise it will be free to optimize in implementation). In this respect, define a virtual upper (lower) bound when df = 0 as in Line 3 and 5 which share similar insights with regular variables to put the current solution at precisely the midpoint of the updated bounds.
4

---

Published as a conference paper at ICLR 2025
3.3 GRAPH-BASER LNS POLICY PARAMETERIZATION
A bipartite graph is recently popularly utilized in Gasse et al. (2019). Nair et al. (2020b), and Wu al. (202Ta) represent the MIP instance states. However, the objective is not explicitly con- sidered, which may contribute to performance degradation in some cases, e.g. when all discrete variables do not exist in the objectives (Yoon] (022). To capture the correlations between objectives with variables and constraints reasonably. we propose to describe the input instance as tripartite graph = (V. C. E) where V. C, and O denote the variable, constraint, and objective nodes, and E denotes the edges. The features of nodes and edges can refer to Appendix A422. where the new objective node representations are defined as the average states of corresponding variables.
We parameterize the policy (a(a))8)) by attention-based Graph Convolution Network (GCN). Different from Graph Attention Networks (GAT') utilized in (Veličković et al. 2018 Ding et al.) 2020), remove the seftmax normalization fully reserve the raw weights between neighboring nodes and edges, capturing the contributions for each node to the final objectives (see Table 2 for comparison with traditional message passing mechanism: LNS-ATT). The C - V passing as follows (likewise for others):
Σ w (h) + b(gg)) h1t1 fev CONCAT h4, JECON,
1CNNN
where h and by, are the features of node and edge (i,j) at step I; lev is a 2-layer perceptron with relu activation that maps the current states to the next iteration h, N₂ denotes the neighborhood nodes of i and |C n CNN is the counts of neighborhood constraint nodes for node i, used to normalize the weighted sum neighboring features; w// denotes the weighted coefficient between node i and node j at step I, measuring their correlations as follows, where Wey is the weight matrix between constraint and variable.
wfy oss (Wev CONCAT(h,,
At each graph attention layer, the message passing between different types of nodes are V - O O - C. - C. O, O + V. C + V. which are calculated as Eq. 3 sequentially. In this way, after K iterations, the features for both the nodes and edges are updated. We finally process the variable nodes by a multi-layer perceptron and the output value can be regarded as the destroy probability for each variable at this step, serving as the neighborhood search policy in Fig. [] It is trained with Q-actor-critic by RL, following the same protocol with Wu et al. (2021a), while with the following differences:
States: We adopt an attentional tripartite graph to capture correlations among variables, constraints, and objectives. The features are gathered in Table in the Appendix.
Actions: For the general variable x, with d substitutes, the LNS decision at step will contain d binary actions of.j, indicating the current solution reliable or not at each encoded bit j (see Alg. II.
Transition and rewards: We follow the same protocol as (Wu et al. 2021a), where the next state 8141 is obtained by the baseline solver, and the reward is defined as objective improvements.
3.4 STEP-WISE GLOBAL INFORMATION BY BRANCHING
As discussed above, previous single-policy ap- proaches were easily trapped in local optimum at an early stage in some complicated tasks, due to the learning complexity and limited explo- ration even in the training phase. To remedy this issue, intuition is to select and optimize those wrongly fixed backdoor variables by LNS policy each step. With this insight, we pro- posed to learn an extra branching network with imitation learning on top of LNS to filter out those variables at each step. Note that it was only applied to binary variables which are more likely to be backdoors that were fixed earlier, leading to local optima.
LSS
Incoeporte cwnerairmsscoom Cy
Carren solutios
Vaniables cfller solution
Brandhing Labeb
Bawndeigg Label
Globel Branderg
Local Drunching
Figure 2: Global branching Local branching on different label collection schemes
5

---

Published as a conference paper at ICLR 2025
The most critical issue for the branching policy learning is the collection of branch- ing variable labels. In other words, we need to figure out how to identify the po- each
Algorithm 2 Offline training of branching policy for LNS
Require: graph-based states S {sr|e = 1, 1,,..... n)
LNS decisions at each step N = {11 |1 1, 1.
tentially wrongly-fixed variables step. We proposed two different variants, which deal with the issue in global and lo- cal view respectively as in Fig. 2
branching variable labels B = {be = 1::0:1,: 2, ..., ...,..) n2
collected from the global or local branching;
Ensure: trained policy xo (B(B|S,N]
1: // Samples are collected by resolving the training instances, along with the learned LNS:
Global branching (BTBS-LNS-G): It
gathers labels from the fixed variables by
2: Let D = [((.t, [[),, be)l( 2,,,....111 n.......
LNS at each step and contrasts them with
3: // train the model;
the global optimal solution. Variables that
Initialize all learnable parameters 9:
exhibit differing values between these so- lutions are indicative of potentially mis-
5: while stopping criteria not meet do Randomly select a batch of instances De from
classified variables within the current LNS decisions from a global perspective. Since the global optimal solution may be too dif- ficult to acquire in reasonable time, it was replaced by the best-known solution obtained across various approaches within the same time budget.
D:
7:
Optimize by minimizing cross-entropy loss; end while
8:
Local branching (BTBS-LNS-L): Dif- ferent from the global view contrast, it gathers labels by incorporating the follow- ing local branching constraints (Liu et al.
Algorithm 3 Branch and search at the th step
Require: Number of variables n;;
LNS decisions No = {nfli 1, 2, ...., n1:
2022) at each step:
branching decisions B² (b 11:=1,2 1,2, 2..,....1. n):
la ++ El
x
< k
(5)
variable set x = {z,li = 1, 2, .... n):
best solution at the 8th step x"
tagli
BEBnT
1.,,
where F is the currently fixed variables set by LNS. With this extra constraint, the re-defined sub-MIP can be solved by the baseline solver, and up to K changed fixed variables will be selected a local view as the branching variable labels at the current step. The selected variables are regarded as locally wrongly fixed variables by LNS.
The ratio for branching variables r;
Ensure: x'+1.
1: Let D = 0:
2: for j = 0 do
3: if r. is general integer variable then
4: Tighten the bound as in Alg. using nf,,
(with d separate decisions for each substitute variable);
With the collected labels for each variable,
5:
else
6:
if 1 and x; is binary variable then D= (i):
branch (1) or not (0), the branching net-
work can be trained offfine. The inputs
7:
tripartite graph- based features (see Ta- ble [7 in the Appendix). where we addi-
8:
else
9:
if n² 0 then
tionally append the LNS decisions made
10:
Fix the value xf+1 z/;;
by the learned LNS policy as variable fea- tures, we only focused on the fixed vari- ables for extra branching. Note that the input states are collected by resolving the training instances, along with the learned LNS policy. The labels are also gathered within the resolving at each step. Then the graph-based features are fed into a similar graph attention network as described in Sec. 3.3 to update the node/edge representations. We finally process the variable nodes by a multi-layer perceptron (MLP) and the output value can be regarded as the branching probability for each variable at this step. Cross-entropy loss was utilized to train the branching network to bring the outputs closer to the collected labels, with the pipeline as in Alg. 2
11:
end if end if
12:
13: end if
14: end for
15: add constraint Σ 10 ++ - 211 Srn to sub-MIP:
LED
16: Optimize x with the solver;
Except for the label collection scheme, BTBS-LNS-L and BTBS-LNS-G remain all the same. The branching policy takes effect on top of LNS, enhancing exploration and optimizing its wrongly fixed backdoor variables at each step. The pipeline for the hybrid framework is given in Alg. 3 where

---

Published as a conference paper at ICLR 2025
Table Comparison on binary Integer Programming (IP) problems: SC, MIS, CA, MC. We also let SCIP run for longer time (500s with SCIP (500s) and 1000s with SCIP (1000s), respectively). So for Gurobi and our BTBS-LNS in other tables.
Methaas
Curi.
Cowming (SC)
Capp
Mixtinal Independent Set (MIS)
Cupdi
Cambinstonal Auction (C.))
Pi(x))))
Mariinum Can [MC)
Capel
SCIP
2:23
20225
0.23
212255
4:71
33124
K.0]
13193
SCIP (500s)
1.40
0.18
3.36
7.11
SCIP (1000k)
1.06
0.09
2.40
6.87
1.54
23459
1.50
11454
9.42
400.0
6.72
11355
R-LNS
4.17
23015
1.20
693.45
6.92
365122
6.33
10933
FTALNS
3.48
20088
1.42
1103.7
933
4123.6
6.30
10554
DINS
3.97
22735
1.24
657.5
4.48
3337.4
5.75
10036
GINS
3.81
22197
0.75
683.6
6.90
3599.8
5.41
9765.1
RINS
3,63
21835
1.33
816.5
7.33
1863
6.04
10277
RENS
2.35
19112
0.79
792 36
4.40
$125
5.29
9116
1.29
17625
0.07
192.63
2:36
2271.6
4.25
6538
Branching
1.72
18007
0.07
183.46
3.09
2492. 7
3.99
6104
GNN-GRIIT
1.78
18169
0.22
295 43
2.24
2206.
4.85
7492
CE-LNS
0.02
17005
0.07
182.99
2.05
2198.5 5
3.03
$881.5
LLSS TO
17:6
16528
0:08
152:24
2:32
2237.8
3315
4782.6
LNS Branch
1.31
17234
0.09
[82 19
2.36
2275.3
3.75
5840.0
LNS-ATT
1165
16714
0.37
182 10
2:23
2251.5
2.99
3975. 1
DIES
1347
16234
0,30
191.47
2:18
21933
1.9
2313
NTBS-LNS-G
0.35
16286
0.05
176.95
1.43
19989
0.59
785
Curobi
16/56
17318
1.44
2073.4
842
Table 3: Generalization to large-scale binary IP instances using the trained policies from small problems in Sec. 4.2
Methods
Sei Cloweing (S(.)
GapSi
P1
Clayrs
Maximnll Inseperalent Sui (MISZ)
Pt
Gap'
Combintiooal Auctivn (CA.)
PloxIoP)
Gap'i
Maximum Cal (MC))
Pl
SCIP
4.51
14953
3.45
9542.1
17.57
12312
5.58
30039
SCIP (500g)
2.74
0.56
5.18
5.36
SCIP (1000))
1.37
0.52
5.13
5.13
L'NNS
1595
14258
0.97
27783
1.57
80123
7.00
21502
R-LNS
3.94
14392
0.71
2079.3 3
6.34
7050.0
6.50
23450
FE-LSS
4.40
14885
0.96
2765.6
9.08
5324.2
6.44
22347
DENS
2.00
13916
0.65
1935.4
6.11
6848.5
7.00
24815
GINS
3.14
1400
6A09
2011
6.74
76337
6,50
21877
3.95
11793
0.58
7130-1
6.75
23619
2.78
1782.6
6.23
20459
15227
3.30
S149.5
Braching
170M
3.19
CL-ENS
12914
1298.5
2.83
7184.1
BYDS-LNS-L
0.51
12431
0.04
$43,89
4800.3
1,45
3583.9
LTDS-LNS-G
0.65
12498
0.02
515.28
1.44
3397.5
12538
0001
295.88
37233
1.01
21950
Methods
P1
MExual Insoperdeo (MTSS4)
PI
Masimum
P1
SCCP
5:41
13524
3.35
3.71
SCIP (506)
4.21
1.44
16.51
8.60
SCIP (1000)
3.05
3.08
16.61
8.46
CALNS
3.21
14814
1.11
97335
7.42
1440
7.30
653345
R-LNS
3.26
14747
0.58
7745.5
6.19
15875
6.98
64712
I'ELSS
3775
1482
1.30
9150.5
8,30
17325
7,00
65529
DENS
1.21
14775
100
7062.4
5.00
14789
6.90
64893
GENS
3.26
14782
0.85
7244.7
5.99
15556
7.04
65777
RINS
2.95
14599
1.00
$21K
5.78
15309
6,89
63575
RENS
2.95
14575
0.32
6972.1
5.17
16916
6,85
62998
RL-ENS
3.71
13866
0.37
5363
1.51
13572
3.76
39645
Braching
S744-8
4.21
43718
GBDT
5233.5
4.52
0.45
4533.4
3.29
37384
1.39
RTBS-INS-G
13789
2616.9
20954
221377
1261
5.38
51296
we fix or tighten the bounds for some variables by the LNS policy (see Line 10p. and select some variables that were labeled 1 by the branching policy (see Line 7) for extra branching. The hybrid branch and search policy work together formulate the sub-MIP at each step.
6
4
EXPERIMENTS
4.1 SETTINGS AND PROTOCOLS
Peer methods. We compare with the following baselines in a 200s time limit by default.
1) SCIP (v7.0.3), Gurobi (v9.5.0): state-of-the-ar open source and commercial solvers, and were fine-tuned with the aggressive mode to focus improving the objectives.
2) U-LNS Wu et al. tation as in Wu et al.
2021a), R-LNSS(Sog et al. 2020): randomized LNS following its implemen- 2021a and Song al. (2220).
3) DINS
Ghosh
2007). GINS (Maher et al., 2017), RINS (Danna et al. 2005) and RENS
(Berthold
2014):
baasd LNS policies that were common utilized.
7

---

Published as a conference paper at ICLR 2025
RENS RE-ENS
6:6
Prinal
112
SCIP
Garde
011
BYRS-LNS
500
1030
1500
cocorad)
Figure 3: Performance on Item (Left) & AMIPLIB (Right).
FT-LNS (Song et al. 2020), RL-LNS (Wu al. 2021a), Branching (Sonnerat et al.) 2021), CL-LNS (Huang et al. 2023b) and GNN-GBDT Ye et al., )023): some learning-based LNS policies with imitation learning or RL, following the same protocol as its original implementation.
5) LNS-TG, LNS-Branch, LNS-IBT, LNS-IT, LNS-ATT: Degraded versions of BTBS-LNS, where we replace the tripartite graph with bipartite graph (LNS-TG); ii) remove the extra branch- ing (LNSS-raach); iii) remove the binarized encoding (LNS-IBT) and bound tightening (LNS-IT); iv) replace the attention-based graph network with widely used GAT (Veličković et al. 2018 (LNS-
ATT). Refer to Appendix A.2 for details.
6) BTBS-LNN--F A variant of BTBS-LNS, where we replace our bound tightening mechanism with Nair et al. 2020b).
Instances. covers both binary and MIP problems. We follow (Wu al. 2021a) to test four NP- hard binary Integer Programming Problems: Set Covering (SC), Maximal Independent Set (MIS), Combinatorial Auction (CA), and Maximum Cut (MC). We generate 200, 20, and 100 instances as training. validation, and testing sets, respectively. To evaluate the generalization ability, we also generate scale-transfee test instances, such as SC2 and MIS4 in Table 3 The suffix number refers to instance scales, for which the details are gathered in Table X in Appendix A.2
We also test on two MIP datasets in Machine Learning for Combinatorial Optimization (ML4CO) competition Balanced Item Placement (Item) and Anonymous MIPLIB (AMIPLIB), their of- ficial testing instances. Balanced Item Placement contained 1050 binary variables, 33 continuous variables, and 195 constraints per instance. The anonymous MIPLIB consists of curated set of instances from MIPLIB2017, long-standing benchmark for MIP solvers with diverse distributions, in which general integer variables are included. We also show empirical results on the whole MI- PLIB2017 benchmark set in Sec. 4.5 where our BTBS-LNS even surpasses Gurobi on average.
Hyperparameters. We run experiments on an Intel 2.50GHz CPU. Performance comparison on CPU vs GPU version of our approach is given in Appendix A.5 All the approaches were evaluated with three different seeds, and the average performance was reported (see detailed stability analysis in Appendix (..6). We use the open-source SCIP (v7.0.3) as the baseline solver by default (recall the blue box in Fig. D. Gurobi version experiments are gathered in Appendix A..4 We train 20 epochs for each instance, with 50 iterations per epoch and 2s re-optimization time limit per iteration. LNS and branching are trained sequentially, with RL (see Sec. (.3) and imitation learning (see Sec. 3.4). respectively. The graph convolutional layers were set K = 2 for both policies, with 64-dimensional latent representations for the nodes and edges. Specifically for branching, we set the max branching variables k: 50 in Eq. 5 for the local branching variant. In the inference phase, the branching variable ratio r in Alg. 3 is empirically set to 10% for both branching variants. BTBS- LNS by default denotes the local branching variant BTBS-LNS-L throughout this paper.
Evaluation metric. We calculate the average primal gap (Nair et al. 2020b) to measure the gap between the current solution x and the best-known solution x* found by all methods among the N testing instances, within a fixed time limit To:
N
C x x111
gap
(6)
maxflc; xzl, lc, x
We also calculate the average Primal Integral (PI, (Huang et al. 2023b evaluate the anytime performance within the time limit:
Achterberg et al. 201 2) to
PI
1 N
Σ
To of xi Toe, x;
8

---

Published as a conference paper at ICLR 2025
where x denotes the best solution within t for instance i.
4.2 OVERALL PERFORMANCE EVALUATION
Table compares the results for integer programming. As can be seen, compared with SCIP and all competing LNS baselines, both BTBS-LNS-G and BTBS-LNS-L, achieve consistently superior performance across all problems. LNS-TG, LNS-Branch, and LNS-ATT are degraded versions of BTBS-LNS, and they all perform slightly worse, revealing the effectiveness of the attention-based tripartite graph and the extra branching policy. Comparing the two variants, BTBS-LNS-G delivers consistently superior performance over BTBS-LNS-L, and even surpasses the leading commercial solver on SC, CA, and MC. Note that detailed anytime performance on these instances are shown in Fig. o Fig. 9 in Appendix A.7 further revealing the effectiveness of BTBS-LNS.
We also test our method on two NP-hard MIP prob-
Table 4: Performance on MIP instances.
lems, and the results are gathered in Table 4 Note
also shown in Fig. 3] Our method consistently outper- forms SCIP and the competing LNS baselines and
that the anytime primal gap comparison
Methods
Item Gap%
MIIPLIB
Obj
P
Gap%
SCIP
23,33
50.73
4152.4
13.72
SCIP (500s)
19.83
39.41
slightly worse than Gurobi, capable of finding even better solutions for around 27% test instances on both Item and AMIPLIB.
SCIP (1000s)
17.02
31.05
/
U-LNS
20.39
44.29
3685.6
15.73
R-LNS
20.04
43.64
3485.0
14.96
RL-LNS
20.04
43.58
3498.5
12.55
DINS
18.08
37.23
3075.9
13.10
For the AMIPLIB problem, which contains a curated set of instances from MIPLIB, we split the instances into train, validation, and test sets by 70%, 15%, and 15% with cross vross-validation Policies learned from di- verse training instances are directly applied to the test set. We increase the solving and re-optimization time limit at each step to 1800s and 60s for the in- stances, as they are too large to be solved. Differ- ent from Wu et al. (2021a). we consistently utilize open-source SCIP as the baseline solver. As seen from Table g and Fig. 3 our method significantly outperforms SCIP and LNS baselines and even de- livers slightly better performance than Gurobi at early stage. LNS-IBT, LNS-IT and BTBS- LNS-F achieve significantly inferior performance than our BTBS-LNS, showing the effect of the "Binarized Tightening" technique and its superiority over Nair et al. (2020b).
GINS
19.78
42.11
3514.7
13.64
RINS
20.53
44.88
3662.5
13.89
RENS
17.51
34.18
2925.0
11.75
Branching
18.84
40.12
3237.6
12.95
LNS-TG
18.05
37.85
3090.5
6,45
LNS-Branch
20.12
43.90
3537.0
9.32
INS-ATT
15.54
2512.8
5.45
LNS-IBT
7.63
LNS-IT
1
7.65
LTRS-LNSSL
13.82
16.82
2030.3
4.19
BTBS-LNS-G
13.45
15.78
1912.5 1
4.35
BTBS-LNS-F
1
7.01
Gurobi
12.67
6.73
1895.6
0.81
4.3 PROBLEM-SCALE GENERALIZATION ABILITY STUDY
We test the generalization ability in line with Wu et al.
2021al with 200s time limit. We directly
the trained policies small-scale problems in Sec. 4.2 with results shown in Table 3
As can be seen, the two variants show similar per-
Table 5: Evaluation on CA against Gurobi.
formance on the generalized instances. Compared
with SCIP and all the competing LNS baselines, our
Methods
CA2
CA4
approach still delivers significantly superior perfor- mance, showing better generalization ability. As the problem sizes become larger, it can produce even better results than Gurobi on SC2, SC4, CA2, CA4, and MC4, and only slightly inferior on the remain- ing 3 groups. It suggests that our policies can sometimes be more efficient for larger instances than the leading commercial solver. Notably, there a significant gap between BTBS-LNS and Gurobi for Combinatorial Auction (CA), particularly on CA4.
Ohj
Gap%
Obj
Gap
Gurrhi
-218245
3.60
3399396
12.61
Gunobi(500s)
.22225
0.95
431626
3.14
Gurohi 1000s)
-225629
0.33
-336188
2.11
BTES-LNS
-222590
1.67
-434311
1.39
(S(50)
-225106
0.56
445563
We further increase the time limit to 500s and 1000s respectively on CA, with results shown in Table 5 Our method consistently outperforms Gurobi with the same time limit. For CA4, it can even produce better solutions with a much shorter time limit. It empirically requires over hours for Gurobi to deliver the same primal gap on CA4, being 58x slower than method.

---

Published as a conference paper at ICLR 2025
Averge Piina Cap
0-1
AMIPLIB
Selecie Oytiniual
Rato Viidle
0.1
Branching cato
Optiniized
M
0.2
5-10-2 0.15 0.2
0.05
Branching Variable Ratio
Figure 4: Impact of different branching ratios (Left). Selected & Optimized variables by the LNS (Middle) & Branching (Right) on Balanced Item Placement instances. The upper dotted line denotes the selected variable ratio that can be re-optimized by the learned Search & Branch policy, while the Solid red line denotes the variable ratio with solution value changes.
Table 6: Performance comparison on the whole MIPLIB2017 benchmark set.
SCIP
SCIP(600s)
SCIP(900s)
U-LNS
R-LNS
FI-LNS
BTBS-LNS
BTBS-LNS.F
Gurobi
Gap%
15.13
1L.88
8.79
16.26
13.94
13.07
1,75
3.11
1.88
4.4 BRANCHING POLICY STUDY BY VARIABLE RATIOS
To enhance exploration, extra branching policy was developed to incorporate global information and help the learned LNS policy escape local optimum. Fig. (Left) depicts the impact branching variables ratios (see Alg. 3)
When the ratio r < 0.1, a larger size leads to better performance, optimizing some wrong decisions made by the learned LNS. Fig. [ (Right) depicts the filtered and updated variable ratios. As can be seen, with increasing iterations, growing number LNS fixed variables were re-optimized by the additional branching policy, indicating the LNS decisions other words, incorporating branching on top of LNS was essential to correct potential errors in the LNS decisions. However, when the branching size becomes extremely large, the performance significantly degrades constrained by the solving ability.
sometimes unreliable. In
4.5 EXPERIMENTS ON MIPLIB2017 BENCHMARK
To further evaluate our proposed approach on some heterogeneous and hard instances, we also eval- uated the whole MIPLIB2017 benchmark set from Hans Mittelmann. It contains 240 instances with diverse distributions and difficulties. We compared different methods in a 300s time limit, which is the geometric mean of solving time of the solved instances with SCIP, and the re-optimization time for each iteration was set as 5s. Other hyperparameters remain the same as AMIPLIB in Sec. 4.2 We perform cross-validation for comprehensive comparison across all instances, splitting them into training, validation, and testing sets by 70%, 15%, and 15% respectively, at each round. The policies learned from the diverse training instances are then directly applied to the test set.
The overall comparison results were gathered in Table 6 As can be seen, our proposed BTBS-LNS can deliver 10% better primal gaps compared with Gurobi and achieve significantly better results compared with all the competing baselines. Compared with Gurobi, it can deliver better solutions on 12.4% instances, and obtained equally better solutions on 77% instances, indicating its effec- tiveness and generalization ability. Furthermore, we notice that BTBS-LNS-F performs slightly inferior to Gurobi and our approach, further revealing the superior performance of our Binarized Tightening technique ovir et al. (2020b). Detailed per-instance comparisons are gathered in Appendix[A.8 We also conducted specific experiments on unbounded variables from MIPLIB2017, which are given in Appendix A.3
5 CONCLUSION AND OUTLOOK
We have proposed a binarized tightening branch and search approach to learn LNS policies. It was designed to efficiently deal with general MIP problems and delivers superior performance over nu- merous competing baselines, including MIP solvers, learning and heuristic-based LNS approaches, on ILP, MIP datasets, and even heterogeneous instances from MIPLIB2017. Sufficient ablation studies demonstrate the effectiveness of each component. Considering the potential of our proposed BTBS-LNS on large-scale and cross-distribution instances, the applications in real-world scenarios may be our future direction.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Tobias Achterberg, Timo Berthold, and Gregor Hendel. Rounding and propagation heuristics for mixed integer programming. In Operations Research Proceedings 2011: Selected Papers of the International Conference on Operations Research (OR 2011). August 30-September 2, 2011, Zurich, Switzerland, pp. 71-76. Springer, 2012.
Yoshua Bengio. Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial opti- mization: a methodological tour d d'horizon. European Journal of Operational Research, 290(2): 405 421, 2021.
Timo Berthold. Rens: the optimal rounding. Mathematical Programming Computation, 6:33-54, 2014.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimiza- tion, Advances in Neural Information Processing Systems, 32, 2019.
Danna, E Rothberg, and Pape C Le. Exploring relaxation induced neighborhoods to improve mip solutions. Mathematical Programming, (1):102, 2005.
Jian-Y Ya Ding, Chao Zhang, Lei Shen, Shengyin Li, Bing Wang, Yinghui Xu, and Le Song, Ac- celerating primal solution findings for mixed integer programs based on solution prediction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 1452-1459, 2020.
Merrill M Flood. The traveling-salesman salesman problem. Operations research, 4(1):61-75, 1956.
Zhang- Chang-Hua a Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre-trained model to arbitrarily large tsp instances. Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 1474-7482 2021.
Optimization L C.G. Gurobi optimizer reference manual. 2020.
Gerald Gamrath, Daniel Anderson, Ksenia Bestuzheva, Wei-Kun Chen, Leon Eifler, Maxime Gasse, Patrick Gemander, Ambros Gleixner, Leona Gottwald, Katrin Halbig, al. The scip optimization suite 7.0. 2020.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combi- natorial optimization with graph convolutional neural networks. Advances Neural Information Processing Systems, 32, 2019.
Michel Gendreau, Jean-Y Potvin, et al. Handbook of metaheuristics, volume 2. Springer, 2010.
Shubhashis Ghosh. Dins, mip improvement heuristic. In International Conference on Integer Progrumming and Combinatorial Optimization, pp. 310-323. Springer, 2007.
Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg, Michael Bastubbe, Timo Berthold, Philipp Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, et al. Miplib 2017: data- driven compilation of the 6th mixed-integer programming library. Mathematical Programming Computation, 13(3):443-490, 2021.
Prateek Gupta, Maxime Gasse, Elias Khalil, Pawan Mudigonda, Andrea Lodi, and Yoshua Bengio. Hybrid models for learning to branch. Advances in neural information processing systems, 33: 18087-18097, 2020.
He He, Hal Daume III. and Jason M Eisner. Learning to search in branch and bound algorithms. Advances in neural information processing systems, 27, 2014.
Gregor Hendel. Adaptive large neighborhood search for mixed integer programming. Mathematical Programming Computation, 14(2):185-21) 2022.
Taoan Huang, Aaron Ferber. Yuandong Tian, Bistra Dilkina, and Benoit Steiner. Local branch- ing relaxation heuristics for integer linear programs. Integration of Constraint Program- ming, Artificial Intelligence, and Operations Research. pp. 96-113. Springer Nature Switzer- land, 2023a. doi:
7. URL /atps: //co:///ccc..o/ org /000 1.077008.
2F 27978-3-033 -

---

Published as a conference paper at ICLR 2025
Taoan Huang, Aaron M Ferber, Yuandong Tian, Bistra Dilkina, and Benoit Steiner. Searching large neighborhoods for integer linear programs with contrastive learning. In Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 13869-13890. PMLR, 23-29 Jul 2023b. URL httpps://prt
ngs. mml.
2reas//202//uang223.... html
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial opti- mization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
Elias B Khalil, Pashootan Vaezipoor, and Bistra Dilkina. Finding backdoors to integer programs: monte carlo tree search framework. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 36, pp. 3786-3795, 2022.
Longkang Li, Hui-Ling Zhen, Mingxuan Yuan, Jiawen Lu, Jia Zeng, Jun Wang, Dirk Schnieders, et al. Bilevel learning model towards industrial scheduling. arXiv preprint drXiv:2008.041300 2020.
Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehicle routing. Ad- vances in Neural Information Processing Systems, 34:26198-26211 2021.
Defeng Liu, Matteo Fischetti, and Andrea Lodi. Learning to search in local branching. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 3796-3803, 2022.
Hao Lu, Xingwen Zhang, and Shuang Yang. learning-based iterative method for solving vehicle routing problems. In International conference learning representations, 2019.
Qiang Ma, Suwen Ge, Danyang He, Darshan Thaker, and Iddo Drori. Combinatorial opti- mization by graph pointer networks and hierarchical reinforcement learning. arXiv preprint 1rXivv1911.0493 2019.
Stephen Maher, Tobias Fischer, Tristan Gally, Gerald Gamrath, Ambros Gleixner, Robert Lion Gottwald, Gregor Hendel, Thorsten Koch, Marco Lübbecke, Matthias Miltenberger, et al. The scip optimization suite 4.0. 2017.
Vinod Nair, Mohammad Alizadeh, et al. Neural large neighborhood search. In Learning Meets Combinatorial Algorithms at NeurIPS2020, 2020a.
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Bren- dan O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.133499 2020b.
Christos H Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: algorithms and com- plexiry. Courier Corporation, 1998.
Vangelis Th Paschos. Applications of combinatorial optimization, volume 3. John Wiley & Sons, 2014.
Max B Paulus, Giulia Zarpellon, Andreas Krause, Laurent Charlin, and Chris Maddison. Learning to cut by looking ahead: Cutting plane selection via imitation learning. In International conference on machine learning, pp- 17584-17600. PMLR, 2022a.
Max B. Paulus, Giulia Zarpellon, Andreas Krause, Laurent Charlin, and Chris Maddison. Learning to cut by looking ahead: Cutting plane selection via imitation learning. In JCML, 2022b.
Jialin Song, Yisong Yue, Bistra Dilkina, al. general large neighborhood search framework for solving integer linear programs. Advances in Neural Information Processing Systems, 33: 20012-20023, 2020.
Nicolas Sonnerat, Pengming Wang, Ira Ktena, Sergey Bartunov, and Vinod Nair. Learning a large neighborhood search algorithm for mixed integer programs. arXiv preprint arXiv:2107.10201, 2021.
Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Reinforcement learning for integer programming: Learning cut. In International conference on machine learning, pp. 9367-9376. PMLR, 2020.
12

---

Published as a conference paper at ICLR 2025
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Ryan Williams, Carla P Gomes, and Bart Selman. Backdoors to typical case complexity. In IJCAI, volume 3, pp. 1173-1178, 2003.
Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Learning large neighborhood search policy for integer programming. Advances Neural Information Processing Systems, 34:30075-30087, 2021a.
Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuris- tics for solving routing problems.. IEEE transactions on neural networks and learning systems, 2021b.
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 AAAI Conference on Artificial Intelligence, volume 35, pp. 12042-12049, 2021.
Zhihao Xing and Shikui Tu. A graph neural network assisted monte carlo tree search approach to traveling salesman problem. IEEE Access, 8:108418-108428, 2020.
J. Yan, S. Yang, and E. Hancock. Learning graph matching and related combinatorial optimization problems. In IJCAI, 2020.
Huigen Ye, Hua Xu, Hongyan Wang, Chengming Wang, and Yu Jiang. Gnn&gbdt-guided fast opti- mizing framework for large-scale integer programming. In International Conference on Machine Learning. pp. 99864-39878. PMLR, 2023.
Taehyun Yoon. Confidence threshold neural diving, arXiv preprint arXiv:2202.07506. 2022.
Giulia Zarpellon, Jason Jo, Andrea Lodi, and Yoshua Bengio. Parameterizing branch-and-boun search trees to learn branching policies. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp.
2021.
Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Xu Chi. Learning to dispatch for job shop scheduling via deep reinforcement learning, Advances in Neural Information Processing Systems, 33:1621-166 1632,, 2020.
Jiayi Zhang, Chang Liu, Xijun Li, Hui-Ling Zhen, Mingxuan Yuan, Yawen Li, Junchi Yan. A survey for solving mixed integer programming via machine learning. Neurocomputing, 519: 205-217, 2023.
13

---

Published as a conference paper at ICLR 2025
A APPENDIX
A.1 FURTHER DISCUSSION ON RELATED WORK
The main contributions of our BTBS-LNS are the general applicability and the addressing for lo- cal optima. Most LNS- based approaches (Liu et al., 2022 Nair et al. 2020a Ding et al., 2020 Song et al. 2020: Wu et al. 2021a) solely deal with the binary programming problems due to their simplicity. Recently, some studies have tried to address the general MIP problems (Hendell 2022 Sonnerat et al. 2021 Paulus et al. 2022a), in which Nair et al. (2020b) proposed similar "bound tightening" technique. They differ from our approach in the following aspects. On one hand, the binary decision for each encoded variable was only applied for bound tightening in our approach, rather than directly fixed similar to Nair et al. (2020b). And on the other hand, the current solution value was also considered in bound tightening decisions in our approach. Variables that sit far from both bounds may have significantly wider exploration scope than close-to-bound variables, as they showed no explicit "preference" in either direction. In addition, our approach can easily transfer to unbounded variables. We made a detailed comparison between the two approaches in Table 4 and Table 6. As can be seen, our BTBS-LNS consistently outperforms BTBS-LNS-F, demonstrating the effectiveness of our novel "Binarized Tightening" technique.
As for the local optima challenge, few studies have tried Adaptive Neighborhood Size (ANS) (Huang et al.) 2023a|b] Sonnerat et al. 202T) or hybrid heuristics control (Hendel, 2022). while still requires hand-crafted hyperparameters, which are essential but difficult to determine. To address it more adaptively, we proposed to combine global-view information on top of LNS. When trapped in local optima, extra branching has the potential select those wrongly fixed backdoor variables by the learned LNS policy for re-optimization. It is important to note that the concept of branching extends beyond the confines of the local branching (Sonnerat et al., 202T) and we also devised a novel variant termed "global branching". which can deliver even better performance in some cases. In addition, the major difference between our hybrid framework and the pure local branching approach (Sonnerat et al. 2021) lies in that we concentrate solely on variables fixed by LNS to correct its decisions, rather than the whole variable set. This specificity arises from the observation that LNS frequently converges to local optima when a limited number of backdoor variables are inaccurately fixed. Empirical results in Table 2. 3, and 4 demonstrated that our BTBS- LNS consistently outperforms the Branching baseline by Sonnerat et al. (2021).
We further review other studies related to ours, which can be divided into two categories: One is learningbbased methods for specific MIP problems and the other is for general MIP problems.
Policy learning for specific MIP Problems: MIP problems cover numerous real-world tasks in many fields (Paschos 2014) and quite few studies attempt to solve certain types of problems, such as Traveling Salesman Problem (TSP) and Vehicle Routing Problems (VRP) (Li et al.] [021]] Lu al. 2019), etc. The algorithms can be divided into construction methods and learned improvement heuristics.
Construction methods usually attempt directly learn approximate optimal solutions, like Graph Pointer Networks (GPNs) (Ma et al. 2019) and Monte Carlo tree search (Xing & Tu 2020 Fu
al. 202I) for TSP instances. Compared to construction models, methods that learn improvement heuristics can often deliver better performance, by learning to iteratively improve the solution (Wu
al. 202 The improvement heuristics can be a guide for the next solution selection (Wu al.; 2021b), or policy to pick heuristics (Chen & Tian 2019), or refinement from the current solution (Lu jet al. 2019: Li et al. 2020). In general, both the learned improvement heuristics and construction methods have proved valid in some specific problems. In contrast, this paper aims to solve general MIP problems by learning improvement hcuristic policies.
Learning to solve general MIP problems: Dual and primal are two main perspectives to improve solving efficiency for general MIP problems. Specifically, dual view aims to improve inner policies of Branch and Bound, like variable selection (Gasse et af.) 2019 Zarpellon et al. 2021 Gupta al. 2020), node selection (He et al. (014)) and cut selection (Tang et al. 20200] Paulus et al. 2022b a With better decision at each node, the overall solving process be greatly simplified.
In the primal perspective, the algorithms aim to find better feasible solutions by prediction or learning-basee heuristies. For example, Ding al. (2020) learned tripartite graph-based deep
14

---

Published as a conference paper at ICLR 2025
Table 7: Description of the tripartite graph features.
Tensor
Feature Description
variable type (binary, integer, continuous).
objective coefficient.
lower and upper bound.
reduced cost.
V
solution value fractionality.
(dynamic) solution value in incumbent.
(dynamic) average solution value.
(dynamic) best solution value.
(Branching Only) LNS decisions at current step. cosine similarity with objective.
tightness indicator in LP solution.
C
dual solution value.
bias value, normalized with constraint coefficients
O
average states of related variables.
C
constraint coefficient per variable.
V-O O
objective coefficient per variable.
C-O
constraint right-hand-side (RHS) coefficients.
Table Average variable/constraints instances
Training
Generalization
Num
SC
MIS
CA
MC
SC2
MIS2
CA2
MC2
SC4
MIS4
CA4
MC4
Variahles
1000
1500
4000
2975
2000
3000
8000
5975
4000
6000
16000
11975
Constraints
5000
5939
2674
4950
5000
11933
5344
9950
5000
23905
10717
19950
Table Training, Validation and Test accuracy for graph-based branching network.
Local Branching
Global Branching
SC
MIS
CA
MC
Item
AMIPLIB
SC
MIS
CA
MC
Item
AMIPLIB
Train's
84.9
86.3
83.5
77.5
87.3
81.3
88.5
83.4
75.9
Validation%
84.8
83.5
75,1
82.1
8288
74.9
83.7
84.9
80.9
87.0
8188
75.1
Test's
81.6
72.9
80.5
81.
74.2
83.1
82.6
80.1
84.5
80.7
73,8
neural network generate partial assignments for binary variables, and to deal with the general integer variables, Nair et al. (2020b) proposed a bound tightening mechanism and learned partial assignments for each bit, respectively. Nevertheless, they were only applied in neural diving, and directly fixing may also lead to performance degradation or even infeasibility. To obtain broader applicability, learning-basse based primal heuristics, like large neighborhood search (Huang et al. 2023b
Song et al. 2020 Sonnerat et al. 2021: Nair et al. 2020a), and local branching (Liu et al. gradually catch more attention.
2022
In this paper, we mainly focus on large neighborhood search heuristics, which have achieved re- markable progress in recent years. For example, [Hendel (2022) designed an adaptive approach to combine multiple existing LNS heuristics to enhance the performance of single policy, while it largely limited by the rule-based heuristics and requires hand-crafted hyperparameters. To make it further, learning better neighborhood function became popular recently. [Sonnerat al. (2021) and Song et al. (2020) both utilized imitation learning to select variable subsets to optimize at each step. However, the equal-size subsets make inflexible and dramatically limit the performance. In this respect, [u et al. (2021a) factorized the LNS policy into elementary actions on each variable and trained an RL-based policy to select variable subsets dynamically. However, current studies on LNS mainly focus on binary variables and are often susceptible to local optima even in the training phase due to the problem's 's complexity. In this respect, we propose a binarized tighreennttitt branch and search approach to learn more efficient LNS policies for general problems.
A.2 DETAIL FOR THE EXPERIMENTS
Tripartite graph-based features: We describe in Table 7 the variable, constraint, objective, and multi-source edge features of the tripartite graph utilized in both the LNS and branching policy
15

---

Published as a conference paper at ICLR 2025
Table 10: Performance comparison on MIPLIB2017 instances that contained unbounded variables.
Instance
SCIP
U-INSS
R-LNS
FT-LNS
ubd
BTBS-LNS
Gumbbi
gen-ip0S4
6858.879
6858.879
6852,733
6858.879
6852,733 -4783.733
6852,733
6840 966*
gen-ip002
4783.733*
-4772.597
4772.599
.4768.253
4733.733*
4783.733*
neos-30466 15-uurg
1610
1670
1651
1651
1610
1607
1600
buildingenergy
42652.34
42652.34
42652.34
42652.34
34243.89
33324.73
33283.85
learning in detail. Then we will clarify the features and connections for the encoded substitute variables. They are also characterized by static and dynamic features. For static features, the variable type and bounds are set to binary and 1/0, respectively, while other features are directly inherited from the original integer variables. For dynamic features, the solution value for each substitute variable determined based on the encoded results. For example, for general integer variable with range of [O, 7]. if the current solution value is 5, the solution values of the three substitute variables would be 1, 0, 1. Additionally, the connections between the substitute variables and other nodes are directly inherited from the original integer variables.
Except for the dynamic solving status, all the other features are collected at the root node of the search tree, and the dynamic features are collected along with the optimization process.
Sizes for the generated instances with different difficulties: The average variable and constraint size used in our experiments are listed in Table 8 which consists of small-scale training instances and some hard instances to evaluate the generalization ability.
Accuracy for the imitation learning based branching policy: Table rrpporrs the training, valida- tion, and testing accuracy of the global and local branching variants.
We compare our proposed BTBS-LNS with various baselines, which are explained as follows in detail:
1) SCIP (v7.0.3), Gurobi (v9.5.0): state-of-the-an open source and commercial solver, and were fine-tuned with the aggressive mode to focus on improving the objectives.
2) U-LNS: LNS version that uniformly samples variables fixed subset size. Note that for U-LNS, R-LNS and FT-LNS, we perform the same settings as Wu et al. (2021a).
3) R-LNS: LNS version (Song al. 2020) that randomly groups variables into equal subsets and re-optimizes them.
4) DINS (Ghosh 2007), GINS Maher et al. 2017). RINS DDnnna al. 2005) and RENS
Berthold 2014): heuristic- based LNS policies.
5) FT-LNS (Song et al. 2020): an LNS approach that applies imitation learning to learn the best R-LNS policies.
6) RL-LNS (Wu et al. 2021a):
Reinforcement learning LNS approach for variable subset opti- mization, while mainly focused on binary variable optimization.
7) Branching (Sonnerat al. 2021): An imitation learning- based LNS approach that learned from local branching constraints.
8) LNS-TG: A variant of our method, where replace the tripartite graph with the widely used bipartite graph.
10) LNS-Branch: A variant of our method, where remove the extra branching policy.
11) LNS-IBT: variant of our method, where the general integer variables are equally treated as binary variables.
12) LNS-IT: A variant our method, where we remove the "Tightening" technique and fix the integer variable its current solution when either bit is fixed.
13) LNS-ATT: A variant of our method, where we replace our attention based graph attention net- work with the widely used GAT.
14) BTBS-LNS-F: variant of our method, where we replace our bound tightening mechanism with that proposed by Nair et al. (2020b).
16

---

Published as a conference paper at ICLR 2025
Table 11: Experiments with Gurobi as the baseline for binary Integer Programming (IP)
SC
MIS
CA
MC
Methods
Gap%
P1
Gap%
Pl
Gap%
Pl(x10')
Gap
Pl
U-LNS
2.59
18820
0.41
635.32
3.78
2690.5
4.07
5633,8
R-LNS
3.01
18925
0.34
545.71
4.85
2999.0
3.75
5189.5
FT-LNS
3.38
19521
0.73
462.45
4.40
2856.4
3.79
5214.7
RL-LNS
1.57
16911
0.09
179.94
1.37
2029.1
3.52
4812.5
ETBS-LNS
0.28
15987
0
165.24
0.27
1710.6
0.38
426.89
Gurobi
0.75
16796
173.15
1.44
2075.4
0.62
842
Table 12: Generalization to large-scale binary integer programming (IP) instances with Gurobi as
the baseline
SC2
MIS2
CA2
MC2
Methods
Gap%i
Pl
Gap%
Pl
Gap%
Pl(x10%)
GapSi
PT
U-LNS
2.48
13599
0.32
1551.6
3.06
5442.1
3.76
13713
R-LNS
2.73
14052
0.55
1845.2
2.60
5112.0
3.75
13359
FT-LNS
3.29
14338
0.28
1485.2
3.72
5823.5
4.04
13753
BTBS-LNS
12275
462.38
0.47
4125.1
350.45
Gurobi
0.71
12528
0.01
495.88
3.60
$723.5
1.01
2195.6
SC4
MIS4
CA4
MC4
Methods
Gap%
P1
Gap%
P1
Gap%
PI(x PI(x10")
Gap
Pl
U-LNS
2.56
14150
0.64
5515.7
4.02
15712
4.95
46965
R-LNS
2.36
14112
0.52
4846.3
3.95
15275
4.84
46380
FE-LNS
3.34
14515
0.54
4915.0
3.68
14588
45795
BTBS-LNS
0.27
13424
0.01
2051.8
0.67
10025
11034
Gurobi
1.22
13795
0.04
2215.7
12.61
21959
5.38
51298
Note that the work by Sonnerat et al. (202I) doesn't 't have open-source code and some hyperpa- rameters are difficult fine-tune in different problems. However, to further evaluate proposed framework with pure local branching based methods, we try to reproduce them, with the following details:
1) For a fair comparison, we replace the neural diving in Sonnerat et al. 2021 with an initial feasible solution generated by SCIP, the same our approach.
2) In data collection, the desired Hamming radius f/ are selected as 50, the same as our branching policy.
3) The model structure was the same as its descriptions, where we use the code provided by Gasse al. (2019), and additionally fixed-size window (3 in the paper) of past variable assignments as variable features.
In the inference phase with the learned policy, we performed the same action sampling mechanism as in Sonnerat et al. (2021). As for the adaptive neighborhood size, we start with 10% of the integer variable size, and the dynamic factor was tuned from 1.01 1.05. Best-performing parameters will be selected for comparison in each problem. As a result, on SC and MIS, was set as 1.02, and 1.03 can deliver the best performance on other problems.
A.3 DETAILED ANALYSIS ON MIPLIB2017
In Sec. 4.5, evaluated approach the whole MIPLIB2017 benchmark set, which showed superior performance. To further eval- uate the effectiveness of our novel virtual bound technique specifically for unbounded integer variables (see Alg. 1). we conducted an ex- tensive analysis across all instances featured in the MIPLIB2017 benchmark set. Notably, there are 19 and 4 instances that contained un- bounded integer variables before and after the presolve, respectively. In this section, we compared our BTBS-LNS with a variant BTBS-LNSW/o ubd, where the special handling for unbounded integer variables (see Line 2-6 in Alg. 1) is removed. In other words, unbounded variables were free to optimize at each step. The comparison results on the four instances that still contain unbounded variables after presolve are gathered in Table TO)
Table 13: Evaluation by Gurobi as baseline solver (MIP).
Item
AMIPLIB
Methods
Obj
Gap%
PI
Gap%
U-LNS
17.64
36.08
3004.3
6,44
R-LNS
16.62
31.94
2788.6
6.01
FT-LNS
15.64
27.31
2519.4
5.45
BTBS-LNS
12.27
4.56
1823.7
0.47
Gurobi
12.67
6.73
1895.6
0.81
17

---

Published as a conference paper at ICLR 2025
Table 14: Average Standard Deviations for our proposed BTBS-LNS on different problems.
Mothods
SC
SC2
SC4
Obj
Cap%
Obj
Gapt
Obj
G
BTBS-LNS
347.88
0.59%
0.47
0.88%
293,50 0.77%
0.51
0.68%
160.0 :: 0.68%
1.0%
Methods
Obj
MIS
Gap
MIS2
Gap%
Obj
MIS4
Gap%
ETES-INS
-683.86 = 0.74%
0.05 = 0.78%
-1372.66 2 0.31%
0.04 = 0.21%
-274700
0.32%
0007 = 0.19%
CA
CA2
Methods
Obj
Capt%
Obj
Gapt%
Obj
Gap%
BTBSSLNS
-112864 1 0.32%
2.18
0.299%
221590 1 0.39%
1.77
0.41%
4494311
0.33%
1.39
0.49%
Methods
MCC
MC2
MC1
0b)
Cap% 1.99
Obj
Gap%
Obi
Gap%
BUBSTAS
-00.17
0.48%
0.52%
0.60%
1.45
0.58%
-3664 0.73%
0.84%
Methods
Item
AMIPLIB
112011
Cap%
Gap%
Obj
Gap%
BTBS-LNS
13.82
1,0%
16.82 = 0.96%
4.19 = 1.51%
1,75 = 1.62%
As can be seen, our proposed BTBS-LNS, outperforms the variant BTBS-LNSW/o ubd on two in- stances and achieves parity the other two. These findings underscore the potent effectiveness of our proposed bound-tightening technique, substantiating its value in enhancing solution quality and optimization efficiency. We will continue the experimentation more unbounded MIP problems in the future.
A.4 GUROBI VERSION OF OUR BTBS-LNS
To evaluate the performance of different approaches with Gurobi as the baseline solver, we perform extensive experiments on MIP problems, four binary integer programming problems, and their scale- transfer instances.
The hyperparameters remain unchanged from those in SCIP counterparts. The results of four bi- nary integer programming problems and their scale-transfer instances are gathered in Table [1 and Table 12 The comparison results on MIP problems are reported in Table [3 As can be seen, our BTBS-LNS consistently outperforms Gurobi across all the problems with different sizes, indicating the effectiveness and generalization ability to different solvers.
A.5 EXPERIMENTS WITH CPU VS GPU
All the experiments presented in Sec. were performed on the Intel(R) Xeon(R) E5-2678 v3 2.50GHz CPU with 4 physical cores, and it achieved competitive performance even compared with the leading commercial solver. In this section, we will further evaluate the GPU version (NVIDIA GeForce RTX 2080) of our proposed BTBS-LNS the balanced item placement problem.
Fig. 5 depicts the anytime primal gap comparison between the CPU and GPU versions in detail within the 200s time limit. As can be seen, compared with CPU implementation, GPU version BTBS-LNS delivers slightly better performance almost at any time, in which the overall primal gap and primal integral improve by 0.83% and 0.99%, respectively. In other words, proposed BTBS-LNS may achieve even better performance when implemented in a GPU environment.
A.6 STABILITY ANALYSIS OF OUR APPROACH
To make a fair comparison between different competing ap- proaches, all the experiments in Sec. 4 were conducted with three different seeds. The average standard deviations for our proposed BTBS-LNS on different problems are gathered in Table 14, As can be seen, it is fairly robust to different seeds, with average standard deviations lower than 2% even on hard and heterogeneous problems, like MIPLIB2017.
Averae Prim
0.8
GPU
0.0
CPU
50
100
150
200
Time (second)
Figure 5: Anytime Performance comparison (GPU vs CPU).
A.7 DETAILED ANYTIME PERFORMANCE ON INTEGER PROGRAMMING PROBLEMS
To further evaluate the anytime performance among the competing approaches, we plot the anytime primal gap curves four binary integer programming problems, Set Covering (SC), Maximal Inde- pendent Set (MIS). Combinatorial Auction (CA), and Maximum Cut (MC), respectively. The results respectively.
gathered in Figure
g
9
18

---

Published as a conference paper at ICLR 2025
Aucing Prinae Clp
Avcrage Oop
Avenuee Frimal Gap
RENS
Branching
RL-LNS
SCIP
Gunchi
BTBS-LNS
(sccond))
(scoond)
Time (sacond))
Figure 6: Anytime Performance on Set Covering (SC) problem and its scale-transfer instances.
From left to right: Performance comparison on instances from SC, SC2, SC4. (see Table g for detail).
10-2
0.15
0.2
Avsuge Prinal Gap
Avérgo Primal Cup
RENS
0.15
Deanching
RL-LNS
SCIP
Averiee
80-2
Guncbi
10-2
(secod))
(second)
(second)
Figure 7: Anytime Performance on Maximal Independent Set (MIS) problem and its scale-transfer
instances. From left to right: Performance comparison instances from MIS, MIS2, MIS4. (see Table for detail).
0.4
Ponng.PimalCoo Cap
0.3
0.3
Avenge Prizaal Cup
0.5
Beanching
RENS
RI-INS
SCIP
Cureeii
0.1
0.1
(sccond)
Figure 8: Anytime Performance on Combinatorial Auction (CA) problem and its scale-transfer
instances. From left right: Performance comparison instances from CA, CA2, CA4. (see Table 8 for detail).
0.8
01.5
Average Primal Cup
RENS
0.2
Beanching
Ateage Phinal
Avtrgge Primal
RI-1NS
SCIP
Curebi
(sccond)
(sccond)
Time (socond)
Figure 9: Anytime Performance on Maximum Cut (MC) problem and its scale-transfer instances. From left to right: Performance comparison on instances from MC, MC2, MC4. (see Table g for detail).
As seen from the results, our BTBS-LNS delivers consistently superior performance over the com- peting LNS basclines almost at any point, demonstrating its efficiency and effectiveness. More surprisingly, the proposed approach solver in some cases, especially on the scale-transfer instances, purely by the learned policy on small-scale instances, with SCIP the off-the-shelf solver.
achieve superior performance over the leading commercial
A.8 PER-INSTANCE PERFORMANCE COMPARISON ON MIPLIB2017
Considering that the results on MIPLIB2017 instances may deliver high variances due to the sig- nificantly different problem distributions across instances, showing only the average gap may not be sufficient. In this respect, we report the detailed per-instance performance within the given time limit on the competing approaches, and the results are gathered in Table 15
19

---

Published as a conference paper at ICLR 2025
We report 218/240 instances from the MIPLIB2017 benchmark set. The following instances were removed, as no feasible solution can be found for them within the pre-defined time limit by the off-the-shelf solver SCIP:
1) Instances that are infeasible (6):
bnatt500
1yptamalysisabi285oobjj...
haww-binpac44-
meos-3988577-wolgan
neos859080
2) Instances that camnot generate feasible solution by the baseline solver within timelimit (16):
crypimalysissb12285ooo666
highschooll-aigio
irish-electricity
neos- 130s-1334092
neos-340245 beos-3402455-bbole
45ox-4532228-waih
neos-5104907-jarama
2oos-5114902-kaaam
161116954
ns1952667
peg-solitaire-a3
physiciansched3-3
rail02
supportcase 19
supportcase22
A.9
A SMALL NUMERICAL EXAMPLE FOR ALG.
Consider general integer variable zo with 00, 15) range and current solution of 3. This variable is encoded using 4 substitution binary variables: T0,1, Fo.2, 20,3, and 20,4- At each LNS iteration distinct actions dj,1- 40.2. 4g.3. and ai,4 are taken for each substitution variable, controlling the range of the original variable at different levels of significance. Specifically, the decision actions ab. for all j are evaluated sequentially, and the upper and lower bounds are tightened around the
current solution whenever u = 0, as described in Line 11 12 of Alg. Here are some examples:
1. If ab,1
0 and the others are 1, the updated bounds for zo will be [0, 10).
2. If ab.1 م 0 and the others are 1, the updated bounds for 26p will be [0, 8).
3.
4. If all decision actions are 0, the updated bounds for xo will be fo, 6]. with the current solu- tion precisely the midpoint of the variable bounds. Similarly, when the current solution is 12, the updated bounds will be [9, 15).
In each LNS iteration, our bound tignt-ttghtening method refines the variable bounds around the currett solution, guided by the LNS decisions, to balance computational complexity and exploration effi- ciency. Importantly, this bound- hound-igghtening process is conducted independently at each step, always initiating from the original variable bounds.
20

---

Published as a conference paper at ICLR 2025
Optimal Solution
302
3311.18
26.374
-3
-41
212
90.01
24544.25
-355544311 312
-284248.2 23
754
6742.2
6205.21
4491.45
53
24
33283 85
$5789390
252
26.39942
-12
6
74
25 35148941
351
173
576.34 976.345
576.925
-160
103333.874 874
101282.642 647
37412.6
Gurobi
302
331
26374
-41
212
90.01
24544.25
-35525.90 96
-284248.22
754
6742.2
6205.21
4491.45
53
33283.55 3.85
55789390
252
26.39942.00
-12
88
25148941
351
173
576.345
576.925
-160
103334
101283
37412.6
BTBS-LNN--
302
3315.24
45
26337
41
212
90.01
24544.25
3340092
-280546.4
754
6742.2
6205.21
4491.45
53
34250 38
55789390
252
26.39942.06
-12
23
88
25148941
351
173
576.345
576.225
-160
103334
101283
37412.6
Table 15: Per-instance performance comparison MIPL IIB2017
BTBS-LNS
302
3311.18
26374
41
212
90.01
24544.25
-3540929
-280546.4
754
6742.2
6205.21
4491.45
53
33324.73
55789390
252
26.3942.00
-12
75
25148941
351
173
576.345
576.22
-160
103333
101283
37412.6
FT-LNS
302
3334.01
228
26441
-29
212
93.01
26379.
-354091
-280546.4
755
6743.24
6565 99
4963.66
54
102
42652 34
57921 400
253
11833721
8
78
225
25164070
354
174
-84
576.52
577.316
-133
103334
101344
5669 23
R-LNS
302
3340.3 37
228
26374
-2
-23
212
95.01
27031,
-3540647
-280566
750
6747.78
6584 43
4963,66
42652. 34
43.16
57921
1400
269
11833720
-11
148
250
25222800
356
178
-80
576.52
581,725
-522
103334
101344
56691.2 23
U-LNS
353
3324.38
228
26439
-24
21
93.01
27540.75
-354064.7
-2803464
759
6746.76
6565 99
4719.1
56
102
42652.34
43.16
57921
400
479
261
11833721
-11
148
250
25222800
362
176
-86
$77.475
581 881.725
152
103334
106897
56691.25
SCIP(900s)
302
3313,18
228
26374
-3
41
212
93.01
25571.02
-35406447
-29912122
754
6742.2
6243.77
4641.77
53
102
34250. 38
5792 57921400
1400
252
11833720
-12
148
142
25 25148941
351
173
.95
576.445
576.925
160
103334
101283
38873.46
(600)))0s)
302
3316.92
228
26374
-3
41
212
93.01
27004.55 55
3354064.7
2291121.2
754
6742.2
6303.11
4719.
53
34250.35
57921 400
254
18337220
-12
148
179
25148941
351
-05
576.345
576.225
-160
103333
101283
46179.85 85
SCPP
302
3340.37
228
26374
-23
212
98.01
27031.16
-354064.7
-29912122
754
6742.2
6565 99
4744.08
53
102
42652.3
5792 1400
261
11833720
-12
823
250
25222800
362
173
576.345
576.925
-160
103334
101283
56691.25
Prademmeeimetaan Jesmall
chromaticindes 102 1024-7
inromattcindex51222 112-7
buildingenery
S0-1lspS-224-8. 2-88-8
comp07-2nd -ldx
comp21 1ampp21-260 2idx
cost266-UUR UUB
cvs [6r 1288989
drayage- 100-23
drayage- 25-233
Instance
30n20b8
50v- IO
air
appl-1
appl-2
assi gssignl -5-8
atlanta-ip
blelsl
bab2
bab6
heas Ccys
binkar10.1
bip aip-ar98
bip-ic98
bnatt400
hppe4-08
bruzil3
ebs-cta
CMS750.4
Co- 100
cod
esched007
esched008
dano3 3
dano3_5
decomp2
dws008--0
21

---

Fublished as a conference paper at ICLR 2025
Optimal Solution
934 00.
880.92
37
100
X1
65887
174
230
138
4783 73
6840.97 9,7
470953692
23
2000126600
-2406733.57
-2677958
19686
6382.1
-2851
3942
6375
12159
204. .8.
-3288
24
404227536
404077441
1480195
0.0268
-495
-II
11801. 11801.1851 1857
40005.05 00
11689
211913
-52301
326481.1
109143.5
0.0553
-21718
-20540
Gurobi
934,008
923.01
37
100
81
65887
174
138
-4783.73
6840.97 97
47135500)
1 2000
-24166-35
2607922
19686
6382.1
-2851
3942
6375
12159,49 .9,49
204.08
-3288
24
404227536
404007441
1494101
0.028
.995
111
11
11801.9
40005.05
11689
211913
-52301
326481.1
109143.5
0,0553
-11788
-20540
STBS-LNS--
934.008
880,92
37
100
81
65887
174
230
138
-4722.3 33
6858.55 58
66440030
12000 26N0
-241K--55
-2017958.3
19688
6382.1
-2851
3952
6.75
12159.49
204.00
-3144
27
404989400
40553 1200
1480195
0.0268
-495
-1I
11
11801.19
40005.05
11689
211913
52301
326481.1
109143.5
0.0553
-21718
-20540
BTBS-LNS
934,008
880. 92
37
100
81
65887
174
138
-4783.73
6852.73
484400630
12000 12000
-2406733
20175584
1968
638.
-2851
3942
6375
12159,9
204.08
-3144
24
404989400
005531200
40553
1200
1480 195
0.0268
.495
.II
11
11801.19
40005.05
11689
211913
.22011
326481.1
109143.5
0,0553
-11788
-01400
FI-LNS
934,008
1443.53
37
100
81
6S887
174
230
138
4466 25
6858 88
484400630
12000 1200
-24166-55
2600930
19772
6382.1
-2811
3952
6376
121615
214 794.79
-204
44
4291 82 100
436444000
1495682
0.0392
472
883
31
11801.19
40005.05
11896
212911
.2331
326481.1
372399.4 4
0.0853
-11678
-04400
R-LNS
987.674
1443.53
37
100
81
65887
175
236
140
4772.6
6852.73
484406330
23
1 2000
-2406458
-20558
-3
19848
6.52.1
-2851
3945
6382
121613
212.96
-204
48
443395 100 100
436700200
1557868
0.0772
410
-78
36
11811.9
40005.05
11731
212874
-2301
326820.6
365944
0.0869
-11668
-20540
U-LNS
987.674 .74
1443.53
37
100
S1
65887
176
230
138
4472.66
6858.88 88
4844063
12NND 2M00
-2406-55
-2015465
-
198488
141699
-2851
3952
6375
12160.2
214.795
-214
46
4882 160200000
438115 (0)
1626587
0.067
468
-82
3
31
11801.19
40005.05
11720
212874
-22011
326820.6
365944
0.0869
1676
-00540
SCIP(900s))
234,008
995.77
37
100
81
65887
174
230
138
4778.73
6840.99
48096
23
12600
22000
-2406455
-2
20
19686
6382.1
-2851
3945
6375
12159.49
204.08
-2288
39
4107092000
424958900
1483960
0.0352
4495
-111
28
11801.1 19
40005.00
11689
211913
-52301
326481.
1.48977
0,0553
-21718
-20540
(600)))05))
934,008
995,7 77
37
100
81
65887
174
230
138
4783.73
6840.99
48096 90
23
12000 260N)
-2406458
26NN930
.9
1968G
6382.1
-2851
3945
6382
12159
204,08
-293
41
4 412600400
426090600
1484323
0.038
495
109
28
11801.19
40005.00
11689
211913
-2.301
3264811
282447.
0.0553
-17788
-20340
SCIP
934.008
1313.47
37
100
81
65887
174
230
140
-4783.73
6858.88 88
184400630
23
12000
-2406-58
260687
19686
63N2.1
-2511
3945
6392
121 2159.49
2044.08
-204
48
41 419655200
436700200
1557868
0.067
480
-78
31
11801.19
40005.05
11689
211913
.23011
326481.1
372,399.4 4
0,0553
-21718
-20540
fastigemm 22660012
fhor- binpackcs-ac... 48
graph20- 20- rand
graphdraw domain
istaan bul ------------ nu-cutoll
milo-v1 milo-v12-6-12-60 2-6-12-00--
exp 500-5-5
hypothyroid-k 1 h80x65200
ic97 pooential
1eir97 Lensson
k mushhoom
lcctsched---o0)
map 66715-04
mark markshhre..ce 4.0
mik-255-20-725
momentuml
mushromm-boe best
Instance
e1133.2
1012
enlight
ex
ex9
F057
fiball
gen- ip002
gen gen-ip 1p054
germanir
glass-ss sc
glass44
gmu-33
gmu-
ipp
Icol
Ico2
lotsize:
mad
map 10
mar kshar22
mas 74
mas76
mel 11
mesched
m22v
m222422
22

---

Published as a conference paper at ICLR 2025 5
Optimal Solution
52200
130800
8105
16]
-309
-195
-17783
176
91
1.81775
2008.2
-2. 2.38806 169
-60702288 702988
26756
1600
6307996
71320
453
0.06725
-34.7
988585.6
-13171
12940.5
2.1416
1471
33.38
45.37
27265.71
25009.7
283627957
1613.00 3,039
2612710
562
182
6260
3645
0.11029
0.00384
203
184380
30
112,002
2358.33
3201
Gurobi
52200
1300800
8105
161
-309
-195
17783
176
91
L88075
2008.2
-2.388
600702988
26756
1600
63077 996
71320
453
0.06725
-34.7
988585.65
-13171
1294 .9
2.1416
1471
33.38
45.37
27265.71
25009.7
28362795
1613.039
26 141888
562
182
6270
3645
0.11029
0.00.384
20.3
184380
112,002
3206, 12
3201
BTBS- I---I
522.00
1300800
8105
161
-309
-195
-17783
178
91
723
2099.6
-2.388
607702988
27349
1611
6.107996
141275
454
0.06725
-34.7
988585.62
-13 -3320
12940.5
2.1416
1473
33.38
45.37
27265.71
25309.66
283627957
1613.039
26 1212710
600
182
6260
3645
0,11029
0,00384
20.3
184390
112.002
2358,43
3201
BTRSS-INS
52200
130800
8105
161
-309
-196
-17783
176
91
1.8007
2008.2
22.388
600702288
26756
1607
6307996
141275
453
0.06725
-34.7
988385.0 62
-13 13127
12940.5
2.1416
1471
33.38
45,37
27265.71
25009.7
283627987
1613.039
2612710
562
182
6260
3645
0.11029
0.00 38
203
184380
30
112,002 202
2358.43
3201
607700998
285010500
FT-LNS
52400
1300000
8105
161
-309
-190
-17783
186
91
7.23
2099.6
-2.388
126520
1651
630799%
141275
453
0.08 175
-34.7
9893016
1
13832.17
6,1813
1479
35.14
45.37
7266848
2627744
6760.735
2678506
600
293
6686
4158
0.11257
0.004006
214
245034.5
30
112,002
12359660
3201
R-LNS
52600
131400
8105
161
-305
-790
11778
184
91
8.06
2099.6
-2.388
607702988
97446
165
6307996
151160
454
0.06725
-34.7
989301.6
1
13832,17
7.4454
1479
35.14
51.94
27268 48
26277.44 1.44
285662910
6760.735
2678506
636
293
6960
4293
0.11257
0.00418
214
225044
112,002
12359660
U-LNS
52800
1308800
8403
161
-307
-173
17783
207
91
7.23
2099.6
-2.197
607702988
81469
1670
6307996
141275
453
0.08775
-34.7
990006.3
11067.1
13832,17
6. 1813
1482
35.14
51.94
2726848
2770788 88
283662910
6760.735
2678506
6.36
293
6686
4194
0.11257
0.00418
214
224993.5
112,002
12359660
3201
SCTP(900s)
52200
1300000
8108
161
.309
-192
-1788
184
91
7.2
2099.6
2,388
-007 702988
71336
1607
6307996
151160
453
0.06725
-34.7
989301
11
13639,92 97
2,7595
1473
35.14
45.37
27268.48
2521088
283680100
6760.735
2624735
636
184
6686
3654
0.11207
0.00384
214
184679.5
112.002
2350.54 54
3201
SCTP(60Ns))
52200
(.00800
8108
I61
-309
199
11788
184
91
7.23
2099.6
2,388
607702988
97446
1610
6307996
151160
453
0.06725
-34.7
989301 66
11677.1
13639.97 97
2.8193
1474
35.14
45.37
27268.48 48
25210.88
283680800
6760.735
26275M0
636
293
6686
3744
0.11257
0,003384
214
184745.5
112.002
2359.54 54
3201
SCTP
52600
(30800)
8105
I6l
:309
-19
-17783
186
91
7.23
2099.6
-2 388
607702988
126520
1610
630999
151
453
0.06725
-34,7
989301 16
1067
13832.11 17
7,4454
1477
35.14
45.37
27268 48
25438 44
785010500
6760.735
26785006
636
293
6686
4248
0.11257
0,00405
24
245034.5
112.002
(2359660
3201
doon
Jonee
n8OS- 304661 S muorg
581 200- 206---0-
bohnn
56271668 666-
moda
FENDE STODY
neos-4 758887 787 BAVI
Huna
SRO--M 164 7030 mICk
widden
--atato
cuanzA
neOS 5052403 -
sygnet
Auahuu
D 5 39 ----599--aaaan
kakapo
D 5 18580S nattal
micmur
neox- 122244
Deox- 171448
nRox- 171173
DROx- 1445765
1456979
1582420
n80s-265 7525
DeON-2 2WON-274003 74
DEON-22 2008-2978811 12
neON-2 -20
310
neor-3 3004002
302 2-22
6931
neos- 362 1684
472 282 28
nOON-2 195
DeOS S093ET
DEOK 19522
631710
DeOS- 662469
neos- 787933
Deos 827175
D2Os- p20s-860 360
120--3555000
Instance
n2xeq,36 36q
n330/v36
n3-3
neos
n205-5
neos
neos-
neos--
Neos
DeOs- 1-008-448550
29

---

Published as a conference paper at ICLR 2025 5
Optimal Solution
549 29921
113.656
54.76
318
-27.76
-238
0.15
15
-3719
214
242
231
2
-1524.33
20622
53905
115
38
16862
-35260
15078
8674.34
-14339.4
49324
125055
8124
11
1473
1747
340
17566
155328
-70.57
174
3712
16$395.3
-38000003
423
4521
6020203
-6.68
19449
[1460
-63.21
Gurobi
113.656
54.76
318
-237.76
-238
0.15
15
-3719
214
242
239
2
11244.3
-16.07
20622
53905
152
58
16862
335 1.
15078
-664..4
11339..4
49324
125055
8124
11
1477
1748
340
17567
155331
-70.57
174
3736
165395.3
-3800663
423
4521
-0020003
5 5.68
19497
11460
-63,2
BTBS- LNS-F
113,656
54.76
318
237.76
-238
0.15
15
-3719
214
244
231
2
-5244.33
-548 02
20622
539005
997
58
T6862
.33269
15078
8664.33
-14339.4
49324
125055
8124
11
2609
1762
340
17569
156939
-69 69.89
174
3712
165395.3
36800003
423
4521
-6020203
-6.68
19449
11460
-63.21
BTBS-LNS
113,656
54,76
318
-237.76
-2388
0.15
15
-3719
214
242
231
-1524.33
-548.02
20622
53905
117
58
16862
-33269
15078
-8674.34
-14339,4
49324
125055
8124
11
2609
1748
340
17566
155330
69,89
174
3712
165393.3
-6800603
423
4521
6020203
-6.68
19449
11460
+3.21
FI-LNS
123,66
54.76
2388
-235.76
-234
0.151
15
-3719
214
263
237
14419.7
-29.33
21622
53905
8080
58
16876
-26538
15078
-8674334
-14324.8
49324
125055
8124
11
2609
2916
340
19202
209796
469.99
174
3715
179751.8
-367995 30
457
5489
6020203
4,65
19988
11460
-63.17
R-LNS
122.92
54.83
2388
-23..66
0.167
15
3719
255
4900438
771
-1466.67
-29.366
23622
53905
8080
16876
-26538
15078
-662 84
144244.66
49324
125055
8124
11
2609
2916
340
19527
235396
-69 39
175
3798
179751.
33779530
424
5489
-040300
5..66
19879
11472
-62.41
U-LNS
125.93
54,83
2389
234.76
0
0.171
15
3319
214
4900433
771
2
-1486 67
429.36 36
2/622
53905
8080
58
16876
-26538
15078
8662 84
14310
49324
133707
8124
12
2609
2916
340
19853
235396
-69,89
178
3798
179836.3
-36777270
442
5489
5040303
4.65
1970
11576
-62.41
SCIP(900s)
122.72
54,76
320
-237.76
-238
0.15
15
3319
214
263
231
-524.33
429 36
20622
53905
7906
58
16862
-33062
15078
-674.34
-13255.8 83
49324
125055
8124
11
2609
2916
340
18874
155354
69.09
174
3712
1797518
36800600
423
4521
200020
-5.67
19534
TT460
-63.7
SCIP()00s)
122.72
34.76
320
-237.76
-238
0.15
15
33799
214
4900438
234
2
1524.33
429.36 36
20622
53905
8080
58
16862
-33062
15078
-8674.34
14324.81
49324
125055
8124
11
2609
2916
340
18874
155354
69 09
174
3714
179751.
36799530
423
5489
6020200
-5.66 5.66
19879
11460
-63. 17
SCTP
122.92
54.76
2388
-2.37.6
0.15
15
-3719
214
3900438
300
1419.67
422 36
20622
53905
8080
T6862
-29112
15078
-674.44
14324.46
49324
125055
8124
11
2609
2916
340
19527
235396
174
3715
179751.8
36721080
423
5489
-6020223
4.65
19988
11530
-61.37
-69
nor murseschedd medium hini03
proteindes /2 1h25 22p
proteindesign (22xxx 1p8
nursese sprint02
madiationml 12-05
radiation=5--1 10-02
TOCoCOCTO- 100000000
nexp- 150-20-8-3
ran 4x 8
rococoB 0000000101000000
Instance
Deos- 87306
Deos-911999 91990
neos- 933966
neos 950242
neos- 93.9957733 937323
Doos- 960392
neldiversion
ns 12080000
ns 16448855
776999
830653
nu25 5- pr
opm2-7
p200x 188c
physicianschedee
piperout-O8 08
piperout-27
nt-rpluse- (usc-]
reblock1
matr 100-11
maar p5
roel 1ocl-411
mell-5-11
mo/2alpha3mt
neos1
neos5
neos8
net
nw04
Pg 34
qupl0
rail01
507
Pg
pk1
24

---

Fublished as a conference paper at ICLR 2025 5
Optimal Solution
52.3222744
12890
-0. 0.166923527
-0.17178
-19
-19
3218
-230.99
423
410.76
7753675
8128831
586803238
-16
69
660705646
$29740625
-394
15
16
-7559 2419
48
1745.124
-345
24256.31
7.7586
51906.48
-1132.22
379.07
397.76
24.16
40417
764772
130596
71820
28290
5189487
22.87
11507.41 017.44
10993, (0993,1314 1314
314
19635558
-149,37
88
Gurobi
-50.39
12890
+0,03945
40.17178
-19
-19
3218
-230
423
410.76
7753676
8130643
586803339
-16
69
660705646
299740623
-338
16
20
7559.2419
49
1745.124
-345
24256.31
7.7586
51906.48 48
-1132.223
379.07
397.76
24.16
40417
764772
130596
71820
28290
5189487
22.87
11507.41
10994.13
314
19635558
-149_375
88
BTBS-LAN-E
-52.88
12890
-0. 0616666
-0.17178
-19
-19
3265
-230 99
42.3
410.76
7753675
$128831
586803236
-16
69
660834000
529005800
-394
8
-7543.2 3.26
48
1755,525
-345
24256.31
7.7713
51906 48
-1132.223
379.07
397.76
24.16
40417
764772
130596
72950
29250
5191562
22,87
11507.41
1
314
19635558
-149,375
8
BTBS-LNN
-52.28
12890
0.16966
40.17178
-19
-19
326S
-230.99 99
423
410.76
7753675
8128831
586803230
-16
69
660705646
529740623
.394
15
-7543.28
48
1755.225
.345
24256.31
7.7586
51906.48
-132.222
379.07
397.76
24.16
40417
764772
130596
71820
2N
5189487
22,87
11507.41
11052.3
314
19635558
149.375
FT-LNS
.44.9
12890
-0.1437
49
27
31846.3
-230.91
427
410.76
7833336
8175655
586821 500
-15
70
679524
100
532891300
-121
21
21
-7449 13
49
1768.264
3445
24294.00 09
7,7811
51906.48 48
-132..223
379.07
397.76
24.16
40432
764772
130608
79180
29250
15981 797790
22,87
11507.41
76.81
314
19635558
-149,375
R-LNS
444.9
12890
-0.1437
27
458759
-230.85
428
410.76
7833336
8163698
587089300
-15
67349
990
900
533455300
300
121
-7366 17
51
1768,264
-345
24478.86
7.7685
5192176
-132,223
381.51
397.76
24.91
40432
766345
13059
84090
28460
7282245
25.5
1150748
48328.09 09
315
19635558
146.312
UILNS
-44.3
12902
-0.1437
49
27
45875.
230.78
427
410.76
7833330
81778.33
586829700
-11
60
681 331350000
533010800
121
26
21
-7351.9
50
1755.845
340
24465 78
7.7678
51921 76
-1299228
379.07
399.33
25.12
40432
766166
130608
79180
28290
18223810
22,87
11507.42
48328.09
317
19635558
-14.0031
88
SCIP(900s)
45.13
12890
-0.1708
27
31846.3
-230.99
423
410,76
7765111
8174767
586804500
-15
69
681 081352100 100
532905600
394
26
29
19
-7475.67
49
1747.033
-345
24465.78
7.7683
51921.76
-1132.223
379.07
397.76
24.16
40432
764772
130596
77420
28460
18223810
25.5
1150741
15347.75
314
19635558
149.375
-8
SCIP(6)0))
44.15
12890
0.1698
28
31846.3
-230.99
425
410.76
7765711
8174767
5868 586816300
-15
69
682989900
533010800
-11
26
29
-7437.1
49
1747.033
3345
24465,78
8.0019
51921.76
-1132223
379.07
397.76
24,16
59310
764772
130596
77420
28460
18223810
25.5
11507.41
48 39328,00 09
314
19635558
-149,375
SCTP
44.89
12890
40.1437
49
28
31846.3
-230.91
427
410.76
7833336
8175655
5869
126912700
-11
69
68883288
537245600
-73
26
29
19
-7430. 15
49
1781.003
-345
24478 86
8.0904
51921.76
-1132,223
379,07
397.76
131.88
59310
764772
130596
79180
29420
25255630
25.5
11507.41
463233.3
315
19635620
-149_375
var- sur-smallemerry hem.lleemmrymiiiilil 6
sate satellites litelll.eeeee. 2-00-s
smp-42- -2-4444440
roiSalphal 8
autellliess22-1 440
sp 550x3000
supportaae
supportcase 2
supportcase 8
supportease26
supportease:3
supportcase40
supporteasedu
supporicase6
supportcase?
telp-
thor50dday
traininstunce2
traininstance6
vut-subprob
Instance
ro103000
<250r10
suvse savschedl hed!
Seymour
seymour
sing:26
sing44
sorrel3
sp97ar
sp9
splice
square41
square47
swathl
swaths
timtabl
1r12-30
trento1
triptiml
uecase12 12
uecase9
uniteal.
wachplan
s100
se12
25


Reviews:
[{"review_id": "sUmUJRSgnZ", "reviewer": "Reviewer_mah2", "summary": "This paper proposes enhancements to an existing ML approach to Large Neighborhood Search (LNS) for Mixed-Integer Linear Programming (MILP). The framework is as follows: value-based RL is used in conjunction with a GNN representation of the MILP to learn a policy that selects, at each step, a subset of the decision variables to fix and search around. The RL reward function favors finding a sequence of improving solutions. This paper aims to improve this framework.\n\nFirst, the authors devise a heuristic for efficiently handling non-binary integer variables, a common feature of many MILP problems that has not been dealt with in prior ML work. Second, an existing GNN architecture for MILP is slightly modified to allow for better attention scores. Third, a supervised learning approach is used to override potentially incorrect LNS variable fixing actions made by the RL agent. This is done by training another GNN to predict high-quality solutions. Should an LNS fixing action for a variable disagree with the predicted value for it, the LNS action is dismissed. \n\nExperiments are performed on four problem classes as well as some MIPLIB2017 instances. The proposed method along with some ablations of it are compared to solvers SCIP and Gurobi, non-ML LNS methods, and existing ML LNS methods. Favorable performance is exhibited.", "questions": "Please refer to the weaknesses above.\n\nThe writing can be improved substantially. Here are some minor comments:\n- line 148: consider rephrasing to “selecting the variable subsets that may need to be optimized at each step, with the remaining variables fixed or bound-tightened”\n- 156: “training details are described in Sec. 3.3. ….”\n-  307: “trained offline”\n-  Table 2 caption is incomplete?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. A significant engineering effort is made to improve the RL-LNS approach. It covers the GNN architecture, the handling of integer variables, and the corrective mechanism. That all these aspects are considered simultaneously is a strength of this paper.\n\nS2. Integer variable handling: Although I have questions about this part, it is a solid contribution to this area of research. Typically, we assume that bounded integers can be recast as a set of binary variables. However, this expansion introduces additional variables and constraints which can slow down MIP solving.\n\nS3. Corrective mechanism: I also liked this contribution given that it addresses limitations of RL. \n\nS4. The experimental setup is sound and the performance of the proposed method is very competitive. It is impressive that it can compete with SCIP and Gurobi.", "weaknesses": "W1. The writing can be improved. I have included a sample of minor comments in “Questions” but I do believe that going over the paper using tools such as Grammarly can help improve the clarity of the paper. This is crucial for publication at a conference at the level of ICLR.\n\nW2. The GNN architecture is essentially the same as that of Ding et al.’s. I am not sure that it stands on its own as a contribution. Rather, I view this as an architecture tuning step that is rather incremental.\n\nW3. The corrective mechanism in section 3.4 requires labeled data, namely near-optimal solutions either globally or locally. This increases the data collection cost which now includes this labeling via a MILP solver in addition to RL simulations. Given that the MILPs of interest are NP-Hard to optimize, it is unclear to me that relying on this solving step during data collection is justified. This is a chicken-and-egg situation because if collecting such solutions was easy, no ML would be required. If it is hard, then ML is justified but then this data collection process is potentially prohibitive.\n\nW4. The bound tightening method is not described sufficiently clearly. Perhaps a small numerical example can help Illustrate what you’re doing in Algorithm 1.", "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": "", "extra_scores": {}}, {"review_id": "LfP7m1o2TR", "reviewer": "Reviewer_aDL4", "summary": "The paper presents the BTBS-LNS (Binarized-Tightening, Branch and Search for Large Neighborhood Search), a method designed to solve large-scale Mixed Integer Programming (MIP) problems. It addresses two main issues in learning-based LNS approaches: limited exploration in search spaces, and a tendency to prematurely fix important variables, which may lead to suboptimal solutions. The proposed method introduces three main innovations:\n\nBinarized Tightening: Encodes integer variables into binary form, allowing bound tightening to reduce solution space complexity.\nAttention-based Tripartite Graph: Models relationships among variables, constraints, and objectives to capture global correlations.\nBranching Network: Optimizes potentially misclassified “backdoor” variables to help escape local optima.\nThrough experiments on benchmarks like MIPLIB2017, the method demonstrates competitive performance, often surpassing traditional solvers like SCIP and sometimes outperforming Gurobi.", "questions": "How does the performance of BTBS-LNS scale with increasing problem size, especially compared to state-of-the-art solvers like Gurobi, in terms of both time complexity and solution accuracy?\n\nDoes the choice of baseline solver (SCIP or Gurobi) for generating initial solutions significantly influence BTBS-LNS's overall performance?\n\nHow does the model handle diverse real-world MIP problems where variables might not align as neatly with the tripartite structure employed in BTBS-LNS?\n\nHave you compared your work with a recent related work by Kong et al.? https://proceedings.mlr.press/v244/kong24a.html", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Innovation in Problem Encoding: Using a tripartite graph structure to represent MIP instances is a novel approach that strengthens the model's ability to capture complex dependencies.\n\nGeneralization to Integer Variables: Unlike many LNS methods that focus only on binary variables, BTBS-LNS can handle a broader class of integer variables, improving the method's applicability to general MIP problems.\n\nSuperior Performance: The method shows strong empirical results across multiple MIP problems and benchmarks, achieving lower primal gaps than SCIP and Gurobi in some cases.\n\nAdaptive Bound-Tightening: Binarized tightening provides an efficient exploration-exploitation balance, with flexibility for bounded and unbounded variables.", "weaknesses": "High Complexity: The approach combines multiple advanced techniques, potentially making it computationally intensive, particularly in scenarios requiring extensive parameter tuning or high-dimensional data.\n\nDependence on Initialization: The method relies on an initial feasible solution generated by baseline solvers. Poor initialization could impact overall performance, as the effectiveness of the LNS-based policy might depend on the quality of the starting solution.\n\nLocal Optima: While the branching network mitigates local optima issues, the reliance on imitation learning and reinforcement learning can still lead to convergence to suboptimal solutions in complex or highly irregular MIP landscapes.", "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": "", "extra_scores": {}}, {"review_id": "Gd8IhQVN2A", "reviewer": "Reviewer_bYsh", "summary": "Authors propose a neural large neighborhood search (LNS) policy which improves upon previously proposed methods in mainly three aspects. First, authors focus on general mixed integer programming (MIP) which some variables can be integer type (as opposed to be only allowed binary type), and proposes a \"binarized tightening\" method, which performs much better than previous methods. Second, authors propose to remove softmax operation in the graph neural network for MIPs. Third, authors train additional LNS policies with imitation learning, and let these policies override decisions from RL-trained LNS policy. These imitation-learned policies provide additional signals and hence help escaping from local minimum.", "questions": "How are substitute variables for integer variables represented?  $j$ in $a_{i,j}^t$ should be reflected as feature somewhere, but features in Table 7 does not seem to discuss it.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Significance: The proposed method demonstrates a strong empirical performance compared against a large number of previous learning-based methods as well as strong traditional solvers (Gurobi, SCIP). Such a strong empirical result can drive a stronger adoption of learning-based MIP solvers in practice. The coverage of experiments and the experimental protocol is high quality (discussed below in the quality section), which will give practitioners high confidence to adopt the proposed approach. If successful, this will make a significant impact to applications of MIP.\n\nQuality: The coverage of benchmarks is very high. Authors not only experiment with synthetic tasks popular in previous papers, but also more recent and challenging benchmarks in ML4CO competition and MIPLIB2017. Authors compare against 13 learning-based baselines, which comprehensively validates algorithmic design decisions made in this paper. Although the proposed method is quite complex, such a strong validation justifies the complexity well.\n\nOriginality: Binarized tightening is a novel technique clearly differentiated from previously proposed methods for general MIPs. Other techniques introduced are not very surprisingly new, but still contributes significantly to the performance of the final approach, and validated well by extensive experiments.\n\nClarity: Although the proposed algorithm is quite complex with many components, authors do a good job clearly explaining them, and providing good justifications both conceptually and empirically for every algorithmic design decision they make. Some terminologies are phrased a bit confusingly, however, which I elaborate in the Weaknesses section.", "weaknesses": "Authors argue their branching network leverages \"global\" information and uses a \"global\" view, but I believe this is a misnomer because at the inference time, the branching network uses the same state representations as the LNS policy. It is just that the branching network is _trained_ with different imitation learning signals, global optimum solution for BTBS-LNS-G and local branching for BTBS-LNS-L. Other than the training method (RL vs. imitation learning), the branching network makes the same decisions (whether to fix each variable) as the LNS policy do; in fact, what authors call as local branching is called LNS from previous work (Sonnerat et al, 2022). I would consider these as simply additional LNS policies, just trained differently (RL vs. imitation learning).\n\nWhile my major concern is mostly on the phrasing of \"global\" information because such information is not available at inference time, I also point out that this perspective - that branching networks are simply LNS policy trained differently - offers more natural ways to combine these branching networks into the algorithm. For example, they could be ensembled together using standard ensemble methods, because they are policies for the same objective which are just trained differently. Or, LNS policy could be initialized by these branching policies for transfer learning. I believe these are more natural ways of combining these two policies, rather than first making predictions with RL policy and then override predictions by imitation-learned policies.\n\nThere's another suggestion for clarification. In Line 070, authors say: \"We further develop an attention-based tripartite graph (Ding et al., 2020)\". Although Ding et al (2020) is attributed here, the statement can be read as attention-based tripartite graph being proposed by authors for the first time. To make the attribution clearer, I would suggest to rephrase as something like: \"We employ an attention-based tripartite graph (Ding et al., 2020). We improve the previously proposed attention architecture by removing the softmax normalization, and demonstrate its empirical effectiveness.\" Such statement will make authors' contribution clearer.", "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": "", "extra_scores": {}}, {"review_id": "cB1VFjkrm6", "reviewer": "Reviewer_Xeij", "summary": "The paper presents an ML-guided LNS framework for MIPs. It combines a binarize-and-tighten scheme to address general integer variables and a branching policy to help escape local optima. It also has a search policy to guide destroy variables. In the experiment, the new method is compared against a variety of ML-guided approaches and heuristic approaches. The presented results show that the proposed method finds better solutions at a faster speed.", "questions": "1. What is eq. 6 in figure 2?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper proposes a combination of ML-guided search policy and branching policy for LNS in MIP solving. Various techniques and engineering designs are proposed. The novelty of the paper comes from those details.\n2. The effectiveness is demonstrated in experiments with different settings and ablation studies.", "weaknesses": "1. The proposed methods are not novel. The global branching idea is similar to [2] by learning from the global (near-)optimal solutions. While the local branching variant is similar to [1]. A detailed explanation of the differences from them should be included.\n2. The paper is a little bit hard to follow. It includes a lot of information, it would be good to include a summary of takeaways for each experiment.\n3. How are the policies trained in the MIPLIB 2017 experiments? How do you perform training, validation and testing? The variance of the hardness for MIPLIB is large, how do you deal with it when splitting the training, validation and testing set? Can you also summarize the results on MIPLIB in comparison with the other baselines besides Gurobi? Can you bold the best entry in the per-instance result tables in Appendix?\n\n\n[1] Vinod Nair, et al. Solving mixed integer programs using neural networks. arXiv preprint, 2020\n\n[2] Qingyu Han et al. A gnn-guided predict-and-search framework for mixed-integer linear programming. ICLR, 2023.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)