Learning to Schedule Heuristics in Branch and Bound
Authors: Antonia Chmiela
Elias Boutros Khalil
Ambros Gleixner
Andrea Lodi
Sebastian Pokutta
Venue: NeurIPS 2021 Poster (2021)
Keywords: integer programming
learning to optimize
data-driven algorithm design
tree search
algorithm configuration

Abstract: Primal heuristics play a crucial role in exact solvers for Mixed Integer Programming (MIP). While solvers are guaranteed to find optimal solutions given sufficient time, real-world applications typically require finding good solutions early on in the search to enable fast decision-making. While much of MIP research focuses on designing effective heuristics, the question of how to manage multiple MIP heuristics in a solver has not received equal attention. Generally, solvers follow hard-coded rules derived from empirical testing on broad sets of instances. Since the performance of heuristics is problem-dependent, using these general rules for a particular problem might not yield the best performance. In this work, we propose the first data-driven framework for scheduling heuristics in an exact MIP solver. By learning from data describing the performance of primal heuristics, we obtain a problem-specific schedule of heuristics that collectively find many solutions at minimal cost. We formalize the learning task and propose an efficient algorithm for computing such a schedule. Compared to the default settings of a state-of-the-art academic MIP solver, we are able to reduce the average primal integral by up to 49% on two classes of challenging instances.

Learning to Schedule Heuristics in Branch and Bound
Antonia Chmiela
Elias B. Khalil
Zuse Institute Berlin, Germany chmie momieeaazib.cc.
University of Toronto, Canada khalil Amaie. utwronto.ccommm ca
Ambros Gleixner
Andrea Lodi
Zuse Institute Berlin, Germany HTW Berlin, Germany gleixner@zib..
CERC, Polytechnique Montréal, Canada andrea lodi @polymt1... ca
Sebastian Pokutta
Zuse Institute Berlin, Germany Technische Universität Berlin, Germany pokutta@zib.de
Abstract
Primal heuristics play crucial role in exact solvers for Mixed Integer Programming (MIP). While solvers are guaranteed to find optimal solutions given sufficient time, real-world applications typically require finding good solutions early on in the search to enable fast decision-making While much of MIP research focuses on designing effective heuristics, the question of how manage multiple MIP heuristics in solver has not received equal attention. Generally, solvers follow hard-coded rules derived from empirical testing on broad sets of instances. Since the performance of heuristics is particular problem might not yield the best performance. this work, we propose the first data-drives framework for scheduling heuristics in an exact MIP solver. By learning from data describing the performance of primal heuristics, we obtain problem-specift schedule of heuristics that collectively find many solutions at minimal cost. We formalize the learning task and propose an efficient algorithm for computing such schedule. Compared to the default settings of a tfte-of-the-att academic MIP solver, we are able to reduce the average primal integral by up to 49% on two classes of challenging instances.
using these general rules for a
Introduction
Many Decision-making problems arising from real-world applications can be formulated using Mixed Integer Programming (MIP). The Branch and Bound (B&B) framework is general approach to solving MIPs to global optimality. Over the recent years, the idea of using machine learning (ML) to improve optimization techniques has gained renewed interest. There exist various approaches to tackle different aspects of the solving process using classical ML techniques. For instance, MI has been used to find good parameter configurations for solver (Hutter et al. 2009 (011). improve node (He et al. 2014), variable (Khalil et al., 2016,, Gasse et al. 2019 Nair al., 2020) or cut
(Baltean-Lugojan et al. 2019) selection strategies, and detect decomposable structures Kruber et al.) 2017).
Even though exact MIP solvers aim for global optimality, finding good feasible solutions fast is at least as important, especially in the presence of time limit. The use of primal heuristics is crucial to
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

0.7
GISP FCMNF
1.0
schedule
0.6
0.8
default SCIP
primal gap
0.6
0.4
solution
0.3
0.2
0.2
0.1
0.0
10a
10
10a
10
0.0
heuristics
time (in seconds)
Figure 1: Average solution success rates of ten heuristics for two problem classes. Heuristic success is problem-dependent: each pair of blue- yellow bars belongs to one heuristic, and the heuristics sorted in descending order w.r.t. the solution success rates for GISP (blue).
Figure 2: Primal gap for exemplary GISP instance. Our method's heuristic schedule (orange) obtains better solutions ear- lier than SCIP's default (blue).
ensuring good primal performance in modern solvers. For instance, |Brrthold (2013a) showed that the primal bound-the the objective value of the best celuutonniiprovee on average by around 80% when primal heuristics were used. Generally, a solver includes variety of primal heuristics, where each class of heuristics (e.g., rounding. diving, large-neighborhood search) exploits a different idea find good solutions. During B&B, some of these heuristics are executed successively at each node of the search tree, and improved solutions, if any, are reported back to the solver. An extensive overview of different primal heuristics, their computational costs, and their impact in MIP solving can be found in
Lodi (2013); Berthold (2013b] 2018).
Since most heuristics can be very costly, it is necessary to be strategic about the order in which the heuristies executed and the number of iterations allocated to each. Such decisions are often made by following hard-coded rules derived from testing on broad benchmark test sets. While these static rules yield good performance on average, their performance can be far from satisfactory when considering specific families of instances. To illustrate this fact, Figure [ compares the solution success rates, i.e., the fraction of calls to a heuristic where a solution was tound, of different primal heuristics for two problem classes: the Generalized Independent Set Problem (GISP) (Hochbaum and Pathria 1997: Colombi al. (2017) and the Fixed- Charge Multiconmodity Network Flow Problem (FCMNF) (Hewitt et al. 2010).
In this paper, we propose a data-driven approach to systematically improve the of primal heuristics in B&B. By learning from data about the duration and success of every heuristic call for set of training instances, we construct a schedule of heuristics that specifies the ordering and duration for which each heuristic should be executed to obtain good primal solutions early on. As a result, we are able to significantly improve the use of primal heuristics as shown in Figure for one MIP instance.
Contributions. Our main contributions can be summarized as follows:
1. We formalize the learning task of finding an effective, cost-efficient heuristic schedule training dataset as a Mixed Integer Quadratic Program (Section 3):
We propose an efficient heuristic for solving the training (scheduling) problem and a scalable data collection strategy (Sections and
3. We perform extensive computational experiments on a class of challenging instances and demonstrate the benefits of our approach (Section 6)
Related Work. Optimizing the use of primal heuristics is a topic of ongoing research. For instance, by characterizing nodes with different features, Khalil et al. (2017) propose an ML method to decide when to execute heuristics to improve primal performance. After that decision, all heuristics are executed according to the predefined rules set by the solver, Hendel (2018) and Hennel et (2018) use bandit algorithms for the online learning of a heuristic ordering. The method proposed in this paper jointly adapts the ordering and duration for which each heuristic runs. Primal performance
can also be improved using algorithm configuratio (Hutter et al. 2009 2011). technique which
generally computational expensive since it relies on many black-box box evaluations of the solver as its parameter configurations are evaluated and does not exploit detailed information about the effect

---

of parameter values on performance, e.g., how parameters of primal heuristics affect their success rates. There has also been work done on how to schedule algorithms optimally. Kadioglu al. (2011) solved the problem for portfolio of different MIP solvers whereas Hoos et al. (2014) focused on Answer Set Programming. Furthermore, SSeip et al. (2015) propose an algorithm that greedily finds schedule of different parameter configurations for automated planning.
2 Preliminaries
Let us consider MIP of the form
min c s.t. Ax b, Is E EZ, =E
(Parr)
with matrix A E RR>X", vectors c E R", b E RT, and a non-empty index set S [n]] for integer variables. A MIP can be solved using B&B, tree search algorithm that finds optimal solution to (uur) by recursively partitioning the original problem into linear subproblems. The nodes in the resulting search tree correspond to these subproblems. Throughout this work, we assume that each node has a unique index that identifies the node even across B&B trees obtained for different MIP instances. For a set of instances X', denote the union of the corresponding node indices by Nx-
Primal Performance Metrics. Since we are interested in finding good solutions fast, we consider a collection of different metrics for primal performance. Beside statistics like the time to the first/best solution and the solution/incumbent success rate, we mainly focus on the primal integral (Berthold 2013a) comprehensive measure of primal performance. Intuitively, this metric can be interpreted as a normalized average of the incumbent value over time. A formal definition can be found in Appendix A Figure gives example for the primal gap function. The primal integrals the areas under each of the curves. It is easy to see that finding near-optimal incumbents earlier shrinks the area under the graph of the primal gap, resulting in smaller primal integral.
3 Data-Driven Heuristic Scheduling
Since the performance of heuristics is highly problem-dependent, it is natural to consider data- approaches for optimizing the use of primal heuristics for the instances of interest. Concretely, consider the following practically relevant setting. We given set of heuristics H and homogeneous set of training instances X' from the same problem class. In a data collection phase, we allowed to execute the B&B algorithm the training instances, observing how each heuristic performs at each node of each search tree. At a high level, our goal is to then leverage this data to obtain a schedule of heuristics that minimizes a primal performance metric.
The specifics of how such data collection carried out will discussed later on in the paper. First, let us examine the decisions that could potentially benefit from data-driven approach. Our discussion is inspired by an in-depth analysis of how the open- MIP solver SCIP (Gamrath et al. 2020) manages primal heuristics. However, our approach is generic and is likely to apply to other solvers.
Controlling the Order. One important degree of freedom in scheduling heuristics is the order in which a set of heuristics H is executed by the solver at a given node. This can be controlled by assigning a priority for each heuristic. in decreasing priority. The loop is terminated if a heuristic finds new incumbent solution that cuts off the current node. As such, an ordering (hi,...,Iu, h&) that prioritizes effective heuristics can lead to time savings without sacrificing primal performance.
heuristic loop, the solver then iterates over the heuristics
Controlling the Duration. Furthermore, solvers use working limits to control the computational effort spent on heuristics. Consider diving heuristics as an example. Increasing the maximal diving depth increases the likelihood of finding an integer feasible solution. At the same time, this increases the overall running time. Figure 3 visualizes this cost-benefit trade-off empirically for three different diving heuristics, highlighting the need for careful "balancing act". For heuristic h E H. let E Ryy denote its time budget. Then, we are interested in finding schedule == ((h,, TI), ..... (hR, Tu)),, hy; E H. Since controlling the time budget directly can be unreliable and lead to nondeterministic behavior in practice (see Appendix F for details), a deterministic proxy measure is preferable. For diving heuristies, the maximal diving depth provides a suitable measure as demonstrated by Figure 3 Similar measures can be used for other types of heuristics, we will
3

---

number of solutions found
1.0
time per call (in seconds)
0.07
0.06
0.8
0.05
0.6
0.04
0.03
0.4
0.02
0.2
0.01
0.0
0.00
50
100
150
200
250 300
350
0
50
100
150
200
250
300
350
maximal diving depth
maximal diving depth
Figure 3: Number of solutions found and cost of different diving heuristics depending on the the maximal diving depth: This figure shows the average fraction of solutions found by heuristic (left) and average duration in seconds (right) of three diving heuristics when limiting the maximal depth of dive. Hereby, the baseline for the values the vertical axis of the left figure is the number of solutions found by the heuristics with no limitations on the diving depth. The likelihood of finding solution increases with the maximal diving depth. At the same time, an average call all three heuristics becomes more expensive as the diving depth increases.
demonstrate with Large Neighborhood Search heuristics in Section 6 In general, we will refer to тą the maximal number of iterations that allocated a heuristic f; in schedule S.
Deriving the Scheduling Problem. sions, will now formalize our heuristic scheduling problem. Ideally, would like to construct schedule that minimizes the primal integral, averaged over the training set X. Unfortunately. is very difficult optimize the primal integral directly, it depends the sequence of incumbents found over time during B&B. also depends on the way the search tree is explored, which affected by pruning, further complicating any attempt directly optimizing this primal metric.
Having argued for order and duration as suitable control deci-
We address this difficulty by considering a more tractable surrogate objective. Recall that Nxx denotes the collection of search tree nodes of the set of training instances X. We will construct schedule that finds feasible solutions for a large fraction of the nodes in Nxx while also minimizing the number of iterations expended by schedule S. Note that consider feasible solutions instead of incumbents here: this way, we are able to obtain more data faster since a heuristic finds a feasible solution more often than new incumbent. The framework propose in the following handle incumbents instead, but we have found no benefit in doing so in preliminary experiments.
For heuristic h and node N, denote by t(h, N) the iterations necessary for h to find solution node N, and set t(h, N) oo if h does not succeed N. Now suppose a schedule S is successful at node N, i.e., some heuristic finds solution within the budget allocated to it in S. Let js = min (j E [|]]]] [(h,, S т be the index of the first successful heuristic. Following the execution of hys the heuristic loop is terminated, and the time spent by S at node N is given by
T)S,N)
Σ Ti ((hjs, N). kE[is-1]
Otherwise, set T(S,N)== E + where the additional penalizes unsolved nodes.
Furthermore, let Ns denote the set of nodes at which schedule S is successful in finding solution. Then, we consider the heuristic scheduling problem given by
min SES
Σ T(S,N) s.t. Wel Wxx
(Ps)
NEAX
Here a E (0, 1] denotes the minimum fraction of nodes for which the schedule must find a feasible Mixed- Quadratic Program (MIQP); the complete formulation can be found in Appendix B
solution. Problem (Ps) be formulated
To find such schedule, need to know f(h, N) for every heuristic h and node N. Hence, when collecting data for the instances in the training set X, we track for every B&B node at which heuristic h called, the number of iterations T took h to find feasible solution;
set
T 30 if h does not succeed N. Formally, we require training dataset D = {h, N, 7

---

E N.N E T&, Ry0 U }. Section 5 describes computationally efficient approach for building D using a single B&B run per training Instance.
4 Solving the Scheduling Problem
Problem is generalization of the Pipelined Set Cover Problem which is known to be N'r-aard (Munagala et al. 2005). As for the MIQP in Appendix B tackling it using a non-linear integer programming solver is challenging: the MIQP has O(H[[<l)) variables and constraints. Since single instance may involve thousands of search tree nodes, this leads to an MIQP with hundreds of thousands of variables and constraints even with a handful of heuristics and tens of training instances.
As mentioned in Related Work, algorithm configuration tools such as SMAC (Hutter et al.) 2011) could be used to solve ( heuristically. Since SMAC is a sequential algorithm that searches for a good parameter configuration by successively adapting and re-evaluating its best configurations, its running time can be quite substantial. In the following, we present more efficient approach.
We now direct attention towards designing an efficient heuristic algorithm for (Ps) A similar problem was studied by Streeter (2007) in the context of decision problems. Among other things, the author discusses how to find schedule of (randomized) heuristics that minimizes the expected time necessary to solve a set of training instances X' of a decision problem. Although this setting is somewhat similar ours, there exist multiple aspects in which they differ significantly:
1. Decision problems are considered instead of MIPs: Solving a MIP is generally much different from solving a decision problem. When using B&B, we normally have to solve many linear subproblems. Since in theory, every such LP is opportunity for heuristic to find new incumbent, we consider the set nodes Nxx instead of as the "instances" we want to solve.
2. A heuristic call can be suspended and resumed: In the work of Streeter, a heuristic can be executed in buspend-and-resune
model": h was executed before, the action (h, represents continuing a heuristic run for an additional J iterations. When h reaches the iteration limit, the rum is suspended and its state kept in memory such that it can be resumed later the schedule. This model is not used in MIP solving due to challenges in maintaining the states of heuristics in memory. As such, we allow every heuristic to be included in the schedule at most once.
3. Time is used to control the duration of a heuristic run: Controlling time directly is unreliable in practice and can lead nondeterministic behavior of the solver. Instead, we rely different proxy measures for different classes of heuristics. Thus, when building a schedule that contains heuristics of distinct types, we need ensure that these measures are comparable.
Despite these differences, it is useful to examine the greedy scheduling approach proposed in Streeter (0007). A schedule G is built by successively adding the action (h, -) that maximizes the ratio of the marginal increase in the number of instances solved to the cost (i.e., r) of including (h, r). As shown in Corollary 2 of Streeter (2007), the greedy schedule G yields a 4-approximation to that version of the scheduling problem. In an attempt to leverage this elegant heuristic in our problem (ss we will describe it formally.
Let us denote the greedy schedule by G = (gI...., .9k)....)))....... Then, G is defined inductively by setting Go = ( and G3 = (g1...., g5) with
KN E 2 STT
= argmax (
Here, Hl denotes the set of heuristics that are not in Gy, N&. denotes the subset of nodes not solved by Gj, and T is the interval generated by all possible iteration limits in D, i.e., T = [min(r& (N, h, 7 E DD, max max(T (N, h, + E DD}. We stop adding actions gj when Gj finds solution at all nodes in Xxx all heuristics contained in the schedule, i.e., Hl 0.
Unfortunately, the resulting schedule can perform arbitrarily bad in our setting: Assume we have [>x = 100 and only one heuristic h. This heuristic solves one node in just one iteration and requires 100 iterations for each of the other 99 nodes. Following the greedy approach, the resulting g9 Whenever > 0.01, G would be infeasible for our
schedule would be G ((h, 1)) since $
100
5

---

iterations
optimel schedule
Mg
modes
Figure 4: Illustration of a toy dataset and the greedy schedule: The data is shown on the left and the (optimal) schedule obtained by following the greedy algorithm is illustrated on the right.
constrained problem P's Since are not allowed add heuristic more than once, this cannot be
fixed with the current algorithm.
To avoid this situation, we propose the following modification. Instead of only considering the heuristics that are not in G5-1 when choosing the next action gj. we also consider the option to run the last heuristic 1 of Gj-1 for longer. That is, we allow to choose (h)-1,7) with Tj-1- Note that the cost of adding (?) to the schedule is not T, but T3-1, since we decide to run h for T--1 iterations longer and not rerun hy-1 for iterations.
Furthermore, when including different classes of heuristics in the schedule, the respective time measures are not necessarily comparable. We observed that not taking the difference of iteration cost into account led to an increase of the primal integral of up to 23% compared default SCIP. To circumvent this problem, we use the average time per iteration to normalize different notions of iterations. We denote the average cost of an iteration by fovg for heuristic h. Note that th be easily computed by tracking the running time of heuristic during data collection. Hence, redefine 9j and obtain
avg can
HN E N I S
9j argmax (b,T)EA;-1
c)-((h,
with Ag = (Hl x (
T T T and
( ( (T - Tz),
if + hj otherwise.
c)(h,
We set Ao = H x T and co (h, the G ((h, 100) (which solves all 100 nodes) in the above example.
T. With this modification, we obtain the schedule
Additionally, it is also possible to consider the quality of the found solutions when choosing the next action gソ- Since we observed that the resulting schedules increased the primal integral by up to 1 11%, omit this here.
Finally, note that this greedy procedure still does not explicitly enforce that the schedule successful at fraction of at least nodes. In our experiments, however, we observe that the resulting schedules reach a success rate of a 98% or above. The final algorithm can found in Appendix C
Example. Figure 4 shows an example of how we obtain schedule with three heuristics and nodes. As indicated by the left figure, the dataset is given by
D = [(hi, N1, 1), (bs, No, oo), (fn, N2, oo), (l2, Ni, 4), (l2,, N2, (hz,, No. 3), (lig, No), (Pis No. 4), (hg. N3. })}.
Let us now assume that all three heuristic have the same costs, i.e., (l,. the tby We build the schedule G as follows. First, add action (hı, 1), since h solves one node with only iteration, yielding the best ratio. Since Ni is "solved" by the current schedule and fı cannot solve any other nodes, both N1 and h do not need be considered anymore. Among the remaining possibilities, the action (/2,33 3) is the best, since h2 solves both nodes in three iterations yielding a ratio of 2. In contrast, executing ha for two and four iterations, respectively, yields a ratio of z. Hence, we add (h2,33 3) to G and obtain G = ((h1, 1), (h2,3), The schedule then solves all three nodes as shown on the right of Figure 4 Note that this schedule is an optimal solution of Ps for > 3.

---

5 Data Collection
The scheduling approach described thus far rests on the availability of dataset D. Among others, each entry in DD stores the number of iterations 7 required by heuristic h to find feasible solution at node N. This piece of information must be collected by executing the heuristic and observing its performance. Two main challenges arise in collecting such dataset for multiple heuristics:
1. Efficient data collection: the sophisticated techniques implemented in today's solvers. This poses difficulties to ML approaches that create a single reward signal per MIP evaluation, which may take several minutes up to hours. In other words, even with a handful of heuristics, i.e., a small set H. it is prohibitive to run B&B once for each heuristic-training instance pair in order to construct the dataset DD
Solving MIPs by B&B remains computationally expensive, even given
Obtaining unbiased data: Executing multiple heuristics at each node of the search tree during data collection can have dangerous side effects: if heuristic finds incumbent, subsequent heuristics are no longer executed at the same node, as described in Section 3
We address the first point by using a specially-crafted version of the MIP solver for collecting multiple reward signals for the execution of multiple heuristics per single MIP evaluation during the training phase. As result, we obtain a large amount of data points that scales with the running time of the MIP solves. This has the clear advantage that the efficiency of our data collection does not automatically decrease when the time to evaluate a single MIP increases for more challenging problems.
To prevent bias from mutual interaction of different heuristics during training, we engineered the MIP solver to be executed in a special shadow mode, where heuristics are called in a sandbox environment and interaction with the main solving path is maximally reduced. In particular, this means that new incumbents and primal bounds are not communicated back, but only recorded for training data. This setting is an improved version of the shadow mode introduced in Khalil et al. (017)).
As result of these measures, we have instrumented the SCIP solver in way that allows for the collection of a proper dataset 'D with a single run of the B&B algorithm per training instance.
Computational Results
The code we use for data collection and scheduling is publicly available
6.1 Heuristics and Instances
We can build a schedule containing arbitrary heuristics as long as there is a time measure available. We focus on two broad groups of complex heuristics: Diving and Large Neighborhood Search (LNS). Both classes are much more computationally expensive than simpler heuristics such rounding (for which scheduling is not necessary and executions are extremely fast), but are generally also more likely to find (good) solutions (Berthold. 2006). That is why it is particularly important to schedule these heuristics most economically.
Diving Heuristics. Diving heuristics examine a single probing path by successively fixing variables according a specific rule. There are multiple ways of controlling the duration of a dive. After careful consideration, we decided on using the maximum diving depth to limit the cost of call to diving heuristic: is both related the effort spent by the heuristic and its likelihood of success.
These heuristics first build a neighborhood of some reference point which is then searched for improving solutions by solving a sub-MIP. To control the duration, we choose to limit the number of nodes in the sub-MIP. The idea behind this measure is similar to limiting the diving depth of diving heuristics: In both cases, we control the number of subproblems heuristic considers within its execution. Nevertheless, the two measures are not directly comparable: The most expensive LNS heuristic was on average around 892 times more expensive than the cheapest diving heuristic.
LNS Heuristics.
To summarize, we schedule 16 primal heuristics: ten diving and six LNS heuristics. By controlling this set, we cover about 2 of the more complex heuristies implemented in SCIP. The remaining heuristics are executed after the schedule according to their default settings.

---

We focus on two problem classes which are challenging on the primal side: The Generalized Independent Set Problem (GISP) (Hochbaum and Pathria 1997; Colombi et al. (017) and the Fixed Charge Mullicommodiiy Network Flow Problem (FCMNF) (Hewitt et al. (01O). For GISP, we generate two types of instances: The first one takes graphs from the 1993 DIMACS Challange which is also used by Khalil et al.] (0017) and Colombii et al. (2017) (120 for training and testing) and the second type uses randomly generated graphs as a base (25 for training and 10 for testing). The latter is also used to obtain FCMNF instances (20 for training and 120 for testing). A detailed description
of the problems and how we generate and partition the instances can be found in Appendix D
6.2 Results
To study the performance of our approach, we used the state-of-the-art solver SCIP 7.0 (Gamrath et al. 2020) with CPLEX 12.10.0.0 as the underlying LP solver. Thereby, we needed to modify SCIP's source code to collect data as described in Section as well as control heuristic parameters that are not already implemented by default. For our experiments, we used a Linux cluster of Intel Xcon CPU E5-2660 v3 2.60GHz with 25MB cache and 128GB main memory. The time limit in all experiments was set to two hours; for data collection to four hours. Because the primal integral depends on time, we ran one process at a time every machine, allowing for accurate time measurements. Furthermore, since MIP solver performance can be highly sensitive to even small and seemingly performance- neutral perturbations during the solving process (Lodi and Tramontani] 2013), implemented an exhaustive testing framework that uses four random seeds and evaluates schedules trained with one data distribution other data distributions, a form of transfer learning.
The main baseline we compare against is default SCIP. Note that since the adaptive diving and LNS methods presented in Hendel (2018) and Hendel et al. (2018) are included in default SCIP as heuristics, we implicitly compare to these methods when comparing to default SCIP; improvements due to our method reflect improvements over Hendel's approach. Furthermore, we also consider SCIP_TUNED, a hand-tuned version of SCIP's default settings for GISP Since in practice, a MIP expert would try to manually optimize some parameters when dealing with homogeneous set of instances, we emulated that process to create an even stronger baseline to compare against.
GISP - Random graph instances. Table [ (rows DIVING) shows partial results of the transfer
learning experiments for schedules with diving heuristics (see 3'ableJin in Appendix [ for the complete table). Our scheduling framework yields significant improvement w.r.t. primal integral on all test sets. Since this improvement is consistent over all schedules and test sets, we are able to confirm that the behavior actually comes from our procedure. Especially remarkable is the fact that the schedules trained on smaller instances also perform well on much larger instances. Furthermore, we can see that the schedules perform especially well on instances of increasing difficulty (size). This behavior is intuitive: Since our method aims to improve the primal performance of a solver, there is more room for improvement when an instance is more challenging on the primal side. Over all test sets, the schedules terminated with a strictly better primal integral on 69 69-76% and with a strictly better primal bound on 59-70% of the instances compared to SCIP SCIP_TUNED TUNED (see Table 4 in Appendix [ for details). In addition, the number of incumbents found by the heuristics considered in the schedule increased significantly: 49-61% % of the incumbents were found by heuristics in the schedule, compared to only 33% when running with default SCIP (see Table in Appendix F for details).
Table I (rows DIVING+LNS) shows the transfer learning experiments for schedules containing diving and LNS heuristics. By including both types of heuristics, we are able to improve over the diving-only schedule in around half of the cases, since the instances we consider, diving seems to perform significantly better than LNS. Furthermore, we also observe less consistent performance among the schedules which leads to the conclusion that LNS's s behavior is harder predict. How to further improve our scheduling procedure to better fit LNS is part of future work.
HiSP-Findin a schedule with SMAC. As mentioned earlier, we can also find schedule by using the algorithm configuration tool SMAC. To test SMAC's performance on the random graph instances, we trained ten SMAC schedules, each with different random seed, on each of the five training sets. We used the primal integral as a performance metric. To make it easier for SMAC, we only considered diving heuristics. We gave SMAC the same total computational time for training we did in data collection: With 25 training instances per set using a four hour time limit each, this comes
We set the frequency offset to 0 for all diving heuristics.
8

---

schodule
[150,160]
[250,260]
[350,360]
[450,460]
[550,560]
Irain
0.89 0.23
0.87 + 0.37
0.87 0.28
0.78 +
0.65 d: 0.24
[150,160]
0.87
0.76 +
0.85 0.22
0.95
0.82 0.26
0:81
0.90 0.27
0.65
DIVING
0.89 = 0.28
0.81 + 0.34
0.92 2 0.23
0.81 = 0.24
0.66 2 0.20
[250.260]
DIVINGHINS
0.86 0.20
0.77 0.27
0.85 =: 0.20
0.85 1: 0.18
0.64 1 0.18
SMAC
0.87 2: 0.26
0.88 1: 0.42
0.87 0.25
0.83 1: 0.24
0.39 :: 0.22
DIVING
0.84 + 0:24
0.82 + 0.36
0.81 0:26
0.80 + 0.21
0.09 = 0:20
[350,360]
DIVINGAENS
0.86 + 0.27
0.85 + 0.29
0.94 + 0.31
0.99 + 0.28
0.66 + 0.23
SMAC
0.86 : 0.24
0.80 + 0.37
0.86 =: 0.25
0.80 + 0.24
0.68 = 0.18
DIVING
0.89 + 0.25
0.83 + 0.36
0.77 0.23
0.81 + 0.21
0.58 = 0.20
[450,460]
DIVINGLUNS
0.84
0.76 + 0.31
0.92 0.23
0.86 : 0.24
0.62 = 0.22
SMAC
0.93 4: 0.26
0.67 +: 0.32
0,90 0.19
0.85 + 0,25
0.69 0.23
0.88 + 0.26
+ 0.42
0.86 0.27
0.81 +
0.63 0.21
[550,560]
0.84 0.26
+
0.96 0.20
0.88
0.60 0.20
SMAC
0.87
0.31
0.92 0.29
0.84
0.58 0.21
SCIP TUNED
0.89 = 0.28
0.99
0:31
1.05 0.28
0.94 + 0.23
0.76 # 0.25
Table 1: Average relative primal integral (mean + std.) of schedule w.r.t default SCIP over GISP instances derived from random graphs. The first fifteen rows correspond to schedules trained on instances of size [L,U] with different methods: DIVING (greedy schedule with diving). DIVING+LNS (greedy schedules with diving and LNS) and SMAC (SMAC-traine schedules with diving).
to 100 hours per training set and schedule. Note that since SMAC runs sequentially, training the SMAC schedules took over four days per schedule, whereas training schedule following the greedy algorithm only took four hours with enough machines. To pick the best performing SMAC schedule for each training set, we ran all ten schedules on the test set of same size as the corresponding training set and chose the best performing one.
The results can be found in Table I (rows SMAC). As we can see, on all test sets, all schedules are significantly better than default SCIP. However, when comparing these results to the performance of the greedy schedules, the SMAC schedules terminated with a strictly better primal integral on 36-54% and with a strictly better primal bound on 37-55% of the instances compared to its greedy counterparts.
can see that SMAC performs worse average. Over all five test sets,
GISP DIMACS graph instances. The first three columns of Table summarize the results on the instances derived from DIMACS graphs. As we can see, the schedule setting dominates default SCIP in all metrics, but an especially drastic improvement can be obtained w.r.t. the primal integral: the schedule reduces the primal integral by 49%. Furthermore, 92% of instances terminated with strictly better primal integral and 57% with strictly better primal bound. Even though SCIP SCIP_TUNT TUNED finds the best incumbent faster than the schedule, the latter terminates with better primal bound (GISP is a maximization problem) explaining the small increase in time. When looking at the total time spent in heuristics, see that heuristics run significantly shorter but with more success: On average, the incumbent success rate is higher compared to default SCIP. That the learned schedule not only improves the primal side of the problem, but also translates to overall better performance is shown by the last two rows: SCHEDULE significantly dominates DEFAULT in the gap at termination as well as the primal-dual integral.
Compared to the results of the method in Khalil et al. (2017), where node features were used to decide if a heuristic should be executed, our scheduling procedure yields competitive performance: On average, their method reduced both the primal integral and the time to best incumbent by 60% (our method: 49% and 47%). Hereby it is important note that our baseline (SCIP 7.0) is much faster than theirs (SCIP 3.2): for DIMACS instances, default SCIP terminated with a gap of 201.95% in Khalil et al. (2017) compared to 144.59% in experiments. Furthermore, SCIP's ss technical reports show that version 7.0 58% faster than version 3.2 on a standard benchmark test set.
FCMNE. The last three columns of Table 2 summarize the results on the FCMNF instances. Also for this problem, we can see that the schedule setting dominates both DEFAULT and SCIP _CI__TUNED in almost all metrics. In particular, we are able to almost double the number of solutions found and triple the incumbent success rate. Even though the improvement in the primal integral is not as drastic as observed with GISP, it is still consistent over the whole test set: 62% of the instances

---

GISP
FOMNE
DEFAULT
SCIP TUNED
SCHEDULE
DEFAULT
SCIP TUNED
SCHEDULE
Prinal Integral
934,48
555.75
270.33
618.52
564.07
Time first Incumbent
1.33
34.89
34.08
36
Time best Incumbent
4266.68
2642.46
2803.78
2973.66
3043.66
5782.45
fncumbent
2382.03
2404.63
1242839
1227125
1231969
Tocal houristic cuils*
138.57
137.38
140.03
15.08
18.83
23.58
Total heuristic time*
258.88
306.96
190.00
1681.39
1620.02
142233
Number of Incumbents found
2.72
3.08
3:33
0.14
0.25
0.23
Incumbent Success Rase*
0.01
0.02
0.02
0.01
0.03
0.02
Gip
144.99
144.03
141.70
9.64
8.19
7.85
Primal dual Integral
450148.72
425321.67
430882.04
107894.01
107381.6
102855.88
Table 2: Summary of results on GISP instances derived from DIMACS graphs and for FCMNF instances (with schedules of diving heuristics). Values shown are aggregates over instances; geometric means are used. Statistics with refer only to the heuristics used in the schedule.
terminated with a strictly better primal integral and 92% with a strietly better primal bound. Similar to the GISP results, SCHEDULE needs more time than DEFAULT to find the best incumbent, since it again terminates with a better primal bound (FCMNF is a minimization problem).
Finally, it is important to note that the trained schedules differ significantly from SCIP's default settings for all training sets. The improvements we observed when using these schedules supports our starting hypothesis, namely that the way default MIP solver parameters are set does not yield the best performance when considering specific use cases.
7 Conclusion and Discussion
In this work, propose data-driven framework for scheduling primal heuristics in MIP solver such that the primal performance is optimized. Central to our approach is a novel formulation the learning task scheduling problem, efficient data collection procedure, and a fast, effective heuristic for solving the learning problem on a training dataset. A comprehensive experimental evaluation shows that our approach consistently learns heuristic schedules with better primal per- formance than SCIP's default settings. Furthermore, by replacing our heuristic algorithm with the algorithm configuration tool SMAC in scheduling framework, but still significant performance improvement w.r.t. SCIP's default. Together with the prohibitive computational costs of SMAC, we conclude that for our heuristic scheduling problem, the proposed heuristic algorithm constitutes an efficient alternative to existing methods.
are able to obtain worse
A possible limitation of our approach is that it produces single, man--siz-ffitsalll schedule for a class of training instances. is thus natural to wonder whether alternative formulations of the learning problem leveraging additional contextual data about input MIP instance and/or a heuristic can be useful. We note that learning a mapping from the space of MIP instances to the space of possible schedules is not trivial. The latter is highly structured output space that involves both the permutation over heuristics and their respective iteration limits. The approach proposed here much simpler in nature, which makes it easy implement and incorporate into a sophisticated MIP solver.
Although we have framed the heuristic scheduling problem ML terms, we are yet to analyze the thheori- aspects of the problem. More specifically, our approach is justified on empirical grounds in Section but we are yet to attempt to analyze potential generalization guarantees. We view the recent foundational results by Balcan et al. (2019) a promising framework that may apply to our setting, as has been used for the branching problem MIP (Balcan et al. 2018).
Disclosure of Funding
This work was partially funded by the Deutsche Forschungsgemeinnchaat (DFG) under Germany's Excellence Strategy - The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689), and by the German Federal Ministry of Education and Research (BMBF) within the Research Campus MODAL (grant numbers 05M14ZAM, 05M20ZBM). Elias B. Khalil acknowledges support from the Scale AI Research Chair Program and an IVADO Postdoctoral Scholarship.
10

---

References
Balcan, M.-F., DeBlasio, D., Dick, T., Kingsford, C., Sandholm, T., and Vitercik, E. (2019). How much data is sufficient to learn high-performing algorithms? arXiv preprint: 1908.02894.
Balcan, M.-F., Dick, T., Sandholm, T., and Vitercik, E. (2018). Learning to branch. In International conference on machine learning, pages 344-355 -533. PMLR.
Baltean-Lugojan, R., Bonami, P., Misener, R., and Tramontani, A. (2019). Scoring positive semidefinite cutting planes for quadratic optimization via trained neural networks, preprint: http: www. optimi ami zation online. org/ DB_ HTML/ 2018/ 11/ 6943. html
Berthold. T. (2006). Primal heuristics for mixed integer programs. Master's thesis, Technische Universität Berlin.
Berthold, T. (2013a). Measuring the impact of primal heuristics. Operations Research Letters, 4166):611-614
Berthold, T. (2013b). Primal MINLP heuristics in a nutshell. In International Conference on Operations Research.
Berthold, T. (2018). A computational study of primal heuristics inside MI(NL)P solver. Journal of Global Optimization, 70:189-206.
Colombi, M., Mansini, R., and Savelsbergh, M. (2017). The generalized independent set problem: Polyhedral analysis and solution approaches. European Journal of Operational Research, 260:41-
55.
Gamrath, G., Anderson, D., Bestuzheva, K., Chen, W.-K., Eifler, L., Gasse, M., Gemander, P., Gleixner, A., Gottwald, L., Halbig, K., Hendel, G., Hojny, C., Koch, T., Bodic, P. L., Maher, S. J., Matter, F., Miltenberger, M., Mühmer, E., Müller, B., Pfetsch, M., Schlösser, F., Serrano, F,, Shinano, Y., Tawfik, C., Vigerske, S., Wegscheider, F., Weninger, D., and Witzig, J. (2020). The SCIP Optimization Suite 7.0. ZIB-Report 20- 10, Zuse Institute Berlin.
Gasse, M., Chételat, D., Ferroni, N., Charlin, L., and Lodi, A. (2019). Exact combinatorial opti- mization with graph convolutional neural networks. In 33rd Conference Neural Information Processing Systems (NeurIPS).
He, H., III, H. D., and Eisner, M. (2014). Learning to search in branch and bound algorithms. In Advances in Neural Information Processing Systems, volume 27, pages 3293-3301.
Hendel, G. (2018). Adaptive large neighborhood search for mixed integer programming, preprint: https: // opus4. kobv. de/ opus4 zib/ frontdorrrooorr///oo indem/ indem/ docId/ 7116
Hendel, G., Miltenberger, M., and Witzig. J. 2). Adaptive algorithmic behavior for solving mixed integer programs using bandit algorithms. In International Conference on Operations Research.
Hewitt, M., Nemhauser, G., and Savelsbergh, M. (2010). Combining exact and heuristic approaches for the capacitated fixed-charge network flow problem. INFORMS Journal Computing, 22:31 325.
Hochbaum, D. and Pathria, (1997). Forest harvesting and minimum cuts: A new approach to handling spatial constraints. Forest Science, 43:544-554.
Hoos, H., Kaminski, R., Lindauer, M., and Schaub, T. (2014). aspeed: Solver scheduling via answer set programming. Theory and Practice of Logic Programming. 15:117-142.
Hutter, F., Hoos, H., Leyton-Brown, K., and Stützle, T. (2009). Paramils: An automatic algorithm
configuration framework. Journal of Artificial Intelligence Research (JAIR), 36:267-306.
Hutter, F., Hoos, H. H., and Leyton-Brown Brown, K. (2011). Sequential model-based optimization for general algorithm configuration. In Learning and Intelligent Optimization, pages 507-523.
Kadioglu, S., Malitsky, Y., Sabharwal, A., Samulowitz, H., and Sellmann, M. (2011). Algorithm selection and scheduling. In International Conference on Principles and Practice of Constraint Programming, pages 454-469.

---

Khalil, E. B., Bodic, P. L., Song, L., Nemhauser, G., and Dilkina, B. (2016). Learning to branch in mixed integer programming. In Proceedings of the 30th AAAI Conference on Artificial Intelligence.
Khalil, E. B., Dilkina, B., Nemhauser, G., Ahmed, S., and Shao, (2017). Learning to run heuristics in tree search. In 26th International Joint Conference Arlificial Intelligence (IJCAI), pages 659-666.
Kruber, M., Lübbecke, M., and Parmentier, A. (2017). Learning when to use a decomposition. In International Conference on Al and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, pages 202-210.
Lodi, A. (2013). The heuristic (dark) side of MIP solvers. Hybrid Metaheuristics, 434:273-284.
Lodi, A. and Tramontani, A. (2013). Performance variability in mixed-intepeee programming, Tutorials in Operations Research, 10:1-12.
Munagala, K., Babu, S., Motwani, R., and Widom, (2005). The pipelined set cover problem. In International Conference Database Theory, volume 3363, pages 83-98.
Nair, V., Bartunov, S., Gimeno, F., von Glehn, I,, Lichocki, P., Lobov, I,, O'Donoghue, B., Sonnerat, N., Tjandraatmadja, C., Wang, P., Addanki, R., Hapuarachchi, T., Keck, T., Keeling, J., Kohli, P., Ktena, I., Li, Y., Vinyals, O., and Zwols, Y. (2020). Solving mixed integer programs using neural networks. arXiv preprint: 1012.13349
Seipp, J., Sievers, S., Helmert, M., and Hutter, F. (2015). Automatic configuration of sequential planning portfolios. 29th AAAI Conference on Artificial Intelligence, pages 3364-33 3370..
Streeter, M. (2007). Using Online Algorithms to Solve NP-Hard Problems More Efficiently Practice. PhD thesis, Carnegie Mellon University.
12


Reviews:
[{"review_id": "ekZ91sLDPZ", "reviewer": "Reviewer_8aHm", "summary": "The paper proposes a method to learn a heuristic schedule in branch and bound solvers, e.g. for mixed integer programming.\nBy learning from collected data an efficient heuristic can be selected more efficiently than from hand-crafted expert rules, so the claim.\nExperimental results show that the proposed method is indeed effective and improves the average primal integral.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The work is well-motivated and clearly explained.\nWhat I personally like is the approach to data collection by executing multiple heuristics at the same time to gather more information in a single run of the optimizer.\nThe trained model is then embedded in the solver at test time to propose a heuristic schedule.\nWhile this area has drawn some attention, the related work section of this paper is relatively small but also highly focused on one small subarea of the field, which is okay.\n\nWhat I find a bit particular is the selection of experimental problems, which appear to not be very common problems (as far as I know). I'm wondering why especially these problems were selected and why not more prominent problems were chosen to make comparisons among the literature easier.\n\nThe evaluation focuses on the primal integral were strong reductions are possible, but which is not the most interesting metric for potential users, although otherwise a good performance indicator.\nThe shown reduction however also translates to improved solving times, although the tuned SCIP still is close or outperforms on the time to best incumbent. For FCMNF even the default configuration has the best performance for time to best incumbent, which is surprising. Is there an intuition why this is the case?\n\nFinally, how does the method generalize? Can collected information from one problem be transferred to other problems or is it strictly necessary to collect a new dataset each time?\n\nIn general, I think this is solid work and the integration of ML into exact (branch-and-bound) solvers is of high interest, but I'm not entirely convinced that we are there yet to actually make strong improvements over the large body of experience and knowledge in solver design and tuning.\nNevertheless, I do not see a strong reason why this paper should not be accepted and contribute to the body of work leading to stronger solvers.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations and societal impact are sufficiently addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "dyyowqcKf2", "reviewer": "Reviewer_Nehp", "summary": "The authors propose a data-driven approach for learning the optimal scheduling heuristics to solve the MILP problems. They formalize the scheduling problem mathematically and suggest an efficient data collection strategy. In experiments, they show the advantage of their algorithms by comparing them with state-of-the-art models over several different datasets.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors propose a data-driven approach for learning the optimal scheduling heuristics to solve the MILP problems. They formalize the scheduling problem mathematically and suggest an efficient data collection strategy. In experiments, they show the advantage of their algorithms by comparing them with state-of-the-art models over several different datasets.\n\nStrengths:\n\nThe authors propose an interesting and important perspective for solving the MILP problems. They observe that having a better solution early on would lead to faster minimization of the primal gap. Most  MILP problems require a large amount of time for tuning the scheduling parameters. As a consequence, they suggest that that the scheduling of MILP can be formalized into a machine learning problem. \n\nPoints of improvement:\n\n-\ttable 1 mainly shows that the proposed algorithm guides the heuristics in an early timestep, so the primal integral value can be improved. I’m curious about the effect of reducing the whole time for solving MILP solvers. In table 2, the authors present some numbers regarding the “time to first incumbent” and “time to best incumbent”. I’m looking forward to a more detailed table/figure about that.\n\n-\tEven though the author claims that the algorithm is not tied to the single solver. We would like to see if they can run a few more experiments on some other solvers to justify this claim.\n\n-\tLine 338 needs to be deleted. Some references are not correct, for example, in line 24, line 78 and etc.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. The authors adequately addressed the limitations and potential negative societal impact of their work", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "chTCrJ2aQLU", "reviewer": "Reviewer_D5iZ", "summary": "**The problem:** This paper studies a machine learning approach to scheduling primal heuristics in branch-and-bound. Primal heuristics are used throughout the branch-and-bound tree to find feasible solutions to the integer program. These feasible solutions help speed up the time it takes branch-and-bound to find the optimal solution. There are a few challenges that arise when using heuristics. First, there are many different heuristics one could employ with varying performance across application domains. Second, there is an inherent time-utility tradeoff: the more time you allocate to a heuristic, the more likely it is that it will find a new incumbent solution, but branch-and-bound’s total runtime may increase. Given a set of heuristics $H$, this paper uses a training set of integer programs from the particular application domain at hand to learn a schedule $\\langle(h_1, t_1), …, (h_k, t_k)\\rangle$ of heuristics $h_i \\in H$ and budgets $t_i > 0$ such that at each node, branch-and-bound will run each heuristic hi in the schedule in order, allocating ti iterations to the heuristic.\n\n**The approach:** First, we describe the data collection process. We begin with a set of integer programs from the application domain at hand. Then, while solving each integer program, at each node $N$, we see for each heuristic $h \\in H$ how many iterations $t$ it takes to find a feasible solution. The training set consists of all such tuples $(N, h, t)$. The authors show that finding the optimal schedule over the training set can be formulated as a mixed-integer quadratic program, but solving it is not generally tractable. Therefore they propose a greedy heuristic algorithm, which at each step (essentially) adds the heuristic-budget pair $(h, t)$ that maximizes the marginal increase in the number of instances solved divided by $t$ (which is the cost of including $(h, t)$ in the schedule). (Their approach is a bit more nuanced than this, but this is the high-level idea.)\n\nThe results: The primary metric that the authors optimize is the “primal integral,” which can be interpreted as a normalized average of the incumbent value over time. We want to find a good incumbent as quickly as possible, so we want the primal integral to be small. They provide experiments for two different classes of integer programs and show that their approach generally improves over a few baselines including default SCIP, a carefully tuned implementation of SCIP, and schedules optimized using SMAC [Hutter et al., LION’11].", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I thought that this paper’s approach to learning heuristic schedules was insightful and well thought-out; I appreciated the example illustrating why Streeter’s greedy algorithm would not work out-of-the-box. I also appreciated the paper’s scalable approach to data collection, since this is a big challenge in research on machine learning for integer programming. Moreover, I thought that the paper was written well overall, though I have a few writing suggestions later in this review.\n\nIn the experiments section, I would have appreciated a bit more clarity on how the results ultimately translate to branch-and-bound’s overall performance. In Table 2, it seems like if the total number of heuristic calls is less than the baselines and the total time spent on heuristics is also less, then B&B should run faster overall, but it would be helpful if the authors could verify this and connect those dots.\n\nI’d also be interested in some discussion of whether it would be possible to implement these ideas using CPLEX callback functions, for example, or if there are some big hurdles to doing so. Improving SCIP itself seems quite worthwhile, but I suppose that an integration with CPLEX or Gurobi would be more practically relevant.\n\nIn terms of writing, I have some detailed comments below, but a higher-level comment is that a fair amount of space was devoted to the MIQP formulation of the problem, but I’m not sure if it was worth the space since it’s not the path the authors end up pursuing. It helped motivate the example in lines 187-192, but maybe the example can be motivated even without the MIQP formulation.\n\nDetailed Comments:\n\n- Line 143: I prefer “scalable” over “computationally efficient”, since you do still have to run B&B, so I’m not sure that data collection can actually be considered computationally efficient.\n- Line 195: There seems to be a noun missing from the sentence “That is, we allow…”\n- Lines 193-197: With this notation, shouldn’t $h_{j-1}$ be $g_{j-1}$? The same comment holds for line 205.\n- Line 200: “lead” -> “led”\n- Line 297: “heurisitcs” -> “heuristics”\n- Lines 307-308: I see what the authors means when they say that only scheduling diving heuristics makes it easier for SMAC to terminate, but does this also make it harder for SMAC to compete?\n- Lines 329-333: Ideally, it would be awesome to run Khalil et al.’s approach on SCIP 7.0 in order to compare it to this paper’s approach.\n- Lines 334-336: These lines say that “the schedule setting dominates both default SCIP and SCIP_TUNED in all metrics,” but in the third row, don’t these two baselines dominate?\n- Table 2: I was a bit confused at first by the “best incumbent row” --- is the GSIP objective maximization and the FCMNF objective minimization? If so, it would be helpful to clarify. Also, why isn’t anything highlighted in rows 4 and 5?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I appreciated the discussion of limitations in the final section.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "YKu0t-VExJt", "reviewer": "Reviewer_JnKT", "summary": "The paper studies the scheduling of multiple heuristics inside of a mixed-integer programming solver. The authors formulate the learning problem exactly, and then present a heuristic method with greater scalability. They then present computational results validating the efficacy of their approach.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written. It builds off papers from the literature, but makes its case for its originality. The significance of the work is bolstered by the computational results. However, I have a concern about the baseline used for comparison. More fundamentally, I am not sure that the result paper matches exactly with its stated goal.\n\n* P1: Good primal solutions are important for another reason: they can help reduce search tree size, which can lead to faster convergence when proving optimality.\n* P2: What is the \"success rate\"? Can the authors provide a reference and/or a brief description?\n* L73: The description of how the authors go from node to UUID in such a way that this is meaningful across instances is very vague, and I would imagine that this is actually very important from a practical perspective. How does this work for problem instances with varying number of variables? Is it robust to shuffling variable indices? Etc.\n* L135: Weighing uniformly across all nodes seems like it may be suboptimal. Intuitively, I would imagine that weighing nodes near the top of the tree (e.g. the root) over ones deeper in the tree would lead to better schedules inside a MIP solver. Have the authors considered this?\n* L161: Point 1 is, frankly, not true without softening or qualification. A cheeky \"counterexample\" would be to point out that each MIP can trivially be transformed into a decision problem (constrain the objective function to be equal to the optimal cost). Additionally, many solvers for decision problems (e.g. SAT) are also tree-based, with multiple opportunities to run heuristics on different subproblems.\n* L194: Why only consider the last heuristic, rather than all preceding heuristics?\n* L297: \"heurisitcs\"\n* The usage of SCIP with default settings is a bit of a strawman. The solver are configured to prove optimality quickly, while the authors only are concerned with primal solutions. As such, SCIP will spend significant times improving the dual bound through cuts, presolve, etc, which renders wall time comparisons unfair. A more fair comparison would configure the solver to focus on the primal bound, using the \"emphasis\" parameter.\n* The previous comment dovetails into my fundamental concern about the framing of the paper. The authors present the work as a method for improving primal heuristics inside a MIP solver, but the contributions are instead framed more as a metaheuristic for producing primal solutions for MIPs. The latter is a fine goal, but fundamentally different from the former, as a MIP solver by default will spend considerable time and effort on the dual bound. To argue for the former, the authors should really present comparisons on the primal-dual gap integral, which take into account the significant effort SCIP spends on the dual side.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: In combinatorial optimization, the design and selection of branching heuristics play a key role. Such heuristics are often carefully hand crafted and their performance is very much dependent  on the particular instances. In fact, the time performance of branching heuristics can vary exponentially  from instance to instance.  The paper proposes a data driven approach for learning  heuristic schedules  for exact  (i.e., with optimality guarantees) Mixed Integer Programming. They formulate the scheduling problem and propose an efficient data collection strategy. The schedule is problem/instance dependent and results show significant improvement with respect to the primal gap, a key measure used in exact MIPs. There was consensus about this paper and the reviewers carefully consider the authors' feedback.
Decision: Accept (Poster)