Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Model
Authors: Zhihai Wang
Xijun Li
Jie Wang
Yufei Kuang
Mingxuan Yuan
Jia Zeng
Yongdong Zhang
Feng Wu
Venue: ICLR 2023 poster (2023)
Keywords: mixed-integer linear programming
cut selection
deep reinforcement learning
sequence to sequence learning

Abstract: Cutting planes (cuts) are important for solving mixed-integer linear programs (MILPs), which formulate a wide range of important real-world applications. Cut selection---which aims to select a proper subset of the candidate cuts to improve the efficiency of solving MILPs---heavily depends on (P1) which cuts should be preferred, and (P2) how many cuts should be selected. Although many modern MILP solvers tackle (P1)-(P2) by manually designed heuristics, machine learning offers a promising approach to learn more effective heuristics from MILPs collected from specific applications. However, many existing learning-based methods focus on learning which cuts should be preferred, neglecting the importance of learning the number of cuts that should be selected. Moreover, we observe from extensive empirical results that (P3) what order of selected cuts should be preferred has a significant impact on the efficiency of solving MILPs as well. To address this challenge, we propose a novel hierarchical sequence model (HEM) to learn cut selection policies via reinforcement learning. Specifically, HEM consists of a two-level model: (1) a higher-level model to learn the number of cuts that should be selected, (2) and a lower-level model---that formulates the cut selection task as a sequence to sequence learning problem---to learn policies selecting an ordered subset with the size determined by the higher-level model. To the best of our knowledge, HEM is the first method that can tackle (P1)-(P3) in cut selection simultaneously from a data-driven perspective. Experiments show that HEM significantly improves the efficiency of solving MILPs compared to human-designed and learning-based baselines on both synthetic and large-scale real-world MILPs, including MIPLIB 2017. Moreover, experiments demonstrate that HEM well generalizes to MILPs that are significantly larger than those seen during training.

Published as a conference paper at ICLR 2023
LEARNING CUT SELECTION FOR MIXED-INTEGER LINEAR PROGRAMMING VIA HIERARCHICAL SEQUENCE MODEL
Zhihai Wang Xijun Li Jie Wang Yufei Kuang', Mingxuan Yuan?,
Jia Zeng', Yongdong Zhang Feng Wu
CAS Key Laboratory of Technology in GIPAS, University of Science and Technology of China
2 Noah's Ark Lab, Huawei Technologies
Institute of Artificial Intelligence, Hefei Comprehensive National Science Center
ABSTRACT
Cutting planes (cuts) are important for solving mixed-integer linear programs (MILPs), which formulate a wide range of important real-world applications. Cut selection-whis aims to select a proper subset of the candidate cuts improve the efficiency of solving MII.Psheavvif depends on (P1) which cuts should be preferred, and (P2) how many cuts should be selected. Although many modern MILP solvers tackle (P1)-(P2) by manually designed heuristics, machine learning offers a promising approach to learn more effective heuris- tics from MILPs collected from specific applications. However, many exist- ing learning- based methods focus on learning which cuts should be preferred, neglecting the importance of learning the number of cuts that should be se- lected. Moreover, we observe from extensive empirical results that (P3) what order of selected cuts should be preferred has significant impact on the ef- ficiency of solving MILPs as well. To address this challenge, we propose a novel hierarchical sequence model (HEM) to learn cut selection policies via re- inforcement learning. Specifically, HEM consists of a two-level model: (1) a higher-level model to learn the number of cuts that should be selected, (2) and a lower-level model-thaa that formulates the cut selection task as a sequence to se- quence learning problem-to learn policies selecting size determined by the higher-level model. To the best of our knowledge, HEM is the first method that can tackle (P1)-(P3) in cut selection simultaneously from a data-driven perspective. Experiments show that HEM significantly improves the efficiency solving MILPs compared to human-designed and learning- based baselines on both synthetic and large-scale real-world MILPs, including MI- PLIB 2017. Moreover, experiments demonstrate that HEM well generalizes to MILPs that are significantly larger than those seen during training. Code is avail- able at |htps:: http//ttttuuutett/ com Swtmm/MIRAAAaa USTC HoM-T (Py- Torch version), and http:////....eeeeoeeooeaan/eeeee htwp://pw.eeemmmmm/eeeeeeeee (MindSpore version).
ordered subset with the
INTRODUCTION
Mixed-integer linear programming (MILP) is general optimization formulation for wide range of important worldw applications, such as supply chain management (Paschos 2014), production planning (Jünger al. 2009). scheduling (Chen 2010), facility location (Farahani Hekmatiar 2009). bin packing (Nair et al. 2020), etc. A standard MILP takes the form of
min(c x/Ax < b,x Z for all j E I},
where e E R", A E Rmxx, b R"" " I, denotes the j-th entry of vector x, I C {l,..., n denotes the set of indices of integer variables, and =¹ denotes the optimal objective value of the problem
"Equal contribution. This work was done when Zhihai Wang was an intern at Huawei Noah's 's Ark Lab. "orresponning author; jiewangx ustc.edu.cn

---

Published as a conference paper at ICLR 2023
in However, MILPs can be extremely hard to solve they are N'P-hard problems (Bixby
ct al. 2004). To solve MILPs, many modern MILP solvers (Gurobi 2021 Bestuzheva et al. 2021
FICO Xpress 2020) employ a
tree search algorithm Land & Doig 2010), in
which a linear programming (I.P) relaxation of a MILP (the problem in or its subproblems) is
solved at each node. To further enhance the performance of the tree search algorithm, cutting planes
| (cuts) [oomory] 1960) are introduced to tighten the LP relaxations (Achterberg) [000 [Bengio et al.)
2021
Existing work on cuts falls into two categories: cut generation and cut selection (Turner
et al. 2022). Cut generation aims to generate cuts, i.e., valid linear inequalities that tighten the LP relaxations (Achterberg 2007). However, adding all the generated cuts to the LP relaxations can pose a computational problem (Wesselmann & Stuhl 2012). To further improve the efficiency of solving MILPss cut selection is proposed to select a proper subset of the generated cuts (Wesselmann) & &Sthh 2012). In this paper, we focus on the cut selection problem. which has a significant impact on the overall solver performance (Achterberg 2007]
Tang ct al. 2020 Paulus et al. 2022).
Cut selection heavily depends on (P1) which cuts should be preferred, and (P2) how many cuts should be selected (Achterberg 2007 Dey & Molinaro 2018b). Many modern MILP solvers Xpress (020) tackle (P1)-(P2) by hard-coded heuris- ties designed by experts. However, hard-coded heuristics do not take into account underlying pat- terns among MILPs collected from certain types of real-world applications, e.g., day-to-day produc- tion planning, bin packing, and vehicle routing problems (Pochet & Wolsey [2006] Laporte] [2009] Nair et al., 20200) To further improve the efficiency of MILP solvers, recent methods (Tang et al., 2020 Paulus et al. 2022] Huang et al., 2022) propose to learn cut selection policies via machine learning, especially reinforcement learning. They offer promising approaches to learn more effec- tive heuristics by capturing underlying patterns among MILPs from specific applications (Bengio ct al. 202T). However, many existing learning- based methods (Tang et al., 2020; Paulus et al. Huang et al.) 2022) whhich learn scoring function to measure cut quality and select fixed ratio/number of cuts with high scores sorres-suffer from two limitations. First, they learn which cuts should be preferred by learning a scoring function, neglecting the importance of learning the num- ber of cuts that should be selected (Dey & Molinaro| (201b). Morcover, we observe from extensive empirical results that (P3) what order of selected cuts should be preferred significantly impacts the efficiency of solving MILPs as well (see Section 3) Second, they do not take into account the interaction among cuts when learning which cuts should be preferred, they score each cut inde- pendently. As a result, they struggle to select cuts that complement each other nicely, which could severely hinder the efficiency of solving MILPs (Dey & Molinaro 20186). Indeed, we empirically show that they tend to select many similar cuts with high scores (see Experiment 4 in Section 5
(Gurobi 202 Bestuzheva et al.
2022
To address the aforementioned challenges, we propose a novel hierarchical sequence model (HEM) to learn cut selection policies via reinforcement learning. To the best of our knowledge, HEM is the first sarming-based method that can tackle (P1)-(P3) simultaneously by proposing a two-level model. Specifically, HEM is comprised of (1) a higher-level model to learn the number of cuts that should be selected, (2) and a lower-level model to learn policies selecting an ordered subset with the size determined by the higher-level model. The lower-level model formulates the cut selection task as a sequence to sequence learning problem, leading to two major advantages. First, the sequence model is popular in capturing the underlying order information (Vinyals et al.] 2016), which is critical for tackling (P3). Second, the sequence model can well capture the interaction among cuts, as it models the joint conditional probability of the selected cuts given input sequence of the candidate cuts. As a result, experiments show that HEM significantly outperforms human- dumanndesigned and learning-basee based baselines in terms of solving efficiency on three synthetic MILP problems and seven challenging MILP problems. The challenging MILP problems include some benchmarks from MIPLIB 2017 Gleixner et al. (02T) and large-scale real-world production planning problems. Our results demonstrate the strong ability to enhance modern MILP solvers with our proposed HEM in real-world applications. Moreover, experiments demonstrate that HEM can well generalize to MILPss that are significantly larger than those seen during training.
2 BACKGROUND
Cutting planes. Given the MILP problem in ①.. we drop all its integer constraints to obtain its linear programming (LP) relaxation, which takes the form of
zip A min(c T x/AAx < R.)
2

---

Published as a conference paper at ICLR 2023
Since the problem in 2 expands the feasible set of the problem in (T. we have 2ip 2* We denote any lower bound found via an LP relaxation by a dual bound. Given the LP relaxation in 2.. cutting planes (cuts) are linear inequalities that are added to the LP relaxation in the attempt to tighten it without removing any integer feasible solutions of the problem in (T) Cuts generated by MILP solvers are added in successive rounds. Specifically, each round lo involves (i) solving the current LP relaxation, (ii) generating a pool of candidate cuts Ch,, (ii)) selecting a subset S C C* (iv) adding S to the current LP relaxation obtain the next LP relaxation, (v) and proceeding the next round. Adding all the generated cuts to the LP relaxation would maximally strengthen the LP relaxation and improve the lower bound each round. However, adding too many cuts could lead to large models, which can increase the computational burden and present numerical instabilities (Wesselmann & Stuhl 2012). Therefore, cut selection is proposed to select a proper subset of the candidate cuts, which is significant for improving the efficiency of solving MILPs (Tang et al.. 2020).
Branch-and-cut. In modern MILP solvers, cutting planes are often combined with the branch-and bound algorithm (Land & Doig 2010), which is known as the branch-and-cur algorithm (Mitchell, 2002]. Branch-anddbound techniques perform implicit enumeration by building a search tree, in which every node represents subproblem of the original problem in II) The solving process begins by selecting a leaf node of the tree and solving its LP relaxation. Let x" be the optimal solution of the LP relaxation. If x" violates the original integrality constraints, two subproblems (child nodes) of the leaf node are created by branching. Specifically, the leaf node is added with constraints 24 I [a]]] and x; 2 [xa] respectively, where I; denotes the i-th variable, x; denotes the i-th entry of vector x", and [] and [T denote the floor and ceil functions. In contrast, if x* is a (mixed-)ineee -integer solution of ( then we obtain an upper bound on the optimal objective value of (T). which we denote by primal bound. In modern MILP solvers, the addition of cutting planes is alternated with the branching phase. That is, cuts are added at search tree nodes before branching to tighten their LP relaxations. Since strengthening the relaxation before starting to branch is decisive to ensure an efficient tree search (Wesselmann & Stuhl 2012 Bengio et al.) 2021), we focus on only
adding cuts at the root node, which follows Gasse al. (2019); Paulus et al. (2022)
Primal-dual gap integral. We keep track of two important bounds when running branch-and-cuee i... the global primal and dual bounds, which are the best upper and lower bounds on the optimal objective value of ( respectively. We define the primal-dual gap integral (PD integral) by the area between the curve of the solver's global primal bound and the curve of the solver's global dual bound. We provide more details in Appendix
3 MOTIVATING RESULTS
Order (different datasets)
Order (different ratios)
We empirically show that the order of se- lected cuts, i.e., the selected cuts are added to the LP relaxations in this order, signif- icantly impacts the efficiency of solving MILPs. Moreover, we empirically show that the ratio of selected cuts matters sig- nificantly when solving MILPs (see Ap- pendix G.I.. Please see Appendix [D22 for details of the datasets used in this section.
Adlev 1.5 (62%)
ratio:0.4
stdev, 0.05 (6%)
D4
sidee 0.12 (6
6 6
stdry 0.2 (209)
D3-
sidew (26%)
(idew 0.17 (15%)
ratio:0.8 8
-itder 0.11 (12%))
ratio:1.0
indevttite (18%)
0.5 1.0 1.5 25 3.0 3.5
0.0 0.4 0.6 0.8 1.4
primal-dual gap integral
primal-dual gap integral
(a) Evaluate RandomAll on (b) Evaluate RandomNy on five different datasets.
MIPLIB mixed neos.
We design two cut selection heuristics, namely RandomAll and RandomNV (see Section for details), which both add the same subset of cuts in ran- dom order for given MILP The results in (a) and (b) show that adding the same selected cuts in different or- der leads variable overall solver performance.
Figure 1:
Order matters. Previous work (Bixby 1992 Maros] 2002. Li et al.] 2022) has shown that the order of constraints for a given linear program (LP) significantly impacts its constructed initial basis, which is important for solving the LP. As a cut is a linear con- straint, adding cuts to the LP relaxations is equivalent to adding constraints to the LP relaxations. Therefore, the order of added cuts could have significant impact on solving the LP relaxations as well, thus being important for solving MILPs. Indeed, our empirical results show that this is the case. (1) We design RandomAll cut selection rule, which randomly permutes all the candidate cuts, and adds all the cuts to the LP relaxations in the random order. We evaluate RandomAll on five challenging datasets, namely D1, D2, D3, D4, and D5. We use the SCIP 8.0.0 (Bestuzheva et al.) 202T) as the backend solver, and evaluate the solver performance by the average PD integral within time limit. We evaluate RandomAll All on each dataset over ten random seeds, and each bar in Figure
3

---

Published as a conference paper at ICLR 2023
la shows the mean and standard deviation (stdev) of its performance on each dataset. As shown in Figure Tal the performance of RandomAll on each dataset varies widely with the order of selected cuts. (2) We further design a RandomNV cut selection rule. RandomNV is different from Rando- mAll in that it selects a given ratio of the candidate cuts rather than all the cuts. RandomNV first scores each cut using the Normalized Violation (Huang al. (022) and selects a given ratio of cuts with high scores. It then randomly permutes the selected cuts. Each bar in [bjshows the mean and stdev of the performance of RandomNV with a given ratio on the same dataset. Figures Ia and 1b show that adding the same selected cuts in different order leads to variable solver performance, which demonstrates that the order of selected cuts important for solving MILPs.
LEARNING CUT SELECTION VIA HIERARCHICAL SEQUENCE MODEL
In the cut selection task, the optimal subsets that should be selected are inaccessible, but one can assess the quality of selected subsets using a solver and provide the feedbacks to learning algorithms. Therefore, we leverage reinforcement learning (RL) to learn cut selection policies. In this section, we provide a detailed description of our proposed RL framework for learning cut selection. First, we present our formulation of the cut selection as a Markov decision process (MDP) (Sutton & Barto 2018). Then, we present a detailed description of our proposed hierarchical sequence model (HEM). Finally, y, we derive a hierarchical policy gradient for training HEM efficiently.
Reinforcement Learning Formulation
1. Environment
2. Agegtt hierarchical sequence model
af+ A
As shown in Figure 2 we formulate a MILP solver as the environment and our proposed HEM as the agent. We consider an MDP de- fined by the tuple Ar, f)). Specifically, we specify the state space S, the action space A, the reward function r : S x A + R, the tran- sition function f. and the terminal state in the following. (1) The state space S. Since the cur- rent LP relaxation and the generated cuts contain the core information for cut selection, we define state 8 by (Mip, C, xip). Here MrP denotes the mathematical model of the current IP relax- ation, C denotes the set of the candidate cuts, and xip denotes the optimal solution of the LP relaxation. To encode the state information, we follow /Achterberg (2007); Huang et al. (2022) to design thirteen features for each candidate cut based on the information of (Mip, C, x..). That is, we actually represent state s by sequence of thirteen-dimensional feature vectors. We present details of the designed features in Appendix F.1 (2) The action space A. To take into account the ratio and order of selected cuts, we define the action space by all the ordered subsets of the candidate cuts C. It can be challenging to explore the action space efficiently, as the cardinality of the action space can be extremely large due to its combinatorial structure. (3) The reward function r. To evaluate the impact of the added cuts on solving MILPs, we design the reward function by (i) measures collected at the end of solving LP re- laxations such as the dual bound improvement, (ii) or end-of-run statistics, such as the solving time and the primal-dual gap integral. For the first, the reward r(s, a) can be defined as the negative dual bound improvement at each step. For the second, the reward r(s, a) can be defined as zero except for the last step (sT.or) in trajectory, i.e., r(st, is defined by the negative solving time or the negative primal-dual gap integral.
sture
1.7MM encoder
0 S Pyy gensrated cuts
fenture voctors
MLP
higher-level policy w
MILP solver
rabio
Fewardl
action
duta: (s.r)
polnter network
update:
8
100,00)
(99,6))))
lower-Ievel policy m
3. Trainer
Figure 2: Illustration of our proposed RL frame- work for learning eut selection policies. We for- mulate a MILP solver the environment and the HEM as the agent. Moreover, we train HEM via hierarchical policy gradient algorithm.
(4) The transition function f. The transition function maps the current state 8 and the action a to the next state 8', where s' represents the next LP relaxation generated by adding the selected cuts at the current LP relaxation. (5) The terminal state. There is no standard and unified criterion to determine when to terminate the cut separation procedure (Paulus et al. 2022). Suppose we set the cut separation rounds T, then the solver environment terminates the cut separation after T rounds. Under the multiple rounds setting (i.e., T > 1), we formulate the cut selection as Markov decision process. Under the one round setting (i.e., T = 1), the formulation can be simplified as a contextual bandit.
Hierarchical Sequence Model
4

---

Published as a conference paper at ICLR 2023
Motivation. Let π denote the cut selection policy : S + P(A), where P(AA) denotes the prob- ability distribution over the action space, and <(-ls) denotes the probability distribution over the action space given the state We emphasize that learning such policies can tackle (P1)-(P3) in cut selection simultaneously. However, directly learning such policies is challenging for the following reasons. First, is challenging to explore the action space efficiently, as the cardinality of the action space can be extremely large due to its combinatorial structure. Second, the length and max length of actions (i.e., ordered subsets) are variable across different MILPs. However, traditional RL usually deals with problems whose actions have fixed length. Instead of directly learning the aforemen-
tioned policy, many existing learning- based methods (Tang et al.) 2020) Huang et al.) [0022] Paulus et al. 2022) learn scoring function that outputs score given a cut, and select a fixed ratio/number of cuts with high scores. However, they suffer from two limitations as mentioned in Section |
Policy network architecture. To tackle the aforementioned problems, we propose novel hier- archical sequence model (HEM) to learn cut selection policies. To promote efficient exploration, HEM leverages the hierarchical structure of the cut selection task to decompose the policy into two sub-policies, i.e., a higher-level policy x² and a lower-level policy n². The policy network architec- ture of HEM is also illustrated in Figure 2 First, the higher-level policy learns the number of cuts that should be selected by predicting a proper ratio. Suppose the length of the state is N and the predicted ratio is k, then the predicted number of cuts that should be selected is [N kj., where [. denotes the floor function. We define the higher-level policy by =² S - P((O, 1J., where x² (-1s) denotes the probability distribution over [0. 1] given the state s. Second, the lower-level policy learns to select an ordered subset with the size determined by the higher-level policy. We define the
lower-level policy by n² : S x [0, 1] + P(A), where >'(1ss, k) denotes the probability distribution over the action space given the state s and the ratio k. Specifically, we formulate the lower-level policy as a sequence model, which can capture the interaction among cuts. Finally, we derive the cut selection policy via the law of total probability, i.e., π Taa (s) (- (ax(as k:),, where k denotes the given ratio and di denotes the action. The policy is computed by an expectation, as us cannot determine the ratio k. For example, suppose that N 100 and the length of a is 10, then the ratio i can be any number in the interval (0. 0.11). Actually, we sample an action from the policy a by first sampling ratio l from x² and then sampling an action from n' given the ratio.
For the higher-level policy, we first model the higher-level policy as a tanh- Gaussian, i.e., a Gaussian distribution with an invertible squashing function (tanh), which is commonly used in deep reinforce- ment learning (Schulman et al. [017] HHarnoja et al.] 2018). The mean and variance of the Gaussian are given by neural networks. The support of the Gan--Gaussian is [-1, 1]. but ratio of selected cuts should belong to [o, 1]. Thus, we further perform a linear transformation on the tanh-Gaussian. Specifically, we define the parameterized higher-level policy by ng, (-Is) = 0.5 tanh (K) + 0.5, oe, where K ~ N(ue, (s), (s)). Since the sequence lengths of states are variable across different instances (MILPs), we use a long-short term memory (LSTM) (Hochreiter & Schmidhuber 1997)
network to embed the sequence of candidate cuts. We then use multi-layer perceptron (MLP) Goodffllow et al. (2166) to predict the mean and variance from the last hidden state of the LSTM.
For the lower-level policy, we formulate it as a sequence model. That is, its input is se- quence of candidate cuts, and its output is the probability distribution over ordered subsets of candidate cuts with the size determined by the higher-level policy. Specifically, given a state action pair (s, k, ax), the sequence model computes the conditional probability Te (anls, k) us- ing parametric model to estimate the terms of the probability chain rule, i.e., T/ (ax) 8s, k) Il Po, (ai.aa....., 1-1 ,,,,,,,,,, k,). Here s = {s² ,N..,,N) is the input sequence, m = [N k is the length of the output sequence, and a = {at...... a% is a sequence of m indices, each corresponding position in the input sequence s. Such policy can be parametrized by the vanilla quence model commonly used in machine translation (Sutskever et al. (0144) Vaswani et al.) 2017). However, the vanilla sequence model can only be applied to learning on single instance, as the number of candidate cuts varies on different instances. To generalize across different instances, we use pointer network (Vinyals al. 2015) Bello* et al. 2017)-wll to select a member of the input sequence as the output at each decoder step to parametrize mie (see Appendix F.4.I for details). To the best of our knowledge, we are the first formulate the cut selection task as a sequence to sequence learning problem and apply the pointer network to cut selection. This leads to two major advantages:
uses attention as pointer
(1) capturing the underlying order information, (2) and the interaction among cuts. This is also illustrated through an example in Appendix E
5

---

Published as a conference paper at ICLR 2023
Training: hierarchical policy gradient
For the cut selection task, we aim to find 0 that maximizes the expected reward over all trajectories
J Ba (-1s) (r(s,
(3)
where - 10,,0,00 02] with [0i, 02] denoting the concatenation of the two vectors, Te(au|s) = Ex (c1e) (ax k)], and fr denotes the initial state distribution.
To train the policy with a hierarchical structure, we derive a hierarchical policy gradient following the well-known policy gradient theorem (Sutton et al. 1999a; /Sutton & Barto 2018). Te(az,
Proposition 1. Given the cut selection policy To (a (s) Ex (1s) [To, (ax (s, k)] and the training
objective the hierarchical policy gradient takes the form of
8. J( 02]) kamp (115) [V, log(T), (ss)) ax]l.
Vo. J(02, 021) = kew (11)),arm, (- VV log mh, (axls, k)r(s, ax)]-
We provide detailed proof in Appendix A We use the derived hierarchical policy gradient to update the parameters of the higher-level and lower-level policies. We implement the training algorithm in a parallel manner that is closely related to the asynchronous advantage actor-critic (A3C) (Mnih al.)
2016). Due to limited space, we summarize the procedure of the training algorithm in Appendix F3..6 Moreover, we discuss some more advantages of HEM (see Appendix [F.433 for details). (1)
HEM leverages the hierarchical structure of the cut selection task, which is important for efficient exploration in complex decision-making tasks (Sutton et 1999b). (2) We train HEM via gradient- based algorithms, which is sample efficient (Sutton & Barto 2018).
EXPERIMENTS
Our experiments have five main parts: Experiment 1. Evaluate our approach on three classical MILP problems and six challenging MILP problem benchmarks from diverse application areas. Experiment 2. Perform carefully designed ablation studies provide further insight into HEM. Experiment 3. Test whether HEM can generalize to instances significantly larger than those seen during training. Experiment 4. Visualize the cuts selected by our method compared the baselines. Experiment 5. Deploy our approach to real-world production planning problems.
Benchmarks. We evaluate our approach on nine -ard MILP problem benchmarks. which con- sist of three classical synthetic MILP problems and six challenging MILP problems from diverse application areas. We divide the nine problem benchmarks into three categories according to the difficulty of solving them using the SCIP 8.0.0 solver (Bestuzheva et al.] 2021). We call the three categories easy, medium, and hard datasets, respectively. (1) Easy datasets comprise three widely used synthetic MILP problem benchmarks: Set Covering (Balas & Ho 1980), Maximum Indepen- dent Set (Bergman et al. 2016), and Multiple Knapsack (Scavuzzo et al. 2022). We artificially gen- erate instances following Gasse et al. ( [Sun et al.) (2020). (2) Medium datasets comprise MIK (Atamtürk) 2003) and CORLAT (Gomes et al. | (0088), ), which are widely used benchmarks for evalu- ating MII.P solvers (He al. 2014| al. 2020). (3) Hard datasets include the Load Balancing problem, inspired by real-life applications of large-scale systems, and the Anonymous problem, in- spired by a large-scale industrial application (Bowly al. (022]). Moreover, hard datasets contain benchmarks from MIPLIB 2017 (MIPLIB) (Gleixner et al. 2021). Although Turner et al. (2022) has shown that directly learning over the full MIPLIB can be extremely challenging, we propose to learn over subsets of MIPLIB. We construct two subsets, called MIPLIB mixed neos and MIPLIB mixed supportcase. Due to limited space, please see Appendix D.I for details of these datasets.
Experimental setup. Throughout all experiments, we use SCIP 8.0.0 (Bestuzheva et al. 2021 as the backend solver, which is the nate-of--the-ar open source solver, and widely used in research of machine learning for combinatorial optimization (Gasse et al. 2019 Huang et al. |202) Turner et al.)
2022 Nair et al.) 2020). Following Gasse et al. (2019) Huang et al. (0022); Paulus et al. (2022). we only allow cutting plane generation and selection at the root node, and set the cut separation rounds as one. We keep all the other SCIP parameters to default so as to make comparisons as fair and reproducible such as presolve and heuristics, are open, which ensures that our setup is consistent with the practice setting. Throughout all experiments, we set the solving time limit as 300 seconds. For completeness,
possible. We emphasize that all of the SCIP solver's advanced features,

---

Published as a conference paper at ICLR 2023
Table 1: Policy evaluation on the easy, medium, and hard datasets. The best performance is marked in bold. Let m denote the average number of constraints and n denote the average number of variables. We report the arithmetic mean (standard deviation) of the Time and PD integral.
Eacy: Set Covoring (o 1030 is 5000)
Bacy Maciman Indeperden Ser = 540, in 19030
Eany Miltgle Kropeact (n 730, in = 729
Timet)..
Imporeemenn:
inscymi
Timeto)
Imperement
Timett)
Improsernctl
NoCas
6.31 (5 61)
NA
56 06:59 136 [91
6.7% (6 661
NA
71.31 (51:75 74)
9.8 (27 (23.4)
NA.
16.41 (14 160
(5 17)
24-90
6/ 713
3.88 (44)
(3 37)
-0.20
16 66 755
Randon
67.08 (46 50)
52.46 (33.00
(25
-32.00
-56.50
16.70
61.0143.55)
13.04
21.75
(5.45)
-53.30
05.66 913
1880
11.10
9.99 (19,02)
-1.10
30.49 (22.1)
SRP
1:91 (1) 56)
69.00
2.45 (5.55)
72.30
21 (80.85)
76 (12 30
21.40
16 15 (16.45
HEM (Oun)
(0.30)
70,69
37.92 (8.46)
1.76 (3,09)
90,00
16.00 (26.31)
(960
35,00
(9:63)
Melian: MIK
Mediu Corlat
686)
Bulansing
Method
Timebo 1
PO inigra
(PD iniegri, (4)
Ingroveeent
Timetss 1
PO integral
JPD iniogr), (6)
Enprovenent
Timmno 1
PD insggal
(143 inagrra 5)
Impeovericct
Deliga::
179.52
(924.30)
64.10
75.20-11200 30)
2412.09 (5992
14.40
300,00
5589.9 (1012.95)
25.40
Randous
200 03133-1120 (28
2036 90 (935.17)
13.50
84.15 (124.34)
2501.98 (6433 1.5)
11.30
300.00 (0.09)
13621 20 (1 (62.02)
5,30
NV
299 76 33)
1642.60
67 $39 49)
-7.0
90.3 W0.66(128-9) 815
1075
70 (7025 55)
.8.10
300.000000 00.055
1591% 98 (971, 100
5:30
(5 545
2416
41)
-3.99
104 (111 BJ]
3155:05 (1039/99)
-11.00
30000000:073
19913.07 (969 951
5,90
SBP
286
81)
12:80
70.41
2023 57
25.20
300.00
12535.30
HIM (Oumn
(125.21
785.04 (79835)
46.70
88.31 (110.51)
1079,99 (268814)
61.48
3000 (0/94)
9496.12 (1018,55)
36.10
Had: Anmyymoss in 07551, (0001)
Rint MIP rrised ronn Do 6908 ro 3600)
Hast: MIP In uscued sugeettase de 18705
19910)
Metoad
Tinneta
insgguall...
(PD
Improeemnnt
(193 inaogral %)
NoDrss
245
00)
18N7 1076700 433
253
14082 79 (17433 57)
NA
170.00 (131 A0)
5017 06 314.00
NA
Rarsken
343 13:44900 21)
16850 11000 N7)
38 (26.5)
18506,
48 (17664 79)
4.41
88 (131 00)
10054 (11957
-1.07
NV
342.01 (08 63)
16073 (071 1.60
7.90
261.81 (54 10)
14379
06 (33306 54)
196
161.67 (131.4))
8667 (0 (969)) 30
5.64
FIT
044.94091-00 m7)
171 (9456 14)
6.30
260-53 (55-54 54
14001 (1770 41)
35 (1.1999)
WA11 (10964565)
-0.04
SUP
245/76 (12. 20)
1815946 (1651.855 1,855
0.50
255-48 (28.99)
13531.00 (12896 22)
7.65
(65 (1:5522)
14086 (1MEES-2)
25.57
241.46 (97.23)
16077.15 (9188.2))
12.10
248.66 (89.46)
8678.76 (12137..0))
60.77
162 (138.21)
68744.00 (6721197)
30.75
we also evaluate HEM with a much longer time limit of three hours. The results are given in Appendix G.6 We train HEM with ADAM (Kingma & Ba 2014) using the PyTorch (Paszke al. 2019). Additionally, we also provide another implementation using the MindSpore (Chen] [Che]] For simplicity, we split each dataset into the train and test sets with 80% and 20% instances. To further improve HEM, one can construct a valid set for hyperparameters tuning. We train our model on the train set, and select the best model the train Appendix F.3 for implementation details, hyperparameters, and hardware specification.
evaluate the test set. Please refer to
Baselines. Our baselines include five widely used human-designed cut selection rules and state-of- the-art (SOTA) learning-based method. Cut selection rules include NoCuts, Random, Normalized Violation (NV), Efficacy (Eff), and Default. NoCuts does not add any cuts. Default denotes the default cut selection rule used in SCIP 8.0.0. For learning-basee based methods, we implement slight variant of the SOTA learning-based methods (Tang et al., 2020. Huang et al., 2022]. namely score- based policy (SBP). Please see Appendix F.2 for implementation details of these baselines.
Evaluation metries. We use two widely used evaluation metrics, i.e., the average solving time (Time, lower is better), and the average primal-dual gap integral (PD integral, lower is better). Ad- ditionally, we provide more results in terms of another two metrics, i.e., the average number of nodes and the average primal-dual gap, in Appendix G.2 Furthermore, to evaluate different cut se- lection methods compared to pure branch-andd-ount without cutting plane separation, we propose an Improvement metric. Specifically, we define the metric by Im = M(Noouns)-M() where M(NoCCut)
M (NoCuts) represents the performance of NoCuts, and (-)) represents a mapping from a method to its performance. The improvement metric represents the improvement of a given method com- pared to NoCuts. We mainly focus on the Time metric on the easy datasets, as the solver can solve all instances to optimality within the given time limit. However, HEM and the baselines cannot solve all instances to optimality within the time limit on the medium and hard datasets. As a result, the average solving time of those unsolved instances is the same, which makes it difficult to dis- tinguish the performance of different cut selection methods using the Time metric. Therefore, we mainly focus on the PD integral metric on the medium and hard datasets. The PD integral is also well-reoognized metric for evaluating the solver performance (Bowly et al. 2021 Cao et al. 2022).
Experiment 1. Comparative evaluation The results in Table D suggest the following. (1) Easy datasets. HEM significantly outperforms all the baselines on the easy datasets, especially on Max- imum Independent Set and Multiple Knapsack. SBP achieves much better performance than all the rule-based baselines, demonstrating that our implemented SBP is a strong baseline. Compared to SBP, HEM improves the Time by up to 16.4% the three datasets, demonstrating the superiority of our method over the SOTA learning- based method. (2) Medium datasets. On MIK and CORLAT,
7

---

Published as a conference paper at ICLR 2023
Table 2: Comparison between HEM and HEM without the higher-level model.
Eacy: Macirmann Independent Sax 500, v 1963)
Maliant Cueaa 156.
(00)
Hant MPLLB misdd note 8868.
Method
Tineti
(Tune, R)
PD inegral
Timetts:
(PD sntggral 15)
Timelo
PD ineggai
(PD unegraa (0)
Nocars
8.7% 10 66)
71.33 (51 T4)
113 32 14)
201
1940 31)
25% (10
14050 (12533.37) 31)
SBP
21.99 (40.80)
(5055.96)
256.48
(12998.22)
223
BEM wis
1.88 (6 20) 1.76 (3,09)
78.59
16.70 151
S3.14 (115-26)
1930/08 (5464.85)
31.30
240.31 028 039
13614 29 (12914.75)
7:06
REM (Ohrs)
79,95
16,00 (26.1)
58.31 (118.51)
1079.99 (2655.1)
61.08
248 (89.46)
8678.76 (12337.00)
48.77
Table Comparison between HEM, HEM-ratio, and HaM--rato-oorer
Easy Maniitan Indeyendort Set 960 m- 1953)
Media Codat io 466, on 486)
Hard MIPLIB nixed seos (y 1866, no (000))
Mashad
Timmat)
(Tane. 90
193 Insegnal
Timoo0 L
P13 insegral $
IPD intggral
Time 1
inaegra
IPD raigora
Nac SHP
8:18 561
71.31 (51.24)
H0S 1ES-90 (125 14)
2818 40 (1908.11)
85 20
14552 (12223
NA
2445 (5.55)
72.31
21.99 (92.963
9841 (122 17)
2023
(3085.99)
28.19
256 99)
13531 00 (12896
7.55
2.40 181
71:80
(38 97)
70:44 9%
1416 66 (TTM0 10)
4975
345 99 (91-67)
14006 (13655
(1170)
HEM
1.76 (3,60)
(26.28)
1079.59 (2653,34)
248.66
9978.76 00)
HEM still outperforms all the baselines. Especially on CORLAT, HEM achieves at least 33.48%
improvement in terms of the PD integral compared to the baselines. (3) Hard datasets. HEM significantly outperforms the baselines in terms of the PD integral on several problems in the hard datasets. HEM achieves outstanding performance on two challenging datasets from MIPLIB 2017 and real-world problems (Load Balancing and Anonymous), demonstrating the powerful ability to enhance MILP solvers with HEM in large-scale real-world applications. Moreover, SBP performs extremely poorly on several medium and hard datasets, which implies that it can be difficult to learn good cut selection policies on challenging MIIP problems.
Experiment 2. Ablation study We present ablation studies on Maximum Independent Set (MIS), CORLAT, and MIPLIB mixed neos, which are representative datasets from the easy, medium, and hard datasets. We provide more results on the other datasets in Appendix G.3
Contribution of each component. We perform ablation studies to understand the contribution of each component in HEM. We report the performance of HEM and HEM without the higher-level model (HEM w/o H) in Table HEM w/o H is essentially a pointer network. Note that it can still implicitly predicts the number of cuts that should be selected by predicting an end token as used in language tasks (Sutskever et al. 2014). Please see Appendix F.4.2 for details. First, the results in Table ( show that HEM w/o H outperforms all the baselines on MIS and CORLAT, demonstrating the advantages of the lower-level model. Although HEM w/o H outperforms Default on MIPLIB mixed neos, HEM w/o performs on par with SBP. A possible reason is that it is difficult for HEM w/o H to explore the action space efficiently, and thus HEM w/o H tends to be trapped to the local optimum. Second, the results in Table Sable[ssho show that HEM sigmificantly outperforms HEM w/o H and the baselines the three datasets. The results demonstrate that the higher-level model is important for efficient exploration in complex tasks, thus significantly improving the solving efficiency.
The importance of tackling (P1)-(P3). We perform ablation studies to understand the importance of tackling (P1)-(P3) in cut selection. (1) HEM. HEM tackles (P1)-(P3) in cut selection simulta- neously. (2) HEM-ratio. In order not to learn how many cuts should be selected, we remove the higher-level model of HEM and force the lower-level model to select a fixed ratio of cuts. We denote it by HEM-ratio. Note that HEM-ratio is different from HEM w/o H (see Appendix F.4.2). HEM- ratio tackles (P1) and (P3) in cut selection. (3) HEM-ratio-ordes To further mute the effect of the order of selected cuts, we reorder the selected cuts given by HEM-ratio with the original index of the generated cuts, which we denote by HEM-ratiooorder. HEM-ratio mainly tackles (P1) in cut selection. The results in Table 3 suggest the following. HEM-ratio-order significantly outperforms Default and NoCuts, demonstrating that tackling (P1) by data-driven methods is crucial. HEM sig- nificantly outperforms HEM-ratio in terms of the PD integral, demonstrating the significance of tackling (P2). HEM-ratio outperforms HEM in terms of the Time and the PD integral, which demonstrates the importance of tackling (P3). Moreover, HEM-ratio and perform better than SBP on MIS and CORLAT. demonstrating the advantages of using the sequence model to learn cut selection over SBP. HEM--atio and -eMrratiooorder perform on par with SBP on MIPLIB mixed neos. We provide possible reasons in Appendix G.3.1
Experiment 3. Generalization We evaluate the ability of HEM to generalize across different sizes of MILPs. Let n x m denote the size of MILP instances. Following Gasse et al.) (2019); Sun et al. 2020). we test the generalization ability of HEM on Set Covering and Maximum Independent Set (MIS), as we can artificially generate instances with arbitrary sizes for synthetic MILP problems.
8

---

Published as a conference paper at ICLR 2023
Table 4: Left: The generalization ability of HEM. Right: Test on Production Planning problems.
Indgesdent (row
Maxmu Jo Seij
100,
Poolackas Passing
3362.25,
MedeJ
Imporeace (lac)))
FD 20
Teatit
Expencace f1am..11
70racpa
Melaal
Time ts
Ieprrsaeen (Elene
PD snigge L
Angesweewed ieagpal
13 (1i06000:11 51)
571 111152223000 24
33, Brih
30A
3194:055 77)
276 To 053
NA
Fi 61 (2) SaM 85)
N4
Botaut
14 34
Detuen
ITRI: (2)0000))
65
0.91
514.5-516:11
1232
WV
180 3010966000 60)
-8385
1e4 0888869033 50
56 (3--))
-5.45
1923 033552308000 971
NY
20M (297 81)
6.91
FT200 in (71394887)
130
-1.59
29.45
-3.9
30
34
5:45
Toacee (21322
0.58
SRP
80:5-189
18.07
363 01- 94
6:88
60E-1 (40.5)
SRP
276 (235
0.71
IORS 95 (3158665))
5:11
2.3408330
35.28
146.0/20.800 KM
18002
00.00
241.77 (22089)
$3.24
1STSLAR (2M00333)
11384
On MIS, we test HEM four times and nine times larger instances than those seen during training. The results in T show that HEM significantly outperforms the baselines in terms of the Time and the PD integral on 4x and 9 MIS, demonstrating the superiority of HEM in terms of the generalization abilityy Interestingly, SBP also generalizes well to large instances, demonstrating that SBP is a strong baseline. We provide more results on Set Covering in Appendix G.44
Experiment 4. Visualization of selected cuts We visualize the di-
Maximum Independent Set
CORLAT
0.025
0.020
SBP HEM-ratio
versity of selected cuts, an impor-
0.015
HEM-ratio
tant metric for evaluating whether
0.010
0.055
the selected cuts complement each
0.000
8
other nicely (Dey Molinaro 2018b). We visualize the cuts selected by HEM-ratio and SBP on randomly sampled instance from Maximum Independent Set and CORLAT, respectively. We evaluate HEM-ratio rather than HEM, as HEM-ratio selects the same number of cuts as SBP. Furthermore, we perform principal component analysis on the selected cuts to reduce the cut features to two-dimensional space. Colored points illustrate the reduced cut features. To visualize the diversity of selected cuts, we use dashed lines to connect the points with the smallest and largest x.y coordinates. That is, the area covered by the dashed lines represents the diversity. Figure 3 shows that SBP tends to select many similar cuts that are possibly redundant, especially on Maximum Independent Set. In contrast, HEM-ratio selects much more diverse cuts that can well complement each other. Please refer Appendix G.r results on more datasets.
0.005
0.010
-011
0.0
0.1
0.2
0.3
0.4
-2 0 2
10
12
Figure 3: We perform principal component analysis on the cuts selected by HEM-ratio and SBP. Colored points illustrate the reduced cut features. The area covered by the dashed lines rep- resents the diversity of selected cuts. The results show that HEM-ratio selects much more diverse cuts than SBP.
Experiment 5. Deployment in real-world production planning problems To further evaluate the effectiveness of our proposed HEM, we deploy HEM to large-scale real-world production planning problems at an anonymous enterprise, which is one of the largest global commercial technology enterprises. Please refer to Appendix [D.3] for more details of the problems. The results in Table (Right) show that HEM significantly outperforms all the baselines in terms of the Time and PD integral. The results demonstrate the strong ability to enhance modern MILP solvers with our pro- posed HEM in real-world applications. Interestingly, Default performs poorer than NoCuts, which implies that an improper cut selection policy could significantly degrade the performance MILP solvers. In addition, we will integrate our proposed HEM into Verse) i.e., the commercial solver developed by Huawei.
CONCLUSION
In this paper, we observe from extensive empirical results that the order of selected cuts has a signif- icant impact on the efficiency of solving MILPs. We propose novel hierarchical sequence model (HEM) to learn cut selection policies via reinforcement learning. Specifically, HEM consists of a two-level model: (1) higher-level model to learn the number of cuts that should be selected, (2) and a lower-level model-that formulates the cut selection task as a sequence to sequence learning problem-to to learn policies selecting ordered subset with the size determined by the higher-level model. Experiments show that HEM significantly improves the efficiency of solving MILPs com- pared to human-designed and learning-basee baselines on both synthetic and large-scale real-world MILPs. We believe that our proposed approach brings new insights into learning cut selection.
Pleasse refer to https://www. htt.://ww...........oooooo..o.aa for details of VptVerse.
oud.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
The authors would like to thank all the anonymous reviewers for their insightful comments. This work was supported in part by National Nature Science Foundations of China grants U19B2026, U19B2044, 61836011, 62021001, and 61836006, and the Fundamental Research Funds for the Central Universities grant WK3490000004, We gratefully acknowledge the support MindSpore used for this research. In addition, would like gratefully thank all the developers of Opt Verse, and Huawei Cloud Solver Lab for their support of this research.
REFERENCES
Tobias Achterberg. Constraint integer programming. 2007.
Alper Atamtürk. On facets of the mixed-integer knapsack polyhedron. Mathematical Program- ming, 98(1):145-175, 2003.
Egon Balas and Andrew Ho. Set covering algorithms using cutting planes, heuristics, and subgra- dient optimization: a computational study. In Combinatorial Optimization, pp. 37-60. Springer, 1980.
Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 344-353. PMLR, 10-15 Jul 2018.
Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. Sample com- plexity of tree search configuration: Cutting planes and beyond. Advances in Neural Information Processing Systems, 34:4015-4022
2021.
Radu Baltcan-Lugojan, Pierre Bonami, Ruth Misener, and Andrea Tramontani. Scoring positive semidefinite cutting planes for quadratic optimization via trained neural networks. preprint: http://www. optimization-onlinee org/DB. HTML/2018/1/644 html, 2019.
Irwan Bello*, Hieu Pham", Quoc V. Le, Mohammad Norouzi, and Samy Bengio. Neural combina-
torial optimization with reinforcement learning, 2017.
Yoshua Bengio. Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial opti- mization: a methodological tour d d'horizon. European Journal of Operational Research, 290(2): 405-421, 2021.
David Bergman, Andre A Cire, Willem-Jan Van Hoeve, and John Hooker. Decision diagrams for optimization, volume 1. Springer, 2016.
Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doormmalen, Leon Eifter, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, et al. The scip optimization suite 8.0. arXiv preprint urXiv:21 2021.
Bob Bixby. The gurobi optimizer. Transp. Re-search Part B, 41(2):159-178. 2007.
Robert E Bixby. Implementing the simplex method: The initial basis. ORSA Journal on Computing, 4(3):267-284, 1992.
Robert E Bixby, Mary Fenelon, Zonghao Gu, Ed Rothberg, and Roland Wunderling, Mixed-integer programming: A progress report. In The sharpest cut: the impact of Manfred Padberg and his work, pp. 325- SIAM, 2004.
Christian Blick 1ú, Pierre Bonami, and Andrea Lodi. Solving mixed-intee quadratic programming problems with ibm-cplex: a progress report. In Proceedings of the twenty-sixth RAMP symposium, pp. 16-17, 2014.
10

---

Published as a conference paper at ICLR 2023
Simon Bowly, Quentin Cappart, Jonas Charfreitag. Laurent Charlin, Didier Chételat, Antonia Chmiela, Justin Dumouchelle, Maxime Gasse, Ambros Gleixner, Aleksandr M. Kazachkov, Elias B, Khalil, Pawel Lichocki, Andrea Lodi, Miles Lubin, Chris Maddison, Christopher Morris, Dimitri J, Papageorgiou, Augustin Parjadis, Sebastian Pokutta, Antoine Prouvost, Lara Scav- uzzo, and Giulia Zarpellon. Machine learning for combinatorial optimization, 2021. URL https:
ecole httt::////ww...ooeeeaa////////11 http:///occocccmmettotooo///
Zixuan Cao, Yang Xu, Zhewei Huang, and Shuchang Zhou. M14co-kida: Knowledge inheritance in dataset aggregation. arXiv preprint arXiv:2201. 2022.
Lei Chen. Deep Learning and Practice with MindSpore. Springer Nature, 2021.
Zhi-Long Chen. Integrated production and outbound distribution scheduling: review and extensions. Operations research, 58(1) 183111133- 2010.
Santanu Dey and Marco Molinaro. Theoretical challenges towards ematical Programming, 170(1):237-266, 201 8a.
selection. Math-
Santanu S Dey and Marco Molinaro. Theoretical challenges towards cutting- plange--peeeaaa selection. Math- ematical Programming, 170(1):237-266) 2018b.
Jiajun Fan. A review for deep reinforcement learning in atari: Benchmarks, challenges, and solu- tions. arXiv preprint arXiv:21 2021.
Jiajun Fan and Changnan Xiao. Generalized data distribution iteration. arXiv:2206.0311 03192. 2022.
arXiv preprint
Jiajun Fan, Changnan Xiao, and Yue Huang. Gdi: Rethinking what makes reinforcement learning different from supervised learning. arXiv preprint arXiv:2106.06232, 2021.
Reza Zanjirani Farahani and Masoud Hekmatfar. Facility location: concepts, models, algorithms and case studies. Springer Science & Business Media, 2009.
FICO Xpress. Xpress optimization suite, https://wwwt fico. sttco.comm/en//roduucto
Fico- www.xs-reesso.e www.ess--opimiizaaiioi. 2020.
Scott Fujimoto, Herke van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th In- ternational Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1587-1596. PMLR, 10-15 Jul 2018
Maxime Gasse, Didier Chetelat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combi- natorial optimization with graph convolutional neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
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.
Carla P Gomes, Willem-Jan van Hoeve, and Ashish Sabharwal. Connections in networks: A hybrid approach. In International Conference on Integration of Artificial Intelligence (AI) and Opera- tions Research (OR) Techniques in Constraint Programming, pp. 303-307. Springer, 2008.
Ralph Gomory. An algorithm for the mixed integer problem. Technical report, RAND CORP SANTA MONICA CA, 1960.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
Zonghao Gu, George L Nemhauser, and Martin WP Savelsbergh. Lifted cover inequalities for 0-1 integer programs: Computation. INFORMS Journal on Computing, 10(4):427-433 1998.
Zonghao Gu, George Nemhauser, and Martin WP Savelsbergh. Lifted flow cover inequalities for mixed ()- integer programs. Mathematical Programming, 85(3):439-455 1999.

---

Published as a conference paper at ICLR 2023
Prateek Gupta, Elias B Khalil, Didier Chetélat, Maxime Gasse, Yoshua Bengio, Andrea Lodi, and M Pawan Kumar. Lookback for learning to branch. arXiv preprint arXiv:2206. 14987, 2022.
Gurobi. Gurobi solver, https: /ttp:://wwww... qww.bi. com/
2021.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In Jennifer Dy and An- dreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1861-1870. PMLR, 10-15 Jul 2018.
He He, Hal Daume III, and Jason M Eisner. Learning to search in branch and bound algorithms. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
Gregor Hendel, Matthias Miltenberger, and Jakob Witzig. Adaptive algorithmic behavior for solving mixed integer programs using bandit algorithms. In Operations Research Proceedings 2018, pp- 513-519. Springer, 2019.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8):
1735-1780, 1997.
Zeren Huang, Kerong Wang, Furui Liu, Hui-Ling Zhen, Weinan Zhang, Mingxuan Yuan, Jianye Hao, Yong Yu, and Jun Wang. Learning to select cuts for efficient mixed-integer programming. Pattern Recognition, 123:108353, 2022, ISSN 0031-3203, doi: https://doi.org/10..0 101100061...ee////
2021.108353.
Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown Automated configuration of mixed integer programming solvers. In International Conference on Integration of Artificial Intelligence (Al) and Operations Research (OR) Techniques in Constraint Programming, pp. 186-202. Springer, 2010.
Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine. When to trust your model: Model- based policy optimization. Advances in neural information processing systems, 32, 2019.
Michael Jünger, Thomas Liebling, Denis Naddef, George L. Nemhauser, William Pulleyblank, Gerhard Reinelt, Giovanni Rinaldi, and Laurence A Wolsey, 50 Years of integer programming 1958-2008: From the early years to the state-of-the-ar. Springer Science Business Media, 2009.
Elias Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning branch in mixed integer programming. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1), Feb. 2016. doi: 10. 13i URL httpt://ooossss.... aaai wwwiiiorg/iing index. php/ hhtp:/aAt//aticll//vieeee
Elias B Khalil, Bistra Dilkina, George L Nemhauser, Shabbir Ahmed, and Yufen Shao. Learning to run heuristics in tree search. In Ijcai, pp. 659-666, 2017.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.69980 2014.
VR Konda and JN Tsitsiklis. On actor-critic algorithms. SIAM Journal on Control and Optimization, 42(4):1143-1166 2003.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference Learning Representations, 2018
Yufei Kuang, Miao Lu, Jie Wang, Qi Zhou, Bin Li, and Houqiang Li. Learning robust policy against disturbance in transition dynamics via cotte-conservatvee policy optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 7247-7254, 2022.
Ailsa H Land and Alison G Doig. An automatic method for solving discrete programming problems. In 50 Years of Integer Programming 1958-2008, pp. 105-132. Springer, 2010.
12

---

Published as a conference paper at ICLR 2023
Gilbert Laporte. Fifty years of vehicle routing. Transportation science, 43(4):408 2009.
2009.
Jan Karel Lenstra and David Shmoys. The traveling salesman problem: A computational study, 2009.
Xijun Li, Qingyu Qu, Fangzhou Zhu, Jia Zeng, Mingxuan Yuan, Kun Mao, and Jie Wang. Learning to reformulate for linear programming. arXiv preprint arXiv:2201.062 2022.
Xijun Li, Qingyu Qu, Fangzhou Zhu, Mingxuan Yuan, Jia Zeng, and Jie Wang. Accelerating linear programming solving by exploiting the performance variability via reinforcement learning. 2023.
Andrea Lodi and Giulia Zarpellon. On learning and branching: survey. Top, 25(2):207-2366 2017.
István Maros. Computational techniques of the simplex method, volume 61. Springer Science & Business Media, 2002.
John Mitchell. Branch-and-cus algorithms for combinatorial optimization problems. Handbook of applied optimization, 1(1):65-77, 2002.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 51 (18(755)):529 533, 2015.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd International Conference on Machine Learning, volume Research, pp. 1928-1937, New York, New York, USA, 20-22 Jun 2016. PMLR.
Proceedings of Machine Learning
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar Foundations of machine learning- MIT press, 2018
Mouad Morabit, Guy Desaulniers, and Andrea Lodi. Machine-leaming-basee column selection for column generation. Transportation Science, 55(4):815 831, 2021.
Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. Advances in neural information processing systems, 31, 2018.
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Bren- dan O' D'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.133499 2020.
Vangelis Th Paschos. Applications of combinatorial optimization, volume 3. John Wiley & Sons, 2014.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary De Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buu E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
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 Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 17584-17600. PMLR, 17-23 Jul 2022.
Yves Pochet and Laurence A Wolsey, Production planning by mixed integer programming, volume 149. Springer, 2006.
Qingyu Qu, Xijun Li, Yunfan Zhou, Jia Zeng, Mingxuan Yuan, Jie Wang, Jinhu Lv, Kexin Liu, and Kun Mao. An improved reinforcement learning algorithm for learning to branch. arXiv preprint 2:Xiv:2201002111 13, 2022a.
13

---

Published as a conference paper at ICLR 2023
Qingyu Qu, Kexin Liu, Xijun Li, Yunfan Zhou, and Jinhu Lü. Satellite observation and data- transmission scheduling using imitation learning based on mixed integer linear programming. IEEE Transactions Aerospace and Electronic Systems, 2022b.
Ashish Sabharwal, Horst Samulowitz, and Chandra Reddy. Guiding combinatorial optimization with uct. In International conference on integration of artificial intelligence (AI) and operations research (OR) techniques construint programming, pp. 356-361. Springer, 2012.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies as a scalable alternative reinforcement learning. arXiv preprint FrXXiv:1703008860 2017.
Matthew J Saltzman. Coin-or: an open-source library for optimization. Programming languages and systems in computational economics and finance, pp. 3-32. Springer, 2002.
Lara Scavuzzo, Feng Yang Chen, Didier Chételat, Maxime Gasse, Andrea Lodi, Neil Yorke-Smithh and Karen Aardal. Learning to branch with tree mdps. arXiv preprint arXiv:2205.114 2022.
John Schulman, Sergey Levine, Picter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In Francis Bach and David Blei l. Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp- 1889-1897, Lille, France, 07-09 Jul 2015. PMLR.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 2017.
Haoran Sun, Wenbo Chen, Hui Li, and Le Song. Improving learning to branch via reinforcement learning. In Learning Meets Combinatorial Algorithmms at NeurIPS2020, 2020.
llya Sutskever, Oriol Vinyals, and Quoc Le. Sequence to sequence learning with neural networks. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999a.
Richard Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: frame- work for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):181- 211, 1999b.
Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Reinforcement learning for integer programming: Learning cut. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 9367-9376. PMLR, 13-18 Jul 2020.
Mark Turner, Thorsten Koch, Felipe Serrano, and Michael Winkler. Adaptive cut selection in mixed- integer linear programming. arXiv preprint arXiv:2202.1096) 2022.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, L ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. Order matters: Sequence to sequence for sets. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference on Learning Representa- tions, ICLR 2016, San Juan Puerto Rico May 2-4, 2016, Conference Track Proceedings, 2016. URL htt.http:/aar www./rr//ooo abs/
06391
14

---

Published as a conference paper at ICLR 2023
Zhihai Wang. Taoxing Pan, Qi Zhou, and Jie Wang. Efficient exploration in resturee-restricted reinforcement learning. arXiv preprint arXiv:2212.069888, 2022a.
Zhihai Wang, Jie Wang, Qi Zhou, Bin Li, and Houqiang Li. Sample-efficient reinforcement learning via conservative model-based actor-critie. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 8612-8620, 2022b.
Franz Wesselmann and U Stuhl. Implementing cutting plane management and selection techniques. In Technical Report. University of Paderborn, 2012.
Rui Yang, Jie Wang, Zijie Geng, Mingxuan Ye, Shuiwang Ji, Bin Li, and Feng Wu. Learning task-relevant representations for generalization via characteristic functions of reward sequence distributions. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2242 2252, 2022.
Giulia Zarpellon, Jason Jo, Andrea Lodi, and Yoshua Bengio. Parameterizing branch-and-bound search trees to learn branching policies. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 3931-3939, 2021.
Qi Thou, HouQiang Li, and Jie Wang. Deep model-based reinforcement learning via estimated uncertainty and conservative policy optimization. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pp. 6941-6948, 2020.
15

---

Published as a conference paper at ICLR 2023
A PROOF
A.1 PROOF OF PROPOSITION 1
Proof. The optimization objective takes the form of
J(t) = E Bemp ax]]
The (k|s) (axls, k))(s, an )dk)
E Exuel k=0
T6 (k|s)Tb, (acls, ()r(s, ax) (d)k),
where 0 = -01.02] with [01, 02] denoting the concatenation of the two vectors, To(ak(s)
Ex (Té (ax (s, k)), and μ denotes the initial state distribution.
We first compute the policy gradient for 01:
Ve, ((01. 02])
-o, (Banpl J
Σ T8 (k:ss)mz (akls, k))(ss ax dxkc))
k=0 au
EB Ve,
Ti (k(s)
Σ
(((ss
42
Let
(s, 02) = Σ Te (axls: k))(s,
an
= Ray (1x4))7(83
then have that
Vo, J(11,
Enp Voi n² (2)))k)))
Eenp (110) (-1a)[Vo Vo. log (s,
Therefore, we have that
Vo, [(01,, 021)
Egnp kwah (-10) (-19)]Ve Ve, log(=,, (k|s)) Bern ( (rs,))((ss
We then compute the policy gradient for 02:
Vo, ((01, 02))
Ve, (E (Eergll
Σ tb; (k(s)Tb, (rrls, an)kk)
k=0
= -Bangakwnyh (1s) Ves
0z (axls,
ax
-Byogakwrh (110),4 (1),,))
Vez log n/ k)r(s,
which completes the proof.
B RELATED WORK
Machine learning for MILP. The use of machine learning methods to help improve the MILP solver performance has been an active topic of significant interest in recent years (Bengio et al.
16

---

Published as a conference paper at ICLR 2023
2021 Lodi & Zarpellon 2017: Bowly et al. 2021 Gasse al. 2019 Qu et al.
2022b Li al,
2023). During the solving process of the solvers, many crucial decisions that significantly impact the solver performance are based heuristics (Achterberg 2007). Recent methods propose to
replace these hand-crafted heuristics with machine learning models (Bengio et al. 2021). This line
of research has shown significant improvement
the solver performance, including cut selection
(Tang et al., 2020; Paulus et al.) [022] Turner et al. [022] Baltean-Lugojan et al. 2019)) variable
selection (Khalil al. [016]] Gasse et al. [2019] Balcan et al. 20118] Zarpellon et
2021 Qu al.
2022a), node selection (He et al.j 2014]] (Sabharwal et al. 2012), column generation (Moabit et al,,
2021]. and primal heuristics selection (Khalil et al. Hendel et al. 2019). In this paper, we
Tocus on cut selection, which plays a significant role in modern MILP solvers Dey & Molinaro
2018a
Tang et al. 2020
For cut selection, many existing learning-based methods (Tang et al., 2020 Paulus et al. 2022 Huang et al.] 2022) focus on learning which cuts should be preferred by learning a scoring function to measure cut quality. Specifically, (Tang et al. 2020) proposes reinforcement learning approach to learn to score Gomory cuts (Gomory 1960) and select a Gomory cut with the best scores. Fur- thermore, (Paulus et al. 2022 designs lookahead selection rule which selects a cut that yields the best dual bound improvement, and proposes to learn the expert rule via imitation learning. Instead of selecting the best cut, (Huang et al., 2022) frames cut selection as multiple instance learning to learn a scoring function and selects a fixed ratio of cuts with high scores. However, they neglect the importance of learning how many cuts should be selected. Moreover, we empirically show that the order of selected cuts has large impact on the efficiency of solving MILPs (see Section 3
Moreover, (Turner al. 2022) proposes to learn the weightings of four existing scoring rules de- signed by experts. For the theoretical analysis, (Balcan et al. 2021 provides some provable guar- antees for learning cut selection policies.
Sequence model. Sequence model such as long-short term memory and Transformer has achieved outstanding performance in language tasks such as machine translation (Hochreiter Schmidhuber, | Sutskever et al. 2014; Vaswani et al. (017]. For combinatorial optimization, recent works (Vinyals al. 2015 Bello* et aal..221.))) propose a variant of the traditional sequence model, namely pointer network, which is applied to directly finding solutions for specific combinatorial optimiza- tion problems, such as the Travelling Salesman Problem (Lenstra & Shmoys, 2009). Instead of finding solutions directly, we propose to use the pointer network for cut selection in modern MILP solvers. To the best of our knowledge, we are the first to apply the pointer network to cut selection, which not only captures the order of selected cuts, but also can well capture the interaction among cuts to select cuts that complement each other nicely.
Reinforcement learning. Reinforcement learning (RL) has achieved great success in decision-
making tasks, ranging from playing video games (Mnih et al.] 2015 Fan 2021 Fan & Xiao 2022) controlling robots in simulators (Haarnoja et al. 2018]] Yang
2022). Roughly speaking, RL
approaches fall into two categories: (1) model-based RL methods (Janner et al. 2019 Wang et al.
20226 Zhou et al. 2020). and (2) model-free methods (Haarnoja et al.) 2018 Wang al. [202aa]
Kuang et al. [2022] Fan et al., 2021). In this paper, we propose a novel RL framework for learning cut selection policies.
C MORE DETAILS OF BACKGROUND
C.I MORE DETAILS OF THE PRIMAL-DUAL GAP INTEGRAL
We keep track of two important bounds when running branch-and-cut, including the global primal and dual bound. The global primal bound corresponds to the value of the best feasible solution found so far, which is the best upper bound of the problem in (T). The global dual bound corresponds to the minimum dual bound across all leaves of the search tree, which is the best lower bound of the problem in II. We define the primal dual gap integral by the area between the curve of the solver's s global primal bound and the curve of the solver's 's global dual bound. With time limit T, we define the primal-dual gap integral by
[" (xxx 2j)dt
17

---

Published as a conference paper at ICLR 2023
Algorithm Pseudo code for constructing MIPLIB datasets
1: Input the initial instance Io. the set of full MIPLIB M, an empty set M', empty queue Q.
2: Initialize Q with the instance la. Jo - Q
3: while Q is not empty do
4: n=Q.size()
5: for L,..., do
6: Pull an element from Q, namely l'
7:
Compute the similarity scores between each instance M except I' and
8:
Select five instances with the best similarity scores M;
9:
for / in M, do
10:
if I not in M' then Push / to MM;; Push I to Q
11:
12: end if
13: end for
14: end for
15:
end while
Return .M'
where e is the objective coefficient vector as in D.. X is the best feasible solution found at time t, z the best dual bound at time I. We define the primal-dual gap by the difference between the global primal bound and the global dual bound. In SCIP 8.0.0 (Bestuzheva et al.] (021), the initial value of the primal-dual gap is set to a constant 100. The primal-dual gap integral is a well-recognized metric for evaluating solver performance. For example, the primal-dual gal integral is primary evaluation metric in the NeurlPS 2021 ML4CO competition (Bowly et al. 2021
D DETAILS OF THE DATASETS USED IN THIS PAPER
D.1 THE DATASETS USED IN THE MAIN EVALUATION
Easy datasets. The SCIP 8.0.0 solver needs one minute to solve the MILP instances in the easy datasets to optimality. Easy datasets are comprised of three synthetic MILP problems: Set Cover- ing (Balas & Ho. 1980), Maximum Independent Set (Bergman et al., 2016). and Multiple Knap- sack (Scavuzzo et al., (002).. We choose these three classes of problems for the following rea- sons. First, they are widely used benchmarks for evaluating MIIP solvers (Gasse et al. 2019. HHung et al. 2022 Sun al., 2020) Gupta et al., 2022). Second, they represent a wide collection of MILP problems encountered in practice. Third, for each class of these problems, the average number of generated cuts is at least twenty, which ensures that proper cut selection strategies are significant for improving the solver performance. Similarly to (Gasse et al. 2019 Scavuzzo et al, 2022 Sun et al. 2020. Gupta et al. 2022), we generate set covering instances with 500 rows and 1000 columns, Maximum Independent Set instances with graphs of 500 nodes and affinity set to 4, multiple knapsack instances with 60 items and 12 knapsacks. For each benchmark, we gener- training set of 10,000 instances, and training. Specifically, readers can refer to or otlttps://github com http://assaaaaaaaaaaaaaaa htwpaaannnrrbbraan...aa for code generate the easy datasets. We will also release our code once the paper is accepted to be published.
set of 100 instances that never seen during com/ ds 4dm/ learn2brand an
Medium datasets. The SCIP 8.0.0 solver needs least five minutes to solve the instances in the medium datasets to optimality. Following He et al. (2014); Hutter et al. (2010): Nair et al. (2000), medium datasets comprise MIK (Atamtürk 2003). set of MILP problems with knapsack constraints, and CORLAT (Gomes et al. (2008), real dataset used for the construction of wildlife corridor for grizzly bears in the Northern Rockies region. Fach problem set split into training and test sets with 80% and 20% of the instances. Readers refer to https: at ant urk. ieor Reor..eerkeley..dd//tttaaa dat wttp://eew.iiiiieeeeeeee.ee wtw.tttgge...aaaa.aaaa. for MIK. Readers can refer to for CORLAT.
Hard datasets. The SCIP 8.0.0 solver needs least one hour to solve the instances in the hard datasets to optimality.
Table 5: Criteria for removing instances from MIPLIB 2017.
Criteria
% of instances removed
Tags: feavibiliry numericx, infeasible, no solution
4.5%, 17.4%, 2.8%, 0.9%
Presolve longer than 300 seconds under default conditions
4.8%
Selged to optimality at root
9.9%

---

Published as a conference paper at ICLR 2023
Table 6: The statistical description of used datasets. In all datasets, m denotes the average number of constraints and n denotes the average number of variables. Inference Time denotes the inference time of our proposed HEM given the average number of candidate cuts.
Cowiing
Sooe Meliple Kxpuck
Arveyroin
sappore
525
1953
22
336
455
62360
40803
So00
19910
Arg. Cand 78051 283.02
STDR 155
65000 = 12.1
62.00 1M
0060 11.29
392.53 = 53.92
79.47 72.64
259000 154
173.55 13:25-:207.22
(1) Benchmarks from MIPLIB
2017. Note that MIPI.IB
2017 (MIPLIB) (Gleixner et al.
[22T] contains instances of MILPss across many different application areas and has been used as a
long-standing standard benchmark for MILP solvers (Nair et al. 2020 Turner et al. 2022 Gleixner
cct al. (02T). Previous work (Turner et al. 2022) has shown that directly learning over the full MIPLIB can be extremely challenging, as these instances heterogeneous but machine learning has difficulty in learning from heterogeneous datasets. Despite this challenge, we take the first step towards learning over subsets of MIPLIB. Specifically, we construct subsets by selecting sim- ilar instances from MIPLIB. We measure the similarity between instances by 100 numan-designed instance features (Gleixner al., 202I). Following Turner et al. (2022), we first discard instances from MILLIB that satisfy any of the criteria in Table 5 This ensures that a good cut selection policy can significantly improve the dual bound on the remaining instances. Note that we only use three of
seven criteria that are used in (Turner et al. 2022) to preserve as many instances as possible.
To select similar instances from MIPLIB 2017, we first choose a representative instance with knap- sack constraints (icos-1459799, and a representative instance with set covering constraints (sup- portcase40). Then we construct the dataset MIPLIB mixed neos following the procedure in Algo- rithm with the initial instance neos- 1456999. We construct the dataset MIPLIB mixed supportcase following the procedure in Algorithm|] [ with the initial instance supportcasc40. Note that We mea- sure the similarity between instances by 100 human-designed instance features (Gleixner et al. 2021 Each dataset is split into training and test sets with 80% and 20% of the instances.
Specifically. MIPLIB mixed neos contains 20 instances: neos- 1456979,
ceir97_tension. 12p12. lectsched-4-obj. lectsched-5-obj loophal3, neos-6861 680s-686190, neos-2294525-abbe neos- 3009394-lami, neos-3046601-mon neos-3046615-murg. 3601-3t10173-itata, snowy, neos-5221 166-paaaa,, neos-52607644oraaee, neos-5261882-treska, neos-5266653-uugela, neos16, and CUTTS
4338-4338804-
Moreover, MIPLIB mixed supportcase contains 40 instances: supportease40, 30_70_45.. 70_45_05__11 _0,055000,,0
30.70.45 155559951000 acc-tight2, acc-tight4, acc-tight5, comp07-2idx, comp08-2idx, comp12- 2idx, comp21-2idh decompl, decomp2, gus-sch, -stanbul-no-cutofff, mkc, mkc1, neos-555343, neos-555424, ne0s-738098. 886-887244,, neos-933562, 9336-9, neos-933966, neos- 935234, neos-935769, ne0s-983171. neos- 133034,,,, meos-1337300 neos- 139612,, meos-3209462. rhin, 2oos-3755335-nizamn neos-3759587-nooss neos-4300652 neos18, physiciansched6-1, physiciansched6-2, piperout-d27, qiu, reblock354, and supportcase37.
(2) Benchmarks used in NeurIPS 2021 MIACO competition The Load Balancing and Anony- mous problems used in the main text are from the NeurIPS 2021 ML4CO competition (Bowly et al.) 2021 J. Readers can refer to httttt:///// /wwww wwwwwwwwwoo......... ecole. details of the competition. The competition releases three challenging datasets, but we only use two of the three datasets. The major reason is that the average number of the candidate cuts on the instances from the third dataset (Item placement) is less than five, which makes cut selection has little impact on the overall solver performance.
22l/2021/mg 4co competition for
D.1.1 DETAILED DESCRIPTION OF THE AFOREMENTIONED DATASETS
In this part, we provide detailed description of the aforementioned datasets. Note that all datasets we use except MIPLIB 2017 are application-specific i.e., they contain instances from only a single application. We summarize the statistical description of the used datasets in this paper in Table 6 Let n, m denote the average number of variables and constraints in the MILPs. Let m X n denote the size of the MILPs. We emphasize that the largest size of our used datasets is up to two orders of magnitude larger than that used in previous learning- based cut selection methods (Tang et al.) 2020)
Paulus et al. 2022), which demonstrates the superiority of our proposed HEM. Moreover, we test
19

---

Published as a conference paper at ICLR 2023
aj x S P
ai S Pz
the optimal solution of the original L.P
the aptimall sobution of the tightened
cutl
cut2
scorel: 0.8 score2: 0.78 score3:
cud2
Gutt
MI.
the intttal bests
af S P cutl
x s Pz
ag x s P3 cut3
cuts
cur2
based policy
0.xx & Bg
af B
end
optimal of the original L.
the optimal solation the tightened I.P
*cut3
curl
cur2 cutl
the onttial basts
x/'x & cutl
a/xx Pz cut2
< Bg cut3
end
Sequence model based policy
Figure 4: Illustration of selecting cuts using a sequence to sequence model compared to using scoring function. The sequence model has two main advantages. First, it captures the interaction among cuts by selecting cuts one by one. Consequently, it selects cut3 and cut that complement each other nicely, leading to more tightened LP relaxation. Second, naturally captures the order of selected cuts. Better order of selected cuts may lead to better initial basis, thus solving the LP relaxation faster (Li et al. 2022)) (see Section (3).
the inference time of our proposed HEM given the average number of candidate cuts. The results in Table show that the computational overhead of the HEM very low.
D.2 DATASETS USED IN SECTION 3 IN THE MAIN TEXT
In Figure Ta in the main text, spectively. Specifically, D1 represents MIPLIB mixed supportcase, D2 represents the single instance meos-1456979 from MIPLIB 2017, D3 represents MIPLIB mixed neos, D4 represents Anonymous, and D5 represents the single instance lectsched-5-obj from MIPLIB 2017. In Figure Tb in the main text, we use the dataset MIPLIB mixed neos.
five challenging datasets, namely D1, D)2, D3, D4, and D5,
D.3 LARGE-SCALE REAL-WORLD PRODUCTION PLANNING PROBLEMS
The production planning problem aims find the optimal production planning for thousands of factories according to the daily order demand. The constraints include the production capacity for each production line in each factory, transportation limit, the order rate, etc. The optimization objective is to minimize the production cost and lead time simultaneously. We split the dataset into training and sets with 80% and 20% of the instances. The average size of the production plamning problems is approximately equal to 3500 x 5000 = 1.75 x 10ah which are large-scale real-world problems. To promote the machine learning community for MILP, we will release the dataset once the paper is accepted to be published.
E ILLUSTRATION OF ADVANTAGES OF USING SEQUENCE MODEL
Figure illustrate two major advantages of using the sequence model learn cut selection. First, the sequence model takes into account the order of selected cuts by modeling the selected cuts as an output sequence. As shown in Figure 4 the order of cuts determined by the sequence model is better than the score-bare based method, thus leading to better initial basis for solving the LP relaxation faster. Second, the sequence model captures the interaction among cuts, it models the joint conditional
20

---

Published as a conference paper at ICLR 2023
probability of the selected cuts given input sequence of the candidate cuts. As shown in Figure 4 the sequence model selects cuts that complement each other nicely, thus leading to a more tightened LP relaxation and speeding up solving the MILP.
F ALGORITHM IMPLEMENTATION AND EXPERIMENTAL SETTINGS
F.1 DESIGNED CUT FEATURES
Following Huang
al. (2022: Wesselmann & Stuhl
Table 7: The designed cut features of generated cut a²'x S B. (Suppose e denotes the objective coefficient.)
2012: Dey & Molinaro
2018b); Achterberg (2007). we design thirteen cut fea- tures for the cut selection task, such as the extent to
Forrme
Dosription
Nanber
iost cuefficients
the more, more min, sad of cun coefficients the mean, mas, nin, sid of the objective cocfficients the purallelias beween the objective and the cur RI the Duclidean distance
4
objective cocfliciants
pandleliam
I
which a cut is violated by
efficacy
hyperpane
cument LP solution
the current LP solution and
support
the progertion of aus-eem cocflicions of the proportion of nun-nem cxefficiens with reque in intteger varishios of on
integral support
the proportion of non-zero coefficients a cut. We present detailed description of the designed cut features in Table 7 We emphasize that do not tune the cut features. Therefore, it is promising to further improve our method by designing better cut features using graph neural networks to learn better features in future work.
victation
violztion cut currer solation max(o, [M]
F.2 IMPLEMENTATION DETAILS OF THE BASELINES
In this part, we present a detailed description of all the baselines used this paper. We denote cut by a'xx x s B and the optimal solution of the current LP relaxation by x². Throughout all experiments, we set the ratio selected cuts as 0.2 for all score-based rules and learning baselines.
Random. Random selects fixed ratio of the candidate cuts stochastically. The ratio is set as 0.2 in this paper.
Normalized Violation (NV). NV is score-based rule. It scores each cut based the normalized violation of the cut to the current LP solution, and selects a fixed ratio cuts with high scores. The normalized violation is defined by max(0, a x }. The ratio is set as 0.2 in this paper.
[,3]
Efficacy (Eff). Eff is a score-based rule. scores each cut based on the Euclidean distance of the cut hyperplane to the current LP solution, and selects fixed ratio of cuts with high scores. The ratio is set as 0.2 in this paper.
Default. Default is the default cut selection rule used in SCIP 8.0.0 (Bestuzheva et al. 2021). Please refer to (Achterberg] (007) for a detailed description of the SCIP's default cut selection rule. Note that Default tackles the two problems: (1) which cuts should be prefered, and (2) how many cuts should be selected, in cut selection by human-designed heuristics. That is, Default selects variable ratios of cuts rather than fixed ratio.
Score-based policy (SBP). Since the state-of-the-art (SOTA) reinforcement learning based method for selection (Tang al., 2020) is designed for the setting that selects the best in each round, we implement a slight variant of the SOTA to adapt to our setting that selects a subset of cuts in each round, namely SBP. Specifically, the core idea of SBP is learning scoring function to measure cut quality as Tang et al. (2020); HHang et al. (202)); Paulus et al. (2022) do. For a fair comparison, SBP uses the same cut features as HEM and we train SBP via reinforcement learning as well. Our implemented SBP is also a slight variant of the method proposed in Huang et al. (2022). We emphasize that experiments the main text show that our implemented SBP is a strong baseline. Specifically, we implement the scoring function with multi-layer perceptron that predicts the score of a given cut. That is, the scoring function predicts a cut's 's score based on the features of the cut. The MLP network contains two hidden layers with 128 units. Moreover, train the scoring function via evolutionary strategies as (Tang et al., (2020) does. We will also release the code for implementing SBP once the paper is accepted to be published.
21

---

Published as a conference paper at ICLR 2023
Algorithm 2 Pseudo code for training the HEM
1: Initialize Hierarchical sequence model 00]+ MILP instances D, training dataset D wains batch
size No, training epochs Ne. policy learning rate
2: for N₂ epochs do
3: Empty the training dataset Dirain
4: for Ng steps do
5:
Randomly sample a MILP so from D Take action & and at state 9o with the policy 7: Receive reward and add (sv, k; ag. r) Darain
6:
8:
end for
9:
Compute hierarchical policy gradient using Dirain as in proposition
10: Update the parameters, 0, 01 + a Va, J[O), 02]), O2 02 + a ((01,0)))
11:
end for
F.3
IMPLEMENTATION DETAILS AND HYPERPARAMETERS
F.3.1
HARDWARE SPECIFICATION
Throughout all experiments, we use single machine that contains eight GPU devices (NVidia GeForce GTX 3090 Ti) and two Intel Gold 6246R CPUs.
F.3.2 SOLVER SETUP
For reproducibility, we emphasize that all results in the main text are obtained by averaging results over the SCIP random seeds {1, 3).
F.3.3 REWARD FUNCTION
On the easy datasets, we the ward as the negative solving time. On the medium and hard datasets. we set the reward the negative primal- dual gap integral within time limit of 300 seconds.
Table 8: Evaluation on real-world production planning problems with rewards being the negative PD integral. The results show that HEM still significantly outperforms all the baselines.
Production planning
For the real-world production plan- ning problems, we set the reward as the negative primal-dual gap integral within time limit of 600 seconds or the negative dual bound improve- ment. The results reported in the
Method
Time (6)
Improvement (Time, %)
PD integral
Improvement (PD integral, %
278.79
NA
17866.01
Default
296. 12
-6.22
17703.39
0.91
Random
280.18
40.50
18120.21
-1.42
259.48
6.93
17295. 18
3.20
Eff
263.60
5.45
16636.52
6.88
276.61
0.78
5.11
main text are achieved by HEM with the negative dual bound improvement reward. We provide the performance of HEM that uses the negative primal-dual gap integral in Table The results still show that HEM significantly outperforms all the baselines in terms of the Time and PD integral.
HEM (Ours)
251.64
9.74
16533.05
7.46
We emphasize that we can the reward according to our objective in real-world problems. For example, suppose we aim to minimize the primal-dual dual gap within time limit, then we can set the reward as the dual gap within the time limit.
F.3.4 POLICY NETWORK ARCHITECTURE
The higher-level model contains an LSTM encoder and an MLP. The LSTM network encodes variable-sized inputs into hidden vectors with dimension 128. The MLP network contains two hid- den layers with 128 units. The lower-level model is essentially pointer network. We keep the hyperparameters of the pointer network that used in (Bello* et al. 2017).
22

---

Published as a conference paper at ICLR 2023
X1
X2
X3
X4
X5
(g)
X4
X5
X1
X2
Figure Illustration of the pointer network architecture introduced by Vinyals al, (015)).
F.3.5 OPTIMIZATION
Throughout all experiments, apply Adam optimizer with learning rate 01 1x 10 to optimize the lower-level model, and learning rate ag x 10 to optimize the higher-level model. For each epoch, we collect 32 samples for training, and we set the total epochs as 100. It is surprising that learning good cut selection policy does not need too much data as shown in Tang et al. (2020). For training stability, often required for convergence the linear setting (Fujimoto et al. 201 Konda & Tsitsiklis 2003). We the delay update freq as two. That is, first train the lower-level policy twice, then train the higher-leve policy once. Additionally, the results in Appendix G.3.4 show that the convergence performance of HEM is insensitive the hyperparameter delay update freq.
delay the higher-level policy update. This creates two-timescale algorithm,
F.3.6 THE TRAINING ALGORITHM
We provide the procedure of the training algorithm of HEM in Algorithm)
F.4
MORE DETAILS OF HEM
F.4.1 DETAILS OF THE POINTER NETWORK
The pointer network is first introduced by (Vinyals al. 2015) for directly finding solutions of spe- cific combinatorial optimization problems, such as the Travelling Salesman Problems. The pointer network architecture is illustrated in Figure 5 The pointer network consists of Long Short- Term Memory encoder, a Long Short-Term Memory decoder, and an attention that is used as pointer select member of the input sequence the output (Vinyals al. (015). Specifically, plement the pointer network following Bello* et al. (2017). Please refer to (Bello" et al. 2017) for implementation details of the pointer network.
im-
The major difference between our used pointer network and the pointer network used in (Bello* al. 2017 is that use the pointer network select ordered subsets of input sequences, but (Bello* et al 2017) use the pointer network to output permutations input sequences.
F.4.2 DIFFERENCE BETWEEN HEM-RATIO AND HEM w/o H
Details of HEM w/o H To implement HEM w/o H. we augment each input sequence with an end token, i.e., thirteen-dimensionaal tensor with values all being one. The end token is at the end position of the input sequence. Once the decoder of HEM w/o outputs the end token, then the decoding ends. That is, HEM w/o H can implicitly predict the number of cuts that should be selected by predicting whether to decode the end token at the current decoding step.
The policy network of HEM-ratio and HEM w/o H are both essentially pointer network (Vinyals) et al. 2013). a variant of the sequence model. We present the major difference between HEM-ratio and HEM w/o H in the following. HEM w/o H predicts an end token used in language tasks (Sutskever et al. 2014] Vaswani et al.] 2017) to determine the number cuts that should be selected implicitly. In contrast, HEM-ratio always selects fixed ratio of cuts, i.e. it always ends decoding
23

---

Published as a conference paper at ICLR 2023
Table 9: Policy evaluation on easy, medium, and hard datasets in terms of the total number of nodes and the primal-dual gap. The best performance are marked in bold.
Set Covering
Maximum Independent Set
Multiple Knapsack
Method
Nodes
PD gap
Nodes
PD gap
Nodes
PD gap
NoCuts
189.44 (423.68)
0.00 (0)
2170.66 (4054.09)
0.00 (0)
16945.58 (41242.04)
0.00 (0.000128)
Default
116.77 (420.09)
0.00 (0)
588.23 (1916.99)
0.00 (0)
16949,88 88 (41297.50 50)
0.00 (0.000128) 28)
Random
95.70 (285.00 0
0.00 (0)
1416.96 (3820.01)
0.00 (0)
21463.16 16 (59411.07)
0.00 (0.000361)
NV
199.70 (436.25)
0.00 (0)
1618.42 (3089.12) 12)
0.00 (0)
20673.32 (62526.13)
0.00 (0.00022)
EM
194.17 (439.35)
0.00 (0)
1575.88 (2742.66)
0.00 (0)
14909.99 93 (28575.12) 12)
0.00 (0)
SBP
1.16 (2.04)
0.00
698.41 (2869.65)
0.00 (0)
13537,5 59 (22527.45 .55)
0.00 (0)
HEM (Ours)
1.11 (1.46)
0.00 (0)
311.64 (1309.94)
0.00 (0)
10463.85 (18491.25)
0.00 (0)
MIK
CORLAT
Load Balancing
Method
Nodes
PD gap
Nodes
PD gap
Nodes
PD gap
NoCuts
395290.17 (120526.2) 21)
0.09 (0.018)
97198.72 (119287.56)
2.00900es 19)
108.20 (56. 28)
0.94 (0.1))
Defoult
224746.60 (179450.800 80)
0.02 (0.033)
70215.01
(113515.62)
2,666667c+18
(1.61419)
65.22 (55.34)
0:43 (b.073)
Random
403618.10 (115802.29)
0.07 (0.035)
74149.90 (1090433.22 .2)
2.00000e++88
19+
107.05 (8)
0.79 (0.13)
NY
397025,47 (106676.73)
0.08 (0.028)
77943.73 (11 (111355,03)
4.606667c+18 (2. (2.11E+19)
81.91 (38.55)
0.82 (0.11
EIT
406832.83
(113363.27)
0.07 (0.033)
95956.53 (1 (120858.92)
5,333333++18 (2.25E+19)
86.22 (45.35)
0.82 (0.11)
SBP
417070.37 (1337722550)
(0.030)
62297.99
(109664.21)
6.666667e+17 (8. 8.144+18))
138.37 (53.79)
0.65 (0.06)
HEM(Oun))
220547.93 (172837.94)
0.02 (0.028)
51929.71 (100973.74)
0.02 (0.051)
74.47 (60.98)
0.42 (0.072)
Ancnymoous
MIPLIB mixed
MIPLIB mixed suppocteass
Method
Nodes
gmp
Nesee
gpp
Nodes
pmp
NoClas
20110.58
(14167.51)
8.339338ex
(9))
10HBA (117745
2.500000
19 (4.33
ON (8679.19))
(19.91
Default
20025.78
3056
8.3333336+
(2.76+199)
161 (107049
5.5000=+19
(4.355-19)
4055.04 (7484.61)
11.73
Random
19824.48
(12366.55)
1.00000e+ (3B-19)
143930.17
(95296.41)
2.500000+119 (4.33B-19)
4856.13 13 (7745.46
6.05 (14.69)
NV
19313.33 (12399.94)) 94)
8.339333e418
(2.768+19)
(2400) 62) 150046.50
19500000=
(4.358-19)
4986.21
(9124 19)
2.78 (10.08)
EI
19536.23
(12116.80) 80)
6 6666667+ (2.49+199)
144128.83 83 (93404.76) 76)
2.50000e=+19 19 (4.35B-19)
4450.88 (7845,
5.58 (15,40)
SBP HEM(Ours)
19381.67
(12537 81)
6.666667c418 18 19))
177736.25 25 (1220015 XI)
2,500000=
(4.35bx19)
5618.00 08 (9765, 43)
0.14 (0.26)
20191.28 (13219:21)
L.666667= 18 (1.28E-19)
177735.83 (129020-42) 42)
2.500000++ 19 (4.33F-19)
4B44 88 (9996. (6)
0.14 (0.25)
at pre-deternined position. Therefore, HEM w/o H can learn the number of cuts that should be selected, but HEM-ratio cannot.
F.4.3 MORE DISCUSSION OF HEM
In this part, we provide details of some more advantages of HEM. (1) Inspired by hierarchical reinforcement learning (Sutton et al. 1999b Nachum et al. 2018). HEM leverages the hicrarchical structure of the cut selection task, which important for efficient exploration in complex decision- making tasks. (2) Previous methods (Tang et al. 2020: Huang et al. 2022) usually train cut selection policies via black-box optimization methods such evolution strategies (Salimans al. 2017). In contrast, HEM is differentiable and we train the HEM via gradient-based algorithms, which is more sample efficient than black-box optimization methods (Sutton & Barto 2018 Schullma et al., 2015). Although we can offline generate training samples as much as possible using a MILP solver, high sample efficiency is significant as generating samples can be extremely time-consuming in practice.
G
MORE RESULTS
G.1 MORE MOTIVATING RESULTS
Ratio matters. To evaluate the effect of the ratio of selected cuts solving MILPs, we focus on the Normalized Violation (NV) cut selection method with different ratios of selected cuts. (1) We first evaluate the NV methods that select 5%, 10%, 20%, 30%, 40%, 50%, 60%, 70%, and 80% of candi- date cuts, respectively, on four datasets. The results in Figure 6a show that the NV achieves better solver performance with larger ratios on CORLAT and MIPLIB mixed neos. The results demon- strate that the ratio that leads to better solver performance is variable over different datasets, which implies that learning that select 5%, 10%, 20%, 30%, 40%, 50%, 60%, 70%, and 80% of candidate cuts, respectively, on four instances from the Anonymous dataset. The results in Figure 6b show that NV achieves better solver performance with larger ratios Anonymous 121 and Anonymous 131. The results demon- strate that the ratio that leads to better solver performance is variable over different instances from the same dataset, which implies that learning instanne-dependent ratios is important well.
-eeeedet ratios is important. (2) We then evaluate the NV methods
24

---

Published as a conference paper at ICLR 2023
Ratto (s) (ifftrent dedanett
Radio (differant instanoes Anooymous)
1.00
1.:55
0.92
0.32
0.7
0.32
0.25
14PLB moodd racee
Aratomhois 222
0.20
CORLAT
Araromoos 224
1EPLI rsood supoorcczo
Aacrymoss 127
0.52
Araromous
0.4 0..
0..5
0.3
0.5 0.5 0.7
5.3
(a) with different ratios on four datasets. (b) NV with different ratios on Anonymous.
Figure 6: We use the Normalized Violation (NV) rule (Huang et al. 2022). The results in (c) show that NV with different given ratios achieve variable normalized PD integral on four datasets, The results in (d) show that NV with different ratios achieve variable normalized PD integral on different instances from the same dataset.
G.2 MORE RESULTS OF MAIN EVALUATION
In this section, we provide more results the main evaluation. The results in Table show the performance of HEM and the baselines in terms of the total number of nodes (Nodes) and the primal-dual gap (PD gap). (1) Easy datasets. On the easy datasets, HEM and most baselines find the optimal solution within the time limit, as the PD gap converges zero. Additionally, HEM significantly outperforms all the baselines in terms of the Nodes on the easy datasets. (2) Medium and hard datasets. In terms of the PD gap, HEM outperforms all the baselines medium and hard datasets, especially on CORLAT. However, the Nodes metric cannot well distinguish the performance of different cut selection methods on the medium and hard datasets for the following two reasons. First, the solving time of the LP relaxation on each node is different, and thus the Nodes cannot directly determine the solving time (Huang et al. 2022p. Second, on those unsolved instances within the time limit, the Nodes metric is not proper metric, as the Nodes cannot evaluate the quality of the solving process.
G.3 MORE RESULTS OF ABLATION STUDY
In this section, we provide more results of ablation studies in the main text.
G.3.1 IN-DEPTH ANALYSIS OF HEM-RATIO AND SBP
We provide possible reasons for HEM-ratio performing poorer than SBP on several challenging MILP problem benchmarks. Fundamentally, HEM-ratio formulates the cut selection task as a se- quence modeling problem, which has two main advantages over SBP. That is. the sequence model can not only capture the underlying order information, but also capture the interaction among cuts. However, training a sequence model is more difficult than training scoring function, as the se- quence model aims to learn a much more complex task. Specifically, the scoring function aims to leamn to score each cut, while the sequence model aims to model the joint probability of the selected cuts. The latter is a more challenging learning task. Moreover, we follow the reinforcement learn- ing paradigm instead of supervised learning train the model, making the training process more unstable. Therefore, the sequence model may suffer from inefficient exploration and be trapped to local optimum. As result, HEM-ratio perform poorer than SBP, especially challenging MILP problem benchmarks.
G.3.2 CONTRIBUTION OF EACH COMPONENT
To understand the contribution of each component HEM, we provide more results of HEM and HEM without the higher-level model on Set Covering, Multiple Knapsack, MIK, Load Balancing, Anonymous, and MIPLIB mixed supportcase. The results in Table 10 show that HEM outperforms HEM w/o H in terms of the solving time, the primal-dual gap, and the primal-dual gap integral on several challenging datasets, demonstrating the importance of our proposed higher-level model. Moreover, HEM w/o H significantly outperforms SBP in terms of the solving time, the primal-dual
25

---

Published as a conference paper at ICLR 2023
Table 10: Comparsion between HEM, HEM without the higher-level model on more datasets.
Set Covering
Multiple Kinasack
Method
Time
Nodes
PD gop
PD integral
Time
Nodes
PD gop
PD integral
NoCuts
(4.61)
189.44 (423.68)
(0)
56.99 (38.89) 89)
9.88 (22.34)
16945.58 (41242.04)
(0.000128)
16.41 (14.16)
Default
4.41 (5.12)
116.77 (420.08)
0.00 (0)
55 (42.21)
9:90 (22.24)
16649 87 (41247.49) 49)
0.00 (0.000122))
16.46(14.25 (14.25)
SBP
1.91 (0:36)
1.16 (2.04)
0.00 (0)
38.96 (8.66)
7.74 (12.36)
13557.58 (22527 45)
0.00 (0)
16.45 (16.62)
HEM
(0.31)
1.18 (2.03)
(0)
(8.33)
(12,9))))))
12418.85
(23256.47)
0.00
(10.94)
HEM (Ours)
1.85 (0.31)
1.09 (1.46)
0.00 (0)
37.92 (8.16)
6.13 (9.61)
10463.84 (18491.25)
0.00 (0)
13.63 (9.63)
MIK
Load Balancing
Methed
Time (8)
Nodes
PD pip
PD integral
Time (1)
Nodes
PD psp
PD integral
NoCuis
300.01 (0.009))
395290.16 16 (1 (120026.221) 21)
0.09 (0L018)
2355.87 (396.008
300000 (0. 12)
108 20 (56.28)
0.54 (0.1))
14853.77 77 (42)
Detauit
179.62 (122.30 361
224746.64 d8l (1 11995000000 80)
0.02 (0.133))
$40.40 (924.30)
300000 (0.05)
66,22 (55
B1.3 (0.07)
9599 39 11012.90 95)
SRP
286 (1)
417070 36 (1 $9702. 49)
0.07 (0 (0.02055
2063 (740. 11)
300.00 (0. (0)
178. 57 (53 79)
0.65 (0.06)
12535 90 (741 43)
HEM wro H
218.57
(115.97)
297055 97 (189410.43)
0.04 (0.025)
1321.43 (1165.23)
300LUS (0.04)
70.93 (60.36)
0.42 (0,87)
9475.36
(1095.81)
HEM (Ours)
176.12 (125.18)
220547.93 (172537..44)
0.02 (0.028)
785.04 (790.38)
300,00 (9.04)
74.47 (60.98)
0.42 (0.07)
9496.42 (1018.35)
MEPLIB mixed suppertoase
Mothod
Nodea
PD pap
arogpal
Nodes
intepril
NoCata
206 22 (34 910
20110.55 5a (14167.51) 513
8.838832=18
12. (NE
L8297 3o (996842)
1R6000 (151 190
5971200 (8679888
9:19 201
9927 96 (1 5437)
244
(97 72)
20005
(13656 5in
12 72000-11 19
17407 (9736.19)
164.6 (139
4055 04 (7
11:73 (31
1172.
(1066)
245
A6 (12307,11)
0006677418
(9651.95)
165
5018.06 (9705/45)
0.14-0.360
(TM13
HEM Ii
2S1 (518899588855) 45)
21192
(0 12)
10000000018 & 22. 18
17206 $4 (p551.90)
158.96 (153.35)
5779.88 (7468.75)
(.56-11-11
F7N8, (8655-48)
IIEM (Cum))
241 341.A8-997.25 (97.25)
20191 28 (15219.21)
1865867e-18 (1.288-11)
1M77
(9188.21)
162.9% (186
4844.57 (1968.
0.14 (8.25)
6874.55 (6729-97)
Table 11: Comparsion between HEM, HEM-ratio, and HEM-ratio-order on more datasets.
Set Covering
Multiplc Knopsack
Mechod
Time (s)
Nodes
PD gup
integral
Time (s)
Nodes
gap
integral
NoClis
6.31 (4.61)
189.44 (423 68)
0.00
56.99 (38 80)
9.88 (22.24) 24)
16945, 5R (41 (44)
0:00 (0.000) 28)
16.41 (14.16)
Default
4.41 (5.12)
116.77 (420.08)
0.00(0)
55.63 (42
9.50 (22.24)
15989.87 (41297.49)
0.00 (0.000128)
16.16
SBP
1.91 (0.36)
1,16 (2.01)
0.00.0)
38,96 (8.66)
7.74 (12.36)
13537,55 58 (22527 (1))
0.00 (0)
16.45 (16.62)
HEM-rzzla-odder
2.11 (0.38)
1.11 29)
0.000()
42,01 (9.88)
10.46.29..2
18434,20 20 (59254, 10y
0.00 (0.000128)
16.92 (18.19)
HEM-ratio
2.10 (0.40)
(1.18)
(0)
41.95 (9.82)
7.63 (12.64)
13507773
(24339.3)
0.00 (0)
(15.1)))
HEM (Ours)
(0.31)
(1.46)
(0)
37.92 (8.46)
(.16()
10463.84 (18491.25)
(0)
(9.63)
MIK
Lood Hulancing
Method
Nodes
zap
PD innegral
(3)
Nodes
pap
PD integral
NoCua
300,01 (0.009))
395290.16 16 (120526.2))
0.09 (0.015)
2355.8 (996.08)
300,00 (0.12)
20 (56.25)
14855.77 (951.42)
Defiult
179.62
224746.00
(1794500
0.02 (0.033)
300.00
9589. (1012.85)
286.07
417070.36 (135702
(0.0295)
2053.30 (740.11)
300,00
138.37 (53.79)
12535 30 (74),43)
HEM rutio onder
282.92 (42.07)
417397. 10 (132077.3)
0.06 (0.034)
2072 09 (849.16)
300.11 (0.13)
145.18 (56.52)
0.65 (0.063)
12368.12 1556811200 (726))12272667) 77)
HEM satio
283.75 (39
401540.57
(131296 S)
0.07 (0.034)
1865 006966661 (978 .5)
300, (0.095)
148.50 188922000 (59. 12)
0.65 (0.058)
12410.84 (7155 (4)
HCM (Ours)
(12.12
220547.90
(172537.94)
0.03 (0,825)
785.04 (790.35)
300,00 (0004)
74.47 (00.98)
0.42 (0.07)
9496.42 (1018.35)
MIPLIB mined supportsaac
pxp
tntegral
NoCai Defast
246
(04 Wi
20110 58 (14167 51)
8 18 ( 20
18390 30 (FTAN 47)
11 800
1971 AO (R67N MA:
M: 1M0 75)
9927 Mo (11354 IT)
244.05
77)
2000 (1999690 90
8855-18
200
1340 01 (9TTA 19)
164 61 (1 635
19.73/91
9672 (10060
SBP
245.73 (92.4))
19351
(11307.8)
6.676-18 1887--1812.488111 199
18158 6D (951155)
668.61 (135.25)
561800 (9765 43
0.14 (0.26)
7408.65 (7903.47)
HEM oane-oa
245.45 (94. 09)
23495 (1397244)
5.00011
(2.18449))
16496 06 (9182
18645 (192.55)
S252 (9827 98:
4.25 (15.97)
9226 95 (9905.34)
HEM
245.17 (9521) 211
30942.00 17 (13578 46)
5.00e-18
(3 188+199
1634890 NO (9347 A8)
163.0 (137 160
5051 29 (HETON 40)
7.56 (55
997M 35 (1 11)
HRM (Dum))
241.48199.25
20191 28 (13319.21)
1.67e-18 (1 191
16877.15 (9100
162 162.61133..3 (138.31
466137 (SSAN) 15:
0.84
6874.80 (6728-97)
gap, and the primal-dual gap integral on several challenging datasets, demonstrating the significance of our proposed lower-level model.
G.3.3 THE IMPORTANCE OF TACKLING P1-P3 IN CUT SELECTION
To understand the importance of tackling P1-P3 in cut selection, we provide more results of HEM, HEM-ratio, and HEM-ratio-order on Set Covering, Multiple Knapsack, MIK, Load Balancing, Anonymous, and MIPLIB mixed supportcase, Here we refresh what HEM, HEM-ratio, HEM-ratio- order mean. (1) HEM. HEM tackles P1-P3 in cut selection simultaneously. (2) HEM-ratio. In order not to learn how many cuts should be selected, we remove the higher-level model of HEM and force the level model to select a fixed ratio of cuts. We denote by HEM-ratio. Note that HEM-ratio is different from HEM w/o H (see Appendix [F). HEM-ratio tackles P1 and P3 in cut selection. (3) HEM-ratio-order To further mute the effect of the order of selected cuts, we reorder the selected cuts given by HEM-ratio with the original index of the generated cuts, which we denote by HEM-ratio-order. HEM-ratio-order mainly tackles P1.
The results in Table suggest the following. HEM-ratio-order outperforms Default and NoCuts on several datasets, demonstrating that tackling P1 by data-driven methods is crucial. HEM signif- icantly outperforms HEM-ratio in terms of the primal-dual gap integral, demonstrating the signifi- cance of tackling P2. HEM-ratio outperforms HEM-ratio-order on several datasets, which demon- strates the importance of tackling P3. Moreover, HEM-ratio performs better than SBP in terms of
26

---

Published as a conference paper at ICLR 2023
Table 12: Sensitivity analysis of HEM the hyperparameter dealy update freq d.
Matiotars Indepesiest
MIPLIBS tined
Method
Tiscisi
FD Lntegral
Imsronennni (PD integral. (6)
PD integna
Improvmmnn (PD ineggnal 1%)
Timel
PD istgural
Imsprssement (PD integri) 160
66)
(5908-31)
HEM (delas=))
1.79
16.56-26..)
(131.70) 11.70)
1260.3
254 (78.54)
9273 (12033
HBM (ddayym2
1.76 (5.80)
01.01000 21:
92.55
58.31 (1388.51)
1079:59
(2637.04 (43
R1AA8
348 (39.46)
96 (1223)
40.77
IBM (ddaymll
(382)
(6.91 125 899
76.20
58 90 (10K 881
1083.52 (2254.91)
64:20
347 (90.15)
6-01. 18 112461 (20)
42.62
HEM (delay=4)
1.80 (3.90)
17.34 (25 40g
75.08
09 (11544)))
1309:35 (3336.99)
53.54
246.53 (91.95)
6368.46 (12449
42.89
Table 13: Evaluate the generalization ability of HEM on Set Covering.
Covering (2x)
Covering (4x)
Method
Timels]
Improvement (tie, %)
PD integral
Time(s) 1
Improveracnt (time, (%)
PD integral
NoCuts
62.69 (78.27)
NA
609.43 (524.92)
284.44 (18.70)
NA
3215.34
Default
(78.12)
491.63 76)
(1651.15)
Random
64.44 (73.98)
22.07
$20.84 (489.57)
208. (1311
26.53
2528. (1678.666
NV
92.05 (10.11)
-11.32
725.53 (541 68)
286.10 (45.47)
-0:58
1422. (1024,
ER
92.32 (79.33)
-11.64
733.72 (538.60)
286.20 (45.04)
-0.62
3437.00
06 (1043.44)
SBP
3.52 (1.36)
95.74
92.89 (25.83)
7.62 (6.16)
97.32
256. 256.79(1:5592)
HEM (Ouns)
3.33 (0.47)
(14.26)
7.40 (5.03)
250.83
the solving time and the primal-dual gap integral on all six datasets except Set Covering and MI- PLIB mixed supportcase, which shows the superiority of formulating the cut selection as a sequence to sequence learning problem over formulating as a scoring task. However, HEM-ratio and HEM- ratio-order perform little worse than SBP on Set Covering and MIPLIB mixed supportcase. A possible reason is that it is more difficult to train a sequence model than to train a multi-layer per- ceptron and thus the sequence model may suffer from inefficient exploration and be trapped to the local optimum. Please refer to Appendix G for a detailed analysis.
G.3.4 SENSITIVITY ANALYSIS
Additionally, we perform ablation studies test the sensitivity of HEM to the hyperparameter delay update freq d. The results in Table 12 show that there is wide range of d for HEM to achieve com- parable performance on Maximum Independent Set, CORLAT, and MIPLIB mixed neos. Moreover, we emphasize that we do not tune the hyperparameter d. As the results shown in Table d = 3 and performs the best on CORLAT and MIPLIB mixed neos, respectively. However, we simply set d = 2 throughout all experiments in the main text.
G.4 MORE RESULTS OF GENERALIZATION
Here we provide more results of the generalization experiments on Set Covering, On Set Covering, we test HEM on two times and four times larger instances than those seen during training. The results in Table 13 show that HEM generalizes well to instances that are significantly larger than seen during training. In particular, HEM achieves at least 70% improvement in terms of the Time compared to all the rule-based baselines. Moreover, SBP also generalizes well to large instances, demonstrating that SBP is strong baseline.
G.5 MORE VISUALIZATION RESULTS
In this part, we provide more visualization results on Set Covering and MIK. On MIK, we vi- sualize the cuts selected by HEM-ratio and SBP on randomly sampled instance. We perform principal component analysis (Mohri et al., 2018) on selected cuts to reduce the cut features to wwo-dimensional space. Colored points illustrate reduced cut features. To visualize the diversity of selected cuts, we use dashed lines to connect the points with the smallest and largest x.y coordinates. The results in Figure still show that HEM--ratio selects much more diverse cuts than SBP on MIK. However, HEM-ratio performs poorer than SBP on Set Covering (see Appendix G for a detailed analysis). Therefore, we visualize the cuts selected by HEM and SBP on a randomly sampled in- stance from Set Covering. Although HEM learns the number of cuts that should be selected, we find that HEM selects much fewer cuts than SBP. Specifically, HEM selects 25 cuts, while SBP selects 158 cuts. Interestingly. the results in Figure / show that SBP selects 158 similar cuts with high scores, while HEM selects much more diverse cuts than SBP. The results show that HEM tends to select cuts that complement each other nicely.
27

---

Published as a conference paper at ICLR 2023
MIK
Set Covering
300
0.25
0.20
SBP
200
SBP
0.15
HHEM-ratio
HEM
0.10
100
0.05
0.00
-0.05
-100
-0.10
-0.15
-1.5-1.0-0.50.00 0.5 1.0 1.5 2.0 2.5
-1000 0 1000 2000 3000 4000
X
x
Figure 7: We perform principal component analysis on cuts selected by HEM-ratio/HEM and SBP. Each colored point illustrates a reduced cut feature. To visualize the diversity of selected cuts, we use dashed lines to connect the points with the smallest and largest x,y coordinates.
Table 14: Policy evaluation on MIPLIB mixed neos and MIPLIB mixed supportcase with a time limit of three hours.
VIPERR wiretonn
MIHU Sitiieennippee
pkp
7D kaugal
[1]
70 puu
Eangul
Sepervetcce
6123 (42250))
BIRTTTATT (6415222)
336-1127)
302 22332440 (90336))
-L23
188 8467: (99940)
101 (2.12)
26.77 64 (186664)
(12))
38104 (90166))
11.00 06 0EC18109
E40 21121)
613432 H664444
4.48,99166 (6916227)
826-0682)
194.5777 (46955)
43.0
348544 (445111
32.76 (1494)))
6.08 (UR67)
17,86508 (248450)
$5.76
G.6 EVALUATION WITH TIME LIMIT OF THREE HOURS
In this section, we aim to evaluate whether HEM can generalize well to solving problems within much longer time limit. Specifically, we evaluate HEM on two extremely challenging MIPLIB datasets within time limit of three hours. Note that we still train HEM with a time limit of 300 seconds, while we test HEM with a time limit of three hours. The results in Table [4] show that HEM still significantly outperforms all the baselines, especially in terms of the primal-dual gap integral on MIPLIB mixed neos and MIPLIB mixed supportcase. In terms of the primal-dual gap, HEM also outperforms the baselines. Moreover, HEM performs better than baselines in terms of the solving time on MIPLIB mixed neos, but HEM performs poorly in terms the solving time on MIPLIB mixed supportcase. Interestingly, the primal-dual gap integral is not always consistent with the solving time. We emphasize that we train with the negative primal-dual gap integral reward. To set the reward as the
further improve the performance of HEM in terms of the solving time, negative solving time instead of the negative primal-dual gap integral.
G.7 TRAINING CURVES
In this section, provide the training curves of HEM on all nine datasets. The results in Figure g show that the performance our learned policies terms of the solving time or the primal-dual gap integral drops with the training epochs, demonstrating the effectiveness of our learning process.
G.8 GENERALIZE TO MORE SETTINGS
G.8.1 GENERALIZE TO NON-ROOT NODES
Our learned models outperform the baselines for all nodes (both root and non-root nodes) under the round setting, shown in Table 17 Specifically, under the one round setting with non- root cuts, our model improves the Time and Primal-dual gap integral by up to 91.29% and 29.61% %, respectively.
G.9 COMPARISON WITH MORE LEARNING- -ANDD METHODS
We compare HEM with AdaptiveCutsel Turner et al. 2022) and Lookahead Paulus et al. 2022 in Table 15 The experiments demonstrate that HEM significantly outperforms the two learning based methods by a large margin in terms of the Time (up to 11.21 improvement) and Primal-dual gap integral (up 24.36% improvement).
28

---

Published as a conference paper at ICLR 2023
Set Covering
Max Independent Set
trainingtolvvi time
HEN
Uranning Soninggsoliing Lime
trainingtow/ii time
HBM
Epoch
Epoch
Epoch
trainingppiimd gop integgal training/prima gap integgal
grainingtorimal dual gap interral training duall gaip Integral
trannngprina-iuui gap integral traininglarmma.om dual gon integral
Load Balancing
KEM
HEN
Epoch
Epoch
Epoch
Anonymous
MIPLIB mixed neos
supportcase
Epoch
Fpoch
Epoch
Figure 8: Training curves of HEM on all nine datasets. The x-axis corresponds to the training epochs. The y-axis corresponds to the average solving time on easy datasets and the primal-dual gap integral on the other datasets. The solid curves correspond to the mean and the shaded region to the standard deviation over three random seeds. For visual clarity, we smooth curves.
Table 15: The average performance of HEM and the baselines with AdaptiveCutsel Turner et al. (022 and Lookahead Paulus et (2022). The best performance is marked in bold.
Maximum Independent Set
MIPLIBS mixed setcovering
Improvement (PD integral, %)
Method
Time(s)
Improvement (Time, %)
PD integral
Time(s)
integral
NoCuts
8.78
NA
71.31
170.00
9927.96
NA
Default
3.88
55.80
29.44
164.61
9672.34
2.57
Random
6.50
26.00
52.46
165.88
10034,70
-1.07
NV
7.84
10.70
61.60
161.67
8967.00
9,68
EN
7.80
11.10
61.04
167.35
9941.55
-0.14
SBP
2.43
72.30
21.99
165.61
7408.65
25.37
AdaptiveCutsel
2.74
68.79
21.40
161.03
8769.63
11.67
Lookahead
2.27
74.15
20.89
159.61
9293.82
6.39
HEM (Ours)
1.76
80.00
16.01
162.96
6874,80
30.75
G.10
COMPARISON WITH THE SCORE-BASED POLICY (SBP) WITH MORE POWERFUL.
MODELS
We have conducted the ablation study to show that the performance improvement achieved by HEM from our novel problem formulation rather than using more powerful models. The results in Table 16 HEM still outperforms the score-based policy (SBP) with more powerful LSTM models, in terms of the Time (up to 11 improvement) and Primal-dual gap integral (up to improvement).
Setups. We implement another baseline, namely SBP with LSTM (SBP+LSTM), which parametrizes the scoring function via LSTM encoder and multi-layer perceptron. In terms of model parameters, the model used by SBP with LSTM (172289) comparable to that of HEM (212749).
29

---

Published as a conference paper at ICLR 2023
Table 16: The average performance of HEM and SBP with LSTM on Maximum Independent Set and MIPLIB mixed supportcase. The best performance is marked in bold.
Maximum Independent Set
MIPLIB mixed supportease
Improvement (PI) integral, %)
Method
Time(s)
Improvement (Time, %)
PD integral
Time(s)
PD integral
NoCuts
8.78
NA
71.31
170.00
9927.96
NA
SBP
2.43
72.30
21.99
165.61
7408.65
25.37
SBP+LSTM
2.87
67.31
26.01
166.25
7726.54
22.17 6874.80
HEM(Ouur) 1.76
80.00
16.01
162.96
30.75
Table 17:
The average performance of HEM and the baselines for non-root nodes under the one round setting. We obtain the results by deploying the models-which -which are learned at root nodes to all nodes (root and non-root nodes). The best performance marked in bold.
One rund with non-root nodes
Fasy: Maximum Independent Set
Hard: MIPLIB mixed supportcase
Method
Time (s)
Improvement (Time, %))
PD integral
Time (6)
PD integral
Improvement (PD integral, %)
NoCuts
8.78
NA
71.32
170.00
9927.96
NA
Default
1.47
83,25
13.95
128.89
9406.43
5.25
Rundom
2,07
76.47
20.78
124.65
9116.01
8.18
NV
3,21
63.42
29.81
134.58
8034.05
19.08
Eff
2.08
76.27
21,06
124.20
9035.90
8.99
HEM (Ours)
0.76
91.29
9.75
135.80
6987.87
29.61
Results. HEM significantly outperforms SBP with LSTM as shown in Table T6
The results demon-
strate that HEM significantly outperforms SBP with more powerful models, suggesting that the better performance of HEM is from our novel problem formulation.
G.11 EXPERIMENTS WITH ADVANCED MODELS
We conduct the following experiments to demonstrate that our method is applicable to advanced models. By replacing the pointer network with the Advanced Model in Kool et al. (2018) (HEM+AM), experiments show that HEM+AM outperforms the baselines (up to 79.61% improve- ment) as shown Table 18
G.12 GENERALIZE OTHER SOLVERS
Our proposed methodology well generalize other solvers shown in Table [9 The results demonstrate that HEM significantly outperforms the default cut selection method in the CBC solver (Saltzman 2002) terms of the primal-dual gap (up 18.67% improvement).
We do not use commercial solvers, such as Gurobi (Bixby 2007) and (Bliek á et al. 2014), as the backend solver, since they do not provide interfaces for users to customize cut selection methods.
As the CBC cannot generate any cut on the dataset Maximum Independent Set, we conduct the experiments the dataset Load balancing.
We use the primal-dual gap metric rather than the primal-dual gap integral due to the reasons as follows. (1) The primal-dual gap is well-recognized metric for evaluating the solvers well. (2) Unlike the SCIP, the CBC does not provide interfaces for users to acquire the primal-dual gap integral. Due limited time, we do not implement the interface.
G.13 A DETAILED COMPUTATIONAL ANALYSIS OF OUR MODEL AND THE BASELINES' MODEL
We provide a detailed computational amalysis our proposed model and the baselines' model in Table 20 We summarize the conclusions in the following.
(1) The training time of HEM and SBP is comparable, as most their training time is spent on interacting with solvers to collect training samples. (2) The model parameters of HEM (212749) and SBP with LSTM (172289) comparable. (3) The inference time HEM longer than that SBP and SBP with LSTM. Nevertheless, the inference time of HEM (0.34s average) is very low compared the solving
30

---

Published as a conference paper at ICLR 2023
Table 18: We evaluate HEM with advanced models.
Maximum Independent Set
MIPLIB mixed supporicase
Method
Time (8)
Improvement (%,. Time)
PD integral
Time
PD integral
Improvement (%. PD integral)
NrCuts
8.78
NA
71.32
170.00
9927.96
NA
Default
3.89
55.69
29.44
164.61
9672.34
2.57
HEM (Ours)
1.76
80.00
16.01
162.97
6874.81
30.75
HEM+AM (Ours)
79.61
16.09
154.66
8440.19
14.99
Table 19:
The performance of HEM and the default strategy used in the CBC solver Saltzman
2002
MIPLIB mixed supportcase
Load balancing
Method
Primal dual gap (PD gap) Improvement (%. gap)
Primal dual (PD gap) Improvement PS.PD gap)
CBC Default
227.93
0.98
NA
HEM (ours)
185.38
18.67
0.91
7.14
time (162s on average), especially on hard datasets. (4) The training of HEM is stable (please see Figure 88.
G.14 EXPERIMENTS WITH SOME SPECIFIC STRUCTURED MODELS
We have analyzed the selected cuts on Multiple Knapsack (specific structured problems) to show that learned policies capture the underlying structure of the specific structured problems. The results in Figure show that our model mainly selects three kinds of cover inequalities, i.e., lifted knapsack cover inequalities (47%) (Gu et al. 1998), lifted minimal cover inequalities (43%) (Gu et al., 1998), and flow cover incqualities (2%) (Gu et al. 1999), for solving Multiple Knapsack problems. Specifically, we analyze the type of cuts selected by our proposed HEM on Multiple Knapsack, class of problems with specific structures. It is known that prominent class of cut for knapsack problems cover inequalities (Gu al. 1998 1999). The results demonstrate that our learned policies can select cover inequalities for solving the knapsack problems, suggesting that our model can well capture the underlying structure of specific problems.
G.15 MEASURING THE PRIMAL AND DUAL INTEGRALS
We have conducted experiments measure the Primal Integral (PI) and Dual Integral (DI) as shown in Table 21 The results show that the performance improvement of HEM is from both the primal and dual sides.
Specifically, we use the optimal objective values the reference values to measure the PI/DI. How- ever, it is time-consuming to obtain optimal solutions for all instances. We conduct the experiments on three easy datasets due to limited time. Interestingly, the results demonstrate that proper cut selection policies can improve both the PI and DI. Moreover, the results show that HEM achieves more improvement from the primal side than the dual side on Set Cover and Maximum Independent Set, while HEM achieves more improvement from the dual side on Multiple Knapsack.
31

---

Published as a conference paper at ICLR 2023
Table 20: A detailed computational analysis our model and the baselines' model.
Moxiammm Independent Set
Midiel characterisiies
Training
Tosting
Model
Model prrsutees
CIP Menory (MB)
Training time (k)
Training samples
Ang Cuts
Inferesee time (6)
Pia Formooooe//ieee
SRP
18435
2.07
3.0
0.0003
2,43
SDF+LSTMM encoder
172289
2,66
2,83
3200
57
0.051
2.87
HEM (Ows)
212749
281
2.54
0L11
1.76
MIPLIB mixed suppericase
Model charateristics
Training
Testing
Model
Model paramters
GPU Memory
Training time (h)
Training samples
Avg Cuts.
Inference time
PerformuncePDD integral
SBP
18435
2.07
13.81
0.0004
7408 8808.65
SRP-1STM encoder
172269
2.66
13.24
3200
173
0,033
7726. S4
HEM
212749
Table 21: Evaluate the performance of HEM and Default in terms of the primal and dual integrals.
Set Cover
Method
PrimalIntegral (PI)
Improvement (%, PI)
DualIntegral (DI)
Improvement (%, DI)
NoCuts
52.34
NA
59,85
NA
Default
45.02
13.99
49.95
16.54
HEM (ours)
28.84
44.90
35.95
39.93
Maximum Independent Set
Method
PrimalIntegral (PI)
Improvement (%, PI)
DualIntegral (DI)
Improvement (%, DI)
NoCuts
66.83
NA
16.24
NA
Default
32.19
51.83
11.92
26.60
HEM (ours)
18.33
72.57
7.97
50.92
Multiple Knapsack
Method
Prigallntegral (PI)
Improvement (%, PI) DualIntegral (DI)
Improvement (%, DI)
NoCuts
39.39
41.62
NA
Default
25.40
35.52
25.70
38.25
HEM (ours)
19.24
51.16
18.90
54.59
Multiple Knapsack
0.5
0.4
Percent
0.3
0.2
0.1
0.0
LCCoer Clique
CMIR FlowCover
Cuts type
Figure 9: The analysis of selected cuts by our learned model Multiple Knapsack.
32


Reviews:
[{"review_id": "rXmiYYZIaN5", "reviewer": "Reviewer_KYdZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work proposes HEM, a hierarchical sequence model, to learn the cut selection policies for mixed-integer linear programming (MILP). According to this paper, there are three main issues for cut selection, namely, 1) which cuts should be preferred, 2) how many cuts should be selected, and 3) what order of selected cuts should be preferred. The modern heuristics MILP solvers focus on 1) and 2), while the learning-based solvers are mainly for tackling 1).\n\nThis work builds a two-level policy to handle all issues 1) 2) 3) at the same time, which includes a higher-level model to predict the number of cuts, and a lower-level model to select the order of cuts. The higher-level model is a simple tanh-Gaussian model, and the lower-level model is the widely-used pointer network for sequence selection. Experimental results show that the proposed method can outperform several heuristic MILP baselines and one learning-based method. ", "summary_of_the_review": "This work proposes a novel two-level policy model to learn the order of cut selection for MILP. However, due to the current major concerns on problem formulation, unclear contribution over other learning-based methods, and the policy model structure, I cannot vote to accept the current manuscript.\n\n", "strength_and_weaknesses": "**Strengths:**\n\n+ This paper is generally well-organized and easy to follow.\n\n+ MILP is important for many real-world applications, and learning-based methods have the potential to significantly improve the efficiency of the MILP solver, especially for specific problems from a given distribution. This work is a timely contribution to an important research topic.\n\n+ The idea to predict the cut order for MILP solver is novel.\n\n**Weaknesses:**\n\n**1. Problem Formulation** \n\nAlthough the idea of cut order prediction is novel, the problem formulation and some design choices are not well supported. To my understanding, the cutting plane operator is important for each branching step in the brand-and-cut algorithm. In other words, cuts can be applied to each node for the search tree. However, this work proposes to only add the learning-based cuts selection at the root node, and run the cut separation with only one single run. As correctly pointed out in this paper, now the problem is formulated as a one-step contextual bandit problem. These simplifications are not well discussed and justified in the paper. Will they significantly hurt the potential and performance of the complete algorithm with a learning-based cut selection at each node with multiple rounds?\n\nIf we want to use the learning-based cut selection for each node (not just the root), will a single policy model still perform well for all nodes with a good generalization performance?\n\n**2. Unclear Contribution over Other Learning-based Methods**\n\nIn this paper, the proposed method is compared with a few heuristic baselines and one single learning-based method. For the only learning-based method, this work implements a variant version for batched cut selection (rather than the original cut selection in [1,2]). However, since the method proposed in [2] already support batched cut selection, it is unclear why a variant version is needed.\n\nIn the implementation, the key score prediction model is a very simple 2-layer MLP trained with evolutionary strategies, which could be less powerful than the model in the proposed method. It is hard to tell whether the better performance of the proposed method is truly from the novel problem formulation or just from using more powerful models. \n\nMore importantly, as discussed in this paper, there are many other different learning-based approaches for solving MILP, such as the closely related cut selection methods [3,4]. According to [3], their proposed method can significantly outperform the method in [1]. The other learning-based methods for variable selection, node selection, column generation, and heuristics selection are all potential alternatives. Why none of them are actually compared and analyzed in this work? \n\nThe lack of thorough comparisons and analyses with other learning-based methods makes it very hard to evaluate this work's actual contribution and advantage. Given many learning-based alternatives for MILP, why should the user choose the method proposed in this work? \n\n**3. The Policy Model**\n\nIt seems that the proposed two-level policy simply incorporates existing models as its policy model. The higher-level model is a simple tanh-Gaussian model, and the lower-level model is the widely-used pointer network where the embedding feature is also already proposed in previous work. No specific model structure or improvement has been proposed for MILP. Is there any structure of MILP that can be further leveraged to build a more efficient model?\n\nThe seq2seq pointer network has been significantly improved over the past few years. For example, the input of the pointer network is indeed not an order sequence (which is also the case for cuts in MILP), so the RNN structure is not essential for the encoder. Many advanced model structures like the Attention Model [5], or efficient training methods like POMO [6] have been widely used in the neural combinatorial optimization community. Why does this work choose to use the original less powerful pointer network in the proposed method?\n\n**Other Comments**\n\n1. The proposed method is learned with SCIP in this work. Can the learned policy be generalized well to work with other solvers like Gurobi?\n\n2. The citations of Bengio et al., 2021 for NP-Hardness (page 1), and brand-and-cut (page 3) are not suitable. Please find more suitable references for these citations.\n\n3. It is not suitable to directly use the illustration figure from the original pointer network paper, even in the Appendix (page 22).\n\n[1] Reinforcement learning for integer programming: Learning to cut. ICML 2020.\n\n[2] Learning to select cuts for efficient mixed-integer programming. Pattern Recognition 2021.\n\n[3] Learning to cut by looking ahead: Cutting plane selection via imitation learning. ICML 2022.\n\n[4] Adaptive cut selection in mixed-integer linear programming. Arxiv 2202.10962.\n\n[5] Attention, Learn to Solve Routing Problems! ICLR 2019.\n\n[6] POMO: Policy Optimization with Multiple Optima for Reinforcement Learning. NeurIPS 2020.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "k02WIZ9uXBH", "reviewer": "Reviewer_j8AA", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a method for constraint generation within the branch-and-cut framework. Differing from prior work, the paper casts the constraint generation problem as an MDP and proposes a hierarchical policy to generate a tuple of cuts of variable length depending on problem state. The constraint generation policy is a stochastic bi-level policy which first selects the number of cuts to generate, then selects the list of cuts with desired cardinality using a pointer network. The state of the problem is represented by the model generated so far and the set of candidate constraints and is encoded via an LSTM due to it's variable-length nature. The policy is trained using policy gradient.  The results are evaluated on standard benchmarks.", "summary_of_the_review": "This is a technically reasonable paper where novelty is somewhat limited, and at present marginally above threshold. I think this novelty/insight can be improved substantially by trying to interpret what these policies do and argue that that they implement some type of abstract reasoning. ", "strength_and_weaknesses": "Strengths: \n* This paper shows progress on an important problem.\n* The idea is sensible, making use of the observation that order matters for constraints and proposing a solution that addresses this.\n\nWeaknesses: \n* While the paper does a good job of comparing the performance of the proposed method to prior work and ablations, there are some really important questions that seemed to be left open. What is the computational cost of the training? Is it stable? How large are the trained models? How long does inference take? It struck me that the main competitor in comparisons (the scoring based policy) is based on a rather small model (which is an important detail and buried all the way on page 20). I then tried to find whether the HEM model is comparable in terms of parameters and training time, and could not find these details. This raises questions as to whether the observed gains are due to a more efficient problem representation, or due to model disparity. This analysis is important and needs to be prominently displayed. \n   ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "_vJ1OEmJa76", "reviewer": "Reviewer_xxrL", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes an algorithm for cut selection in a mixed-integer linear programming (MILP) solver. The algorithm aims to determine which subset of a collection of proposed cuts to add at the root node, and in what order they should be added. To accomplish this, the authors propose a hierarchical reinforcement learning-based method that first determines the number of cuts to add, and then determines  which cuts to add and in what order.", "summary_of_the_review": "The authors successfully build on prior work on cut selection for MILP solvers. While I have a few points where I think the paper could be further clarified or improved with greater insight, I generally think it is a nice contribution to the literature.", "strength_and_weaknesses": "The paper is well-written and is a worthwhile contribution to an interesting and relevant stream of research on cut selection and MILP solver configuration more broadly.\n\nWhile the authors choice of primal-dual integral as the metric of choice for the method comparisons, I think the paper would benefit from some additional quantitative measurements in the computational study. This additional data (and accompanying analysis) could help give more insight into _how_ the new cut selection method is improving SCIP. For example, also measuring the primal and dual integrals would potentially give some insight into whether the gains are coming from the primal side (e.g., better aligned with SCIP's heuristics) or the dual side (e.g., better aligned with SCIP's tree search algorithm). Additionally breaking out the node count or simplex iteration count would provide insight into how much work SCIP is expending on the node LP solves.\n\nI do not think this further analysis is necessary for all of the computational results, but it would be welcome in certain spots. In particular the ablation study would benefit from more of a breakdown to understand what each component of the proposed method is affecting the underlying solver.\n\nBeyond this, my biggest lingering questions relate to how these results will generalize to other solvers, and what exactly \"cut ordering\" means in the implementation.\n\nThe authors write: \"RandomAll...randomly permutes all the candidate cuts, and adds all the cuts to the LP relaxations in the random order.\" In your implementation, are you explicitly adding the cuts to the LP relaxation? Or are you instead registering the cuts through the \"Separator\" API, or filtering them through the \"Cut Selector\" API? If it is through one of these higher-level SCIP APIs, have the authors verified that all the cuts are added \"as-is\" to the LP relaxation in the given order, or is SCIP potentially applying some filtering/transformations/reordering to the cuts registered in the pool before adding to the LP? If the latter, is there some order dependence in SCIPs internals (e.g., SCIP keeps a running tally of some type of condition number as it takes a linear pass through the registered cuts and filters based upon it).\n\nThe reason I belabor this a bit is that I think it can give some insight into whether the method is learning how to make SCIP work well, as opposed to learning something more general about the instances in a somewhat solver independent fashion (e.g., the method is learning how to order cuts to make the underlying linear algebra more efficient). If the method is doing the latter, this makes the case that the results will plausibly generalize to other solvers (the current paper does not make a strong argument to this effect, understandably so given the sheer implementation complexity such a study would entail).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster