Learning To Dive In Branch And Bound
Authors: Max B. Paulus
Andreas Krause
Venue: NeurIPS 2023 poster (2023)
Keywords: Generative Modeling
Combinatorial Optimization
Mixed Integer Programming
Graph Neural Networks
Diving Heuristics
TL;DR: We learn a diving heuristic for use in branch and bound to solve to integer programs

Abstract: Primal heuristics are important for solving mixed integer linear programs, because they find feasible solutions that facilitate branch and bound search. A prominent group of primal heuristics are diving heuristics. They iteratively modify and resolve linear programs to conduct a depth-first search from any node in the search tree. Existing divers rely on generic decision rules that fail to exploit structural commonality between similar problem instances that often arise in practice. Therefore, we propose L2Dive to learn specific diving heuristics with graph neural networks: We train generative models to predict variable assignments and leverage the duality of linear programs to make diving decisions based on the model's predictions. L2Dive is fully integrated into the open-source solver SCIP. We find that L2Dive outperforms standard divers to find better feasible solutions on a range of combinatorial optimization problems. For real-world applications from server load balancing and neural network verification, L2Dive improves the primal-dual integral by up to 7% (35%) on average over a tuned (default) solver baseline and reduces average solving time by 20% (29%).

Learning to Dive in Branch and Bound
Max B. Paulus
Andreas Krause ETH Zurich krauseadethz.co ch
ETH Zurich max pax.puulss awraulus@inf.eth..coo ethz.ch .c
Abstract
Primal heuristics are important for solving mixed integer linear programs, because they find feasible solutions that facilitate branch and bound search. A prominent group of primal heuristics are diving heuristics. They iteratively modify and resolve linear programs conduct depth-first search from any node in the search tree. Existing divers rely on generic decision rules that fail to exploit structural commonality between similar problem instances that often arise in practice. Therefore, we propose L2Dive to learn specific diving heuristics with graph neural networks: We train generative models predict variable assignments and leverage the duality of linear programs to make diving decisions based on the model's predictions. 1.2Dive is fully integrated into the open-source solver SCIP. We find that 1.2Dive outperforms standard divers to find better feasible solutions on a range of combinatorial optimization problems. For real-world applications from server load balancing and neural network verification, L2Dive improves the primal-dual integral by up to 7% (35%) on average over a tuned (default) solver baseline and reduces average solving time by 20% (29%).
Introduction
Mixed integer linear programming problems are optimization problems in which some decision variables represent indivisible choices and thus must assume integer values. They arise numerous industrial applications, e.g., workload apportionment to balance server loads. They can be used to
solve combinatorial problems or to verify the robustness neural networks [11, 44]. We write
mixed integer linear program M := Pt), with A Rm** b R C. E R n, H E Rg and
I C (1.....n)) n) indexing the variables restricted to be integrals,
: min cTæ, PEPt
pt fx R" Ar b, ISES EEV EZ)
(I)
Typically, mixed integer linear programs are solved with variant of branch and bound search [29, B&B]. This approach recursively builds search tree, whose root represents the original problem (1). Child nodes are created by introducing additional constraints (branching) to partition the set of feasible solutions. B&B uses bounds on the optimal solution prune the tree and direct the search. To obtain strong upper bounds for zf, modern solvers typically rely are methods designed to quickly find good feasible solutions or an optimal solution xf E X' == (ar e pi c = 2t}. Primal heuristics include problem specific methods [e.g.. 34, 30], variants of large neighborhood search [15, 13, 7, 38], rounding procedures [47, 4] or diving heuristics [see e.g. 6, 48].
array of primal heuristics. These
Diving heuristics prominent group of primal heuristics. They based on the linear program (LP) relaxation M = (c, P*) of the problem in (1) given by
== min eTT, P
p
(x E RR"
As = b E S x ST
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

(a) Traditional approach:
Diving heuristies in branch and bound
+
=
Manual Design
Solver Integration
(b) Our approach: L2Dive
+
+
Collect I' pt
Generative Model
Duality
Solver Integration
Figure 1: Traditional diving heuristics are based on generic manual heuristics and integrated efficiently into the branch and bound solver. In contrast, our approach L2Dive learns application-specifee diving heuristics by collecting feasible solutions for a of training instances to train generative model. At test time, L2Dive uses the model predictions and leverages the duality of linear programs for diving. Finally, we integrate L2Dive into an open-source branch and bound solver.
Diving heuristics attempt to drive the LP solution x² E X == arg min e s.t. I E P* towards integrality. For this purpose, they conduct a depth-first search from any node in the search tree by repeatedly modifying and resolving linear programs. Diving heuristics are popular, because linear programs can typically be solved relatively fast and hence number of diving heuristics have been proposed. However, standard divers rely generic rules that fail to exploit problem-specine characteristics. This is particularly severe in applications, where similar problem instances are solved repeatedly and structural commonality exists. In this setting, learning is a promising alternative to design effective divers with the ultimate goal improving solver performance.
We propose 1.Diive to learn such application-specifi diving heuristics. L2Dive collects good feasible solutions for some instances of a particular application and trains a generative model to minimize variational objective on them. The model is a graph neural network that, for a given mixed integer linear program, predicts assignment of the integer variables. At test time, L2Dive uses the model prediction and leverages the duality of linear programs to select variables for diving and tighten their bounds. We fully integrate L2Dive into the open-soures solver SCIP and demonstrate the effectiveness of our approach in two sets of experiments. Our approach is illustrated in First, we compare L2Dive against existing diving heuristies on common benchmark of combinatorial optimization problems and show that it finds better feasible solutions with the same diving budget. Second, we use 1.2eive within branch and bound and test it on two real-world applications where we find that 1.2Dive improves overall solver performance, For server load balancing. it improves the average primal-dual integral by up to 7% (355) over tuned (default) solver baseline and in neural network verification reduces average solving time by 20% (29%).
2 Background
2.1 Diving Heuristics
Diving heuristics conduct depth-first search in the branch and bound tree to explore single root- leaf path. They iteratively modify and solve linear programs to find feasible solutions. Algorithm I illustrates a generic diving heuristic. A dive can be initiated from any node in the branch and bound tree and will return a (possibly empty) set of feasible solutions X' for the original mixed integer linear program in (1). Typically, diving heuristics alternate between tightening the bound of single candidate variable zj with j C C I (line 5) and resolving the modified linear program (line 7), possibly after propagating domain changes [1]. The resultant solution may be integral (Iz E 2, Vj E Z) admit an integral solution via rounding [line 9, 1]. Eventually, the procedure guaranteed to result in at least one primal-feasibe solution (line 10) or an infeasible program (line 6). However, in practice solvers may prematurely abort dive to curb its computational costs,

---

for example by imposing a maximal diving depth (line 2), an iteration limit on the LP solver or bound on the objective value.
Diving heuristics feature prominently in integer programming. In contrast to large neighborhood search, they only require repeatedly solving linear programs (in complexity class P) instead of small integer programs (NP-hard). As result, they tend to be considerably faster and more applicable in practice. Diving heuristics may also leverage sophisticated rounding methods in each iteration which makes them more likely to be successful. Various diving heuristics have been proposed. We briefly list and describe the most common ones in Appendix A. They mostly differ in how they select variables for bound tightening (line 3). For example, fractional fractie,faattonal diving selects the variable with
the LP solution, while linesearch diving computes score sj for each variable based on the LP solutions at the current and the root node. All of these diving heuristics choose integer variables for diving from the same set of candidates C. This set of divable variables typically excludes integer variables that are slack variables [10, Chapter 1.1] or that have already been fixed (œ 7). general, diving heuristics apply to any mixed integer linear program. Empirically, however, standard divers often tend to be only effective for certain problems. For example, we found Farkas diving to deliver good results on class of facility location problems, but to be ineffective for instances of maximum independent set (Section 5.1). As result, modern solvers use an array of different diving heuristics during branch and bound. Selectively tuning this diving ensemble can be effective in improving solver performance particular applications (Section 5). In contrast, our approach is to directly learn problem-specific diving heuristics for particular applications and demonstrate in our experiments that this yields improvements in solver performance over using (tuned) ensemble of divers as is common practice.
the lowest fractionality 12; [x] + 0.5]
Algorithm 1: Generic Diving Heuristic
Input: M i with relaxation M maximal depth dmax
Output: X. (possibly empty) set of feasible solutions
Require:s ss, a scoring function select variables for bound tightening
d 1
2 while S dmux do
j = arg max Either 3 + |2 [2 [z]] Pa + P* P Szz S m
if P* is infeasible then break;
x² = arg argmin(cTe <cTx
P*]
x is roundable then ā = round(x*) + X end
10
11
12
d + d+1
13
Possibly update candidates C
14
end
2.2
Solver Performance and Primal Performance
The most intuitive way to assess the performance of solver for mixed integer linear programs is by measuring solving time, i..., the average time it takes to solve set of instances. However, realistic instances are often not solved to completion, because this may be prohibitively expensive or particular application only requires bounds on the optimal solution, which the solver readily yields. In these cases, common to consider the primal-dual gap!:
0 < 32 < 00
(pd 87)
max
(3)
else
Note that we use definition of the primal primal-dual gap that is used in SCIP 7.0.2 for the computation of the integral and do not quantify the gap the integral per cent.

---

Here, == cTu is the upper (also known primal) bound given by the feasible solution . and 2" is global lower (also known as dual) bound on the optimal solution zt, Performance can be measured by solving instances with a fixed cutoff time T and then computing the primal-dual gap (pd(2r, *7), where & and & denote the solver's best lower and upper bounds at time f. (if non-existent, then 00 and 4:0 respectively).
Primal-dual integral Unfortunately, measuring the primal-dual gap at time T is suspectible the particular choice of cutoff time. This is particularly troublesome, because the lower and upper bounds of branch and bound solvers tend to improve a stepwise fashion, order to alleviate this issue, common to integrate the primal-dual gap over the solving time and measure the primal-dual integral:
(T) = f:n Tpal2e, dt
Primal gap When directly comparing diving heuristics with each other, it can be useful consider primal performance instead of solver performance. Primal performance assesses the quality of the feasible solution i a heuristic may find and can be measured by the primal gap:
7n =
Sometimes, the primal gap is normalized by |e*| which can be useful when % is averaged across disparate instances. We do not normalize "/p in this work.
3 Learning to Dive
We propose L2Dive to learn application-specinn diving heuristics with graph neural networks. L2Dive uses generative model to predict an assignment for the integer variables of a given mixed integer linear program. This model learnt from distribution of good feasible solutions collected initially for set of training instances of a particular application. The model is graph neural network closely related to the model in Gasse al. [17]. It is trained minimize a variational objective. At test time, L2Dive leverages insights from the duality of linear programs to select variables and tighten their bounds based on the model's 's predictions. We fully integrate 1.2Dive into the open-source solver SCIP,
3.1 Learning from feasible solutions
We propose to learn generative model for good feasible solutions of a given instance M For this purpose, we first pose a conditional probability distribution over the variables x::
logp:(r(M)) :o { -ctx//r if x E X
(6)
-00 else
The distribution Pr (1 (x|MM) M is defined with respect to a set of good feasible solutions X' for the given instance. Solutions with better objective are given larger mass as regulated by the temperature т, while solutions that are not known to be feasible or are not good (x & X') are given no probability mass. practice, model for diving will only need make predictions on the divable variables ze that are integral, non-fixed and not slack (Section 2). Hence, our model will target the marginal distribution pt (xc MT)) := E 1(re E 3] (x(
Our goal is to learn a generative model qe that closely approximates the distribution pf. The model qe will be used to make predictions on unseen test instances for which and X' are unknown. To learn good generative model, our objective minimize the Kullback-Leiber divergence between pf and qo.
( (M))
(L(pfl19)) Ep((FclM") log
(7)
qo (xc MM)
jointly over all training instances. The sum in (7) can be evaluated exactly, because the number of good feasible solutions in X' tends to be small. Our model for qo is variant of the graph neural

---

network described in Gasse et al. [17] and we give details in Appendix B. This model represents a mixed integer linear program as bipartite graph of variables and constraints (Figure 3 in Appendix B) and its core are two bi-partite graph convolutions between variables and constraints (Figure 2 in Appendix B). Our variant uses some of the variable and constraint features from Paulus et al. [35] as well as batch normalization. It makes conditionally independent predictions for each integer variable, such that go(rc ;= Iljer (=, ). For binary variables, qo (z(z)
)M is a Bernoulli
distribution and the model outputs the mean parameter 0. For general integer variables, qo ( MMT is a sequence of Bernoulli distributions over the bitwise representation of the variable's integer domain and the model outputs mean for each. Although conditionally independent predictions limit our model to unimodal distributions, this parameterization delivered strong empirical performance in our experiments (Section 5). It is possible to choose more delicate models for qe. such as autoregressive models, but those will typically impose a larger cost for evaluations.
Solution augmentation At train time, we rely on the availability of a set of good feasible solutions X' for each instance. This is required to define po in (6) and evaluate the objective in (7) on all training instances. Several choices for X' are possible, and the effectiveness of our approach may depend on them. For example, if X' only contains poor feasible solutions, we cannot reasonably hope to learn any good integer variable assignments. The most obvious choice perhaps is to let X = {x J. where xf is the best solution the solver finds within a given time limit T. However, solvers are typically configured to not only store z², but also a set number of its predecessors. Thus, alternatively some or all of the solutions in store could be used to define X' at no additional expense. Lastly, many instances of combinatorial optimization (e.g., set cover, independent set) exhibit strong symmetries and multiple solutions with the same objective value may exist as result. These can be identified by using a standard solver to enumerate the solutions of an additional auxiliary mixed integer linear program as described Appendix C. We used this method to augment solutions in X' for some of our experiments. This technique may be of independent interest, because the problem of handling symmetries is ubiquitous in machine learning for combinatorial optimization [28]. While it can be expensive to collect feasible solutions for each training instance regardless of the choice of X, this cost may be curbed, because we do not require X' to contain the optimal solution. Moreover, the cost is incurred only once and ahead of training, such that all solver calls embarassingly parallelizable across instances. In some cases, practitioner may be able to draw on previous solver logs and not be required to expend additional budget for data collection. Finally, any training expense will be ultimately amortized in test time service.
3.2 Using a generative model for diving
At test time, we use our generative model qe to predict an assignment for the divable integer variables Te of a given instance. Typically, we will choose åc arg max go (xcclM)) to predict an assignment, but assignments can also be sampled from the model, if multiple dives are attempted in parallel. To use the prediction for diving, we need to decide which variable to select (line 3 in Algorithm 1) and how to tighten its bounds (line 4). Ideally, our decision rules will admit a feasible solution at shallow depths, i.e., only few bounds must be tightened to result in an integral or roundable solution to the diving linear program. Which variables should we tighten for this purpose and how? Compellingly, the theory of linear programming affords some insight:
Proposition 1. Let ă be a feasible solution for Mt as in (1). For the linear program M its dual linear program MD is defined in (11) in Appendix D. Let y² == (yh-vt, V(r) ) be an optimal solution
for MD Let (ā) and [(x) index the set of variables that violate complementary slackness (12) between Tt and y", such that
(ū, II) 12,335 vnz > 00 J(T): :- (ē, F,) UZy > 0}
and define := J ( Let Mj := (c. Pī) be the linear program, where the bounds of all variables indexed by J [z) are tightened, such that
Pj P; P' E R. I, 2 3, Vj E J(t), 2 S E
Then, ă is optimal solution to the linear program Mj, i.e., 5 E arg min cl..
5

---

Proof. 2 is clearly feasible solution for 5. y" is feasible solution for the dual linear program of Mj. because is feasible for M. I and y satisty complementary slackness, hence I optimal. [
This suggests that for a prediction &c. the bounds of variables in (ăc) should be tightened to restore complementary slackness. If the integer variable assignment de is feasible and the candidate set includes all integer variables, this will yield diving linear program for which the assignment is optimal and that may be detected by the LP solver. Unfortunately, this is not guaranteed in the presence of slack variables (where typically C C I) or if multiple optimal solutions exist (some of which may not be integer feasible). In practice, it may thus be necessary to tighten additional propose the following dual reasoning rule select to
variables in C. Inspired by Proposition select a variable j E C for tightening
arg max 8j == 40 (0 I(j J(c))
(8)
This rule will select any variables in Jâc) before considering other variables for tightening. The score 8 breaks ties by selecting the variable in whose predictions the model is most confident in. Conveniently, the set (() can be easily computed on the fly from the dual values y². which standard LP solvers readily emit on every call at no additional expense. We tighten I, = 4 if ē S xj and we tighten j æj if ê; 2 x; to replace line 4 in Algorithm 1. We update the candidate set C in line 13 to exclude variables whose value has been fixed, i.e., I, = J as usual. We validate dual reasoning in an ablation study in section 5.1.
3.3 Deployment
We fully integrate 1.2Dive into the open-source solver SCIP 7.0.2 [16]. This solver exposes plug-in for diving heuristics that implements an optimized version of Algorithm 1 in the programming language C. We extend the solver's Python interface [32] include this plug-in and use it to realize L2Dive. This integration facilitates direct comparison to all standard divers implemented in SCIP (Section 5.1) and makes it easy to include L2Dive in SCIP for use in branch and bound (Section 5.2). Importantly, we call our generative model only once at the initiation of dive to predict variable assignment. While predictions may potentially improve with additional calls at deeper depths, this limits the in-service overhead of our method. It also simplifies the collection of training data and produced good results in our experiments (Section 5).
Related Work
Nair et al. [33] propose a method that learns to tighten a subset of the variable bounds. It spawns smaller sub-integer program which is then solved with an off-the-shelf branch and bound solver to find feasible solutions for the original program. Sonnerat et al. [41] improve this approach using imitation learning. Others explore reinforcement learning [49] or hybrids [40], but only focus on improving primal performance. All of these methods are variants of large neighborhood search [39, 2, 36], where neighborhood for local search is not proposed heuristically, but learnt instead. In contrast, our approach L2vive does not propose fixed neighborhood and it does not require access to branch and bound solver to run. Instead, we use our model's predictions to iteratively modify and solve linear programs instead of sub-integer programs. In practice, linear programs tend to solve significantly faster which makes L2Dive more applicable. Khalil et al. [26] propose a method to learn variable assignments from good feasible solutions, but combine their model predictions with heuristic rule for node selection, whereas we consider diving.
Overall, there is vivid interest in exploring the use of machine learning for integer programming [5, 52, 31]. With regard to branch and bound, several works learn models for variable selection in branching [25, 3, 17, 19, 42, 51]. Others focus on node selection in the search tree [20, 50] or deal with cutting plane management [35, 22, 43, 9, 45]. Further, related work includes both general [23, 24, 46] and specific [12, 9, 8] attempts of learning to configure the solver. To the best of our knowledge, we are the first to propose learning to dive to improve the performance of branch and bound solvers.

---

5 Experiments
The goal of our work is to learn application-specins diving heuristics to improve on existing diving heuristics. We view other primal methods (Section 4) as complementary, and accordingly compare primarily to other diving heuristics. We evaluated the effectiveness of L2Dive in two different experiments and on a total of six datasets. The first set of experiments (Section 5.1) was designed to study the diving performance of L2Dive in isolation and compare it against existing diving heuristics. On a benchmark of four synthetic combinatorial optimization problems from previous work [17], we performed single dives with each diver and measured the average primal gap. We found that L2Dive outperformed all existing divers on every dataset and produced the best solutions amongst all divers. The second set of experiments (Section 5.2) directly included L2Dive into the branch and bound process of the open-source solver SCIP, The solver called L.Dive in place of existing diving heuristics and our goal was to improve overall performance on real-world mixed integer linear programs. We considered instances from neural network verification [33] and server load balancing in distributed computing [18]. We measured performance with L2Dive against the default configuration and a highly challenging baseline that tuned the solver's diving ensemble. We found that L2Dive improved the average primal-dual integral by 7% (35%) on load balancing and improved average solving time by 20% (29%) on neural network verification over the tuned (default) solver.
We collected data for training and validation: In all experiments, we extracted a bipartite graph input representation of each instance's root node. On all but two datasets, we chose X = x={x²} where x' is the best solution the solver finds within a given time limit T. For set cover and maximum independent set only, we observed strong symmetries and used the solution augmentation described in Appendix C. We trained separate models for each dataset. We trained each model with ADAM [27] for 100 epochs in the first set of experiments and for 10 epochs in the second set of experiments. We individually tuned the learning rate from a grid of [10-2, 10-3 10-#1. For each dataset, we chose the batch size to exhaust the memory of a single NVIDIA GeForce GTX 1080 Ti device. We validated after every epoch and chose the model that achieved the best validation loss. In all experiments, we use the mode prediction of the generative model and only perform a single dive from a given node. We do not attempt multiple dives in parallel and did not use any accelerators at test time. In all experiments, we only call L2Dive's 's generative model once at the beginning of dive to limit the in-service overhead from serving the graph neural network.
5.1 Diving with L2Dive
With this first set of experiments, we studied the diving performance of L2Dive and compared it against existing diving heuristics. We used the same benchmark as previous work [17]. This benchmark consists of four different classes of combinatorial optimization problems, including set covering, combinatorial auctions, capacitated facility location and maximum independent sets. For each class, we used 2000 instances in total; we trained on 1000 instances and validated and tested on 500 instances respectively. We presolved all instances before diving, but did not branch and disabled cutting planes and other primal heuristics as our interest is solely diving. We compared L2Dive against all other standard diving heuristics that are implemented in the open-source solver SCIP and do not require an incumbent solution. This includes noeffcient.fraaciiona.. fractional, linesearch, pseudocost, distributional, vectorlength [6] and Farkas diving [48]. We briefly describe these baseline divers in Appendix A. In addition, we considered three trivial divers that respectively fix integer variables to their lower (lower) or upper limit (upper) or either with equal probability (random). All divers ran with the same diving budget (dmar = 100) and their execution was directly triggered by the user after resolving the root node. We ignore the few test instance that were solved directly at root by SCIP before we could initiate a dive.
L2Dive outperformed all other standard divers (Table 1). It achieved the lowest average test primal gap on each of the four problem classes. The improvements over the best heuristic diver ranged from roughly 15% for combinatorial auctions to more than 70% for independent sets. The trivial divers only found solutions that are significantly worse, which indicates that L.Diive learnt to exploit more subtle patterns in the problem instances to find better feasible solutions. Some baseline divers (e.g., linesearch, distributional) failed to consistently outperform the trivial divers across all problem classes and best heuristic diver varied (pseudocost diving for combinatorial auctions, Farkus diving for facility location, vectorlength diving for set cover, independent set). This confirms that in practice most diving heuristics tend to be specialized and work particularly well for particular problem classes.
7

---

Table 1: L2Dive finds better feasible solution all four problem classes than existing diving heuristics. Average primal gap with standard error on test set. Best diver is in bold and best heuristic is in italics.
SET COVER
COMB. AUCTION
FAC. LOCATION
IND. SET
L2vive
55 (3)
222 (7)
160 (10)
5 (
Best heuristic
95 (3)
256 (8)
484 (7)
18 (2)
Coefficient
3,700 (55)
671 (11)
762 (9)
246 (4)
Distributional
3,900 (50)
1,504 (12)
760 (9)
196 (3)
Farkas
105 (3)
476 (9)
484 (7)
Fractional
3,726 (57)
672 (10)
1,058 (11)
232 (4)
Linesearch
1,269 (24)
467 (10)
1,036 (15)
77 (1)
Pseudocost
195 (9)
256 (8)
505 (11)
32 (2)
Vectorlength
95 (3)
832 (20)
840 (19)
18 (8)
Random 2,918 (63)
416 (13)
704 (12)
902 (14)
78 (2)
Lower
1,587 (11)
623 (8)
171 (5)
Upper
239 (6)
611 (11)
828 (14)
62 (2)
L2Dive is generic recipe to design effective divers for any specific application. Finally, we found that the mode predictions of our learnt models were rarely feasible (c.g., set cover, combinatorial auctions) or yielded poor solutions (e.g., independent set). This highlights that learning a generative model for diving may be more promising approach than trying to predict feasible solutions directly.
In order to validate the dual reasoning rule proposed subsection 3.2, we paired L2Dive with two alternative rules for variable selection in capacitated facility location. The first ablative rule chooses a variable j E C uniformly at random, i.e., sjand ~ Up.11. The second ablative rule simply uses model confidence, i.e., $4 connf qo (f² and unlike dual reasoning does not treat variables j (āte) preferentially. We found that even when variables were selected uniformly at random (where the model prediction is used only for bound tightening). L2Dive outperformed the best standard diver (Table 2). However, selecting variables whose model predictions are more certain significantly improved performance by large margin, while additionally employing dual reasoning tended to improve performance further for capacitated facility location. The effectiveness of dual reasoning likely problem-specific as dual reasoning will collapse the model confidence rule, if the set n C' is empty. To test the generalization performance of L2Dive to larger instances, we performed an additional ablation study and report the results in Appendix E.
Table 2:
Dual reasoning in L2Dive tends to improve diving performance on capacitated facility location. Even selecting variables for diving uniformly at random outperforms the best heuristic diver, using model confidence (and dual reasoning) facilitates significant improvements.
FAC. LOCATION
L2Dive
160 (10)
L2Dive (with 8 gond)
164 (10)
L2vive (with s grand
335 (14)
Best heuristic
484 (7)
5.2 L.Dive in branch and bound
With this second set of experiments, our goal was to use L2Dive within branch and bound to improve solver performance on real-world mixed integer linear programs. To this end, we included L.Dive into the open-source solver SCIP. We disabled all other diving heuristics in SCIP and dive with 1.2Dive from the root node. We found this to work well, but results for 1.2Dive may likely improve with more subtle schedule for L2Dive or by integrating L2Dive into the solver's 's diving ensemble.

---

We considered two strongly contrasting applications from previous work. The first application deals with safely balancing workloads across servers in a large-scale distributed compute cluster. This problem is an instance of bin-packing with apportionment and can be formulated as mixed integer linear program. We used the dataset from Gasse et al. [18] which contains 9900 instances for training and 100 instances for validation and testing respectively. Solving these instances to optimality is prohibitively hard? and we therefore set a time limit of T iimit = 900 seconds, both for data collection and test time evaluations. The second application deals with verifying the robustness of neural networks. This problem can be formulated as a mixed integer linear program [111, 44J. We considered the instances from Nair et al. [33], but used the same subset as Paulus et al. [35] who disregard trivial and numerically unstable instances. This dataset contains 2384 instances for training, 519 instances for validation and 545 instances for testing. These instances are challenging, but can mostly be solved within a reasonable time. We set a limit of Timit 3600 seconds, both for data collection and test time evaluations.
To assess solver performance, we measure solving time T for neural network verification and the primal-dual integral I' ("Timit) for server load balancing. Both measures fully account for the entire in-service overhead of L2Dive (e.g., computing the bipartite graph representation from the tree node, peward-propagating the generative model, diving etc.), because the L2Dive diver is directly included into SCIP and called by the solver during the branch and bound process. Our experiments were conducted shared distributed compute cluster. To reduce measurement variability, ran all test time evaluations repeatedly on machines equipped with the same Intel Xeon Gold 5118 CPU 2.3 GHz processors for three different seedings of the solver. We batched evaluations randomly across instances and methods to be processed sequentially on the same machine. We report test set means and standard errors over the three different random seeds.
Table 3: L2Dive improves the performance of the branch and bound solver SCIP on real-world applications. When using L2Dive instead of standard divers, the average primal-dual integral for load balancing improves by 7% (35%) and solving time on neural network verification shrinks by 20% (29%) against the tuned (default) solver.
LOAD BALANCING
NEURAL NETWORK VERIF.
Primal-dual Integral
Wins
Solving Time
Wins
SCIP Default
4,407 (34)
(
55.8 (2.3)
54 (5)
No diving
4,221 (21)
(
53.7 (0.6)
40 (4)
Tuned
3,067 (10)
(3)
49.9 (2.8)
164 (3)
L2Dive
2,863 (13)
93 (3)
39.8 (2.3)
287 (5)
L2Dive improved solver performance ad-hoc (Table 3, L2Dive). On load balancing, L2Dive improved the average primal-dual integral by over 30% from the solver at default settings (Table 3, Defauli). On neural network verification, 1.2Dive reduced the average solving time from approximately 56 seconds to less than 40 seconds (35%). As a control, we also ran SCIP without any diving and surprisingly found small improvements on both datasets (Table 3, No diving). The solver's 's default setting calibrated on a general purpose set of mixed integer programs and are typically a challenging baseline to beat. However, our results suggests that SCIP's 's divers are either ineffective or may be poorly calibrated for these two applications. For this reason, we decided to tune the diving heuristics of the solver to seek an even more challenging baseline for comparison. We leveraged expert knowledge and random search to find strong diving ensembles in the the vicinity of the default configuration. Then, we selected the best tuned solver configuration on validation set using the same budget of solver calls that 1.2Dive expended for data collection. Details are in Appendix F. Our tuned solver baseline (TTbll 3, Tuned) significantly improved performance over Defauls, but still outperformed by 1.2Dive. This highlights that our approach to learn specific divers may be more promising than fitting ensembles of generic diving heuristics particular application. Overall, L2Dive achieved the best average performance on 93 (out of 100) test instances for load balancing, and achieved the best
Using a Xeon Gold 5118 CPU processor with 2.3 GHz and 8 GB of RAM, none of the instances could be solved with SCIP 7.0.2 at default settings within hour.

---

average performance on 287 (out of 545) test instances for neural network verification, more than the three SCIP configurations collectively.
Conclusions
We presented L2Dive learn upplication-specifee diving heuristics for branch and bound. Our approach combines ideas from generative modeling and relational learning with a profound under- standing of integer programs and their solvers. We tested L2Dive range of applications including combinatorial optimization problems, workload apportionment and neural network verification. found better feasible solutions than existing diving heuristics and facilitated improvements in all solver performance. We view our work as yet another example that demonstrates the fruitful symbiosis of learning and search design powerful algorithms.
Broader Impact and Limitations
This work presents method to use machine learning for improving the performance of branch and bound solvers. Branch and bound is a powerful general-purpe purposs method for solving mixed integer linear programs which appear frequently across business, science and technology. Therefore, we expect the impact of this work to overwhelmingly beneficial. However, cases where integer programming is exploited with ill intentions, our work may potentially have a harmful societal impact.
There are limitations in learning diving heuristies for specific applications. For example, in some cases the set of training instances may be small or collecting feasible solutions could be prohibitively expensive. In such cases, may be desirable to transfer models from other applications or utilize self-supervised representations that require fewer labelled examples for training [14]. This is a natural direction to explore the future, for this and other work at the intersection of machine learning and integer programming. Alternatively, one may attempt to learn universal diving heuristic using diverse set of instances from variety of applications. However, the extent to which machine learning can prove effective in this setting, for diving or other sub-routines, remains an open question.
Acknowledgements
MBP gratefully acknowledges support from the Max Planck ETH Center for Learning Systems. Resources used in preparing this research were provided, in part, by the Sustainable Chemical Processes through Catalysis (Suchcat) National Center of Competence in Research (NCCR).
References
[1] Tobias Achterberg, Timo Berthold, and Gregor Hendel. Rounding and propagation heuristics for mixed integer programming. In Operations research proceedings 2011, pages 71-76. Springer, 2012.
[2] Ravindra K Ahuja, James B Orlin, and Dushyant Sharma. New neighborhood search structures for the capacitated minimum spanning tree problem. 1998.
[3] Alejandro Marcos Alvarez, Quentin Louveaux, and Louis Wehenkel. machine learning- approximation of strong branching. INFORMS Journal on Computing, 29(1):185-195, 2017.
[4] Egon Balas, Stefan Schmicta, and Christopher Wallace. Pivot and shift-22 mixed integer programming heuristic. Discrete Optimization, 1(1):3-12, 2004.
[5] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: A methodological tour d'horizon. European Journal of Operational Research, 290c2):405-221 2021. ISSN 0377-2217. doi:
URL
https:// wwwwenceiieeeetcc... wwwo//science
[6] Timo Berthold. Primal heuristics for mixed integer programs. 2006.
[7] Timo Berthold. Rens-relaxation enforced neighborhood search. 2007.
[8] Timo Berthold and Gregor Hendel. Learning to scale mixed-integer programs. Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 3661-3668, 2021.
10

---

[9] Timo Berthold, Matteo Francobaldi, and Gregor Hendel. Learning to use local cuts. arXiv preprint arXiv:2206.116616 2022.
[10] Dimitris Bertsimas and John N Tsitsiklis. Introduction to linear optimization, volume 6. Athena Scientific Belmont, MA, 1997.
[11] Chih-Hong Cheng, Georg Nührenberg, and Harald Ruess. Maximum resilience of artificial neural networks. In International Symposium on Automated Technology for Verification and Analysis, pages 251-268. Springer, 2017.
[12] Antonia Chmiela, Elias Khalil, Ambros Gleixner, Andrea Lodi, and Sebastian Pokutta. Learning to schedule heuristics in branch and bound. Advances in Neural Information Processing Systems,
34:24235 14224235-24246, 2021.
[13] Emilie Danna, Edward Rothberg, and Claude Le Pape. Exploring relaxation induced neighbor- hoods to improve mip solutions. Mathematical Programming. 102(1):71-99) 2005.
[14] Haonan Duan, Pashootan Vaezipoor, Max B Paulus, Yangjun Ruan, and Chris Maddison. Aug- ment with care: Contrastive learning for combinatorial problems. In International Conference on Machine Learning, pages 5627-5642. PMLR, 2022.
[15] Matteo Fischetti and Andrea Lodi. Local branching. Mathematical programming, 98(1):23-477 47, 2003.
[16] Gerald Gamrath, Daniel Anderson, Ksenia Bestuzheva, Wei-Kun Chen, Leon Eifler, Maxime Gasse, Patrick Gemander, Ambros Gleixner, Leona Gottwald, Katrin Halbig, et al. The scip optimization suite 7.0. 2020.
[17] Maxime Gasse, Didier ChAOtelat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. In Advances in Neural Information Processing Systems 32, 2019.
(18) Maxime Gasse, Simon Bowly, Quentin Cappart, Jonas Charfreitag, Laurent Charlin, Didier Chételat, Antonia Chmiela, Justin Dumouchelle, Ambros Gleixner, Aleksandr M Kazachkov, et al. The machine learning for combinatorial optimization competition (ml4co): Results and insights. In NeurlPS 2021 Competitions and Demonstrations Track, pages 220-231. PMLR, 2022.
[19] 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:1 18:1188818007, 2020.
[20] He He, Hal Daume III, and Jason M Fisner. Learning to search in branch and bound algorithms. Advances in neural information processing systems, 2014.
[21] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 98): 1735-1780, 1997.
[22] Zeren Huang, Kerong Wang, Furui Liu, Hui-Ling Zhen, Weinan Zhang, Mingxuan Yuan, Jianye Hao, Yong Yu, and Jun Wang. Learning to select cuts for efficient mixed-inie inttegrreerrrrrr programming. Pattern Recognition, 123:10835: 2022.
[23] Frank Hutter, Holger H Hoos, and Kevin Browon-Brown. Sequential model- optimization for general algorithm configuration. In International conference on learning and intelligent optimization, pages 507-523. Springer, 2011.
[24] Frank Hutter, Lin Xu, Holger H Hoos, and Kevin Leyton- Broww. Algorithm runtime prediction: Methods & evaluation. Artificial Intelligence, 006:79-111, 2014.
[25] Elias Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning to branch mixed integer programming. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
[26] Elias B Khalil, Christopher Morris, and Andrea Lodi. Mip-gnn: A data-driven framework for guiding combinatorial solvers. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 10219-10227, 2022.
[27] Diederick P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Interna- tional Conference on Learning Representations (ICLR), 2015.
11

---

[28]
James Kotary, Ferdinando Fioretto, and Pascal Van Hentenryck. Learning hard optimization problems: A data generation perspective. Advances in Neural Information Processing Systems, 14-24981-24992, 2021.
[29] Ailsa Land and Alison G Doig. An automatic method for solving discrete programming problems. In 50 Years of Integer Programming 1958-2008, pages 105-132. Springer, 2010.
[30] Shen Lin and Brian W Kernighan. An effective heuristic algorithm for the traveling-salesmun problem. Operations research, 21(2):498-511 1973.
[31] Andrea Lodi and Giulia Zarpellon. On learning and branching: survey. Top, 25(2):207-236.
2017.
[32] Stephen Maher, Matthias Miltenberger, João Pedro Pedroso, Daniel Rehfeldt, Robert Schwarz, and Felipe Serrano. PySCIPOpt: Mathematical programming in python with the SCIP opti- mization suite. In Mathematical Software- ICMS 2016, pages 301-307. Springer International Publishing, 2016. doi: 10.1007/978- 0000//997---319--422--3-3
[33] Vinod Nair. Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O' O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012. 13349, 2020.
[34] Hoon Liong Ong and JB Moore. Worst-case analysis of two travelling salesman heuristics. Operations Research Letters, 2(6))273-277 1984.
[35] 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, pages 17584-17600. PMLR, 2022.
[36] David Pisinger and Stefan Ropke. Large neighborhood search. In Handbook of metaheuristics, pages 399-419. Springer, 2010.
[37] Jennifer Pryor and John W Chinneck. Faster fnteger-feasibility in mixed-integer linear programs by branching to force change. Computers & Operations Research, 38(8): 143-1152, 2011.
[38] Edward Rothberg. An evolutionary algorithm for polishing mixed integer programming solu- tions. INFORMS Journal on Computing, 19(4):534 541, 2007.
[39] Paul Shaw. Using constraint programming and local search methods to solve vehicle routing problems. In International conference on principles and practice of constraint programming, pages 417-431. Springer, 1998.
[40] Jialin Song, Yisong Yue, Bistra Dilkina, al. A general large neighborhood search framework for solving integer linear programs. Advances in Neural Information Processing Systems, 33: 20012-20023, 2020.
[41] Nicolas Sonnerat, Pengming Wang. Ira Ktena, Sergey Bartunov, and Vinod Nair. Learn- ing a large neighborhood search algorithm for mixed integer programs. arXiv preprint arXiv:2107.10201, 2021.
[42] Haoran Sun, Wenbo Chen, Hui Li, and Le Song. Improving learning to branch via reinforcement learning. 2020.
[43] Yunhao Tang, Shipra Agrawal, and Yuri Faenza Reinforcement learning for integer pro- gramming: Learning to cut. In Hal DaumÅ III and Aarti Singh, editors, Proceedings of the 37th International Conference
Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 9367-9376. PMLR, 13-18 Jul 2020. URL http: //proceedingsco mlr. prwss/ vetpsvv199/ htt///11999ttt0000 httml.
[44] Vincent Tjeng, Kai Y Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In International Conference on Learning Representations, 2018.
[45] Mark Turner, Thorsten Koch, Felipe Serrano, and Michael Winkler. Adaptive cut selection in mixed-integer linear programming. arXiv preprint arXiv:2202. 10962, 2022.
[46] Romeo Valentin, Claudio Ferrari, Jérémy Scheurer, Andisheh Amrollahi, Chris Wendler, and Max B Paulus. Instance-wise algorithm configuration with graph neural networks. arXiv preprint arXiv: 04920.0 2022.
[47] Chris Wallace. Zi round, mip rounding heuristic. Journal of Heuristics, 16(5):715-722, 2010.
[48] Jakob Witzig and Ambros Gleixner. Conflict-driven heuristies for mixed integer programming. INFORMS Journal on Computing, 33(2):706-720, 2021.
12

---

[49] 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, 2021.
[50] Kaan Yilmaz and Neil Yorke-Smith. Learning efficient search approximation in mixed integer branch and bound, arXiv preprint urXiv:2007.03944 2020.
[51] Giulia Zarpellon, Jason Jo, Andrea Lodi, and Yoshua Bengio. Parameterizing franch-and-bowd search trees to learn branching policies. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 3931-3939) 2021.
[52] Jiayi Zhang, Chang Liu, Xijun Li, Hui-Ling Zhen, Mingxuan Yuan, Yawen Li, and Junchi Yan. survey for solving mixed integer programming via machine learning. Neurocomputing, 519: 205-217, 2023.
13

---

A Diving Heuristics
In Table we briefly describe existing diving heuristics. In addition, SCIP's diving ensemble includes adaptive diving, conffict diving, objective pseudocost diving and guided diving. We did not compare against these heuristics in Section 5.1, because they either choose from the other heuristics (adaptive), were ineffective (conflic(), require a feasible solution (guided) do not use the generic diving algorithm (objective pseudocost). However, these divers are active for baselines Section 5.2. Berthold [6] gives more detailed illustration of some of the divers.
Table 4: Overview of standard diving heuristics.
Diver
Description
Coefficient
Selects the variable with the minimal number of (positive) up-locks or down- locks and bounds in the corresponding direction; ties are broken using Fractional diving.
Distribution Farkas
Selects a variable based on the solution density following [37].
Attempts to construct Farkas proof, Farkas diving bounds variable in the direction that improves the objective value and selects the variable for which the improvement in the objective is largest.
Fractional
Selects the variable with the lowest fractionality |x] - Lx, +0.5 || in the current LP solution xx and bounds it in the corresponding direction.
Linesearch
Considers the ray originating at the LP solution the root and passing through the current node's s LP solution x² selects the variable j whose coordinate hyperplane 2 = | or 2; = [až] is first intersected by the ray.
Pseudocost
Selects and bounds variable based on its branching pseudocosts, its fraction- ality and the LP solutions at the root and the current node.
Vectorlength
Inspired by set partition constraints, selects a variable for which the quotient between the objective cost from bounding it and the number of constraint it appears in smallest.
B Bipartite Graph and Graph Neural Network for L2Dive
B.1 Bipartite Graph
In our experiments, we represent mixed integer linear program as a bipartite graph of variables and constraints. This idea is taken from Gasse et al. [17] and has been adopted by many others since. Each variable æy and each constraint A, in the program gives rise to node in a bipartite graph. For every non-zero coefficient A; in linear constraint of the program the nodes of the corresponding variable j and constraint are joined by an undirected edge, Each node is associated with a vector of features. We use the same features as Paulus et al. [35] but exclude cut-specific ones, such that variable nodes use features and constraint nodes use 69 features total.
Bipartite Graph
A
I
+
Fn
bj
Aa
+
Agn
Fn
bz
Aij
Am
I1
+
Amn
En
bm
Variables
Constraints
Figure 2: Our model uses a bipartite graph representation to represent a mixed integer linear program as in [17]. Both variables and constraints of the program represent nodes bipartite graph. Edges in the graph correspond to non-zero coefficients in the linear constraint of the program. We use the same features for variables and constraints as in [35], but exclude cut-specific ones.
14

---

B.2 Graph Neural Network
Our model is a graph neural network that closely resembles the model proposed in Gasse et al. [17] and uses some of the modifications from Paulus al. [35]. The model is sketched in Figure After separately applying batch normalization to both variable and constraint nodes, we embed all nodes in 64-dimensional space using multi-layer perceptron with single hidden layer. This is followed by two bipartite graph convolutions, first from variables to constraints and then from constraints to variables, as in Gasse et al. [17]. Finally, we predict from the convolved variable embedding the parameters 0 of probability distribution go (M+) for each divable integer variable using another multi-layer perceptron with a single hidden layer. Binary variables are the most common variables in integer programs, and all the instances we considered feature exclusively binary divable variables. For binary variables, Qo (xtg [MT) is a Bernoulli distribution and the model outputs the mean parameter 0, such that PT( 1) 0. For general integer variables, we suggest to consider the bitwise representation of the integer domain. For example, the domain of a variable that can assume no more than eight unique integer values can be represented using at most four bits. Each of these bits can be parameterized with its own Bernoulli distribution and the model outputs a mean for each. This approach may be more favorable for diving than for other applications, because slack variables from cutting plane constraints (whose domains are not known initially and may be large) are not divable. In cases where outputting fixed-size array of Bernoulli parameters may not be applicable, a variable length array could be outputted by using a recurrent layer, such as an LSTM [21]. as is proposed in Nair al. [33]. Alternatively, fixed size array could still be used with an additional bit to indicate integer overflow that must be handled appropriately. For example in diving, variables for which the model predicts overflow may be ignored. Further, the frequency with which overflow would be encountered in practice could plausibly be reduced by making predictions relative to the current solution [x]]] rather than with respect to the lower variable bound I..
Embeddings
Graph Convolutions
MLP
Variables Constraints
Figure 3: Our model is a graph neural network based on Gasse et al. [17] and Paulus et al. [35]. first embeds variable and constraint nodes using batch normalization and single-layer feedforward network. It then convolves variable and constraint features with two bi-partite graph convolutions as in Gasse et al. [17]. Finally, for each variable it outputs the parameters of the distribution qo (x(z)) using another single-layer feedforward network.
C Solution Augmentation by Counting Optimal Solutions
Many integer and mixed integer linear programs exhibit strong symmetries, particularly those from combinatorial optimization. In these cases multiple optimal solution may exist, and in particular different integer variable assignments that correspond to an optimal solution. It is possible to identify those by first solving for 2t to then define the auxiliary mixed integer linear program,
min xr PEPX
p = Ex Pi Pi,cc==2l)
(9)
Standard solvers, including SCIP 7.0.2, can enumerate the set of feasible solutions PA of (9) by adding constraint handler whenever a new feasible integer variable assignment is found and continuing the solving process. We use this solution augmentation for our experiments on set covering and independent sets where the solver identified multiple optimal solutions in a short period of time.
15

---

D Background: Linear Programming
In this section, we briefly review some concepts from linear programming and duality.
Definition (Standard Form). A linear program M of the form
min e" subject to Az b, IS
(10)
said to be in standard form with variable bounds. A basis for this program is triplet (C,B,U). where Tg are the basic variables and IC Te and Tu = =uu-
Definition (Dual linear program). The dual linear program MD of the program given in 10 is
yo b Mb.
max
+
y
I subject to A + Vn + ya c, ys ym $0.
(11)
Theorem (Complementaryy Slackness). Let x² be a feasible solution to the linear program in (10) and let y" = (Wh Vn Vir) be a feasible solution to its corresponding dual linear program given in (11). Then, x² and y are optimal solutions for the two respective problems if and only if
(x" I v =0
(12)
(x*
vir
(13)
where @ denotes the Hadamard product. The additional conditions yi, @ (Ax - b) and (c ATyb Vu Wr) @ x = 0 are satisfied because both x² and y" are feasible.
Proof. The conditions derived from the definition of the dual program and strong duality in linear programming [see e.g., 10].
E
Additional experimental results
E.1
Generalization to larger instances
For capacitated facility location, we evaluated the generalization performance of 1.2Dive. For our experiments in subsection 5.1, trained and tested the small instances from Gasse et al. [17] for each problem class. In this additional experiment, we tested the L2Dive model trained on the small capacitated facility location instances and evaluated it along with all standard divers on 100 large capacitated facility location test instances from
[17]. We find that L2Dive gracefully generalizes to larger instances of the same problem class (Table 5). It achieves the lowest relative primal gap and outperforms all standard divers on the larger test instances. Overall, the relative primal gap tends to be larger which is expected the larger instances tend to be more difficult solve.
E.2 Relative primal gap
In Table we report the relative primal gap for the experiments in section 5.1. The relative primal gap is computed
7/p3 |z
(2)
(14)
where (2) is as defined in equation (5). It is ill-defined, if the objective value is zero, but this was not the case for any instances considered in our experiments. As the instances within each the four problem classes tend to have objective values of the same magnitude, the conclusions that can be drawn from the relative primal gap not differ from those we can draw from the absolute primal gap in Table 1. We included the results here for completeness.
16

---

Table 5: L2Dive outperforms standard divers large test instances from capacitated facility location, even when only trained on small instances. Average primal gap with standard error on test set.
small
large
L2Dive
0.89 (0.05)
1.43 (0.11)
Best heuristic
2.70 (0.04)
2.25 (0.10)
Coefficient
4.25 (0.05)
5.35 (0.17)
Distributional
4.24 (0.05)
(0.17)
Farkas
2.70 (0.04)
3.16
Fractional
5.91 (0.06)
9.38 (0.20)
Linesearch
5,78 (0.09)
4.56
Pseudocost
2.82 (0.06)
2.25 (0.10)
Vectorlength
4.68 (0.10)
3.09 (0.19)
Random
5.03 (0.08)
(0.16)
Lower
3,48 (0.05)
4.01 (0.13)
Upper
4.62 (0.08)
3.17 (0.15)
Table 6: We report mean and standard error of the relative primal gap in equation (14) for the experiments in subsection 5.1. The conclusions the same those drawn from Table 1.
SET COVER
COMB. AUCTION
FAC. LOCATION
IND. SET
L2Dive
2.86 (0.14)
2.84 (0.09)
0.89 (0.05)
0.23 (0.02)
Best heuristic
5.06 (0.16)
3.27 (0.1)
2.70 (0.04)
0.82 (0.05)
Coefficient
198.02 (2.23)
8.56 (0.14)
4.25 (0.05)
10.91 (0.17)
Distributional
209.29 (1.79)
19.18 (0.15)
4.24
8.70 (0.11)
Farkas
5.57 (0.17)
6.08 (0.12)
2..04
Fractional
198.82 (2.26)
8.57 (0.13)
5.91 (0.06)
10.27 (0.16)
Linesearch
69.05 (1.29)
5.96 (0.12)
5.78 (0.09)
3.42 (0.05)
Pseudocost
10.44 (0.43)
3.27 (0.1)
2.82 (0.06)
1.44 (0.08)
Vectorlength
5.06 (0.16)
10.65 (0.26)
4.68 (0.10)
0.82 (0.05)
Random
22.07 (0.6)
8.99 (0.16)
5.03 (0.08)
3.46 (0.11)
Lower
153.59 (2.81)
20.23 (0.14)
3.48 (0.05)
7.59 (0.20)
Upper
12.69 (0.28)
7.81 (0.14)
4.62 (0.08)
2.78 (0.09)
E.3
Execution Times
For completeness, we also report the execution times all divers considered in the experiments in subsection 5.1 in Table 7. On the instances considered, diving tends be rapid and differences in execution times are largely negligible (in contrast to differences in the quality of solutions found). Extremely short execution times typically result from diving being aborted early, e.g., because the L.P was rendered infeasible.
Tuning the SCIP solvers for diving
We leveraged expert knowledge and used random search to optimize the use diving heuristics in SCIP 7.0.2 for our baseline Tuned. The most important parameters to control the standard divers in SCIP are freq and freqofs. For each diving heuristic, these parameters control the depth at which the heuristic may be called or not called. By varying these parameters, diverse diving ensembles can be realized that call different heuristies at different stages of the branch and bound search. We randomly sample solver configurations by setting either freg = -1 (no diving), or freq (double frequency) or freq = fre4 (leave frequency at default) or freq = 2 x frequctautt (halve frequency) with equal probability and setting either freyofs = 0 or freqofs = freqofSjctaul. with equal probability independently for each diving heuristic. We run the solver with the usual time limits for each configuration and each validation instance and pick the configuration with the lowest primal-dua
0..5 freqdefaut.
17

---

Table 7: We report and standard deviation of the execution time for the experiments in subsection 5.1. Diving on these instances is very fast and differences are mostly negligible. Extremely short execution times tend to indicate that diving was aborted early, e.g., because the LP was rendered infeasible.
SET COVER
IND. SET
COMB. AUCTION
FAC. LOCATION
Diviv
0.45 (0.05)
0.58 (0.15)
0.38 (0.08)
3.99 (0.76)
Coefficient
0.28 (0.13)
0.04 (0.01)
0.02 (0.01)
3,40 (0.61)
Distributional
0.25 (0.11)
0.04 (0.01)
0.08 (0.02)
3,41 (0.63)
Farkas
0.05 (0.03)
0.02 (0.01)
3.66 (0.68)
Fractional
0.29 (0.14)
0.04 (0.01)
0.02 (0.01)
3,83 (0.60)
Linesearch
0.10 (0.04)
0.03 (0.01)
0.03 (0.01)
3.53 (0.79)
Pseudocost
0.02 (0.01)
0.04 (0.02)
0.02 (0.00)
2.77 (0.76)
Vectorlength
0.02 (0.01)
0.02 (0.01)
0.05 (0.01)
1.82 (0.59)
Random
0.08 (0.04)
0.25 (0.10)
0.05 (0.01)
4.42 (1.50)
Lower
0.74 (0.43)
0.66 (0.26)
0,49 (0.07)
4.11 (0.79)
Upper
0.05 (0.02)
0.17 (0.08)
0.04 (0.01)
2.79 (1.02)
integral for server load balancing and with the lowest solving time for neural network verification. For server load balancing, since the original validation dataset was relatively small, we created new validation dataset of 625 instances from the original training and validation sets, We optimized over 16 random configurations and thus used budget of 10,000 solver calls for load balancing. For neural network verification, we used the original validation dataset of 505 validation instances. We considered six random configurations and thus used a budget of 3,030 solver calls which is slightly more than what L2Dive used for data collection (2903).
We did not tune any parameters to optimize the use of L2Dive, but this might improve performance.
18


Reviews:
[{"review_id": "G07DSarhx1", "reviewer": "Reviewer_gbBh", "summary": "The paper develops a learning strategy to enhance variable selection in primal diving heuristics. More specifically, such a methodology relies on a generative model based on graph neural networks to predict the likelihood of variables assuming specific values. The predictions of the mean values are then integrated with dual reasoning (i.e., determining whether tightening would lead to an optimal linear programming solution) to decide the next variable to dive into. Numerical results evaluate the impact of the heuristic on a class of four combinatorial optimization problems, as well as its impact on a complete branching method for load balancing and neural network verification instances.", "questions": "1. From my understanding, if variables are discrete then $q_{\\theta}$ provides a vector of means for a Bernoulli sequence. How would $j^*$ be calculated in this case? \n\n2. Could you the authors kindly comment on (a), describing how instances for both the training and evaluation sets are picked?\n\n3. Have the authors performed experiments with/without Proposition 1?\n\n4. Would it be possible to augment any of the diving heuristics with Proposition 1 to evaluate if they would improve performance? \n\n5. Could the authors also include table with the primal-dual gap?", "limitations": "Limitations were properly addressed.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "+ Well-motivated application.\n+ Model is nicely designed.\n\nThe paper contributes to the research stream of machine-learning methods incorporated into combinatorial methods. I found that the generative model is compelling and fits well within diving heuristics, and it could as well be applied to other similar primal heuristics. The solution augmentation is indeed a challenge for training, but I appreciate the discussion and I also found the counting strategy quite novel (albeit possibly expensive?). I imagine that could be considered in other contexts as well, especially when providing sufficiently diverse solutions. ", "weaknesses": "- Numerical results lack detail and more thorough analysis.\n- Presentation needs a few revisions.\n\nMy primary concern is that results are not examined in detail; the proposed L2Dive technique completely dominates the other heuristics on the primal gap (Table 1) and has very small standard errors; for n=1,000 instances, this would indicate that the variance is quite small across a large instance class. This is somewhat rare in primal heuristic development and for such a variety of instances, and it is unclear from the text why this is happening. More specifically:\n\n(a) The text does not detail how instances of the four combinatorial optimization problems are selected. In particular, it refers to reference [17] for the benchmark tested, but in that paper they utilize multiple combinations of \"easy\", \"medium,\" and \"hard\" cases for each class; I am not sure which ones are considered in the paper. The training set choice is not clear as well. For instance, given that Erdos-Rényi instances are so particularly structured, are the independent set results really representative in practice in this particular context? It could be more beneficial to consider, e.g., DIMACS cases, which present a more diverse structure.\n\n(b) The paper only reports the non-normalized $\\textit{absolute}$ primal gap, which is the difference between the primal solution value and an optimistic bound. In this case, it is difficult to assess how significant the improvements are; for example, \"222\" and \"256\" could effectively have a small difference in terms of the primal-dual gap in combinatorial auctions if the bound is large.  \n\n(c) One important missing analysis is the relevance between the model $q_{\\theta}$ and the prioritization given by Proposition 1. First, how would LP2Dive behave without the indicator term from Proposition 1? Or, in other words, is the learning effective? Second, what would happen to the other diving heuristics (coefficient, Farkas etc.) if variables are first prioritized by Proposition 1?\n\nI also believe the presentation needs to be revised. In particular:\n\n- There are several typos and incomplete sentences. For example, \"verificationw\" (l.13), missing \"in Figure 1\" (l.50), adjectives miss hyphen (branch and bound tree --> branch-and-bound tree), and errors in references (e.g., in [17])\n- Table legends should start with what the table represents and not with what their aims, as that is a bit confusing.  \n- Figure 1 is a bit informal and not needed, as the overall sequential process is relatively easy to understand.\n- One suggestion is that $\\pi$ is typically used as dual variable as opposed to a bound. Perhaps $\\ell$ and $u$ could be clearer?\n\n** Updated score after thorough discussion with the authors.\n\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Thank you. We made revisions based on your feedback.\n\n**Thank you very much for your thoughtful review. We have made revisions to our paper based on your feedback and address your concerns in more detail below.**\n\n&nbsp;\n## We performed additional ablations to isolate the effects of dual reasoning. \n>*“experiments with/without Proposition 1? [...] L2Dive without the indicator term in Proposition 1?  [...] is the learning effective?”*\n\nThank you for this suggestion! We fully agree that this ablation is a good idea! And it was also proposed by Reviewer cl66. We have carried out an ablation study on capacitated facility location, where we evaluated\n\n- L2Dive with $s_j = q_\\theta(\\hat{x}_j)$, i.e. only using model confidence, not using dual reasoning. \n- L2Dive with $s_j = \\text{Uniform}(0, 1)$, i.e. a random variable selection, not using model confidence, not using dual reasoning. \n\nThe results are shown in the attachment. Even with a random scoring rule, L2Dive outperforms the best heuristics in terms of primal gap. However, the results significantly improve when using model confidence, and they tend to slightly improve when additionally using dual reasoning. Since using dual reasoning comes at negligible additional costs, because the dual values are readily available in the solver, we choose to use dual reasoning. We have added these results to the main text along with a short discussion. \n\n>*\"Would it be possible to augment any of the diving heuristics with Proposition 1 to evaluate if they would improve performance?\"*\n\nWe agree that this is an interesting avenue for future work in operations research, but we are primarily concerned with developing machine learning methods. Since we rely on the plug-in to call all standard divers in SCIP  (Section 3.3), using a dual reasoning rule for existing diving heuristics will require editing their source in SCIP directly and is out of scope for this work. However, we will release our code publicly upon acceptance and hope that this will facilitate research in this direction. \n\n&nbsp;\n## Experiments in 5.1 are intended to assess primal performance.\n>*““only reports non-normalized absolute primal gap […], what about primal-dual gap?“*\n\nWe report the primal gap in Table 1, because this is the bound that any diving heuristic will effectively improve. We choose to report the absolute primal gap, because it is conceptually easier. We were initially concerned about using the relative gap as defined in SCIP, because it is ill-defined if the primalbound and objective value have opposite signs and it may choose to normalize the absolute gap using either the primalbound or the objective value which can hinder comparisons between divers.\n\nHowever, we are happy to report the relative primal gap where we always normalize by the absolute objective value (we found that for all instances, primalbounds and objective values are of the same sign) in the attachment and now include these additional results in the appendix.\n\nThe experiments in section 5.1 were designed to study the diving performance of L2Dive and compare it against existing diving heuristics without confounding the results with other subroutines of the solver. Therefore, we did not branch and disabled cutting planes and other primal heuristics. Hence, we do not compute the dualbound or the primal-dual gap in these experiments, they are naturally weak. We focus on overall solver performance (primal-dual integral, solving time) in our experiments in section 5.2. \n\n&nbsp;\n## Data is appropriate for our experimental goals. \n>*““How instances of the four combinatorial optimization problems are selected?” Are independent set results really representative […]?“*\n\nWe use the “easy” (i.e., smaller-sized) instances for our experiments. These instances were randomly generated with exactly the same procedure as described by Gasse et al using the generators made available in Ecole [Prouvost et al., 2020]. We now include the explicit reference to the Ecole library in the main text. \n\nWe chose these instances, because they collectively represent a diverse set of combinatorial problems and they have been adopted by previous work [e.g., Gasse et al. (2019), Gupta et al. (2020), Scavuzzo et al. (2022) among others]. We believe there is value in using the same problem benchmark. We chose the “easy” instances, because they allowed us to test many methods at scale with relatively modest computational resources. In addition, our results indicate that they are “sufficiently hard” for existing diving heuristics (larger average primal gaps). Thus, they provide a useful test bed. In section 5.2, we focus on overall solver performance in real-world application and use harder and larger instances. \n\n\n&nbsp;\n## Table 1 reports the standard error of the mean, not the standard deviation of the sample. \n>*“The primal gap (Table 1) has very small standard errors. [...] for n=1,000 instances, this would indicate that the variance is quite small across a large instance class.“*\n\nWe apologize for the confusion. Table 1 reports the standard error of the mean (SEM), not the standard deviation of the sample (all n observations). Specifically, the standard error of the mean is defined as \n\n$$\n\\text{SEM} = \\frac{s}{\\sqrt{n}}\n$$\n\nwhere $s$ is the standard deviation of the sample computed for $n=500$ observations. Naturally, as the sample size $n$ increases, the standard error of the mean is reduced, as the estimate becomes more accurate. We choose to report the standard error of the mean, because statistical significance can be more easily gauged (e.g., via t-test) from it than from the standard deviation of the sample. We find that the standard deviation on all four datasets is of the same order as the standard deviation of the objective value and find no anomaly. We are happy to report the standard deviation in the main text or the appendix if others find it helpful. "}, {"review_id": "OGAcdFA3k4", "reviewer": "Reviewer_qRaC", "summary": "This paper presents a technique for heuristically generating good feasible solutions for mixed-integer programming problems by leveraging known, good feasible solutions for related problem instances. The technique is a \"diving\" heuristic, which subsequently fixes subsets of the integer decision variables, and uses a generative model (and a bit of LP duality) to determine the subsets. A computational study suggests that their technique outperforms the diving heuristics contained in the SCIP solver. ", "questions": "* L49: Unfinished sentence.\n* L149: What are \"trivial solutions\"?\n* Proposition 1: The paper should be self-contained, and not require the appendix to comprehend. I'd suggest listing the dual LP in the text, and perhaps move some of Section 2.2 to the appendix if space is needed.\n* Citation [17] has broken typesetting.\n* L257: Can the authors please confirm that a _different_ set of 500 instances are used for validation and testing?\n* Section 5.1 could be further strengthened by comparing against other, non-diving, heuristics in SCIP.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper falls squarely in a line of research (learning for optimization) that is of substantial interest to the NeurIPS and mathematical optimization communities. The ideas are interesting and nontrivial (the application of LP duality is neat and clean, if not especially deep). The contributions are, to my reading, quite solid, though the general area in which they are operating has been studied for some years. The paper is very well-written and, to my understanding, original, though there are a handful of closely related papers that the authors situate themselves against explicitly.", "weaknesses": "As the authors themselves recognize (to their credit), the computational baseline against SCIP's existing diving heuristics may be a weak one. But, as SCIP is a best-of-breed open MIP solver and this study requires tight integration into the solver, I do not see this as something that can be held against this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Thank you for your positive reception of our work. \n\n**We are happy to integrate the dual LP into the main text. We have fixed the typos you found in the main text. We address your outstanding questions below.**\n\n>*“Please confirm that a different set of 500 instances are used for validation and testing?”*\n\nAbsolutely! We apologize for the confusion. They are different! Specifically, for each dataset considered in Table 1, we  generated 2000 (iid) instances in total, and used 1000 of these instances for training, 500 of these instances for validation and the remaining 500 of these instances for testing. This question was also raised by Reviewer cl66  and we have edited the main text to make this crystal clear. \n\n\n>*“Existing diving heuristics may be weak, [... cannot] be held against this paper”*\n\nThank you! We agree and would like to confirm that unfortunately Gurobi’s diving code is closed-source to date and thus does not facilitate any experiments with *L2Dive*. We also highlight that we compare against a *tuned* diving ensemble in section 5.2 which significantly improves over SCIP’s default setting and is a strong baseline for direct comparison.\n\n>*“What are trivial solutions (Line 149)?”*\n\nWe were originally referring to the trivial solutions that SCIP tests in the beginning of a solve, e.g., setting all variables to zero. However, we believe that “poor feasible solutions” is much clearer in this context. Thank you for flagging this, we have changed the main text! \n\n"}, {"review_id": "P4O8OIRgZZ", "reviewer": "Reviewer_GD8n", "summary": "This paper introduces a new framework to improve B&B MIP solvers by neural networks. This paper proposes a neural network-based primal heuristic, namely L2Dive. The authors implement L2Dive with SCIP and conduct extensive experiments on several datasets.\n\n\n---------------------\n\nPost-rebuttal: Thanks a lot for the response. I feel positive about this paper and will vote for accept.", "questions": "* Why different measurements are considered for different tasks in Table 2?", "limitations": "None", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "* This paper shows the feasibility of using neural networks to replace & improve existing primal heuristics.\n* The design details of L2Dive seem technically sound.\n* The experiments are extensive and convincing.", "weaknesses": "* The authors should provide the timing statistics of different primal heuristics in Table 1.\n* As I know, Nair et al. [32] proposed \"neural diving\" and the conceptual idea is very similar to the contribution of this paper. The authors should make more efforts to address the original technical contributions compared to [32] and try to compare with [32] in experiments.\n* Some details of the approach remain unclear to me: \n    * The neural network is trained with high-quality solutions, while the output of the neural network represents the score of whether a variable should be dived. How do you connect these two? What is exactly the loss function during training?\n    * How many times is the neural network called when running Algorithm 1?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Thank you for your review.\n\n**Thank you very much for your feedback. We address your concerns in more detail below.**\n\n&nbsp;\n## Other primal heuristics are complementary to diving, no heuristic rules them all!\n>*“The authors should make more efforts to address the original technical contributions compared to Nair et al. [32] and try to compare with [32] in experiments.*\n\nWe view Nair et al. [32] as complementary, because it is a primal, but not a diving heuristic. In our experiments in section 5.2, we deploy L2Dive within branch and bound, and our model is called by the solver along with many other subroutines (including other primal heuristics) and the method by Nair et al. [32] could also be used in addition to improve performance further. Intuitively, we expect L2Dive to be particularly effective for instances where the solutions of linear programs can be rendered integral easily, and we expect Nair et al. [32] to be particularly effective on instances, where the overhead of solving sub-MILPs in place of linear programs tends to be small. \n\nOverall, the goal of our work is not to demonstrate the superiority of diving heuristics over other primal heuristics, but to improve on existing diving heuristics with machine learning. We believe diving heuristics play an important role in branch and bound, but so do other primal heuristics, and which method is more appropriate will depend on the particular problem instances under consideration. This is the reason why we compare primarily against other diving heuristics. \n\nWe think this is an important discussion, and we have expanded our related work section to include it. \n\n\n&nbsp;\n## Variable selection is based on model confidence and dual reasoning. Model is only called once. \n>*\"The neural network is trained with high-quality solutions, while the output of the neural network represents the score of whether a variable should be dived. How do you connect these two? What is exactly the loss function during training?\"*\n\nYou are spot on! Our objective is to minimize the KL divergence in equation (7) and at training time our loss function is a mini-batched average of this KL divergence. Our model is only learnt from good feasible solutions, there is no direct supervision on diving or variable selection. While this choice offers several advantages, e.g., much cheaper to collect training data, the model is trained to only predict correct variable assignments, but not what variables to choose to fix for diving.\n\nTo bridge this gap, we suggest the rule in equation (8) that balances the model confidence in a prediction with duality theory to encourage shorter dives. Intuitively, the dual reasoning rule is justified if the prediction is correct. The better the prediction, the more confident the model, the better the dual reasoning rule is expected to work. Our empirical results along with the additional ablations we performed support our choice. \n\n>*“How many times is the neural network called when running Algorithm 1?”*\n\nThank you, this is an important question! For any dive, we only call the model once at the beginning of the dive. While it’d be possible to call the model more frequently to potentially improve predictions, this keeps the in-service overhead of our method low and simplifies considerations for data collection.\n\n&nbsp;\n## Load balancing instances are hard, L2Dive is fast.\n>*“Why are different measurements considered for different tasks in Table 2?”*\n\nTable 2 reports the primal-dual integral for instances from load balancing, but solving time for instances from neural network verification. The goal of Table 2 is to report the overall solver performance for different methods on each task (dataset). Overall solver performance is naturally measured by solving time, i.e., the total time it takes to completely solve an instance (primal-dual gap is zero). However, the load balancing instances are so difficult to solve, that they cannot be solved in a reasonable amount of time. For example, not a single instance can be solved using SCIP (Default) within 60 minutes. Therefore, we set a time limit of 900 seconds and report the primal-dual integral instead. The primal-dual integral is an accepted measure of solver performance (Achterberg et al.). \n\nThank you for raising this point. We now highlight the reason for reporting the primal-dual integral for load balancing in Table 2 more prominently. \n\n>*The authors should provide the timing statistics of different primal heuristics in Table 1.*\n\nWe are happy to report the overall execution times for all divers in the attachment and will include them in the appendix, but did not do so initially, because they are largely negligible. On set cover, independent set and combinatorial auctions, all divers take less than a second to run, while on facility location all divers tend to run in between three to four seconds. For all instances, execution time is mostly correlated with the depth of the dive. A method that renders an instance quickly infeasible and thus aborts the dive (unsuccessfuly) will have a small execution time, while a method that dives deep will have a longer execution time, but not necessarily a good solution (for example Lower on set cover runs 50% longer than L2Dive). L2Dive naturally incurs a small overhead for calling the neural network, but it also consistently finds better solutions (Table 1 in main text). \n"}, {"review_id": "2uf84GxLtJ", "reviewer": "Reviewer_cL66", "summary": "The authors propose L2Dive to learn dataset-specific diving heuristics with graph neural networks. Specifically, they employ generative models to predict variable assignments and leverage the duality of linear programs to make diving decisions based on the model’s predictions. Experiments show improved performance on both diving and branch-and-bound tasks.", "questions": "1. The authors describe in line 257 that they \"validated and tested on 500 instances\". I am not sure whether they validate and test the model in the same dataset, which is discouraged in practice.\n2. What is the standard deviation of the results in Table 1&2? As the solving time for different instances varies a lot, can you provide the geometric mean of these results as that in [2,3]?\n3. I cannot find any code availability claims in both the paper and the appendix. I think this is not encouraged for an AI conference like NeurIPS. Can the codes of this paper be available once the paper is accept?\n\nI would like to raise my score if  the authors reply well (especially question 3) to the above weaknesses and queations.\n\n[2] Gupta, Prateek, et al. \"Hybrid models for learning to branch.\" Advances in neural information processing systems 33 (2020): 18087-18097.\n[3] Achterberg, Tobias. Constraint integer programming. Diss. 2007.", "limitations": "See weakness above.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Interesting research topic. The diving heuristic can be well formulated as a 0/1 prediction task. Thus, employing generative models for this task is meaningful and practical.\n2. Novel algorithm design. The leverage of the duality property for variable selection is insightful, as it is not obvious to design such approach compared to the design of generative models.\n3. Well written paper. The presentation is really clear, which makes the readers easy to follow.", "weaknesses": "1. Inefficient literature research. The main idea used in this topic is similar to that in [1] in the node selection task. Personally, I think the diving task and the node selection task on binary problems are really similar, and the GNN model proposed in [1] can be used in this task directly without much adaptations. Thus, the introduction and comparison to [1] is required.\n2. (I am not sure for these results in my memory. So if I am wrong, please inform me the correct results.) Confusing results in Table 1. In my memory,  after presolve, SCIP can find optimal solutions easily at the root nodes on most instances from the four benchmarks the authors used. That is the reason why these four benchmarks are usually used for the variable selection task (dual task). Thus, I am confused that whether the results in Table 1 is convincing enough, as the benchmarks used here may be too easy for this task. (I am not sure about this comment)\n3. Insufficient ablation study. The comparison bettween dual theory based variable selection and vanilla variable selection is missing. Thus, I am not sure whether the proposed dual based selection strategy is effective. The relationship between the complexity of the generative models and the final performance is also missing. The precision increases with more complex models, while the inference time also increases. Thus, there may be a trade-off for model design. I searched for the keyword \"ablation\" in both the main paper and the Appendix but have not found any results. For better completeness, it is better to include them in the *main paper*.\n4. Insufficient comparative experiments. The generalization ability for this approach is missing. Thus, what is the performance of L2Dive on larger instances? Moreover, I observe that the results on the branch-and bound tasks are relatively limited. Thus, I also doubt about the overall performance on the B&B task as the generalization problem in this setting is usually more severe.\n\n[1] Khalil, Elias B., Christopher Morris, and Andrea Lodi. \"Mip-gnn: A data-driven framework for guiding combinatorial solvers.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 36. No. 9. 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Thank you. We made revisions based on your feedback.\n\n**Thank you very much for your thoughtful review. We have made revisions to our paper based on your feedback and address your concerns in more detail below.**\n\n&nbsp;\n## We performed additional ablations to isolate the effects of dual reasoning. \n>*“Insufficient ablation study. The comparison bettween dual theory based variable selection and vanilla variable selection is missing.*\n\nThank you for this suggestion! We fully agree that this ablation is a good idea! And it was also proposed by Reviewer gbBh. We have carried out an ablation study on capacitated facility location, where we evaluated\n\n- L2Dive with $s_j = q_\\theta(\\hat{x}_j)$, i.e. only using model confidence, not using dual reasoning. \n- L2Dive with $s_j = \\text{Uniform}(0, 1)$, i.e. a random variable selection, not using model confidence, not using dual reasoning. \n\nThe results are shown in the attachment. Even with a random scoring rule, L2Dive outperforms the best heuristics. However, the results significantly improve when using model confidence, and they slightly improve when additionally using dual reasoning. Since using dual reasoning comes at negligible additional costs, because the dual values are readily available in the solver, we choose to use dual reasoning. We have added these results to the main text along with a short discussion. \n\n&nbsp;\n## Khalil et al. is relevant and related, but different. \n>*“main idea [...] is similar to that in [1] in the node selection task [...] introduction and comparison is required.”*\n\nThank you for bringing Khalil et al. [1] to our attention. This is a cool paper! Like us they leverage supervised learning on solutions of MILP to train a GNN for predicting variable assignments, (albeit both our model architecture and objective differ from theirs). But most importantly, as you note, they propose a heuristic rule to perform node selection from the model prediction, while we consider diving. One of our key contributions is to propose a method for using a generative model for diving (section 3.2). Our approach offers several benefits, e.g., (a) depth-first search for node selection is known to be problematic, because node selection needs to balance the primal and dual objective, while diving is solely concerned with the primal objective (Achterberg, page 73), (b) diving can leverage the fast LP solver rather than fully (and time-consumingly) resolving each node in the search tree, (c) since diving is conducted in probing mode, a “bad” dive leading to many open nodes can simply be aborted without impacting the solver state, while bad node selection decisions must be undone via a solver restart. \n\nWe think this is a valuable discussion. Therefore, we have added a reference to Khalil et al [1] in the main text, and clearly highlight similarities and differences. \n\n&nbsp;\n## Problem instances are large-scale and experimental protocol is thorough.\n>*“results on the branch-and bound tasks are relatively limited. [...] performance of L2Dive on larger instances? ”*\n\nWe politely disagree. The instances we consider in our experiments in Section 5.2 are large-scale. For example, the load balancing instances contain 61,000 variables and 64,410 constraints per instance prior to pre-solve and more than 4,000 variables and 4,000 constraints after pre-solve. Similarly, the neural network verification instances are of the same order of magnitude. \nThis is comparable or larger to the “hard” instances considered by Gasse et al. (2019). In addition, our instances are harder to solve. Not a single load balancing instance can be solved with the SCIP solver within 60 minutes, while the results reported in Gasse et al. suggest that their instances can be solved on average in 2 minutes (set cover) to 35 minutes (independent set). \nMoreover, our experiments on branch and bound are extensive and thorough. Notably, we compare against (and outperform) a strong “tuned” solver baseline, something that is arguably important fto benchmark machine learning methods for branch and bound against, but rarely done (with some notable exceptions in [Nair et al. (2020),  Sonnerat et al. (2021), Chmiela et al. (2021) ]. We establish a thorough protocol (Appendix E) for evaluation where our baseline receives the same budget of solver calls for tuning as L2Dive expended for data collection. \nOverall, we consider a total of six datasets. \n\n&nbsp;\n## Experiments in 5.1 are for comparing diving heuristics\n>*“benchmarks [used in 5.1] too easy for this task?”*\n\nThank you for raising this point. Our goal for the experiments in Section 5.1 was to study the diving performance of L2Dive and compare it to existing diving heuristics. While it is true that these instances can be solved relatively quickly with a full branch and bound solver, our results suggest that they are challenging for diving heuristics (larger primal gaps), and thus these instances are appropriate and provide a useful testbed. We chose these instances, because they have been adopted by prior work in machine learning for branch and bound and represent a diverse set of combinatorial problems. \n\n&nbsp;\n## Validation and test set are different!\n> *“validate and test the model in the same dataset?”*\n\nAbsolutely not! We apologize for the confusion. Validation and test set are different! Please see response to qRaC \n\n\n&nbsp;\n## Code will be made publicly available upon acceptance. \n> *“Can the codes of this paper be available once the paper is accepted?”*\n\nAbsolutely! We will make all experimental code publicly available upon acceptance. In addition, we are in discussions with the SCIP/ PySCIPOpt development team to contribute a new diving plug-in available to the PySCIPOpt library. We hope our contributions will facilitate further research into machine learning for branch and bound generally, and diving heuristics specifically. \n"}]

Author rebuttal:
## Thank you for your thoughtful feedback!

**We have incorporated the feedback of the reviewers and made the following revisions to our draft:**

- We present an additional ablation study (see attachment!) on capacitated facility location to study L2Dive’s variable selection (dual reasoning and model confidence) in more detail. We propose to add it to the main text along with a short discussion and interpretation of the results. 
- We report additional metrics (e.g., relative gap, execution time, see attachment!) as suggested and propose to add them to the main text/ appendix. 
- We added discussions of relevant related work as suggested in the main text. 
- Small edits (typos, clarifications, etc.), thank you all for flagging any you found!

Please see individual responses for more detail below. 


Meta-review: All reviewers agreed this paper should be accepted: it addresses an important problem, the algorithm is well-designed and novel, and the paper is clearly written. A clear accept. Authors: you've already indicated that you've updated the submission to respond to reviewer changes, if you could double check their comments for any recommendation you may have missed on accident that would be great! The paper will make a great contribution to the conference!
Decision: Accept (poster)