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 is 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 Strreter (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 S
= 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) with Tj-1- Note that the cost of adding (h) 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, (lz,, No. 3), (ly. No), (Pis No. 4), (hg. N3. })}.
Let us now assume that all three heuristic have the same costs, i.e., (l,. the tbg 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., 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": "gHmNDJNIQCA", "reviewer": "Reviewer_zjih", "summary": "The paper focuses on scheduling primal heuristics in an exact MIP solver to find feasible and fast solutions rather than finding the expensive global optimal. An exact MIP solver has a variety of primal heuristics implemented during the branch-and-bound algorithm. This paper aims to propose a data-driven and generic approach to improve the primal heuristics scheduling in the B&B algorithm. They formalized the problem as an MIP, and the goal here is to find the order of the heuristics and their iterations. Paper proposes a greedy heuristic inspired by Streeter’s algorithm to compute different parameter configurations. It is claimed that the heuristic is constructed by learning from data about the duration and success of two kinds of heuristics that call for two sets of training instances. In the data collection phase, the objective is to collect the heuristics performances on each node of the search tree. For this purpose, they used strategies that will result in running just one B&B execution for each instance. It is asserted that authors have solutions at a less expensive cost in comparison to the baseline SCIP and SMAC in terms of primal integral. Based on results the average primal integral is reduced by up to 49% on two classes of instances.", "questions": "", "limitations": "", "rating": 4, "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": "1. The problem statement is interesting, but the contributions made do not seem much strong. This is because the heuristic they are proposing is very simple, and the methodology authors have implemented is a variation of Streeter’s approach, so I don’t see significant contributions in the scientific area.\n2. The structure of the paper looks good, but it is better to have a more in-depth literature review in the related works section.\n3. The approach is asserted to be data-driven, but I don't think it is because no explanation exists about instance structures or features in order to create a data-driven approach. Also, authors are just using a homogeneous set of instances which means not many diversities exist in the set of problems.\n4. The result can be hard to reproduce and this is because of:\n    - The randomly generated instances in which there is no explanation in the paper.\n    - Not enough information about the cross-validation method is mentioned for line 278.\n    - Among that large number of used instances, 121 instances are available.\n5. In Line 154, authors mentioned a fact without any reference. I mean it’s mentioned that “the SMAC schedule can get very expensive quickly”, but how we can find information about this fact without any reference.\n6. In line 170, it is mentioned that \"we allow every heuristic to be included in the schedule at most once\", and this seems that the approach is simplified version of Streeter's and it defines fixed parameters for scheduling.\n7. The shadow mode and the sandbox environment used in the data collection phase do not seem to be real data. This can be because in practice no sandbox environment will be used, and in the shadow mode, the state of the current heuristic can have an impact on the next heuristic.\n8. In line 277, they claimed they have implemented “a more exhaustive testing framework than the commonly used benchmark methodology”. The reader does not know what is the commonly used benchmark methodology without any references.\n9. In the result section, in line 296, they have talked about the dominance of their approach in “the number of incumbents found by the heuristics” in comparison to SCIP, and I wish I could see the exact difference as a table in appendices.\n10. For tables, it is preferred to have statistical plots to show the comparisons more clearly. \n11. Comparing SMAC with the greedy approaches results in table 1, the average of primal integral for greedy schedules is dominating the SMAC in just 11 out of 25 cases, and this is not much significant improvement.\n12. For table 2, it is recommended to include SMAC results in order to compare the other performance metrics. \n13. Line 312, what does enough machines mean here? This can make the evaluation biased. \n\t\nMinor comments:\n    1. In the introduction section, (line 22) they mentioned “classical ML techniques” in the literature, but in the cited papers I found some neural network related papers and I guess are they are not using classical machine learning. So, the term “classical” should be removed.\n    2. The y-axis of the left plot in Figure 3 is mentioned to be “in percent”, but it’s not. So “in percent” term should be removed.\n    3. Every single table and plot should be self-explained, but in Table 1 the number of instance headers is not mentioned which makes the table hard to understand.\n    4. In line 142, one extra closing parenthesis in the mathematical description.\n    5. For the formulation in lines 204 and 205, I couldn’t find any definition of “c” variable in the text, and I guess it’s cost. Also, the same happened for “A” variable.\n    6. In line 248, “It is both related to the effort spent by the heuristic and its likelihood of success.”, they have talked about just one work limit, not two.\n    7. Typos:\n        ◦ line 275, 291 and 350, typo in “Furtheremore”\n        ◦ line 286 “partitial”\n        ◦ line 297 “heurisitcs”\n        ◦ line 323 “stricly”\n        ◦ line 337 “improvment”", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "16"}, "extra_text": {}}, {"review_id": "YJs7jdsrx29", "reviewer": "Reviewer_UfX4", "summary": "Modern MIP solvers run multiple heuristics throughout its branch-and-bound tree using a fixed order. This paper introduces the problem of learning a schedule of heuristics, that is, the order and computational effort spent by each heuristic, with the goal of reducing the solving time of a MIP solver given a distribution of instances to train on. The learning task is formalized as a Mixed-Integer Quadratic Program but solved with a greedy heuristic. The paper also discusses an efficient approach to collect training data. Computational experiments are done on the Generalized Independent Set Problem and the Fixed Charge Multicommodity Network Flow Problem, using only diving and LNS heuristics, and they show that this learning method significantly improves upon SCIP with tuned hyperparameters, and produces similar or slightly better results than a schedule produced by the hyperparameter tuning tool SMAC.", "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": "This is overall a very good paper that I believe advances the state-of-the-art in learning for MIP solvers, an important area to enable us to better solve discrete optimization problems. The idea of learning the schedule of heuristics is interesting and novel as far as I am aware. Both the proposed learning task and the greedy learning method are simple and clean, which is appropriate for the scope of this paper, and it opens the door for future exploration of more sophisticated methods. The paper is overall well-written and does a good job at relating it to previous work. I particularly like the example plots that help the reader understand the context.\n\nThe computational setup is sound and adopts good practices for MIP computational research, such as using a tuned version of the MIP solver as a baseline and random seeds to account for inherent MIP solver variability. They also do a fair amount of cross-validation for the random graph instances. The final computational results show that this approach works well overall. They are not particularly striking especially compared to SMAC, but still represent significant improvements in the context of MIP solvers. Perhaps one aspect that feels missing from the paper are ablation experiments that could give us more insight on which components of this approach are important (e.g. does the ordering matter more than number of iterations?), but I believe this paper is good enough for NeurIPS without them, although there is one ablation experiment below in particular that I would like to suggest.\n\nOverall I recommend this paper for acceptance, though I have a few requests:\n\n1. In Section 3, the paper says: \"The loop is terminated if a heuristic finds a new incumbent solution.\" This is used to explain that a good ordering can reduce solve time. However, in the function SCIPprimalHeuristics in solve.c in SCIP 7.0.1, I see that the heuristics are interrupted only if a feasible solution that cuts off the current node is found, otherwise it seems to continue. Please correct me if I an incorrect, but if this is the case, then the statement above would not be correct and overstate the value of choosing a good ordering. It is still valuable because you want to be able to cut off nodes early (which could happen fairly often, not just at infeasible nodes but also when finding a feasible solution that meets the local dual bound), but otherwise if you have a node where no heuristic is able to do that, then does the ordering really matter? Or is the benefit here solely to be able to cut off nodes with primal heuristics? In any case, I would like to ask the authors to double-check whether the statement about heuristics cited above is correct. If not, this should be corrected and clarified in the paper. It is fine if a better ordering is meant to produce earlier node cut offs, but this should be clear in the paper.\n\n2. The notion of using the number of iterations needed to find any feasible solution instead of an incumbent or high-quality solution is counter-intuitive to me. I would be interested in a clarifying discussion on this in the paper. There are a few situations where I would expect considering the quality of the solution important, such as the case where feasibility is easy (i.e. when most heuristics should find a feasible solution early) and the case with improvement heuristics where a starting feasible solution is given. For example, for GISP, a schedule where a trivial heuristic that sets all variables to zero is the first one is always an optimal schedule. This does not happen in your case because you use diving and LNS heuristics, but I suspect that your approach is not robust to this type of behavior. I imagine that the dependency on the node is relevant here (e.g. the incumbent solution passed to the improvement heuristic might not be feasible for a particular node), but I could use some clarification as to why the cases above are not problematic. Could you add a discussion on this to the paper, and if possible, an ablation experiment in the appendix showing your attempt at rewarding for improving incumbents? In addition (and this is only out of curiosity, not a request), have you tried making your reward dependent on the quality of the feasible solution (and/or node cut off) rather than it just improving the incumbent?\n\n3. Section 5 appears to be too vague. What is the special version of the MIP solver that collects multiple reward signals? How is the shadow mode improved from previous work? It is fine if the discussion is done in the appendix, but the description of how these challenges were overcome needs to be complete.\n\n\nWriting notes:\n\n- Many citations throughout the text are supposed to be parenthetical citations but are not.\n- Section 2: It is worth to briefly define \"incumbent\" and its distinction to \"feasible solution\", since that is important later in the paper.\n- Section 3: I suggest briefly mentioning here that the average iteration cost can be taken into account as described in Section 4, since this is an immediate concern that one might have when reading this section.\n\n\nTypos:\n\n- Line 143: Missing period before \"Section 5\".\n- Line 275: \"Furtheremore\".\n- Line 291: \"Furtheremore\".\n- Line 323: \"stricly\".\n- Line 337: \"improvment\".\n- Table 2 caption: \"Statictics\"\n- Formulation in Appendix B.4: In constraint (9), there is an extra \")\" and extra space before $\\mathcal{H}$. In constraint (12), $s_n$ should be $s_N$.\n- Line 564 (Appendix): \"unifromly\".\n- Line 567 (Appendix): \"insatnces\".", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Societal impact was not discussed, but this is not particularly relevant.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "VYHXeCI4aT", "reviewer": "Reviewer_QJyG", "summary": "Branch-and-bound (B&B) algorithms systematically enumerate all solutions of a combinatorial optimization problem. In order to prune the enumeration tree early, these algorithms periodically solve problem relaxations and execute problem heuristics, thus generating upper and lower bounds on the value of an optimum solution. Usually, the better the bounds are, the smaller the enumeration tree is.\n\nIn general, we have at our disposal several heuristics that may be run at certain re-occuring points during the excecution of the B&B algorithm. Each heuristic may be run for a given number of iterations, with more iterations increasing the chance of successfully improving the bound at the expense of computation time. Classically, a B&B algorithm would include simple fixed decision rules that govern the execution of the heuristics. It is, however, understood that a more sophisticated decision framework potentially improves the overall running time of the algorithm. \n\nHence, the authors wish to learn when -- and for how many iterations -- best to execute the problem heuristics in the case that the B&B is used to solve a mixed-integer linear program (MILP). To that aim, they:\n\n1. derive a formal model for the heuristic scheduling problem, \n2. formulate a learning problem as a mixed-integer quadratic program (MIQP), \n3. propose a heuristic greedy heuristic for the learning problem (the MIQP is too difficult to solve exactly)\n4. propose a scheme to effiently collect training data from B&B runs (B&B runs are very expensive)\n5. seem to use the training data and the training problem to derive a fixed schedule (see comments below) that schedules the heuristics based on the index of a node in the enumeration (B&B) tree", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper certainly covers an interesting and potentially high-impact topic, as having fewer parameters to optimize is something that every MILP expert is very happy about. It is clearly geared towards applications with little theoretical contribution. The general idea -- learning parameters for MILP solvers -- has been seen before, but a successful execution seems to be difficult so far. This is because -- in my experience -- (a) even the B&B trees of near identical instances of the same problem may bear little to no ressemblence and (b) decisions that are superb in one B&B tree may prove disastrous in another seemingly very similar B&B tree. Hence, to me a big challenge seems to be to derive meaningful features from a B&B tree that generalize well.\n\nHaving said that, the feature used for generalization here seems to be the index of a node in the B&B tree. Aside for the general experiments which seem to largely favor the author's approach, there is no argument why this measure should be a good feature for distinguishing B&B nodes with different characteristics. In my view, the index is a measure of how far into the procedure a node was processed and the important question is whether a good choice of heuristics is merely a function of this progress. The answer could also depend on the traversal strategy, since for BFS traversal, the node index corrolates to the depth of the node in the tree, whereas it could correspond to any random position in the tree for best-first or DFS traversals. \n\nI am not entirely sure if I have understood correctly how the generalization works and I would like the authors' opinion on the above concern.  If my reasoning is correct, however, I would propose the following two ways to provide strong indications of the quality of a good generalization:\n\n- Could you check how your proposed schedule performs against pure random schedule? \n\n- Generally, we cannot expect to understand learned models due to their complexity. In this particular case, however, the learned schedule should be interpretable. In fact, what does a schedule produced by your algorithm look like? Do we see trends like \n + a preference for certain heuristics in early or late nodes of the tree,\n + a progress over a (largely) contiguous sequence of heuristics over time,\n + the number of iterations being proportional to the node index,\n + a corrolation of heuristics and the number of iterations (i.e., if the same heuristic appears twice in the schedule, does it have a similar number of iterations?)\n + ...\n \n Further researching this point could also become a strong point of this work since it would enable us to understand when and maybe why certain heuristics should be used. \n \n I feel those two points would be reasonable sanity checks of the approach.\n ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I feel an argument why the selected features will lead to a good generalization is missing.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "66X15sB_w5q", "reviewer": "Reviewer_Ad3G", "summary": "This paper considers integrating data driven approaches into the design of mixed integer programming (MIP) solvers.  In particular, the problem of scheduling primal heuristics is the main focus.  A MIP solver may use various primal heuristics - efficient techniques for generating feasible integer solutions - at various nodes of the branch and bound tree.  Generating good feasible solutions can speed up the solution process and some primal heuristics may work better for certain classes of problems than others.  Thus it makes sense to use data driven/learning approaches to tailor the choice of primal heuristics to run.\n\nThis paper proposes a learning approach to generating a fixed heuristic schedule (i.e. the learned schedule does not depend on the current instance being solved by the MIP solver).  The schedule must specify the order to run the heuristics and (roughly) how long to run each.  Finding the learned schedule is formulated as an MIQP.  A greedy approach to construct the schedule and a heuristic for data collection (which is needed to avoid running B&B multiple times) are proposed.  The effectiveness of these heuristics are demonstrated empirically on two types of benchmark problems (generalized independent set and fixed charge multicommodity flow), with the main metric of interest being the primal integral.  The proposed method shows a significant improvement over standard heuristic schedules (those used by SCIP) and the hyperparameter tuning method SMAC (which can also be used to set the heuristic schedule).  The downside of SMAC compared to the proposed methods is that SMAC has a high computational cost for the learning stage.\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Improving MIP solvers using data driven approaches is a relevant problem and has seen some recent interest (along with other data driven approaches to algorithm design).  This paper focuses on the primal aspect of MIP solving and shows promising results\n\nThe main weakness of this paper is the lack of theory.  In addition to studying this problem from the perspective of learning theory (which the authors make a note of in the conclusion), it would also be interesting to see further justification for the greedy approach to designing the schedule and the data collection procedure.  Does the proposed greedy algorithm (Algorithm 1 in the Appendix) have a constant approximation ratio?  Can it be made more formal that the data collection procedure (Section 5) is unbiased?\n\nOverall, the strengths of this paper outweigh the weaknesses, so I would vote to accept this paper.\n\n-------------------------------------\n\nEdit after rebuttal period\n\nThanks to the authors for responding to my comments, my overall (positive) opinion is unchanged.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is discussion of the limitations of the work, and I do not see any issues in terms of negative societal impact stemming directly from this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Three of the reviewers felt this is a good paper and should be published.  One reviewer was negative and thought the paper had several shrotcommings.  

In this case, I feel this interest in the work outweighs the concerns. 
Decision: Accept (Poster)