Learning to Configure Separators in Branch-and-Cut
Authors: Sirui Li
Wenbin Ouyang
Max B. Paulus
Cathy Wu
Venue: NeurIPS 2023 poster (2023)
Keywords: Combinatorial Optimization
Branch-and-Cut
Learning Guided Optimization
Deep Learning

Abstract: Cutting planes are crucial in solving mixed integer linear programs (MILP) as they facilitate bound improvements on the optimal solution. Modern MILP solvers rely on a variety of separators to generate a diverse set of cutting planes by invoking the separators frequently during the solving process. This work identifies that MILP solvers can be drastically accelerated by appropriately selecting separators to activate. As the combinatorial separator selection space imposes challenges for machine learning, we *learn to separate* by proposing a novel data-driven strategy to restrict the selection space and a learning-guided algorithm on the restricted space. Our method predicts instance-aware separator configurations which can dynamically adapt during the solve, effectively accelerating the open source MILP solver SCIP by improving the relative solve time up to 72% and 37% on synthetic and real-world MILP benchmarks. Our work complements recent work on learning to select cutting planes and highlights the importance of separator management.

Learning to Configure Separators in Branch-and-Cut
Sirui Li' MIT siruil memill@mitt.eee. edu
Wenbin Ouyang' MIT oywenbin@mit.cm edu
Max B. Paulus
Cathy Wu MIT cathynu@mit.edu
ETH Zürich
max. max.paulus@inf. ethz. ch
Abstract
Cutting planes are crucial in solving mixed integer linear programs (MILP) they facilitate bound improvements on the optimal solution. Modern MILP solvers rely on a variety of separators generate a diverse set of cutting planes by invoking the separators frrequetly during the solving process. This work identifies that MILP solvers can be drastically accelerated by appropriately selecting separators to activate. As the combinatorial separator selection space imposes challenges for machine learning, we learn separate by proposing a novel data-driven strategy to restrict the selection space and a learning soeniingggiieddd guided algorithm on the restricted space. Our method predicts instance-aware separator configurations which can dynamically adapt during the solve, effectively accelerating the open source MILP solver SCIP by improving the relative solve time up 72% and 37% on synthetic and real-world MILP benchmarks. Our work complements recent work on learning to select cutting planes and highlights the importance of separator management.
Introduction
Mixed Integer Linear Programs (MILP) have been widely used in logistics 115], management and production planning [17 Modern MILP solvers typically employ a Branch-and-Cut (B&C) framework that utilizes Branch-and- and-Bound (B&B) tree search procedure to partition the search space. As illustrated in Fig. [ cutting plane algorithms are applied within each node of the B&B tree, tightening the Linear Programming (LP) relaxation of the node and improving the lower bound.
This paper presents a machine learning approach to accelerate MILP solvers. Modern MILP solvers implement various cutting plane algorithms, also referred that tighten the LP solutions. Different separators have varying performance and execution times depending on the specific MILP instance. Typical solvers use simple heuristics select separators, which can limit the ability to exploit commonalities across problem instances. While there is
separators, to generate cutting planes
growing body of work considering the 'branch' and 'cut" aspects of B&C 18
profiling the open-source academic MILP solver SCIP M we find generating cutting planes through separators a major contributor the total solve time, and deactivating unused separators leads faster solves and fewer B&B tree nodes. That is, well-configured separator setup allows the selected cutting planes to more effectively tighten the L. solution, leading to fewer nodes in the B&B tree.
$5
S1
?
To our knowledge, the problem of how to leverage machine learning for this critical task of separator configuration, namely the selection of separators to activate and deactivate during the MILP solving process has not been considered. Therefore, the goal of this paper is to explore the extent to which
"Equal Contribution
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Previous
Brancb-and-Bound Tree
Seporator Configuration
Cut Selection
MILP X" argmin S: AX D, Vj
Curpool
" x
Gomory
5
2,2
y '
Separators Generate Cuts: 5's
Clique
5,5-3 2
Figure I: Separator Configuration in Branch-and-Cut (B&C), Modern MILP solvers perform Branch-and-Bound (B&B) tree search to solve MILPs. At each node of the B&B tree, cuts are added to tighten the Linear Programming (LP) relaxation the MILP. To generate these cuts, a set of separators (e.g. Gomory) are invoked to first generate cuts into the cutpool C*.. A subset of these cuts p C* are then selected and added to the LP. The process is repeated for several separation rounds at each node. While previous works study cut selection from a pre-determined cutpool, this work focuses on the upstream task of separator configuration to generate a high quality cutpool efficiently.
tailoring the separator configuration to the MILP instance in data-driven manner can accelerate MILP solvers. The central challenge comes from the high dimensionality of the configuration search space (induced by the large number separators and configuration steps), which we address by introducing data-driven search space restriction strategy that balances model fitting and generalization. We further propose a learning- -uidded algorithm, which is cast into the framework of neural contextual bandit, an effective means of optimizing configurations within the reduced search space.
Our contributions can be summarized as
We identify separator management as crucial component B&C, and introduce the Separator Configuration task for selecting separators to accelerate solving MILPs.
To overcome the high dimensionality of the configuration task, we propose a data-driven strategy, directly informed by theoretical analysis, restrict the search space. We further design a learning method to tailor instance-aware configurations within the restricted space.
Extensive computational experiments demonstrate that our method achieves significant speedup over the competitive MILP solver SCIP on a variety of benchmark MILP datasets and objectives. Our method further accelerates the state-of-the-an art MILP solver Gurobi and uncovers known facts from literature regarding separator efficacy for different MILP classes.
2
Related Work
The utilization of machine learning in MILP solvers has recently gained considerable attention. Various components in the B&B algorithm have been explored, including node selection [25]
49
35
variable selection [8
2 [8), branching rule (A)
2 58 46]. scheduling primal heuristics 31 26
B
and deciding whether to apply Dantzig-Wi Wolfe decomposition 344.
Our work is closely related to cutting plane selection, which can be achieved through heuristics 55 or machine learning (51 42 The key difference, as shown in Figure in Sec. that these works focus on selecting cutting planes from a pre-given cutpool generated by the available separators. That is, they consider the 'how to cut' question, whereas we focus on the equally crucial, but much less explored 'when (and what separators should we use) to cut' question [14 16, 7 For example, Wesselmann and Stuhl (55) state that they do not use any additional scheme to deactivate specific separators. In contrast, our work configures separators to generate a high-quality cutpool.
Another closely related line of work is on algorithm selection and parameter configurations [56] 57
4
The most relevant works 57 5 consider portfolio- prafolio-bbaed algorithm selection by first choosing a subset of algorithm parameter settings, and then selecting parameter setting for each problem instance from the portfolio. We specialize and extend the general framework to separator configuration, by proposing novel data-driven subspace restriction strategy, followed by learning method, to configure separators for multiple separation rounds. We further present a theoretical analysis that directly informs our subspace restriction strategy, whereas the generalization guarantees from the prior work [5] is not informative for designing the portfolio-constructio procedure.
5
27
2x

---

It is common to restrict combinatorial space to improve the quality of solutions in discrete optimization. Previous research focuses primarily on decomposing large-scale problems, including heuristic works on Bender decomposition |4 and column generation [6. and recent learning- based works [50 36 that train networks to select among a set of random or heuristic decomposition strategies. Our data-driven action space restriction strategy is general and could be of interest for broader set of combinatorial optimization tasks, as well as other applications such as recommendation systems.
3 MILP Background
Mixed Integer Linear Programming (MILP). A MILP can be written as x arg min Ax S b, 2y E Z Vj E I}. where x E 1" the set of n decision variables, A E Rm*x and b E R" formulate the set of constraints, and IR" formulates the linear objective function. I I (1,...nn) n defines the integer variables. x" E IR" denotes the optimal solution to the MILP with an optimal objective value 2².
Branch-and-Cut. State-of-the-ar art MILP solvers perform branch-and-cut (B&C) to solve MILPs, where a branch-and-boune (B&B) procedure is used to recursively partition the search space into tree. Within each node of the B&B tree, linear programming (LP) relaxations the MILP are solved to obtain lower bounds. B&C further invoke Cutting plane algorithms to tighten the LP relaxation.
Cutting Plane Separation. When the optimal solution zir to the LP relaxation is not feasible solution to the original MILP, the cutting plane methods aim to find valid linear inequalities f/T S w (cuts) that separate ZiP from the convex hull of all feasible solutions of the MILP. Cutting plane separation happens in rounds, where each round & consists of the following steps (1) solving the current LP relaxation, (2) calling different separators to generate a set of cuts and add them to the cutpool Ck. (3) select subset of cuts Pk S C2 and update the LP with the selected cuts. Detailed background information on separators the B&C framework can found Appendix A.I.
4 Problem Formulation
Different separators are designed to exploit different structures of the solution polytope defined by the MILP instance. The solution polytope also varies at different separation rounds, as changes to the constraints (e.g. after branch) lead to different structures and thus different effective separators. Moreover, multiple separators can combine to exploit more sophisticated structures. The inherently combinatorial nature of the problem hence presents a challenge assigning the appropriate separators to each MILP instances. This work aims to enhance the MILP solving process via intelligent separator configuration. We formally introduce the separator configuration task as follows.
Definition 1 (Separator Configuration). Suppose the MILP solver implements M different separator algorithms. Given set X' of N MIIP instances (where | N), and maximum number of separation rounds R in a MILP solving process, we want to select a configuration $z,1 E {0, 13. for each instance x E and separation round 1 S n S R, where the whth entry of 82,n equaling one means we activate the wh separator separation round n, and equaling zero means we deactivate the wh separator in the corresponding round.
Figure I iilustrates the separator configuration task and highlights the difference between our task and the downstream cutting plane selection task in previous works [1
We measure the success of algorithm for the separator configuration task by the relative time improvement from SCIP's default configuration. Denote a proposed configuration policy as æ X' + II {0, 13.M, where for each MILP instance x E X, we have ((x) [s.,1:..., R2,R as the proposed configurations. Let t (x) be the solve time of instance using the configuration sequence (2) and to (z(2) (z) be the solve time using the default SCIP configuration (both to optimality or fixed gap). We evaluate the effectiveness of π by the relative time improvement
((T) == Exex ( (1) where 8(<(T), = (to(x) - (t()))/to(())
The search space for the separator configuration task is enormous, with a size of N Nx2 MxR SCIP con- tains M = 17 separators, and a typical solve run yields R 2 30, making the task highly challenging. In the next section, discuss our data-driven approach to finding high quality configurations.
3

---

5 Learning to Separate
Two sources of high dimensionality in the search space come from (1) combinatorial number [O] = 2M of configurations, where each element of O == {0. 1) 1 is a combination of separators (e.g., Gomory, Clique) activate, and (2) large number of configuration updates that results in the |O factor. We address the first challenge in Sec. 5.1 by restricting the number of configuration options, and the second challenge in Sec. by reducing the frequency of configuration updates. The resulting restricted search space allows efficient learning in Sec. 5.3 to find high quality customized configurations for each MILP instance, which we term as instance- aware configurations.
5.1 Configuration space restriction
For simplicity, we first consider a single configuration update such that we apply the same configu- ration for all separation rounds, and our goal is to learn instance-aware configuration predictor f + O. That is, we set 82,1 to multiple configuration updates. To address the challenge of learning the predictor in the high dimensional space O, we constrain the predictor fA to select from a subset A C of configurations with |A| reasonably small, ie. fa( E A Vz E X. We design a data- kata-driven strategy, supported by theoretical rationale, to identify a subspace A for f' to achieve high performance.
82 R f(x for each E X'; Sec. 5.2 discusses extensions
Preliminary definitions. Let X' be a class of MILP instances, and KC = (x1, σk} C X' be a given training set where we can acquire the time improvement {ō(s, ..)) The true performance of FA on X is A(fA) = EExx[ x)), and the empirical counterpart on K. is Á(fa) = - Σ 2.) We further denote the true instance-agnoste performance of applying single configuration
{0, 1 to all MILP instances 0(s) = Exex (ō(s, x)), and the empirical counterpart as 8(s) K Σ 8(s, 24). Appendix 1.2.1 details all relevant definitions.
Restriction algorithm. To find subspace A that optimizes the true performance A(fA) for the predictor SA, we employ the following training performance v.s. generalization decomposition:
A(FA)= = Á(fA) ( -
training perf.
generalization
The first term measures how well fA performs on the training set K., while the second term reflects the generalization gap of ÍA the entire distribution X. Notably, similar trade-off exists in standard supervised learning [4]] where regularizations are used to balance fitting and generalization by implicitly restricting the hypothesis class. Relatedly, in this problem, we can balance the two terms by explicitly restricting the output space of the predictor. Intuitively, a larger subspace A can improve training performance (more configuration options leverage), but hurt generalization (more options that could perform poorly on unseen instances). This intuition is formalized next.
First, since the second term in Eq. is unobserved, the following proposition imposes assumptions that allow us to restrict the configuration space. detailed proof can be found in Appendix A.2.2.
Proposition 1. Assume the predictor fA, when evaluated on the entire distribution X', achieves perfect generalization (i.e., zero generalization gap) with probability 1 az with probability a, the predictor makes mistake and outputs configuration s E A uniformly at random. Then, the trainset performance v.s. generalization decomposition can be written as A(fa) = (1 a)A(F)) + a J E.Ea 8()).
As ((s) is also unobservable, we further rely on its empirical counterpart (s(s) (see Appendix A.2.2 for a discussion of the reduction) and select the subspace A based on the following objective:
(1 - ()Fx) +
1
Σ 8(s)
A
SEA
The impact of the subspace A on these two terms further depends on the nature of fA: we assume that the predictor FA uses empirical risk minimization (ERM) and performs optimally on the training set K., i.e. fERM (x:) = arg m ö(s, .r) Vx E K. hence bypassing the need to train any predictor for constructing A. The discussion of the ERM assumption's 's validity and the extension to predictors with training error provided in Appendix A.2.4 (See Lemma 3 for the extension).

---

Eq. then sheds light on how to construct good A under the ERM assumption: an ideal subset A allows fERM to have (1) high training performance ((ARRM) obtained when some configuration in A achieves good performance for any MILP instance in a training set, and (2) low generalization gap, achieved when each configuration in A has good performance across MILP instances in test set, which we approximate with the average instance-agnostic performance on the training set TA] EEE 8(s). In fact, larger or more diverse subspace A results in better Â(fARM), as the ERM predictor can leverage more configuration options to improve the training set performance. 1 Meanwhile, it may also lower 17 ExEa 0(s) which harms generalization, as we may include some configurations that perform poorly on most MILP instances but well on a small subset. The following proposition (proven in Appendix A.2.3) formalizes the diminishing marginal returns of fA fARMS "s training performance with respect to A, which enables an efficient algorithm to construct A:
1
The empirical performance of the ERM predictor Á(FARM) is monotone submodular, and greedy strategy where we include the configuration that achieves the greatest marginal improve- ment arg m0.), M A(A AU(s) ) Á(F at each iteration is (1 - apprroxppooiiinoo
Proposition 2.
algorithm for constructing the subspace A that optimizes Á(FĀRM)
To balance the two terms in Eq. we couple the greedy selection strategy with a filtering criterion that eliminates configurations with poor instance-agnostie performance to construct the subspace A. Due the high computational cost of calculating the marginal improvement for all 2 configurations, we first sample large set S' of configurations, which we use to construct the subspace A. Then, at each iteration, we expand the current set A with the configuration that produces the best marginal improvement in training performance, but only considering configurations s E S whose empirical
instance-agnen aggnosti performance is greater than threshold, i.e. 8(s) > b. The extra filtering procedure enables us to improve the second term with small concessions in the first term. We continue the process while monitoring the two opposing terms, and terminate with a reasonably small that balances the trade-off. The detailed algorithm and discussions of the filtering and termination procedure are provided in Appendix A.3.
5.2 Configuration update restriction
Learning to update configurations at each separation round is challenging due to cascading errors from a large number of updates. Instead, we periodically update the configuration at a few intermediate rounds and hold it fixed between updates: we perform < R updates at rounds {n, 1 ;=1 with Ss.mfi1-1 for each 1 S
I S ny < R, and set Sa,", Appendix A.4 shows an example of the configuration update restriction with = and R = 6, where also discuss the trade-off of & in approximation v.s. estimation. We empirically find a small number of updates can already yield a decent time improvement (we set k = 2 in Experiment Sec. (
j < k and E X. Fig. 7 (Left) in
We use a forward training algorithm 45 to learn the configuration policy ((x) X + II (0, 13 The algorithm decomposes the sequential task into k single configuration update tasks (k) {for 1 Jm=11 where each for X + {0, 1J M is a separate network for the j-th configuration update. As illustrated in F (Right) of Appendix A.4, at each iteration, we fix the weights of the trained networks for earlier updates {foz y-1 and train the network fg for the jth update. The detailed algorithm is provided in Alg. 2 of Appendix A.4. We incorporate the configuration space restriction in Sec. 5.1 by constraining each network F/ to select configurations from a subset A C O, such that 7
A for all x: X. This reduces the search space from N M N |A] x k. significantly easing the learning process. Notably, we construct the subspace A once at the initial update for computational efficiency benefits, as it yields comparable performances to constructing a new subspace for each update. Further details and discussions can be found in Appendix A.7.2.
5.3 Neural UCB algorithm
Given the restricted configuration space A, we frame each configuration update as a contextual bandit problem with A arms (configurations). Conditional on the context (a MILP instance x E X²), each arm s E A has a reward (time improvement 5(s, r)). We employ the neural UCB algorithm [59 to efficiently train network for (z, s) X A + I to estimate the reward, where the confidence
5

---

Kmboddinng ViC-Gruph
Convelation Canralation Convolution
S/V-Gruph
SCC-Graph
SAltecttin
Meas- Puol
Crocatennto
Final Emholding
Variable nodes
Constraint
Mean-Pool
and
Mean-Pool
1+1
score
Beparator nodes B
Aleetton
Masn-PPol
(a)
(b)
Figure 2: (a) Our triplet graph encoding of the MILP instance (the context) and the separator configuration (the arm action). (b) Our neural architecture fo. It involves three graph convolutions, an attention block for the separator nodes, and global poolings to extract the final score for reward prediction. We show the dimensionality of a tensor in gray if it is different from the previous size.
bound estimation is enabled by the small size of A. We provide the complete training procedure in Alg. 3 of Appendix A.5. At each training epoch i, we randomly sample P instances from X. For each instance, we sample D configurations based on the upper confidence bound ucb(x, s), which combines a reward point estimate fg.-1 (2, s) and a confidence bound estimate. The confidence bound estimate incorporates the gradient Vo Fo (2, s) and a normalizing matrix Z₁-1 only feasible to obtain when the number of arms is small. We run the MILP solver on each of the P X D pairs of instance-configuration and observe the reward labels. Lastly, we add all instance-configurationn reward tuples {ar, 8, r) Px to the data buffer and retrain the network f At test time, we select the configuration with the highest predicted reward $ = arg max, A faz (I. s) or the highest UCB score s = arg m ueb(x, s), based on validation performance, at each update step nz. We provide further details the inference strategy in Appendix 1.6.1.
Context encoding. We encode the context for each MILP instance x and separator configuration s as triplet graph with three types of nodes in the graph: variable nodes V, constraint nodes C, and separator nodes S. The variable and constraint nodes (V, C) appear in the previous works [8 We follow Paulus et al. 42] to use the same input features for V and C, and construct edges between them such that a variable node V; is connected to a constraint node C, if the variable appears the constraint with the weight corresponds to the coefficient A. # O. The separator nodes S are unique to our problem. We represent each configuration & by M separator nodes; each node S₃ has M + 1 dimensional input features, representing whether the separator is activated (the first dimension), and which separator it is (one-hot M -dimenssionll vector). We connect each separator node with all variable and constraint nodes, all with weight of for complete pairwise message passing. We provide detailed descriptions of the input features in Appendix A.5.
Neural architecture Jo. We extend the architecture Paulus et al. for our network To(o, 8) X' x S + R. The architecture, as illustrated in Fig. involves Graph Convolutional Network (GCN) [K], an attention block on the hidden embeddings of the separator nodes [48, and a global pooling to output a single score for reward prediction. It first embeds C. V. and S input features into hidden representations, and performs message passing following the directions of V-C-V, S-V-S and S- Then, the S nodes pass through an attention module to emphasize the task of the separator configuration. Lastly, since we require the model to output a single score (in contrary to Paulus et al. 42] which outputs a score for each cut node), we perform global mean pooling on each of the C, V, and S hidden embeddings to obtain three embedding vectors, concatenate them into single vector, and finally use a multilayer perceptron (MLP) to map the vector into scalar.
Clipped Reward Label. To account for variations solve time, we perform MILP solver runs for each innfiuurationiintaace pair (s, and take the average time improvement as the unclipped reward label. Additionally, if a certain configuration s takes significantly longer solve time than SCIP default on MILP instance 2, we terminate the MILP solver run when the relative time improvement is less than a predefined threshold Tmin < 0 to expedite data collection, and assign a clipped reward label of pelip (x, .r) (E= max (8(+) (s, 4:), (min)) 1)/l. Reward clipping also simplifies learning by obviating the need to accurately fit the exact value of extreme negative improvements, which may skew the network's 's prediction. As long as the prediction's sign is right, we will not select such a configuration with negative predicted value during testing.

---

Table 1: Tang et al. and Ecole. Absolute solve time of SCIP default, and the median (higher the better) and standard deviation (in parentheses) of relative time improvement different methods.
Tang
Ecole
Method
Bin. Pack.
Max. Cut
Pack.
Comb. Auc.
Indep.
Fac. Loc.
0.076s
1.77s
8.82s
2.73s
8.21s
61.1s
Default Time (s)
(0.131s)
(0.56s)
(25,46s)
(4.43s)
(114.15s)
(55.37s)
Default
0%
0%
0%
0%
0%
0%
-23.4%
108.4%
.91%
-48.6%
-5%
-33.3%
Heuristic
Random
(153.8%)
(168.2%)
(127.8%)
(159.0%6)
(161.4%)
(157.2%)
Baselines
13.9%
2.7%
6.6%
12.3%
18.0%
24.7%
Prune
(27.0%)
(26.2%)
(45.0%)
(24.2%)
(24.2%)
(47.9%)
Inst. Agnostic
33.7%
69.8%
20.1%
60.1%
57.8%
1 11.5%
Ours
Configuration
(36.6%)
(10.5%)
(38.0%)
(27.6%)
(29.5%%
(2188%)
Heuristic Variants
Random within
26.9%
68.0%
18.8%
58.1%
57.4%
17.7% (33.0%)
Restr. Subspace
(33.6%)
(11.0%)
(38.7%)
(28.7%)
(75.8%)
Ours Learned
42.3%
71.9%
28.5%
66.2%
72.4%
29.4% (39.6%)
L2Sep
(34.2%)
(11.3%)
(39.3%)
(26.2%)
(27.8%)
Loss function L. We La loss between the prediction fo(ur, s) and the clipped reward label y.llip;
L(Jo(z,)) = (fo r
6 Experiments and Analysis
We divide the experiment section into two main parts. First, we evaluate our method on standard MILP benchmarks from Tang et al. [5I] and Ecole [43]. where the number of variables and constraints
range from 60 to 10, 000. We conduct detailed ablation studies to validate the design choices made for our method. Second, we examine the efficacy of our method by applying it to large-scale real-world
MILP benchmarks, including the MIPLIB 20 NN Verification [40, and Load Balancing in the ML4CO challenges 119, where the number of variables and constraints reaches up to 65, 000. We omit certain MILP classes from the benchmarks with excessively short solve times, few generated cutting planes, or small dataset sizes. Appendix A.6.5 provides detailed description of the datasets.
6.1 Setup
Evaluation Metric. As aim accelerate SCIP solving through separator configuration, evaluate our learned configuration by the relative time improvement from SCIP default, defined in Eq. ( when both are solved optimality (for standard instances) or a fixed gap (for large-scale instances) as described in Appendix A.6.4. We report the median and standard deviation across all test instances, and defer mean and interquartile mean to Appendix A.8 as they yield similar results.
ML Setup. We train the networks with ADAM 32 under a learning rate of 10-3 3 The reward label collection is performed via
with 48 CPU processes. As in previous works [51 42
54]. we train separate models for each MILP class. By default, we generate a training set Kamaat of 100 instances for configuration space restriction, another training set Kterge of 800 for predictor network training, a validation set of 100 instances, and test set of 100 instances for each class Appendix A.6 provides full details of the setup.
Baselines. To our knowledge, our separator configuration task has not been explored in previous research. We design the following basclines to assess the effectiveness of our proposed methods: (1) Default, where we run SCIP with the default parameters; (2) Random, where for each MILP instance x, randomly sample configuration default on the Kamatts and then at test time, we deactivate separators whose generated cutting planes never applied any instances in Kymalt-
{0, 1) M; (3) Prune, where first SCIP
Proposed Methods. We evaluate the performances of our complete method and its sub-components: (L) Ours (L2Sep), where we perform A = 2 instance-aware configuration updates per MILP instance

---

Table 2: Detailed ablations of different components in our L2Sep algorithm. Learning with neural UCB in the restricted config. space and performing t = 2 config. updates achieves the best result.
Config. Space Restriction
Config. Update Restriction
Neural
Ours: 1.2Sep
Contextual Bandit
Ablation
No Restr.
Greedy Restr.
Supervise (x4)
w/ Restr. + h: = 2 + UCB
k = 1
k 3
e-greedy
Method
18.6%
35.8%
40.4%
44.2%
40.2%
36.3%
42.3% (34.2%)
Bin. Pack.
(125,3%)
(35.6%)
(42.3%)
(32.4%)
(19.7%)
(32.3%)
19.6%
18.4%
23.8%
27.8%
24.0%
25.1%
28.5%
Pack.
(6%)
(49.8%)
(38.1%)
(38.1%)
(44.1%)
(44.3%)
(39.3%)
38.6%
68.5%
70.2%
69.7%
68.7%
64.1%
72.4%
Indep. Set
(23.5%)
(28.1%)
(38.6%)
(29.1%)
(33.9%)
(48.7%)
(27.8%)
15.5%
27.1%
20.1%
29.7%
31.0%
28.1%
29,4%
Fac. Loc.
(121.2%)
(38.7%)
(37.8%)
(29.8%)
(41.5%)
(23.6%)
(39.6%)
(Sec. 5.2 We use forward training to learn predictors via the neural UCB algorithm (Sec. 5.3 within the restricted configuration subspace (Sec. 5.T). (2) Instance Agnostic Configuration, where we select single configuration 8 with the best instance-agnostie performance 8(3) on Kamalt from the initial large subset S for our space restriction algorithm ([S) R 2000); is included A. (3) Random within Restricted Subspace, where for each MILP instance, select a random configuration within A. The latter two sub-components assess the quality of the restricted subspace and the benefit of learning instance-aware configurations. Further details can be found in Appendix A.
6.2 Standard MILP Benchmarks with Detailed Ablations
Performance. Table I presents the relative time improvement of different methods over SCIP default, on the datasets of Tang et al. and Ecole. Our method demonstrates a substantial speed up from SCIP default across all MILP classes, with relative time improvement ranging from 25% to 70%. In contrast, the random baseline performs poorly, demonstrating that separator configuration is a nontrivial task. Meanwhile, although the pruning baseline generally outperforms SCIP default, its time improvement is significantly less than ours, confirming the efficacy of our proposed algorithm. Notably, both of our two heuristic sub-components achieve impressive speed-up from SCIP default, indicating the high quality of our restricted subspace (and a configuration within) to accelerate SCIP; additionally, our complete learning method outperforms the sub-components on all MILP classes, further underscoring the advantages of learning for instance-aware configurations.
We note that the high standard deviation, exhibited in all methods including SCIP default and also observed in the recent studies [544 is reasonable due to instance hetcrogeneity, as the standard deviation is calculated based on the time improvements across instances within each MILP dataset.
blations. Table we further conduct comprehensive ablation studies to assess the effectiveness of our learning method. The ablations are performed on four representative MILP classes in Ecole and Tang, covering a wide range of problem sizes and solve times. Appendix A.7 provides detailed descriptions well as additional ablation results. We aim to answer the following questions: (i) Does the restricted config. space improve learning performance? (ii) How does the performance vary with fewer or more updates? (iii) Does the use of neural UCB lead to efficient predictor learning?
We train our configuration predictors to select within a restricted subspace A constructed by greedy strategy coupled with filtering criterion. To evaluate the importance of the space restriction in learning high quality predictors, we perform an ablation study where we train the predictors to select within (1) the unrestricted space O = f0, 1 1 (No Restr.). and (2) a same-sized subspace A' constructed solely by the greedy strategy without filtering (Greedy Restr.). The restricted search space substantially enhances the learned predictors when compared to No Restr. improving the median performance and lowering the standard deviation. We also observe the benefit of the filtering criterion when compared to Greedy Restr.. The filtering criterion excludes configurations with subpar instance-agnostie performance from entering the restricted configuration space, improving model generalization demonstrated in theoretical analysis.
(i) Configuration space restriction (Sec. 5.1
8

---

Table 3: weal-world MILPs. Absolute solve time of SCIP default, and the median (higher the better) and standard deviation (in parentheses) of relative time improvement of different methods.
Heuristic Baselinses
Ours Heuristic Variants
Ours Learned
Default Times (8)
Inst. Agnostic Configuration
Random within Restr. Subspace
Methods
Default
Random
Prune
L2Sep
25.08s (57.05s)
-149.1%
4.8%
5.5%
1.9%
12.9%
MIPL.IB
0%
(149.7%)
(107.6%) (6)
(71.5%)
(74.9%)
(73.1%)
31,42s
-300.0%
31.5%
31.4%
30.7%
37.5%
NN Verification
0%
(22,44s)
(152.3%)
(36.3%)
(38.3%)
(34.1%)
(33.9%)
31,86s
-300.1%
21.1%
10.4%
10.0%
21.2%
Load Balancing
0%
(7.07))
(129.5%)
(150.8%%
(8.5%)
(31.5%)
(20.3%)
(ii) Configuration update restriction (Sec.5.. 5.2). We apply the forward training algorithm (Sec. 5.2 to perform two configuration updates (k = 2) for each MILP instance. To examine the impact of fewer or more updates, we conduct an ablation study where we (1) performed a single update at round n1 = 0 (k = 1), and (2) added an additional third update at later round ng (k = 3). The results show that while single update yields decent time improvement, adding the second update leads to further time savings. Meanwhile, we observe little improvement from the third update (k = 3). We speculate that this is because the performance improvement primarily occurs during the early stages of a solve, and holding a fixed configuration for longer may be advantageous by making the solve process more stable. We leave further investigation of more configuration updates future work.
(iii) Neural UCB algorithm (Sec. 5.3) Our method employs the online neural UCB algorithm to improve training efficiency for configuration predictors. We present the ablation (1) where we train the predictor using an offline regression dataset whose size is four times as ours while training the model until convergence (Supervise (x4)); we conduct an additional ablation (2) where we train the predictor using neural contextual bandit with e-greedy exploration strategy (e-greedy). Our model performs comparably to Supervise (x4) while using significantly fewer data, highlighting the importance of the contextual bandit for improving training efficiency by collecting increasingly higher quality datasets online. The ablation results with e-greedy further confirm the benefit of the confidence bound estimation in neural UCB for more efficient contextual bandit exploration.
6.3 Large-scale Real-world MILP Benchmarks
The real-world datasets of MIPLIB, NN Verification, and Load Balancing present significant chal- lenges due to the vast number of variables and constraints (on the order of 10*), including nonstandard constraint types that MILP separators are not designed to handle. MIPLIB imposes further challenge of dataset heterogeneity, as contains a diverse set of instances from various application domains. Prior research [52] struggles to learn effectively on MIPLIB due to this heterogeneity, and recent study [54] attempts to learn cutting plane selection over two homogeneous subsets (with 20 and 40 instances each). In contrast, we attempt to learn separator configuration across a larger MIPLIB subset that includes 443 of the 1065 instances in the original set, while carefully preserving the heterogeneity of the dataset. We provide subset curation procedure in Appendix A.6.5.
Main Results. Table AablleBrressee presents the relative time improvement of various methods over SCIP default, on the large-scale real-world datasets. Again, our complete method displays a substantial speed up from SCIP default with a relative time improvement ranging from 12% to 37% Our method also improves from our heuristic sub-components, further indicating the efficacy of our learning component on the challenging datasets. In contrast, the random bascline fails to improve from SCIP default, while the pruning baseline, despite having reasonable median performance, suffers from a high standard deviation due to poor performance on many instances (See Appendix A. for IQM and mean results). Our results show the effectiveness of our learning method in improving the efficiency of practical applications that involve large-scale MILP optimization.
Although not perfect comparison, for reference, we attempt to contextualize our result by examining the time improvement in the most comparable setting we found, which we provide comparison details in Appendix A.8.2: the learning method for cutting plane selection in Paulus et al. 42] achieves a median relative time improvement of 11.67% on the NN Verification dataset, and that Wang et al. [54] obtains 3% and 1% improvement in the solve time on two small homogeneous MIPLIB

---

Table 4: Gurobi the MILP Solver. Absolute solve time of Gurobi default, and the median (higher the better) and standard deviation (in parentheses) of relative time improvement of different methods.
Heuristic Baselinses
Ours Heuristic Variants
Ours Learned
Default Times
Inst. Agnostic Configuration
Random within Restr. Subspace
Methods
Default
Random
L2Sep
0.087s
18.6%
35.1%%
37.3%
45.4%
Max. Cut
0%
(0.051s)
(49.0%)
(35.8%)
(48.0%)
(38.4%)
4.048s
15.5%
22.9%
24.3%
30.6%
Pack.
0%
(3.216s)
(28.2%)
(39.4%)
(32.2%)
(29.6%)
1.687s
-10.7%
3.1%
5.1%
12.6%
Comb, Auc.
0%
(3,5968)
(69.1%)
(65.3%)
(84.2%)
(63.5%)
27.872s
13.4%
40.6%
40.2%
56.7%
Fac. Loc. (14.733s)
0%
(46.0%)
(48.1%)
(46.8%)
(35.7%%
subsets. While the comparison is far from perfect, our learning method for separator configuration achieves much higher time improvements of 37.5% on NN Verification and 12.9% on MIPLIB.
6.4 Interpretation Analysis: L2Sep Recovers Effective Separators from Literature
Bin Packing: is known that instances with few bins approximate the Knapsack problem (Clique cuts are known to be effective [9] ) and that instances with many bins approximate Bipartite Matching
(Flowcover cuts can be useful [53] We analyze the separators activated by L2Sepp when we gradually
decrease the number of bins, and observe that the prevalence of selected Clique and Flowcover cuts increased and decreased, respectively. This is illustrated Fig Appendix A.8.3.
Other MILP Classes: We provide visualizations and interpretations for other MILP classes in Appendix A.8.3. Notably, Clique is known to effective for Indep. Set [T6] L2Sep recovers this fact by frequently selecting configurations that activate Clique. Mcanwhile, L2Sep discovers the instance heterogeneity of MIPLIB, resulting in a more dispersed distribution of selected configurations.
6.5 State-of-the-art MILP Solver Gurobi
We apply our method L2Sep with Gurobi, which contains a larger set of 21 separators. As Gurobi is closed-source, cannot change configurations after the solving process starts, one stage of separator configuration (k = 1). As seen from Table 4 L2Sep achieves significant relative time improvements over the Gurobi default, with gains ranging from 12% to 56%. This result confirms the efficacy L2Sep as an automatic instance-aware separator configuration method.
only consider
6.6 Additional Results
In Appendix A.8.5 and A.8.4, we further demonstrate (1) Separator Configuration has immediate and multi-step effects in the B&C Process. For instance, even though L2Sep does not modify branching. the branching solve time is reduced. (2) 1.2Sep is effective under an alternative objective, achieving 15%- relative gap improvements under fixed time limits.
7 Conclusion
This work identifies the opportunity of managing separators to improve MILP solvers, and further for- mulates and designs a learning-bast based method for doing so. We design data-driven strategy, supported by theoretical analysis, to restrict the combinatorial space of separator configurations, and overall find that our learning method able improve the relative solve time (over the default solver) from 12% to 72% across a range of MILP benchmarks. In future work, we plan to apply our algorithm to more challenging MILP problems, particularly those that cannot be solved to optimality. We also aim to learn more fine- fine-graine grained controls by increasing the frequency of separation configuration updates. Our algorithm is highly versatile, and we plan to investigate its potential manage aspects of the MILP solvers, and further integrate with previous works on cutting plane selection. Our code is publicly available at Inttps: : :/:::://tttie tuub. com/mit- wu- -asetttuulllallaa waa--labllearre waaabbaaaningttaa conf wew.g- We believe that our learning framework can be powerful technique enhance MILP solvers.
10

---

Acknowledgments and Disclosure of Funding
The authors would like thank Mark Velednitsky and Alexandre Jacquillat for insightful discussions regarding an interpretative analysis of the learned model. This work was supported by a gift from Mathworks, the National Science Foundation (NSF) CAREER award (#2239566), the MIT Amazon Science Hub, and MIT's Research Support Committee. The authors acknowledge the MIT SuperCloud and Lincoln Laboratory Supereomputing Center for providing HPC resources that have contributed to the research results reported within this paper.
References
[1] Tobias Achterberg. Constraint integer programming. PhD thesis, 2007.
[2] Edoardo Amaldi, Stefano Coniglio, and Stefano Gualandi. Coordinated cutting plane generation via multi-objectivv separation. Mathematical Programming, 143:87-110, 2014.
[3] Egon Balas, Sebastian Ceria, Gérard Coruéjols, and N Natraj. Gomory cuts revisited. Opera- lions Research Letters, 19(1):1-9, 1996.
[4] Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data sufficient to learn high-performing algorithms? generalization guarantees for data-driven algorithm design. In Proceedings of the 53rd Anmual ACM SIGACT Symposium on Theory of Computing, pages 919-932, 2021.
[5] Maria-Florime Balcan, Tuomas Sandholm, and Ellen Vitercik. Generalization in portfolio- based algorithm selection. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 12225-12232, 2021.
[6] Cynthia Barnhart, Ellis L Johnson, George Nemhauser, Martin WP Savelsbergh, and Pamela Vance. Branch-and-priee Column generation for solving huge integer programs. Operations research, 46(3):316-329, 1998.
[7] Timo Berthold, Matteo Francobaldi, and Gregor Hendel. Learning use local cuts. arXiv preprint arXiv:2206. 11618, 2022.
[8] Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper Doornmalen, Leon Eifler, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, al. The scip optimization suite 8.0. arXiv preprint arXiv:2112.088777 2021.
[9] Natashia Boland, Andreas Bley, Christopher Fricke, Gary Froyland, and Renata Sotirov. Clique- based facets for the precedence constrained knapsack problem. Mathematical programming, 133:481-511, 2012.
[10] Endre Boros, Yves Crama, and Peter L. Hammer. Chvátal cuts and odd cycle inequalities in quadratic 0-1 optimization. SIAM Journal Discrete Mathematics, 5(2):163-177, 1992.
[11] Alberto Caprara and Matteo Fischetti. (0. 1/2)-chvvtal-gomoryy cuts. Mathematical Program- ming. 74:221-233. 1996.
[12] Steven Cheng, Christine W Chan, and Gordon H Huang. An integrated multi-criteria decision analysis and inexact mixed integer linear programming approach for solid waste management. Engineering Applications of Artificial Intelligence, 16(5-6):543-555 2003.
[13] Antonia Chmiela, Elias Khalil, Ambros Gleixner, Andrea Lodi, and Sebastian Pokutta. Learning to schedule heuristics in branch and bound. Advances in Neural Information Processing Systems, 34:24235-24246, 2021.
[14] Claudio Contardo, Andrea Lodi, and Andrea Tramontani. Cutting planes from the branch- and-bound tree: Challenges and opportunitics. INFORMS Journal on Computing, 35(1):2-4, 2023.
[15] Eray Demirel, Neslihan Demirel, and Hadi Gökçen. A mixed integer linear programming model to optimize reverse logistics activities of end-of-life vehicles in turkey. Journal of Cleaner Production, 11:22101-2113, 2016.

---

[16] Santanu S Dey and Marco Molinaro. Theoretical challenges towards cutting plane selection. Mathematical Programming, 170:237-266, 2018.
[17] Christodoulos A Floudas and Xiaoxia Lin. Mixed integer linear programming in process scheduling: Modeling, algorithms, and applications. Annals of Operations Research, 139: 131-162, 2005.
[18] Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. Advances in neural information processing systems, 32, 2019.
[19] Maxime Gasse, Simon Bowly, Quentin Cappart, Jonas Charfreitag, Laurent Charlin, Didier Chételat, Antonia Chmiela, Justin Dumouchelle, Ambros Gleixner, Aleksandr M Kazachkov, et al. The machine learning for combinatorial optimization competition (ml4co): Results and insights. In NeurlPS 2021 Competitions and Demonstrations Track, pages 220-231. PMLR. 2022.
[20] Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg, Michael Bastubbe, Timo Berthold, Philipp Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, et al. Miplib 2017: data-driven compilation of the 6th mixed-integer programming library. Mathematical Programming Computation, 13(3):443 490, 2021.
[21] Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint 1e 12715, 2018.
[22] Zonghao Gu, George L. Nemhauser, and Martin WP Savelsbergh. Lifted flow cover inequalities for mixed 0-1 integer programs. Mathematical Programming, 85:439-467, 1999.
[23] Prateek Gupta, Maxime Gasse, Elias Khalil, Pawan Mudigonda, Andrea Lodi, and Yoshua Bengio. Hybrid models for learning to branch. Advances in neural information processing systems, 33: 13087777788,7, 2020.
[24] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023. URLhhttps:/ gurobi com
[25] He He, Hal Daume III, and Jason M Fisner. Learning to search in branch and bound algorithms. Advances in neural information processing systems, 27, 2014.
(26) Gregor Hendel, Matthias Miltenberger, and Jakob Witzig. Adaptive algorithmic behavior for solving mixed integer programs using bandit algorithms. In Operations Research Proceedings 2018: Selected Papers of the Annual International Conference of the German Operations Research Society (GOR), Brussels, Belgium, September 12-14, 2018, pages 513-519. Springer, 2019.
[27] Frank Hutter, Holger Hoos, Kevin Leyton- Leyton-Brown, and Thomas Stützle. Paramils: an automatic algorithm configuration framework. Journal of Artificial Intelligence Research, 36:267-306. 2009.
[28] Frank Hutter, Holger H Hoos, and Kevin Leyton- Brown. Sequential model-based optimization for general algorithm configuration. In Learning and Intelligent Optimization: 5th International Conference, LION 5, Rome, Ital, January 17-21, 2011, Selected Papers 5, pages 507-523. Springer, 2011.
[29] Michael Jünger and Sven Mallach. Exact facetial odd-cycle separation for maximum cut and binary quadratic optimization. INFORMS Journal on Computing, 3314):141-11430, 2021.
[30] Elias Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
[31] Elias Khalil, Bistra Dilkina, George I. Nemhauser, Shabbir Ahmed, and Yufen Shao. Learning to run heuristics in tree search. In Ijcai, pages 659-666, 2017.
12

---

[32] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 2014.
[33] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
[34] Markus Kruber, Marco E Lübbeeke, and Axel Parmentier. Learning when to use a decomposi- tion. In Integration of Al and OR Techniques in Constraint Programming: 14th International Conference, CPAIOR 2017, Padua, Italy, June 5-8, 2017, Proceedings 14, pages 202-210. Springer, 2017.
[35] Abdel Ghani Labassi, Didier Chételat, and Andrea Lodi. Learning to compare nodes in branch and bound with graph neural networks. arXiv preprini arXiv:22 16934, 2022.
[36] Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehicle routing. Advances in Neural Information Processing Systems, 34:26198-2633 2021.
[37] Stephen Maher, Matthias Miltenberger, João Pedro Pedroso, Daniel Rehfeldt, Robert Schwarz, and Felipe Serrano. PYSCIPOpt: Mathematical programming in python with the SCIP opti- mization suite. In Mathematical Software - ICMS 2016, pages 301-307. Springer International Publishing, 2016. doi: 1111007/97--3-31-44441
[38] Alberto Maria Metelli, Flavio Mazzolini, Lorenzo Bisi, Luca Sabbioni, and Marcello Restelli. Control frequency adaptation via action persistence in batch reinforcement learning. In Interna- tional Conference on Machine Learning, pages 6862-6873. PMLR, 2020.
[39] Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):529-533 2015.
[40] Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid Von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O' O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, al. Solving mixed integer programs using neural networks. arXiv preprint (a0i:::2012.133499 2020.
[41] George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions-i. Mathematical programming. 14:265-294, 1978.
[42] Max B Paulus, Giulia Zarpellon, Andreas Krause, Laurent Charlin, and Chris Maddison. Learning to cut by looking ahead: Cutting plane selection via imitation learning. In International conference on machine learning, pages 17584-17600. PMLR, 2022.
[43] Antoine Prouvost, Justin Dumouchelle, Lara Scavuzzo, Maxime Gasse, Didier Chételat, and Andrea Lodi. Ecole: A gym-like library for machine learning in combinatorial optimization solvers. In Learning Meets Combinatorial Algorithms at NeurIPS2020, 2020. URL https //openreview. net/forummid -ooooumnidd-ehhgiiipp
[44] Ragheb Rahmaniani, Teodor Gabriel Crainic, Michel Gendreau, and Walter Rei. The benders decomposition algorithm: A literature review. European Journal of Operational Research, 259 (3):801-817, 2017.
[45] Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 661-666 JMLR Workshop and Conference Proceedings. 2010.
[46] Lara Scavuzzo, Feng Chen, Didier Chételat, Maxime Gasse, Andrea Lodi, Neil Yorke-Smithh and Karen Aardal. Learning to branch with tree mdps. Advances in Neural Information Processing Systems, 35: 15111181488666. 2022.
[47] Shai Shalev-Shwartz and Shai David. Understanding machine learning: From theory to algorithmss. Cambridge university press, 2014.
[48] Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjing Wang, and Yu Sun. Masked label prediction: Unified message passing model for semi-supervised classification. In Proceed- ings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pages 1548 1154,554,00 8 2021.
13

---

[49] Jialin Song, Ravi Lanka, Albert Zhao, Aadyot Bhatnagar, Yisong Yue, and Masahiro Ono. Learning to search via retrospective imitation. arXiv preprint arXiv:1804.00880 0084600046.... 2018.
[50] Jialin Song, Yisong Yue, Bistra Dilkina, al. A general large neighborhood search framework for solving integer linear programs, Advances in Neural Information Processing Systems, 33: 20012-20023, 2020.
[51] Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Reinforcement learning for integer program- ming: Learning cut. In International conference machine learning, pages PMLR, 2020.
[52] Mark Turner, Thorsten Koch, Felipe Serrano, and Michael Winkler, Adaptive cut selection in mixed-integer linear programming. arXiv preprint arXiv:220210066,, 2022.
[53] Mathieu Van Vyve. Fixed-charge transportation on a path: Linear programming formulations. In International Conference on Integer Programming and Combinatorial Optimization, pages 419-429. Springer, 2011.
[54] Zhihai Wang. Xijun Li, Jie Wang, Yufci Kuang, Mingxuan Yuan, Jia Zeng, Yongdong Zhang, and Feng Wu. Learning cut selection for mixed-integer linear programming via hierarchical sequence model. In The Eleventh International Conference on Learning Representations, 2023.
[55] Franz Wesselmann and Uwe Stuhl. Implementing cutting plane management and selection techniques. In Technical Report. University of Paderborn, 2012.
[56] Lin Xu, Holger Hoos, and Kevin Leyton-Brown. Hydra: Automatically configuring algorithms for portfolio-based selection. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 24, pages 210-216. 2010.
[57] Lin Xu, Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown Hydra-mip: Automated algorithm configuration and selection for mixed integer programming. In RCRA workshop experimental evaluation of algorithms for solving problems with combinatorial explosion at the international joint conference artificial intelligence (IJCAI), pages 16-30, 2011.
[58] Giulia Zarpellon, Jason Jo, Andrea Lodi, and Yoshua Bengio. Parameterizing search trees to learn branching policies. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 3931 2021.
[59] Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning, pages 11492-11502. PMLR, 2020.
14


Reviews:
[{"review_id": "fv31xIYQdM", "reviewer": "Reviewer_LDTP", "summary": "This paper uses machine learning to decide which families of cutting planes should be applied in each of a finite number of rounds when a discrete mathematical optimization problem is solved by an MILP solver. The authors conduct experiments on the SCIP solver, in which they show that their selection of separators (generators of different families of cutting planes) is able to solve problems faster than the default configurations of SCIP.", "questions": "1) Can you compare your work with prior cut selection approaches?\n\n2) In plain terms, what exactly is the subset of configurations A and how is it pre-selected?\n\n3) What is the relevance of Propositions 1 and 2 in the context of MILP? \n\n4) How exactly are the separator nodes S used in the representation of the instances?\n\n5) How exactly do you consider instances in which neither SCIP nor skip with your separator selection were able to solve?\n\nFigure 1: The letter b is used both as the RHS of the set of constraints as well as the RHS of the next cut generated; also using A and a with different meanings (constraint LHS and cut LHS) does not seem advisable.\n\nEquation 2: Why is the term on the left repeated at the end of the equation? Is this a typo?", "limitations": "Although the authors do not explicitly acknowledge this, their focus on runtime for solving problems to optimality means that their approach is of little help precisely for the case in which it would be needed the most: problems in those benchmarks for which the provable optimal solution is not known. It is also unclear what happens in the case of the problems that do not finishing running on time: my guess is that timeout is counted equally as bad, although it would make more sense to look for the best solution found or the remaining optimality gap.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "Within the mathematical optimization community, it is known that many people have looked at this problem but few obtained good results, which shows in the limited number of direct references shown by the authors.\n\nThe results are certainly motivating, and the authors managed to analyze their work across a representative number of datasets.\n\n*****\n\nFollowing the rebuttal, I still have concerns about the significance of the work, which are similar to the ones presented in reviewer wvgK's review. For that reason, I cannot be more enthusiastic than a borderline accept for this paper.", "weaknesses": "I tend to consider the selection of separators a special case of what was done in prior work, in which the cuts themselves were selected. By using a setting in which their work is not comparable to prior ML studies on this topic, I am left wondering if what is proposed in this paper indeed leads to a better approach than the ones already known.\n\nThe paper explains very little about MILP, to the point that it fells like the application is an afterthought. While the appendix generously makes up for that, a reader unfamiliar with MILP might read the entire paper and not understand much about the application considered. In fact, for a span of approximately 3 pages (Line 56 in Page 2 to Line 175 in Page 5) there is very little that is specific to the application to MILP solvers. In great part that is because of using a language that is very different. I would not say that this is an issue of using ML instead of MILP terminology because I also got lost with the abstractions used, such as when the authors say \"single configuration update\" to mean that the same separators would be used in every round. This abstractness of the language left me with many questions about what exactly was done (see Questions). For someone with a greater interest in MILP as myself, I find it difficult to translate what the authors did to the application. As a consequence, I would have a hard time trying to reproduce their work if I wanted to.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for valuable input on paper presentation and other insightful questions. We provide our responses next, and present our new experiments in the general comments, covering (1) analysis of effective separators for each MILP class from our learning results, and applying our method to (2) a different MILP solver Gurobi, and (3) a different metric (relative gap improvement). If appropriate, we encourage the reviewer to increase our review score.\n> The paper explains very little about MILP, to the point that it feels like the application is an afterthought\n\nAs the camera ready permits one more page, we plan to present more details on MILPs (which are currently in the Appendix) and provide additional clarification on other terminologies.\n> Q1. Can you compare your work with prior cut selection approaches?\n\n**Learning Method differences:** prior cut selection learning methods do not consider reducing the dimensionality of the action space. However, our separator configuration space with a size $2^M$ is challenging to learn (see ablation “No Restr” in Table 2). This motivates our proposed data-driven configuration space restriction algorithm.\n\n**Result Comparison:** in Main Paper Sec. 4.3, we contextualize our time improvement on comparable datasets (NNV and MIPLIB); our method achieves larger time improvements than prior cut selection works.\n\n**Task differences:** Separator configuration is applied for cut generation, which happens earlier than cut selection (See Main Paper Fig. 1 caption). At each separation round, activated separators first generate cuts to a cutpool; then cut selection algorithms choose cuts from the cutpool. The two tasks are mostly orthogonal and can be combined in future work.\n> Q2. In plain terms, what exactly is the subset of configurations A and how is it pre-selected?\n\nEach element of the subset A is a combination of separators (e.g., Gomory, Clique) to activate; we call this a configuration and it can be thought of as a binary vector of length the number of separators (17 for SCIP). We select A from the full configuration space by choosing configurations that are effective but without being redundant. To do so, we use a small training set for each MILP class (100 instances) and semi-randomly generating and evaluating around 2000 configurations to select the target subset A of size around 15-30. The specific strategy leverages submodularity, i.e., diminishing marginal returns on performance with more configurations, which justifies the use of a greedy strategy to select the configuration subset A.\n> Q3. What is the relevance of Propositions 1 and 2 in the context of MILP?\n\nOur learning method first constructs a subset A of high quality separator configurations for the MILP. We then learn a network $\\tilde{f}_A$ to select a configuration among A.\n\nProp. 1 characterizes the test performance of $\\tilde{f}_A$ as a function of the subset A, which sheds light on how to construct a good A: an ideal subset A allows $\\tilde{f}_A$ to have (1) high training performance, obtained when **some** configuration in A achieves good performance for *any* MILP instance in a training set, and (2) low generalization gap, achieved when **each** configuration in A has good performance *across* MILP instances in a test set. In practice, we approximate the generalization gap using the training set  (see empirical justification in Appendix Fig. 5). \n\nProp. 2 formalizes the diminishing marginal returns (submodularity) of $\\tilde{f}_A$’s training performance with respect to A, which enables a greedy algorithm to iteratively construct A. Based on Prop. 1, we further augment the greedy algorithm with a filtering criterion to improve the generation gap by eliminating ineffective configurations from A.\n\n> Q4. How exactly are the separator nodes S used in the representation of the instances?\n\nOur network takes a separator configuration-MILP instance pair as input and predicts the time improvement of applying the configuration to the instance.\n\nWe represent each configuration by M separator nodes; each node has M+1 dimensional input features, representing whether the separator is activated (the first dimension), and which separator it is (one-hot M-dimensional vector). Our GNN input graph connects each separator node with all variable and constraint nodes; the input features of latter nodes contain the MILP instance information (see Appendix A5.2).\n> Q5. How exactly do you consider instances in which neither SCIP nor SCIP with your separator selection were able to solve?\n> \n> \n> In the case of the problems that do not finishing running on time, it would make more sense to look for the best solution found or the remaining optimality gap.\n\nFor larger MILP classes, we exclude instances that cannot be solved by SCIP default to a specific optimality gap within a predefined time limit, ensuring most instances are retained (optimality at 120s for NNV, and a gap of 10% at 300s for MIPLIB and Load Balancing, see Appendix A.6.5); 26% of NNV instances are excluded while all instances from Load Balancing are retained. Our experiments then consider the time improvement of all instances to reach the respective gaps. In general, we can increase the gap threshold to allow learning on harder MILP classes.\n\nWe conduct a new experiment where we change the objective to the relative gap improvement, which is amenable to instances that cannot be solved to optimality under a given time limit. For example, on Load Balancing where SCIP default has a average gap of 32% within 16s, L2Sep is able to reduce the average gap to 21% (34% improvement). We refer the reviewer to General Response [GR3] for details.\n> Eq. 2: Why is the term on the left repeated at the end of the equation?\n\nThe test performance $\\Delta(\\tilde{f}_A)$ on an unknown test set can be decomposed into (1) the training set performance $\\hat{\\Delta}(\\tilde{f}_A)$, and (2) the generalization gap $\\hat{\\Delta}(\\tilde{f}_A) - \\Delta(\\tilde{f}_A)$."}, {"review_id": "jrftoxfaUp", "reviewer": "Reviewer_JiCg", "summary": "This paper studies learning to manage separators to improve MILP solvers. Specifically, it learns a policy to determine which separators to use to generate cutting planes. The task is well formulated and experiments on many datasets demonstrate the effectiveness of the proposed model.", "questions": "See Weakness.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.\tThe paper is well written. Especially the problem is well formulated.\n2.\tThe paper identifies the opportunity of managing separators to improve MILP solvers.\n3.\tExperiments on many datasets demonstrate the effectiveness.", "weaknesses": "In general, I think this paper is an OK work, but it is just borderline to the NeurIPS bar, so I only give borderline accept.\n\nThere have been many works that study different parts of branch-and-bound, e.g., cut selection and node selection. Replacing one of the solving stages to a learning method, which leads to improvements compared with heuristic rules, is unsurprising. However, in real applications, it would be impossible to replace every part to learned models because of the memory limitation. Whether the studied part is critical enough in branch-and-bound is an important question. Therefore, separator configuration may not be in a trend of the research community, and thus the impact of the proposed method may be limited.\n\nI would give some suggestions in improving the work. First, the authors can compare the focused task, i.e., separator configuration, with other solving stages to demonstrate its significance. Or the authors can compare the resource usage to show the proposed method is lightweight enough so that it can be used jointly with other methods. Or the authors can try to merge the proposed framework with existing work and conduct enough ablation study. Summarily, the authors should denonstrate the real usefulness of the proposed method beyond only its performance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the insightful suggestions from the reviewer and provide our response below. We hope the reviewer may also take a look at the general comments for our additional experiments, covering (1) interpretations of effective separators for each MILP class from our learning results (2) applying our method to a different MILP solver Gurobi, and (3) applying our method to a different metric (relative gap improvement under a fixed time). We hope that the reviewer may consider increasing our score accordingly if the new results adequately address the concerns.\n\n> Whether the studied part is critical enough in branch-and-bound is an important question.\n\nUnderstanding what separator families are useful for each MILP class is important to the mathematical programming community [1, 2] (also, see reviewer wvgK’s summary of our paper’s strengths). While a few separator families are known to be effective for specific MILP classes (e.g. Clique for Independent Set and FlowCover for problems with network flow substructures [2]), the knowledge remains limited and cannot cover the wide variety of separator families and MILP classes. \n\nDespite abundant research on cut selection, there is a surprising lack of work on the higher-level decisions such as configuring separators, or deciding whether to cut (B&C) or not (pure B&B) [3]. We hypothesize that this scarcity is because the abstract nature of the tasks poses challenges to acquiring useful heuristic information. Our work allows an automatic approach to detect effective separators for each MILP class, providing an important step toward understanding the interactions among separators and identifying when a specific separator is useful. It also allows for instance-level specification, enabling different configurations on different MILP instances. We refer the reviewer to General Response [GR1] for visualizations and interpretations of our learning results.\n\n*[1] Contardo, Claudio, Andrea Lodi, and Andrea Tramontani. \"Cutting Planes from the Branch-and-Bound Tree: Challenges and Opportunities.\" INFORMS Journal on Computing 35.1 (2023).*\n\n*[2] Dey, Santanu S., and Marco Molinaro. \"Theoretical challenges towards cutting-plane selection.\" Mathematical Programming 170 (2018).*\n\n*[3] Berthold, Timo, Matteo Francobaldi, and Gregor Hendel. “Learning to use local cuts.\" arXiv preprint arXiv:2206.11618(2022).*\n\n> First, the authors can compare the focused task, i.e., separator configuration, with other solving stages to demonstrate its significance. Or the authors can compare the resource usage to show the proposed method is lightweight enough so that it can be used jointly with other methods.\n\n**The Immediate and Multi-step Effect of Separator Configuration in the B&C Process:**\n\n1. immediate: some separators take a long time to run, but generate mostly low-quality cuts that are ultimately never selected by the downstream cut selector. Deactivating those separators leads to an immediate time improvement by reducing the time to generate the cut pool. \n2. multi-step: improved separator configuration can tighten the dual bound faster through better-selected cuts; it may also accelerate other B&C components such as branching (e.g. strong branching requires solving many children LPs and hence may benefit from tighter dual bounds).\n\nThe following table presents the total solve time and total separator execution time for our complete method L2Sep and SCIP default on several MILP classes. We report the median and standard deviation evaluated on 100 instances for each class. L2Sep significantly reduces the total separator execution time. Upon closer examination, we find L2Sep adeptly deactivates expensive yet ineffective separators while activating effective ones.\n\n||Total Solve Time (L2Sep)|Total Separator Execution Time (L2Sep)|Total Solve Time (SCIP Default)|Total Separator Execution Time (SCIP Default)|\n|-|-|-|-|-|\n|Comb. Auc.|**0.65s (2.36s)**  |**0.02s (0.054s)**|3.01s (4.60s)   |1.39s (1.14s)|\n|Indep. Set|**3.81s (116.42s)**|**0.35s (9.94s)** |13.16s (120.89s)|7.38s (37.94)|\n|NNV|**20.75s (18.56s)**|**0.16s (0.13s)** |34.76s (25.05s) |6.58s (8.05s)|\n||\n\nIn Fig. 3 of the rebuttal pdf, we plot the primal-dual bound curves (median and standard error) of L2Sep and SCIP default on Independent Set and NN Verification. The significantly faster dual bound convergence of L2Sep demonstrates the multi-step effect of improved separator configurations. We further summarize the synergistic interaction effects between separator selection and other B&C components (branching, dual LP) in the next table. Notably, even though our method does not modify branching, the branching solve time is reduced.\n\n||Strong Branching Time|Pseudocost Branching Time|Dual LP Time|\n|-|-|-|-|\n|Comb. Auc. (L2Sep)|0.31s (1.15s)|0.35s (1.46s)|0.08s (0.58s)|\n|Comb. Auc. (SCIP Default)|0.41s (1.79s)|0.45s (2.17s)|0.18s (0.83s)|\n|Indep. Set (L2Sep)|2.82s (21.44s)|3.01s (22.29s)|0.3s (73.95s)|\n|Indep. Set (SCIP Default)|3.92s (19.68s)|4.6s (21.67s)|1.14s (55.51s)|\n|NNV (L2Sep)|6.56s (4.06s)|8.18s (4.81s)|3.67s (6.52s)|\n|NNV (SCIP Default)|8.31s (5.55s)|9.69s (6.13s)|5.07s (5.81s)|\n||\n\n**Resource usage of learned separator configuration v.s. other B&C parts (cut selection, branching):** At inference time, we require only two model calls (two separator configurations) during each MILP solve. In contrast, learning to branch or cut selection requires model calls at a higher frequency, such as at each node of the B&C tree (branching) or at each separation round (cut selection). Moreover, each model call for cut selection requires evaluating each cut in the cutpool ($\\approx 10^2-10^3$), whereas each of our model calls is more efficient due to the reduced number of separator configurations to evaluate ($\\approx 20-30$, enabled by our restricted space). As such, our method is lightweight enough to be integrated during the solve process. \n\n\n\n\n"}, {"review_id": "JClqiV5lOf", "reviewer": "Reviewer_TfAQ", "summary": "The paper proposes a pipeline for a learning-enhanced cut separation management in modern MIP solvers (specifically, in the academic solver SCIP). To pick a promising subset of the large number of possible settings, the authors derive a data-driven and theoretically motivated method to focus on specific configurations that are expected to perform well. The actual policy on how cut separators are used during a MIP solving run are then learned over the restricted configuration space. The experimental results show significant solve-time improvements for a variety of benchmark MIP classes and test sets; this holds both when learning within MIP subclasses and when learning within heterogeneous benchmark sets such as MIPLIB. The presented work has the potential to replace current fixed, heuristic solver settings for cutting plane separation by carefully learned policies that often yield large speed-ups, which in turn can increase the size of problem instances that can be solved to optimality, and therefore represents a very notable advancement in data-driven MIP solving techniques.\n\n-- update: I have read and acknowledged all other reviews and the authors rebuttals, see discussion. --", "questions": "- there are several (minor) typos throughout paper and supplementary document (e.g., no comma after \"e.g.\", \"c.f.\" or \"v.s.\" instead of \"cf.\" and \"vs.\", \"constraint\" <-> \"constrained\" (caption of Fig.2), \"contrary\" <-> \"contrast\" (l.193), \"included A\" <-> \"included in A\" (l. 239), \"which we provide comparision\" <-> \"for which we provide comparison\" (l. 311), \"U Stuhl\" (ref. [47] -- what's the first name?))\n- some wordings are a bit inaccurate (at least when not having seen the supplementary document yet, i.e., when reading just the first paper):\n  * l.19: \"lower bound\" -- this implies that the problem is a minimization problem, which is not specified here (only in the supplement). Maybe clarify, or use \"dual bound\"?\n  * l. 66 and again later: The product-sign (\\prod , large Pi) should be a *Cartesian* product-sign\n  * Prop. 1 is referred to as \"lemma\" in the paragraph preceding it.\n   * Sect. 3.2: \"network\" kind of drops out of nowhere -- please clarify a bit here that neural networks are used for the discussed task\n   * in Tab. 1 and 3 at least: \"higher the better\" only applies to the median; for standard deviation, lower is better!\n   * is the reported standard deviation given in percent deviation from the default or as percent variation from the median values? how often, if at all, does reconfiguration actually slow down the solver? what are the mean/average deviations from default? \n- it would be good to clarify in the main paper that the separation rounds after which configuration updates occur are specified in advance; this only becomes clear in the supplementary document, so reading the main paper, one wonders how this is decided and/or if it is part of the learning procedure to decide when to update configurations. Also, are there cases in which the MIP solver terminates before the number k of updates has been performed?\n- have you tried reverting to the default configuration as the last update? \n- which LP solver was used by SCIP to solve the relaxations? SoPlex? \n- were all MIPs solved in single-thread mode?", "limitations": "Limitations have been appropriately addressed (at least in the supplementary material).", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "Besides the impressive empirical results, the theoretical justification/motiviation for the configuration pre-selection is a strength of this work. Moreover, although the work spans quite many different and subtle aspects of the intricate workings of MIP solvers and employs different machine learning techniques, the authors did an excellent job in condensing their work into an understandable and well-written main paper; the supplementary material, while containing the technical proofs, is largely additional information that well complements the main paper but is mostly not necessary to follow the main paper.", "weaknesses": "It appears to have become common practice to submit papers to NeurIPS (and ICML) whose actual, main content is put in a separate \"Supplementary Material\" document whose length far exceeds that of the supposed main paper. This paper is only a partial exception -- the main paper provides enough information and details to stand on its own except for the most technical bits, which can then be found in the very long Appendix (supplementary document; three times as long as the main paper) along with a host of additional information. Thus, it may be considered a weakness of the paper to have such a long Appendix, because this format bears the danger of the formally most important parts of the work (proofs; algorithm details and specific setups) not being reviewed thoroughly due to the short review period and high review load of reviewers at these conferences. I cannot exclude myself from this -- I simply did not have the time to rigorously check all the details in the long supplementary document, and therefore cannot give a definitive answer regarding the proofs' correctness beyond \"believing\" everything appears to be well in order. In this regard, I cannot help but wonder if a full journal paper would not be the better way to publish results that simply do not fit into the 9-page limit. But, again, I have seen papers that exploit the main paper/supplementary material split in a much worse way; for the present work, it actually hardly bothered me because the main paper is nearly self-sufficient. Nevertheless, if I have to point to a weakness, this aspect is what stands out to me.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are delighted and truly appreciate the reviewer‘s positive feedback on our work. We made a great effort to integrate empirical methodology with theoretical justification, aiming at bridging an important gap in the existing learning for MILP literature that has been predominantly empirical. We provide a response to the reviewer’s questions below, and we include additional experiments as suggested by other reviewers in the general response, covering (1) interpretations of effective separators for each MILP class from our learning results (2) applying our method to a different MILP solver Gurobi, and (3) applying our method to a different metric (relative gap improvement under a fixed time).\n\n> is the reported standard deviation given in percent deviation from the default or as percent variation from the median values? how often, if at all, does reconfiguration actually slow down the solver? what are the mean/average deviations from default?\n\nThe following table shows the percentage of test instances in each MILP class for which our learned configuration improves over SCIP default (% win). We observe that, while not always, our learned model does accelerate SCIP default for the majority of instances.\n\n||Bin. Pack.|Max. Cut|Pack.|Comb. Auc.|Indep. Set|Fac. Loc.|NNV|MIPLIB|Load Balancing|\n|-|-|-|-|-|-|-|-|-|-|\n|% win (ours > default)|91.2%|100%|75%|98.9%|95.7%|74%|88.5%|67.5%|84%|\n|standard deviation (from mean), Table 1 |(34.2%)|(11.3%)|(39.3%)|(26.2%)|(27.8%)|(39.6%)|(33.9%)|(73.1%)|(20.3%)|\n| deviation from median|(39.0%)|(11.6%)|(42.8%)|(29.3%)|(37.0%)|(43.5%)|(35.5%)|(78.8%)|(22.1%)|\n| deviation from default|(52.1%)|(68.4%)|(44.2%)|(67.2%)|(66.6%)|(46.3%)|(45.2%)|(75.3%)|(32.2%)|\n||\n\nIn our paper, we report the standard deviation from the mean $\\sqrt{\\frac{1}{N}\\sum\\limits_{i=1}^{N} (\\delta_i - \\bar{\\delta})^2}$ of each method, where $\\bar{\\delta} = \\frac{1}{N}\\sum\\limits_{i=1}^{N}\\delta_i$, and $\\delta_i$'s are the relative time improvement of each method from SCIP default on $N$ MILP test instances. In the table above, we further include the deviation from the median $\\sqrt{\\frac{1}{N}\\sum (x_i - x_{median})^2}$ and the deviation from SCIP default $\\sqrt{\\frac{1}{N}\\sum (x_i-0)^2}$ (since the time improvement of default from default is 0%), both for our complete method. We observe that the deviation from the median is similar to the deviation from the mean reported in Table 1, while the larger deviation from SCIP default demonstrates the ability of our method to achieve time improvement from the default parameters.\n\n> it would be good to clarify in the main paper that the separation rounds after which configuration updates occur are specified in advance; this only becomes clear in the supplementary document, so reading the main paper, one wonders how this is decided and/or if it is part of the learning procedure to decide when to update configurations. Also, are there cases in which the MIP solver terminates before the number k of updates has been performed?\n\nWe appreciate the reviewer for carefully reviewing the supplementary document. We will add clarifications in the main paper to state that the separation rounds are specified in advance. In our experiments, we set the second separator configuration ($k=2$) to be at around 15%-25% of the average total separation rounds for each MILP classes, and set the third separator configuration ($k=3$ in our Ablation Table 2) to be at around 25%-50%, as the early solving stage (e.g. earlier in the B&B tree) may benefit more from additional configuration updates. \n\nIt is an interesting suggestion to consider learning to decide when to update the configurations, but it comes with learning challenges as the search space becomes a larger, joint space of (which separation round to configure $\\times$ which configuration to choose). We consider this as a future work to explore additional search space reduction techniques to enable joint learning. While there are instances that terminate before the $k^{th}$ of updates has been performed, they only constitute a very small portion of all instances in our experience. Moreover, such instances that terminate before the $k^{th}$ configuration update likely have a short solve time (due to fewer separation rounds to solve the instance). The model at the $k^{th}$ configuration update can then focus on the harder instances that take longer to solve and further improve their solve time from default.\n\n> have you tried reverting to the default configuration as the last update?\n\nWe conduct an experiment where we revert to the default SCIP configuration at two intermediate separation rounds (20 and 40) for Ecole instances (Combinatorial Auction, Independent Set, and Capacitated Facility Location). We compare the time improvement for these two scenarios with our complete method, where we apply learned configuration updates for the entire solve process. Our results (median and standard deviation) are as follows:\n\n||Comb. Auc.|Indep. Set|Fac. Loc.|\n|-|-|-|-|\n|Revert to default at separation round 20|61.9% (31.3%)|39.3% (53.2%)|21.4% (40.8%)|\n|Revert to default at separation round 40|62.8% (31.4%)|61.3% (90.8%)|27.4% (40.9%)|\n|Ours: L2Sep|**66.2% (39.3%)**|**72.4% (27.8%)**|**29.4% (39.6%)**|\n||\n\nWe observe that the relative time improvement increases as our learned configurations cover more separation rounds,  demonstrating our learned method is able to achieve time improvement throughout the solve process.\n\n\n\n> which LP solver was used by SCIP to solve the relaxations? SoPlex?\n>\n>\n> were all MIPs solved in single-thread mode?\n\nWe use the default LP solver by SCIP, which is SoPlex [1], and solve all MIPs in single-thread mode.\n\n*[1] Gamrath, Gerald, et al. \"The SCIP optimization suite 7.0.\" (2020).*\n\n\n> typos and wording\n\nWe are very thankful that the reviewer points out typos and suggests wording changes. We will correct them in the updated paper.\n"}, {"review_id": "QAZVgjjVoy", "reviewer": "Reviewer_wvgK", "summary": "The authors use machine learning to decide how and when to toggle the on/off switches for different cutting plane families provided by SCIP, the fastest open-source MIP solver. Their learning algorithm outperforms the default setting of SCIP on various benchmark sets.", "questions": "The title/phrase “learning to separate” slightly misleading. The *separation problem* refers to the specific problem of generating a cut (from some class of cuts) that cuts off the LP optimum. The authors here are not concerned with that problem, rather they are concerned with the on/off toggle for a particular family of cuts that is being generated via SCIP’s separation routines.\n\nThe authors discuss generalization guarantees but do not cite or compare to any prior work on such theoretical guarantees for cutting planes/integer programming/tree search. It might be worth mentioning how this compares to that work and where it is different (ostensibly “learning to toggle” falls into some of the frameworks studied previously).\n\nAs mentioned previously, one of the most interesting questions that is completely missing: what cut families ended up being selected and working well for the different problem instances? To me this would be the most interesting set of conclusions, since it is well known that MIP solvers need to be tuned to yield improved performance. The question of what cuts work best for what problems is much more elusive. Overall, I would be much more in favor of acceptance if there was some discussion about this aspect. Presumably this question is already answered by the experiments the authors ran, and including some observations here would be great.\n\nGiven that the authors are controlling granular on/off parameters (and not fundamentally modifying the underlying algorithms), why not compare to a state-of-the-art solver like Gurobi or CPLEX, which are free for academic use and significantly faster than SCIP?\n", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The techniques used to deal with the high dimensional combinatorial space of possible configurations are interesting. The results are promising and yield speedups over SCIP default on established benchmark sets.\n\nThe interactions between different cut families is not an extremely well understood topic. It is nice to know that machine learning can help decide what families to activate, and when.\n", "weaknesses": "Ultimately I don’t think the proposed methodology is too novel, since it boils down to learning how to set on-off toggles for a variety of cut families. I acknowledge that this toggling is a critical component of tuning MIP solvers, but since this paper doesn’t mention what cut families ended up being selected and most useful for the different problem instances, I believe it leaves the most interesting question of what separator families worked best for which problems on the table. So methodologically this paper doesn’t seem too different from an array of previous algorithm configuration papers for MIP (e.g. Hydra-MIP by Xu, Hutter, Hoos, Leyton-Brown) that aim to tune parameters of a MIP solver from past data, but without any deeper principled investigation of what the parameters are actually doing. Hypothetically, it could be the case that turning off SCIP’s Gomory cut generation helps out for a class of MIPS, but maybe if the actual Gomory cut generation was tweaked performance would improve. Learning to toggle does not yield any such insights, as far as I can tell. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the actionable feedback in terms of interpreting the results, using other MILP solvers, and providing pointers to relevant theoretical works. We have made great efforts to address the reviewer’s concerns in our response below and have included additional experiments in the general response, covering (1) interpretations of effective separators for each MILP class from our learning results (2) applying our method to a different MILP solver Gurobi, and (3) applying our method to a different metric (relative gap improvement under a fixed time). We hope that the Reviewer will take these new results into account and increase our score if we have adequately addressed the main concerns.\n\n> As mentioned previously, one of the most interesting questions that is completely missing: what cut families ended up being selected and working well for the different problem instances?\n\nWe sincerely appreciate the reviewer’s excellent suggestions on interpreting our learning results. We provide visualizations and interpretations in General Response [GR1]. These visualizations lead to several intriguing observations, including (1) our learned model can automatically select separator families that are known to be effective for certain MILP class, and (2) our learned model can differentiate heterogeneous instance class and select customized separators tailored to different types of MILP instances.\n\nWe plan to include visualizations for all MILP classes in the Appendix of the updated paper. Given the alignment of effective separator families on standard MILP benchmarks between our learning model and the existing literature, we believe our learned model can serve as a valuable tool for guiding the automatic selection of separator families for different MILP classes, and inspiring the mathematical programming community to further investigate the interconnection between certain separators and MILP instances as suggested by our learning method.\n\n> Given that the authors are controlling granular on/off parameters (and not fundamentally modifying the underlying algorithms), why not compare to a state-of-the-art solver like Gurobi or CPLEX, which are free for academic use and significantly faster than SCIP?\n\nSCIP allows us to update separator configurations multiple times during a solve process (by modifying the source code), while state-of-the-art solvers Gurobi does not (separator configurations have to be fixed before the solve starts). Nonetheless, we can apply our method to Gurobi by configuring separators once before the solve starts. Inspired by the reviewer’s question, we perform this additional experiment in General Response [GR2]. We are delighted to report that our method is also effective in accelerating Gurobi.\n\n> The authors discuss generalization guarantees but do not cite or compare to any prior work on such theoretical guarantees for cutting planes/integer programming/tree search. It might be worth mentioning how this compares to that work and where it is different.\n\nWe thank the reviewer for providing references to relevant papers. We will include them in the updated paper. \n\nThe most relevant work [1] studies generalization of portfolio-based algorithm selection, where the procedure first selects a subset of algorithm parameter settings, and then, for a given problem instance, uses an algorithm selector to choose a parameter setting from the portfolio. We summarize the key differences below:\n\n- Our theoretical generalization analysis **directly informs** our empirical configuration subspace restriction algorithm, where we design a filtering criterion to improve the generalization bound. In contrast, the previous theoretical work analyzes the generalization bound on a *given* subspace construction procedure; however, their bound is not informative for designing the construction procedure, as it contains an abstract constant (representing the number of piecewise constant regions in the performance function [2]) which is unknown in practice and hence cannot be applied empirically. \n- the generalization bound in the previous work does not consider the influence of the quality and diversity of the parameter settings within a subset of a fixed size, which our generalization bound captures. In our experiments, we demonstrate that the quality of each configuration is important for a fixed size configuration subspace (see our ablation “Greedy Restr.” in Table 2 which does not apply our filtering criterion to consider individual configuration’s quality, and leads to suboptimal results).\n\nAdditional theoretical works investigate the generalization bound of the branch-and-cut framework, mainly focusing on cut selection [3, 4]. However, the analyses either rely on the structure of a specific MILP cut family (e.g. Chvátal-Gomory) or study how a selected cut affects the LP relaxation’s optimal solution, which cannot be generalized to the upstream, higher-level task of separator configuration. \n\n*[1] Balcan, Maria-Florina, Tuomas Sandholm, and Ellen Vitercik. \"Generalization in portfolio-based algorithm selection.\" Proceedings of the AAAI Conference on Artificial Intelligence (2021).*\n \n*[2] Balcan, Maria-Florina, et al. \"How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm design.\" Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. (2021).*\n\n*[3] Balcan, Maria-Florina F., et al. \"Sample complexity of tree search configuration: Cutting planes and beyond.\" Advances in Neural Information Processing Systems 34 (2021).*\n\n*[4] Balcan, Maria-Florina F., et al. \"Structural analysis of branch-and-cut and the learnability of gomory mixed integer cuts.\" Advances in Neural Information Processing Systems 35 (2022).*\n\n> The title/phrase “learning to separate” is slightly misleading.\n\nWe are happy to change the title to “Learning to configure separators in branch-and-cut”.  "}]

Author rebuttal:
# General Responses to All Reviewers
We thank each of the reviewers for their detailed and constructive comments. We provide the following additional interpretations and new experimental results in response to the reviewers’ suggestions.

$\ $
### [GR1] Interpretation analysis: The learned model recovers known facts from the literature regarding effectiveness of different separators

Reviewer wvgK inquired about interpretations of our learned model to understand the efficacy of different separators for different problem instances. In Rebuttal PDF Fig. 1 and 2 (see figure captions for explanations of the figures), we provide an investigation, summarize the findings below, and will include additional analysis for other MILP classes in the appendix. 

**Bin Packing:** It is known that instances with few bins approximates the Knapsack problem (Clique cuts are known to be effective [1]), and that instances with many bins approximates Bipartite Matching (Flowcover cuts can be useful [2]). We analyzed the separators activated by our learned model when we gradually decrease the number of bins, and observe that the prevalence of selected Clique and Flowcover cuts increased and decreased, respectively. This is illustrated in Fig. 1, right column.

**Other MILP classes:** We provide visualizations for Independent Set and MIPLIB in Fig. 2. Clique is known as an effective separator for Independent Set [3]; L2Sep automatically recovers this fact by frequently selecting configurations that activate Clique. Meanwhile, we see that L2Sep discovers the instance heterogeneity of MIPLIB, resulting in a more dispersed distribution of selected configurations.

*[1] Boland, Natashia, et al. "Clique-based facets for the precedence constrained knapsack problem." Mathematical programming 133 (2012).*

*[2] Van Vyve, Mathieu. "Fixed-charge transportation on a path: Linear programming formulations." International Conference on Integer Programming and Combinatorial Optimization. (2011).*

*[3] Dey, Santanu S., and Marco Molinaro. "Theoretical challenges towards cutting-plane selection." Mathematical Programming 170 (2018).*

$\ $
### [GR2] Learning-to-separate effectively accelerates state-of-the-art MILP solver Gurobi

As inquired by Reviewer wvgK, we replicated our method L2Sep with Gurobi (containing a larger set of 21 separators). As Gurobi is closed source, we cannot change configurations after the solving process starts$^1$, so we only consider one stage of separator configuration.

To our delight, L2Sep achieves significant relative time improvements over the Gurobi default, with gains ranging from 12% to 56%. This result confirms the efficacy of L2Sep as an automatic instance-aware separator configuration method. Similar to our results for SCIP, we observe that (1) our two heuristic sub-components (See Section 4.1) achieve impressive speedup from Gurobi default, indicating the high quality of our restricted configuration subspace, and (2) our complete method L2Sep improves the performance further, highlighting the benefit of learning instance-aware configurations. Our results (median and standard deviation) are as follows:
||Method|Max. Cut|Pack.|Comb. Auc.|Fac. Loc.|
|-|-|-|-|-|-|
||Default Time (s)|0.087 (0.051)|4.048 (3.216)|1.687 (3.596)|27.872 (14.733)|
|Heuristic Baseline|Gurobi Default|0%|0%|0%|0%|
||Random|18.6% (49.0%)|15.5% (28.2%)|-10.7% (69.1%)|13.4% (46.0%)|
|Ours Heuristic Variants|Inst. Agnostic Configuration|35.1% (35.8%)|22.9% (39.4%)|3.1% (65.3%)|40.6%  (48.1%)|
||Random within Rest. Subspace|37.3% (48.0%)|24.3% (32.2%)|5.1% (84.2%)|40.2% (46.8%)|
|Ours Learned|L2Sep|**45.4% (38.4%)**|**30.6% (29.6%)**|**12.6% (63.5%)**|**56.7% (35.7%)**|
||

*$^1$ Gurobi official documentation states “Parameters control the operation of the Gurobi solvers. They must be modified before the optimization begins.”*


$\ $
### [GR3] Learning-to-separate is effective under alternative objective (relative gap improvement)

Inspired by reviewer LDTP’s comments, we analyzed an alternative objective of the relative gap improvement under a fixed time limit. Let $g_0(x)$ and $g_\pi(x)$ be the primal-dual gaps of instance $x$ using the SCIP default and another configuration strategy $\pi(x)$ under a fixed time limit $T$. We define the relative gap improvement as $\delta_g(\pi(x), x) := (g_0(x) - g_\pi(x)) / (\max(g_0(x), g_\pi(x)) + \epsilon)$. We choose the denominator to avoid division by zero when the instance is solved to optimality.

In the table below, we find that L2Sep achieves a 15%-68% relative gap *improvement* over SCIP default. Specifically, the table presents the relative gap improvement (mean and standard deviation) of each method over SCIP default, along with the fixed time limit for various MILP classes (mostly around 50% of medium SCIP default solve time), and the absolute gap of SCIP default at the time limit. In Rebuttal PDF Fig. 3 (right two columns), we further plot histograms of the gap distribution on the entire dataset for L2Sep and SCIP default, where we observe L2Sep effectively shifts the *entire gap distribution* to a lower range. These results demonstrate the effectiveness of our method across different objectives, and its ability to improve primal-dual gaps for instances that cannot be solved to optimality within a given time limit.
||Method|Pack.|Comb. Auc.|Indep. Set|NNV|Load Balancing|
|-|-|-|-|-|-|-|
||Time Limit (s)|4.4|1.4|8.2|16|16|
||Default Gap|9.1e-4 (9.3e-4)|0.060 (0.098)|0.057 (0.059)|0.50 (0.80)|0.32 (0.13)|
|Heuristic Baseline|SCIP Default|0%|0%|0%|0%|0%|
||Random|-37.1% (41.7%)|-27.3% (69.1%)|-23.2% (44.1%)|-40.3% (72.8%)|-48.0% (35.8%)|
|Ours Heuristic Variants|Inst. Agnostic Configuration|11.9% (38.4%)|52.4% (45.3%)|23.5% (34.5%)|33.6% (72.1%)|14.0% (18.9%)|
||Random within Rest. Subspace|10.1% (42.5%)|54.1% (45.1%)|21.6% (33.7%)|24.8% (75.9%)|9.5% (17.6%)|
|Ours Learned|L2Sep|**15.4% (40.0%)**|**68.8% (38.2%)**|**29.6% (34.7%)**|**36.0% (68.2%)**|**34.2% (27.5%)**|
||

Meta-review: The paper has received mixed reviews that improved partially in the course of the rebuttal process. The good rebuttal has been noted. On the upside reviewers note impressive results and nice theoretical results as well as good writing. On the more pessimistic side, limited novelty and inclarities were noted.
The authors are urged to follow wvgK's recommendation for changing the title and other suggestions that have come up during the rebuttal process.
In summary, this paper has met the bar for acceptance for NeurIPS.
Decision: Accept (poster)