Rethinking Branching on Exact Combinatorial Optimization Solver: The First Deep Symbolic Discovery Framework
Authors: Yufei Kuang
Jie Wang
Haoyang Liu
Fangzhou Zhu
Xijun Li
Jia Zeng
Jianye HAO
Bin Li
Feng Wu
Venue: ICLR 2024 poster (2024)
Keywords: Combinatorial Optimization
Branch and Bound
Deep Symbolic Optimization
Learn to Optimize
Machine Learning for Combinatorial Optimization
Primary area: general machine learning (i.e., none of the above)
TL;DR: In this submission, we develop the first deep symbolic discovery framework to learn high-performance branching policies for lightweight and reliable application to exact combinatorial optimization solvers.

Abstract: Machine learning (ML) has been shown to successfully accelerate solving NP-hard combinatorial optimization (CO) problems under the branch and bound framework. 
However, the high training and inference cost and limited interpretability of ML approaches severely limit their wide application to modern exact CO solvers. In contrast, human-designed policies---though widely integrated in modern CO solvers due to their compactness and reliability---can not capture data-driven patterns for higher performance. To combine the advantages of the two paradigms, we propose the first symbolic discovery framework---namely, deep symbolic discovery for exact combinatorial optimization solver (Symb4CO)---to learn high-performance symbolic policies on the branching task. Specifically, we show the potential existence of small symbolic policies empirically, employ a large neural network to search in the high-dimensional discrete space, and compile the learned symbolic policies directly for fast deployment. Experiments show that the Symb4CO learned purely CPU-based policies consistently achieve *comparable* performance to previous GPU-based state-of-the-art approaches. 
Furthermore, the appealing features of Symb4CO include its high training (*ten training instances*) and inference (*one CPU core*) efficiency and good interpretability (*one-line expressions*), making it simple and reliable for deployment. The results show encouraging potential for the *wide* deployment of ML to modern CO solvers.

Published as a conference paper at ICLR 2024
RETHINKING BRANCHING ON EXACT COMBINATO- RIAL OPTIMIZATION SOLVER: THE FIRST DEEP SYM- BOLIC DISCOVERY FRAMEWORK
Yufei Kuang!?, Jic Wang Haoyang Liu Fangzhou Zhu', Xijun Li
Jia Zeng', Jianye Hao', Bin Li Feng Wu
CAS Key Laboratory of Technology in GIPAS, University of Science and Technology of China.
2 MoE Key Laboratory of Brain-inspired Intelligent Perception and Cognition, University of Sci- ence and Technology of China.
Noah's Ark Lab, Huawei Technologies.
ABSTRACT
Machine learning (ML) has been shown successfully accelerate solving NP- hard combinatorial optimization (CO) problems under the branch and bound framework. However, the high training and inference cost and limited inter- pretability of ML approaches severely limit their wide application to modern exact CO solvers. contrast, human-des suman-desigged policies- widely integrated modern CO solvers due to their compactness and reliability- not capture data- driven patterns for higher performance. To combine the advantages of the two paradigms, propose the first symbolic discovery Slamework-nameee symbolic discovery for exact combinatorial optimization solver (Symb4C0)-t learn high-eerformance symbolic policies the branching task. Specifically, we show the potential existence of small symbolic policies empirically, employ large neural network to search in the high-dimensional discrete space, and com- pile the learned symbolic policies directly for fast deployment. Experiments show that the Symb4CO learned purely CPU-based policies consistently achieve com- parable performance to previous GPU-based state-of- of-the-art approaches. Further- more, the appealing features of Symb4CO include its high training (ten training instances) and inference (one CPU core) efficiency and good interpretability (one- line expressions), making simple and reliable for deployment. The results show encouraging potential for the wide deployment of ML to modern solvers. Codes are available at /tttttt://// /ttts::/gitaae tttpbbttuuuuuutgggg www/MIRALabbbb......... USTC/L20 Symb4co
deep
INTRODUCTION
Combinatorial optimization (CO) problem is one of the most fundamental and challenging opti- mization problems in the field of mathematical optimization (MO), widely used to formulate a rich set of important real-wor world problems, c.g., routing (Liu et al.) 2008), scheduling (Chen 2010). and chip design (Ma et al.] 2019). Generally, the solving efficiency and solution quality of CO prob- lems related to enormous economic value (Chen et al. 2011). while solving CO problems is usually computationally expensive due to their NP-hard nature. Thus, the acceleration on solving CO problems plays core role in the field of MO. Modern exact CO solvers like SCIP (Achterberg) 2007) and Gurobi (Gurobi, 2022) usually employ various human-designed heuristics, whose design requires considerable manual tuning and complex working flows. Recently, researchers apply ma- chine learning (ML) to different solver components (Paulus & Krause 2023 Li et al.) 2024]: He] jet al. 2014, Wang et al. 2023 Geng et al. 2023) Liu et al.) 2023) to accelerate the solving process, and the results show encouraging improvements on problems with chosen implicit distributions.
However, the general limitations of ML approaches on training, inference, and interpretation (Lan- dajuela al.) 2021) makes their wide deployment to modern CO solvers relatively slow process for a long time. First, (L1) ML approaches usually require considerable training data to achieve superior
Conrrsponning author; jiewangx ustc.edu.cn

---

Published as a conference paper at ICLR 2024
performance, while may only have limited data due to reasons like privacy issues in real-worls applications. Second, (L.) ML approaches in CO can encounter the dilemma between training ac- curacy (complex model) and inference efficiency (deployment device), eurrently most CO solver servers for industrial purpose are purely CPU-based. Lastly, (1.3) the "black-box' nature of many MI. approaches prevents further understanding skepticism among many researchers in MO. Note that these limitations are usually regarded intrinsic for machine learning, but they starkly misalign with the requirements in industrial-level applications.
the learned policies, which engenders sense of
Gupta et al. (2020) employ hybrid graph neural network (GNN) and multilayer perceptron (MLP) models to tackle (L2) on purely CPU-based devices, while the neural networks still lead to low training efficiency (L1) and interpretability (L3) for deployment.
In contrast, human-designed policies are widely incorporated in modern CO solvers (Achterberg 2007]. Generally, these policies consists of hard-coded mathematical expressions and working flows, whose design are coincident to human intuitions and thus regarded to be reliable. Note that the use of mathematical operators can be regarded as strong regularizations (Petersen 2019 Landajuela ct al. 202T). Thus, these policies are usually more compact compared to the ML learned policies. However, designing and developing these policies is extremely challenging as it requires extensive expert knowledge. Moreover, these policies are designed for generic purpose, missing data-driven patterns from specific data distribution for higher performance (Bengio et al.! 2021).
In light of this, a natural idea is to combine the application reliability and superior performance of these two paradigms. Then, based the idea of genetic programming (Poli et al.) 2008), we propose the first symbolic discovery framework- deep symbolic optimization for exact combinatorial optimization solvers (Symb4CO)-to search for high-performance symbolic policies on the branching task. First, we conduct preliminary experiments to show the potential existence of small symbolic branching policies. Then, we employ a deep symbolic discovery framework, which employ a large sequential model to search in the nigh-dimensional discrete space of symbolic expressions and use the behavioral cloning accuracy as the fitness measure. Finally, we compile the learned expressions directly for fast deployment to modern exact CO solvers.
The empirical results demonstrate the following advantages of Symb4CO: (1) Superior performance on pure CPU devices. Symb4CO learned purely CPU-based policies achieve comparable perfor- mance to GPU-based state-of-the-are (SOTA) approaches and outperform all the CPU-based branch- ing policies. (2) High training and inference efficiency. We use only training instances train Symb4CO to SOTA performance and observe it can achieve high performance even with one train- ing instance, and the learned policies only require one CPU core for stable inference. (3) High interpretability. All the learned policies are one-line compact mathematical expressions, which are easy to deploy the distributions of CO solver packages and can help researchers further understand and optimize the human-designed branching policies.
2 PRELIMINARIES
2.1 BRANCHING VARIABLE SELECTION IN THE BRANCH-AND-BOUND ALGORITHM
Many CO problems can be formulated as the mixed integer linear programmings (MILPs):
arg min c. s.t. Ax < b, x E x R"-",
where is the cost, A is the constraint matrix, b is the constraint right hand side vector, and p is the number of integer variables. Popular exact solvers such as SCIP (Achterberg) 2007) commonly employ the branch-and -nd--uund (B&B) algorithm to solve MILPs. B&B algorithm operates by re- cursively solving a series of subproblems and organizing them as nodes within search tree. When exploring each node of the subproblem, the solver performs the brunching policy, where selects an integer variable I; (branching variable) with fractional value x in the LP solution. The solver then partitions the feasible region to generate two new subproblems of child nodes by adding constraints J; [x]]] and 2; 2 [x;]] After that, the solver determines new subproblem to explore next.
Empirically, the policies for branching variable selection significantly influence the size of the search tree then the overall solving efficiency. The commonly used branching policies include the strong branching and pseudocost branching policies. The strong branching policy is known to produce the smallest search trees among all the heuristics but requires huge amount of computation, while the
2

---

Published as a conference paper at ICLR 2024
"wct fecuracy Thaving
Performane Sevires
Text Model Archiecttre
HL2 (GPU)
1re0
08.91
GR1
06
madeed
M.F
001
30
30
39
3>
1.00
3.6
5:00
250
Doining instanies
Betowior Can ro RCCURCY
(a) Training efficiency (LI).
(b) Inference efficiency (L2).
(c) Model Architecture.
Figure 1: Motivations for symbolic discovery the branching task. All the experiments
ducted on the combinatorial auction benchmark. Figure [[a]] shows deep learning models require extensive training data achieve satisfactory performance, while lighter tree models struggle to achieve high learning accuracy. Figure [[b] shows deep learning models, especially GNN, severely depend on GPU for efficient inference. Figure [[c] shows the potential existence of compact but high-performance branching policies, which motivates us to employ symbolic operators in this work.
pseudocost branching employs simpler and faster branching score function which depends on con- siderable human intuition and considerable manual tuning. Thus, these numan-designe branching policies are still not satisfactory enough in real-world applications (Jünger et al. 2009)), leaving vast possibilities to improve solving efficiency with ML-dissooverd,, powerful and fast policies.
2.2 GENETIC PROGRAMMING FOR SYMBOLIC DISCOVERY
Genetic programming (GP) is an evolutionary computation technique that automatically solves prob- lems without requiring the form or structure of the solution advance. Specifically, GP approxi- mates mapping from the dataset by generating mathematical expressions in the form of expression trees. The internal nodes of the trees are unary or binary, representing unary (e.g. pow, log, exp and on) and binary (e.g. +, -, x, +) mathematical operators, respectively. The leaf nodes of the trees stand for input variables and constants (e.g. variables {z, y, >} and constants {ci, C22 C2 GP repeatedly improves the performance of the generated expressions using selection, crossover and mutation operations. Finally, a fitness metric is used for evaluating the generated expressions.
3 RETHINKING MACHINE LEARNING FOR BRANCHING
One of the fundamental problems in modern solvers how to rank a set of candidates, which widely exists in modules like basis selection, cut selection, and variable selection (branching) (Jünger al. 2009). Many policies rank candidates via human-designed scoring functions (e.g., pseudocost in branching), while designing these functions usually requires considerable expert knowledge. In this paper, we mainly focus on the branching task, in which many previous ML approaches attempt to learn better ranking functions with complex ML models like ExtraTrees (Alvarez al. 2017), graph neural network (GNN) (Gasse et al. 2019). and hybrid models (Gupta et al. 2020).
3.1 LIMITATIONS FOR MACHINE LEARNING BASED BRANCHING POLICIES
Though ML based branching policies show promising results previous research, in practice, we observe three main limitations that significantly hinder their wide deployment to modern CO solvers:
(LI) The extensive requirement on training instances. We compare the test accuracy of different ML models trained with different number of instances in Figure ((a) Results show that limited training data severely hurts the performance of ML approaches. However, in many real-world situations we only have limited training data due to reasons like privacy issues.
(L2) The requirement for GPU devices for high performance. We compare the performance of previous SOTA approaches on CPU and GPU devices in Figure [(b) to show that. Similar results and conclusions are reported in previous work (Gupta et al. (2020) as well. However, many servers where CO solver are deployed for industrial purpose are purely CPU-based.
(L3) The 'black-box' nature of learned models. ML models like neural networks are usually regarded uninterpretable, which engenders sense of skepticism among MO researchers as
3

---

Published as a conference paper at ICLR 2024
MILP instance
Branch and bound
Library
Sequential model
purel Riing ounaa
min N, 2xg
025 1075*r
operators: MormKttllgg exp,
Expression
2
025-1
pow) pow)
-x 52
features: s[1-91]
Ny 2.0
constants:
4.00
[0:2 U.5, 5.0.
2. Generate Symbolic Branching Policies
collected data:
Fitness Measure
RL Trainer
Deployment
Legund
global upper bound
0.3
bandit model
entropy Hegularizor
dikkssekking PG
compuled libray
exgression
branching
Selected
b. local lower bounds
d. current solutions
strong branching soores)
r(t)
1.0
601
(1.0)
PPO trainer
Imgth pricr
objective
Integrotod To
DO solver
1. Collect Full Strong Branching Data
3. Evaluabe Expressions and Train the Deep Symbolic Model
Figure 2: Illustration of the deep symbolic discovery framework for branching. Part 1 illustrate the FSB rule and the collected data with simple MILP example; Part shows how the sequential model generate symbolic policies; Part 3 shows the RL-based training process and the deployment.
it prevents further understanding on the learned policies. Furthermore, integrating series of complex MI. models into CO solver package distribution is typically intractable.
In conclusion, the high training and inference cost and the limited interpretability of existing MI. approaches severely limit their wide deployment to modern CO solvers.
3.2
MOTIVATION FOR SYMBOLIC DISCOVERY
Gupta al. 2020 employ a hybrid approach that replaces time-consuming GNN inference with faster ML.P to tackle (1.2). However, the employed neural network still makes its training efficiency (L1) and interpretability (L3) unsatisfactory for practical applications. An one-step further idea is to employ lighter models to alleviate (L1) and (L3). However, previous research based on lighter SVM (Khalil et al. 2016 or tree models (Alvarez et al. 2017) falls into suboptimal learning accuracy, making it a dilemma between model size and learning capacity for these lighter models.
Thus, there some compact model that alleviates (L1)-(L3) while maintaining a commendable level of performance? Based on the MLP model and the 91 features employed in Gupta et al.] (020)) we conduct experiments and get the following results (in Figure [(c) to empirically answer it:
1. Sparse active features. We randomly mask 80% input features and train the MLP model with remained ones. We then report the highest test accuracy among five random repeats. We find this achieves comparable accuracy MLP trained with full features.
2. Simple but nonlinear mapping. We employ (16) and (8, 8) hidden layers to replace the original (256, 256, 256) one used in Gupta et al. (2020). We find these compact MLP models still achieve high accuracy. However, directly removing hidden layers (i.e., using linear model) results clear decrease on the behavioral cloning accuracy.
We use fixed-length features rather than graph- based states in Gasse et al, (2019) as the branching policy requires to be lightweight enough for fast inference CPU, and we use the raw features in Gupta et al. (2020) rather than the GNN embedded ones for better interpretability.
The results indicate the potential existence of compact branching policies that involve only small set of active features and a simple (but nonlinear) mapping between inputs and decisions. Previous light ML models struggle to achieve high performance (Alvarez al. 2017 Khalil et al., 2016 Gupta et al. 2020), which motivates us to employ more complex symbolic operators in the policies. Generally, these operators leverage the "unreasonable effectiivnness of mathematics" to significantly enforce the expressive capacity of ML models (Landajuela et al. (021).
4 DEEP SYMBOLIC DISCOVERY FRAMEWORK FOR BRANCHING
Intuitively, the introduction of symbolic operators will make the optimization non-differentiable That is, rather than the continuous optimization task in other MI. approaches, need to search
4

---

Published as a conference paper at ICLR 2024
for symbolic expressions in discrete and nigh-dimensional space of symbolic expressions. In this section, we introduce the first symbolic discovery framework for exact combinatorial optimization solve (Symb4CO) to learn high-performance symbolic branching policies (see Figure 2
4.1 THE SYMBOLIC BRANCHING FUNCTION
In genetic programming (Poli al. 2008), functions are typically expressed as symbolic trees, in which leaf nodes are features or constants and other nodes are mathematical operators. In this task, we generate functions to score all branching candidates and select the one with the highest score.
Input Features. We choose the features of candidate branching variables that: a) contain as much as possible information about the branching task; b) simple enough to handle on purely CPU-based devices. Thus, we use the feature vector employed in Gupta et al. (2020), which consists of 91 features in total (see Table B8 Appendix). These features can be roughly divided into two classes (Gasse et al., 2019 Khalil et al. 2016), i.e., the static features describing the input MILP problem and the dynamic features representing the status of the solver at current node. See Appendix F for more discussions on tackling bipartite graph Gasse et al. (219)) inputs via symbolic graph models.
Mathematical Operators and Constants. In the Symb4CO, we use mathematical operators from {+, -, X, log, exp, pow). Though there are more complex operators like (sin, cos). J. we find their contribution to higher performance is limited in practice. We use constants from {0.2, 0.5, 2.0, 5.0) and other constants are generated by combining them in the symbolic tree (Landajuela et al. 2021 Another approach to generate constants is to employ placeholders and optimize them in inner opti- mization loops each iteration (Petersen 2019). However,
find this approach achieves similar asymptotic performance to the above one in this task, while introducing an inner optimization loop generally requires higher training cost. See comparisons in Table 6 comparisons.
4.2 THE GENERATOR OF SYMBOLIC TREES
There are multiple ways generate the symbolic trees. Traditional approaches in genetic program- ming employ evolutionary algorithms (Chen et al. 2023 Cranmer et al., 2020b). In this paper, we employ deep learning models generator based on recent development of deep symbolic opti- mization algorithms (Petersen 2019 Landajuela et al. 2021). We observe this achieves significantly
higher asymptotic imitation accuracy in our task (see Table 3
The Sequential Model. Once given the traversal, an expression tree is one-to-one to a expression sequence r (Petersen 2019). Thus, we can employ a sequential model to generate the expression sequence. Specifically,
recurrent neural network (RNN) to output the tree nodes step by step. At each step, we input the parent and the sibling nodes to capture the hicrarchical information of the expression tree (or empty token if no parent or sibling exists) that in Petersen (2019), and we output a categorical distribution over all possible tokens to sample the current token. Then,
(T( 11_L1_ Pe (T: T1:(6-1))
is the likelihood to generate the expression sequence т, where pe is approximated by an RNN.
Constraints as Prior. We can further apply constraints on the the search space to accelerate the training process (Petersen 2019 Landajuela et al.) (02T). In Symb4CO, we employ: a) length constraints, which restrict the complexity of the expression tree specific ranges; b) inverse operator constraints, which restrict the child of a unary operator not to be the inverse of its parent; c) non- trivial constraints, which ensures the symbolic tree to contain at least one input feature.
4.3 THE FITNESS MEASURE
Due to the NP-hard nature of CO problems, training from scratch (i.e., randomly generated branch- ing policies) with end-to-end solving time as fitness measure could be extremely intractable. Thus, similar previous research KKaliil al., 20166 Gasse al. 2019 Gupta al., 22000), we use the full strong branching (FSB) (Achterberg) 2007) to collect expert demonstrations and use the behav- ioral cloning accuracy as the fitness measure. The collected data D (SL (1:ke))= includes the features 8; and the FSB scores U; of all branching candidates i 1, 2, ... ki at each node
5

---

Published as a conference paper at ICLR 2024
t == ., .T. Then, the fitness measure can be written
r(r) = B(OLa)LL))D 5 arg Nergmax E fi 10220 Uj 1 k3)
(2)
l:k
where (81:k) Vi:k) is an expert demonstration sampled from D, 8(F) is Dirac delta function that returns if and only if the event J is true (Williams] 1991), and otherwise returns O. Then, the fitness measure is that how many branching variables does the symbolic policy т select in average over the given expert dataset DD that have the highest FSB scores.
4.4 THE TRAINING ALGORITIMM
Based on the generator Pe and the fitness measure r(T), the searching task in the high-dimensional discrete space is converted to an continuous optimization parameters θ to maximize the probabil- ity of generating with high fitness. Observe that the objective non-differentiable with respect to 0. Thus, a natural way optimize it is introduce reinforcement learning (RL) (Petersen 2019).
Problem Formulation. Specifically, we can formulate the training task as a continuous bandit problem. The RNN generator pe (T) is the parameterized policy, the expression sequence output by the generator is the selected action, and the fitness r(T) with given dataset D is the reward.
Policy Gradient Objective. The general RL objective is to maximize the expected rewards of the stochastic policy p(T). i... Er>pe(r) (r]]] Note that we only care about the best 7 generated by the model. Thus, instead of optimizing the average performance, we employ the risk- objective
(Petersen 2019
Tamar et al. 2014) to optimize the best-case performance, i.e.,
J(0;)) = (x) (((T) 2 re(()).
(3)
where e is used to select rewards larger than the (1 (1-c) quantile of all the rewards in the current batch. We employ the proximal policy optimization (PPO) algorithm (Schulman al. 2017) maximize this objective. We further employ the hierarchical entropy regularizer and soft length regularizer as that proposed in Landajuela al. 12021 in Symb4CO.
4.5 THE DEPLOYMENT TO EXACT COMBINATORIAL OPTIMIZATION SOLVER
After the training process, obtain symbolic policy that scores all the candidate variables and then selects the best one to branch. Intuitively, this policy can be regarded as a data-driven version of the juman-designed pseudocost branching rule (PB) integrated in modern CO solvers. As expected in Section 3.22 the learned policy is highly compact, which involves only a small set of active features and simple mapping between inputs and outputs (see T). Thus, similar PB, we directly compile the learned policy to a lightweight shared object using simple script and then integrate into the CO solver package. See Appendix for more details about the deployment.
RESULTS
We conduct extensive experiments to evaluate Symb4Co, which mainly have three goals: a) to illustrate that Symb4CO learned branching functions significantly outperforms existing approaches in terms of the efficiency of solving MILPs; b) to show the appealing features of Symb4CO on training, inference, and interpretability; c) to conduct ablation studies on Symb4Co.
Benchmarks We evaluate Symb4CO on four standard benchmarks used previous research (Gasse et al. 2019 Gupta et al. 2020). That is, the set covering (setcover) (Balas & Ho 1980) the combi- natorial auction (cauctions) (Leyton-Brr) Brown et al. 2000), the capacitated facility location (facilities) (Coruéjolss et al. [191]. and the maximum independent set (indset) (Bergman al. 2015). These four benchmarks can be generated from open-source source codes. We generate small instances (Easy) for training and testing, and larger instances (Medium and Hard) for generalization. We report the size of different benchmarks and the hyperparameters we used in Table D14 in Appendix.
Baselines There are five different baselines to compare in this section to illustrate the superior perfor- mance of GS4CO. We compare Symb4CO to seven baselines to illustrate the superior performance. Specifically, the reliability pseudocost branching (RPB), the pseudocost branching (PB), and the full

---

Published as a conference paper at ICLR 2024
Table 1: Performance of different branching policies with the time limit of 3000s. Both the time and the nodes are 1 1-shifted geometric mean over 80 test instances. All models are trained on easy instances only. (On hard benchmarks, the solver fails to obtain optimal solutions on many instances within the time limit. Thus, the node comparison may not fully reflect the actual performance.)
Setcover:
Fasy
Medium
Hard
Model
Time(s)
Wins
Nodes
Time(s)
Wins
Nodes
Timc(*)
Wins
Nodes
FSB
96.96
0/80
55.2
242.92
0/80
107.0
2852.33
799.1
RPB
11.40
1/80
212.5
100.32
4/80
6116.0
1911.32
13/47
117450.0
PB
42.49
6/80
3686.6
112.39
3/80
9874.2
2158.00
0/20
149628.9
Trees
15.95
0/80
367.0
176.04
0/80
4350.2
2567.31
0/23
56962.9
MLP
9.63
0/80
290.7
102.63
0/80
5023.7
2142.81
0/40
75772.8
GNN
14.19
0/80
239.5
104.22
0/80
3381.5
2661.75
0/17
28517.8
Hybrid
8.97
6/80
279.4
90.20
8/80
4103.5
1900,96
G/47
72712.7
Symb4CO
7.10
67/80
304.7
86.92
65/80
5623.2
1894,38
30/48
129231.6
GNN-GPU
7.74
-880
239.5
74.91
-/80
3381.5
1810.93
-/50
92996.7
Cauctions:
Easy
Medium
Hard
Model
Time(s)
Wins
Nodes
Time(s)
Wins
Nodes
Time(s)
Wins
Nodes
FSB
14.05
0/80
17.7
156.20
0/80
116.6
1903.37
0/51
533.8
RPB
3.00
0/80
26.2
23.05
1/80
1434.4
209.57
40/80
14532.4
4.02
0/80
731.8
29.05
0/80
4855,2
397.38
2/80
41536.9
Trees
3.50
0/80
116.0
64.43
0/80
2251.6
1270.82
0/73
31945.8
MLP
1.98
0/80
107.8
21.14
0/80
1298.5
273.85
0/80
17295.3
GNN
2,20
1/80
93.6
26.93
0/80
1201.8 8
266.80
0/80
12898.0
Hybrid
1.87
0/80
96.5
19.04
4/80
1149.1
225.70
10/80
16638.3 3
Symb4Co
1.57
79/80
99.1
15.14
75/80
1328.5
211.08
28/80
17429.1
GNN-GPU
1.74
-/80
93.6
16,29
-/80
1298.5
193.14
-880
12898.0
Facilities:
Easy
Medium
Hard
Model
Time(s)
Wins
Nodes
Time(s)
Wins
Nodes
Time(s)
Wins
Nodes
FSB
92.45
0/80
110.00
428.35
0/80
185.3
1089. 16
0/69
76.0
RPB
54.05
3/80
211.10
250.88
1/80
369.3
766.29
0/78
270.3
PB
53.30
8/80
468.70
195.22
22/80
651.5
687.64
4/75
461.5
Trees
59.68
0/80
460.70
283.73
3/80
790.3
828.91
0/75
532.8
MLP
40.39
6/80
395.40
215.02
6/80
593.2
636.26
12/75
463.4
GNN
52.28
1/80
376.90
311.58
0/80
597.1
790.21
0/75
402.5
Hybrid
39.24
19/80
383.70
207.89
18/80
597.4
625.23
28/78
428.5
Symb4CO
37.76
43/80
401.20
194.01
30/80
533.6
618.77
34/78
377.4
GNN-GPU
34.95
-180
376.90
204.16
-180
597.1
593.39
-778
476.5
Indset:
Hasy
Medium
Hard
Model
Time(s)
Wins
Nodes
Time(s)
Wins
Nodes
Time(s)
Wins
Nodes
FSB
620.48
0/80
28.7
2110.75
0/41
133.9
3000.00
0/0
57.4
RPB
42.69
0/80
1500.5
178.43
10/80
6891.2
2140.77
5/37
53112.4
PB
153.59
1/80
14221.9
1226.90
D/60
86695.5
2975.40
0/4
73390.6
Trees
87.91
0/80
1317.5
371.75
0/66
25544.9
2833.05
0/G
60291.7
MI.P
39.23
10/80
2490.9
236.63
10/80
12938.9
2202.30
2/27
39195.5
GNN
29.77
23/80
826.2
707.70
3/78
8375.2
2735.31
0/15
40107.2
Hybrid
36.27
14/80
2016.1
166.38
18/80
8337.4
1918.32
7/31
33558,9
Symb4CO
29.21
32/80
954.6
138.80
39/80
5724.2
1578.58
27/41
43582.6
GNN-GPU
25.13
-/80
826.2
145.72
-/80
8375.2
2026.70
-/36
57640.6
strong branching (FSB) are three human-designed branching policies integrated in modern solvers like SCIP by default (Achterberg. 2007): We compare Symb4CO to seven baselines to illustrate the superior performance. Specifically, the reliability pseudocost branching (RPB). the pseudocost branching (PB), and the full strong branching (FSB) are three human-designed SOTA branching policies integrated in SCIP by default (Achterberg) 2007); the Trees model (Alvarez et al.) (017)) based on the ExtraTrees (Geurts et al., 2006), the GNN (Hamilton) 2020) based model proposed in Gasse et al. (2019). and the MLP and Hybrid models proposed in Gupta et al. (2020) are four ML approaches. We compare to: a) tree models as they are widely used ML models for their reliability and interpretability; b) MLP models Symb4CO learned policies use the same input features as that in MLP models, and thus the symbolic policies can be regarded as an extremely lightweight version of MLP: e) GNN and Hybrid models they are SOTA ML. approaches on GPU and CPU.
7

---

Published as a conference paper at ICLR 2024
Table 2: The performance of MI. approaches when only one training instance is available. Results show that Symb4CO is the only approach maintaining high performance in such condition. We note this evaluation setup practical as we have learn from scratch in many real-worke CO tasks.
Cauctions:
Easy
Medium
Hard
Model
Time(s)
Wins
Nodes
Time(s)
Wins
Nodes
Time(s)
Wins
Nodes
RPB
3,00
1/80
26.2
23,05
10/80
1434,4
209.57
65/80
14532.4
Trees-1
3.13
0/80
205.6
67.54
0/80
2767.1
1692.58
0/51
56263.2
MLP-1
3.75
0/80
541.5
1293.25
0/80
160516.7
2911.52
0/7
203175.6
GNN-1
2.76
1/80
183.7
92.73
0/80
5408.4
1762.33
0/58
96201.0
Hybrid-1
2.25
3/80
183.5
30.90
0/80
2349.2
691.18
1/49
38745.2
Symb4C0-1
1.72
75/80
116.1
18.48
70/80
1987.7
255.06
14/80
20139.2
Training and Evaluation Settings For Symb4CO, we use only ten and four instances to generate 1, 000 and 400 samples for training and validation on all benchmarks. We normalize the imput fea- tures of all candidates inside each B&B node to [0, 1] as that in previous work (Gupta et al. )020). We observe that the end-to-end performance is not entirely positively correlated to its imitation ac- curacy. Thus, select the symbolic policies with top ten imitation learning accuracy on validation sets and then execute them on the validation instances to select the best-performed one. For all the other ML-based baselines, we use their official implementations and the default settings used in pre- vious work (Gasse et al. 2019 Gupta et al. 2020). Specifically, we use 10, 000 and 2, 000 instances to generate 100, 000 and 20, 000 samples for training and evaluation for these baselines, respec- tively. For Hybrid models, we use the FiLM features (Perez et al., 2018) with euclidean distance as the auxiliary task and knowledge distillation techniques, which we find effectively improves the training efficiency. We use 80 instances to evaluate the performance and the generalization ability. We report the standard metrics used in previous research: a) Time: the 1-shifted geometric mean (Achterberg] (007) of running time in seconds; b) Nodes: the 1-shifted geometric mean of B&B nodes generated by the branching policies, which are hardware-indene inndaarr-indeeedeett c)Wins: number of times that branching policy wins all the others. We tune all hyperparameters the cauctions benchmark and then directly apply to all the other benchmarks. See Appendix for more details.
5.1 COMPARATIVE EVALUATION
Solving Efficiency We compare Symb4CO to all baselines and report the results in Table Results show that Symb4CO learned purely CPU-based policies achieve comparable performance to GPU- based GNN policy and clearly outperform all the other CPU-based policies. Moreover, Symb4CO learned policies generalized well to Medium and Hard datasets. Note that Symb4CO achieves such performance with only ten training instances and one CPU core.
Imitation Learning Accuracy We report the imitation learning accuracy on the test sets in Table 3 The results show that Symb4CO learned policies achieve comparable accuracy com- plex MLP models and significantly higher than the interpretable Trees. Note that Symb4CO learned policies lightweight, interpretable, and re- quire much fewer training instances. Symb4CO achieves higher accuracy than GPLearn (Stephens & contribu- tors Year of access), which one of the SOTA open-source GP libraries.
Table 3: Imitation learning accuracy on test sets. Here
GPLearn is a genetic programming library for symbolic dis- covery. Symb4CO achieves comparable accuracy to MLP, while it is training efficient, lightweight, and interpretable.
Model
Cauctions
Facilities
Indset
Setcover
PB
12.10
7.49
27.82
19.60
Tree
38.40
61.50
19.20
40.30
MLP
43.14
66.78
48.34
47.30
Hybrid
44.30
67.60
$1.10
49.20
GNN
47.29
69.60
56.86
$3.88
GPLeam
38.56
63.00
38.00
42.30
Symb4Co
43.20
66.30
46.50
47.70
5.2 STRENGTHS FOR APPLICATION
Training Efficiency Besides the results in Figure ((a) we further compare the performance of Symb4CO the other ML baselines with only training instance. Results in Table 2 show that Symb4CO is significantly more training efficient than other ML approaches, as it can achieve high performance with only one training instance. This is mainly because that the use of symbolic
8

---

Published as a conference paper at ICLR 2024
operators can be regarded enforcing strong regularizations (Landajuela et al. (021). We note this setting is practical as we have to learn from scratch in many real-world CO tasks.
Inference Efficiency We compare the de- cision making time (the time of feature ex- traction plus model inference) for differ- ent ML approaches. Results in Table 4 show that Symb4CO learned policies are extremely efficient on purely CPU-based devices. The efficiency comes from both the small set of extracted features and the compact symbolic policies. We also empir- ically observe that their inference efficiency more stable than other MI. policies on workstations where CPU usage exhibits significant fluctuations due to other parallel tasks.
The average decision making time (in mil- lisecond) of all ML-based branching policies on dif- ferent problem sizes. Results show that Symb4CO learned policies are extremely efficient for inference compared to the other ML-based approaches.
Table 4:
Cauctions: Trees MLP GNN Hybrid Symb4CO GNN-GPU
Easy
14.70 3.00
5.26
3.73
0.04
1.74
Medium 17.20 6.47
11.57
7.34
0.07
2.84
Hard 28.50 9.56 10.50
9.91
0.08
3.19
Interpretability We report the learned poli- cies in Table 5 We observe that expressions containing log and exp can achieve high learn- ing accuracy but fail to achieve the best end- to-end time efficiency during validation. As expected in Section 3.2] the symbolic policies are significantly more compact than other ML models. We note that the complied symbolic policies are only 1/80 the size of Hybrid mod- els in average, which highly facilitates their deployment to CO solvers. Furthermore, we found policies trained on one benchmark tend to generalize well to another benchmark (Ta- ble B). We observe RPB integrated in SCIP Gleixnnr et al. 2018) uses scoring function
Table 5: Symb4CO learned branching policies are significantly more compact than other MI. models (see Table B8 for feature descriptions). They are easy to be integrated into the distributions CO solver packages due to their lightness. We believe these policies can help MO researchers to further optimize hard-coded branching policies like RPB.
880 (4 7835 + 5887 + 3838
Setcover
+855 + 2865 + 857 + 2871)
Cauctions
835 8a5.818844888 S3 (80 + 889)
Say (48 + 38.s + 2826 + 2854
Facilitics
+8.7 + 3853 + 2854 + 6877 + 48ss)
Indset
823 + 7836 852 + 5850 + 871
with human-daa designed features and expressions rather than vanilla pseudocosts. The intuition behind
the design of this scoring function is highly similar to the learned symbolic policies in Table Thus, we believe Symb4CO can help researchers further understand and optimize these hard-coded rules.
5.3 ABLATION STUDY
We conduct ablation study to compare different mathematical operators and constant choices (as mentioned in Section 4.1) in Table 6 First, we compare the mathematical operators we used with a larger one containing (sin, cos, tan]. Then, we compare the constant placeholder approach (Pe- tersen, 2019) with the constants used in Symb4CO. Results show that neither of them contributes to higher performance, which aligns with our expecta- tions. Intuitively, this is because there is no period- icity in CO solvers and scoring functions in ranking tasks are usually stable against perturbations.
Table 6: Ablation study on more mathemat- ical operators and constant choices. Results show neither of the them contributes to higher performance. Note that both introducing more operators and optimizing constant placchold- ers can lead to additional training costs.
Method
Cauctions
Facilities
Default
43.3
67.3
More Math Operators
43.3
67.3
Constant Placeholder
42.8
67.3
6 CONCLUSION AND FUTURE WORK
In this paper, we propose the first deep symbolic discovery framework Symb4CO for exact CO solver. Experiments show that Symb4CO achieves high performance and remarkably efficient and interpretable for deployment. Exciting avenues for future work include discovering more complex working flows (c.g.. the complex working flow in the RPB policy), handling more general input data structures (e.g., sequences and graphs), and deploying Symb4CO to more components in modern solvers (e.g., the simplex pricing strategies and the primal heuristics). We firmly believe the immense potential of symbolic models in wide range of critical real-world applications like CO solvers.
9

---

Published as a conference paper at ICLR 2024
REPRODUCIBILITY
We conduct all experiments the open-source solver SCIP Optimization Suite 6.0 Gleixnnr al. 2018). All benchmarks in this paper are widely used ones in previous research (Gasse et al. 2019
Gupta al. 2020). which be generated directly with open-sourced codes and hyperparameters
listed in Table D14 All baselines are evaluated directly using the GitHub repository (pg2455 2023)
provided by Gupta al. (2020) and the default settings described Section The learned policies
are all reported in Table 5 and the implementation details are provided in C Then, the imitation
learning accuracy can be evaluated directly using the features implemented in Gupta et (2020).
ACKNOWLEDGMENTS
The authors would like to thank all the anonymous reviewers for their insightful comments, This work supported by National Key R&D Program of China under contract 20227D01 19801 and National Nature Science Foundations of China grants U23A20388, U19B2026, U19B2044, and 62021001.
REFERENCES
Tobias Achterberg. Constraint integer programming. PhD thesis, Berlin Institute of Technology, 2007.
Alejandro Marcos Alvarez, Quentin Louveaux, and Louis Wchenkel. A machine learning- based approximation of strong branching. INFORMS J. Comput., 19(1):185-195, 2017. doi: 10.1287/ 201c.2016.0723. URL ht..tt:::ps//..m....
10. 1287/1 jac 201 6. 0723
Egon Balas and Andrew Ho. Set covering algorithums using cutting planes, heuristics, and subgra- dient optimization: a computational study. Springer, 1980.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial opti-
mization: A methodological tour d' d'horizon. Eur. J. Oper. Res., 290(2):405-421, 2021. doi: 0.001///.ejorr.22200077
David Bergman, André Augusto Ciré, Willem Jan van Hoeve, and J. Hooker. Decision diagrams for optimization. Constraints, 20:494 495. 2015.
Der-San Chen, Robert G Batson, and Yu Dang. Applied integer programming: modeling and solu- tion. John Wiley & Sons, 2011.
Xiangning Chen, Chen Liang, Da Huang, Esteban Real, Kaiyuan Wang, Yao Liu, Hieu Pham, Xu- anyi Dong, Thang Luong, Cho-Jui Hsieh, Yifeng Lu, and Quoe V. Le. Symbolic discovery of optimization algorithms. ArXiv, abs/2302.06675, 2023.
Zhi-Long Chen. Integrated production and outbound distribution scheduling: review and extensions. Operations research, 58(1) 130-148, 2010.
Antonia Chmiela, Elias Boutros Khalil, Ambros Gleixner, Andrea Lodi, and Sebastian Pokutta.
Learning to schedule heuristics in branch and bound. 2021.
Gérard Cornuéjols, Ramaswami Sridharan, and Jean-Michel Thizy. comparison heuristics and relaxations for the capacitated plant location problem. European Journal of Operational Research, 50:280-297, 1991.
Miles Cranmer, Alvaro Sanchez Gonzalez, Peter Battaglia, Rui Xu, Kyle Cranmer, David Spergel, and Shirley Ho. Discovering symbolic models from deep learning with inductive biases. Advances in Neural Information Processing Systems, 33:17429 17442, 2020a.
10

---

Published as a conference paper at ICLR 2024
Miles D. Cranmer, Alvaro Sanchez-Gonzales Peter W. Battaglia, Rui Xu, Kyle Cranmer, David N. Spergel, and Shirley Ho. Discovering symbolic models from deep learning with induc- tive biases. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Bal- can, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: An- nual Conference Neural Information Processing Systems 2020, NeurIPS 2020, December 6- 12, 2020, virtual, 2020b. URL http:::: http://ttttttttttee/eeeeeeeeeeee blah/c9f2f99 c9f2f91 2tt/8822dd22233333beeee hwtp:poooeeennnnn...iippp..pp.pp
http::::///cccceeeeeeeee www.:occaaaabtttttt........ wwwplppp.ccpppppppeee cc/paper/202c/
Mare Etheve, Zacharie Alès, Côme Bissuel, Olivier Juan, and Safia Sillad-Sidhomm. Reinforcement learning for variable selection in branch and bound algorithm. Emmanuel Hebrard and Nysret Musliu (eds.), Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pp. 176-185, Cham, 2020. Springer International Publishing. ISBN 978-3-030-58942- 4.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact com- binatorial optimization with graph convolutional neural networks. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference Neural Informa- fion Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp- 15554-15566, 2019.
Zijie Geng, Xijun Li, Jie Wang. Xiao Li, Yongdong Zhang, and Feng Wu, A deep instance generative framework for MILP solvers under limited data availability. In Thirty-sevnnth Conference on Neural Information Processing Systems, 2023.
net. forum?
Id=AiEipk1X0s
Pierre Geurts, Damien Ersst, and Louis Wehenkel. Extremely randomized trees. Mach. Learn., 63(1):3-42, 2006. doi: 10. 00.1007/11999--066-2266111 URL $10994-006 0226-0666666622
Ambros Gleixner, Michael Bastubbe, Leon Eifler, Tristan Gally, Gerald Gamrath, Robert Lion Gottwald, Gregor Hendel, Christopher Hojny, Thorsten Koch, Marco E Lübbecke, al. The scip optimization suite 6.0. technical report. Optimization Online, 2018.
Prateek Gupta, Maxime Gasse, Elias B Khalil, M Pawan Kumar, Andrea Lodi, and Yoshua Bengio. Hybrid models for learning to branch. 2020.
Prateek Gupta, Elias Boutros Khalil, Didier Chételat, Maxime Gasse, Andrea Lodi, Yoshua Ben- gio, and M. Pawan Kumar. Lookback for learning to branch. Transactions on Machine Learn- ing Research, 2022. ISSN 2835-8856. URL https: httt:::://penreviee net/ feet/forrsee forummiii EQpGkw5rvI Expert Certification.
Gurobi. Gurobi Optimizer Reference Manual, Utttt:t::://w/t URU/ttps:/www.uuo00...
William L. Hamilton. Graph Representation Learning. Synthesis Lectures Artifi-
cial Intelligence and Machine Learning. Morgan & Claypool Publishers, 2020. doi:
10.200//010445EDI001 Y202009990 5010455D100112220000AA
URL httpp:://ci.. org/10 2200/
He He. Hal Daumé III, and Jason Eisner. Learning to search in branch and bound algorithms. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger (eds.), Advances Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pp- 3293-3301, 2014.
Sean B Holden et al. Machine learning for automated theorem proving: Learning to solve sat and qsat. Foundations and Trends@ in Machine Learning. 14(6):807-989) 2021.
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. Patlern Recognition, 123: 108353, 2022.
11

---

Published as a conference paper at ICLR 2024
Michael Jünger, Thomas M Liebling, Denis Naddef, George L Nembauser, William R 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-an, Springer Science & Business Media, 2009.
Elias Boutros Khalil, Pierre Le Bodic, Le Song, George L. Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. In Dale Schuurmans and Michael P. Wellman (eds.), Proceedings of the Thirtieth AAAI Conference Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA, pp. 724-731, AAAI Press, 2016. doi: 10.1609/anai.v30i1..000
URL
https: // /ww./oo..oo//// owg. 10. 1 609/ aaai. 1033011100000
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http:
/112 6980
Mikel Landajuela, Brenden K Petersen, Sookyung Kim, Claudio P Santiago, Ruben Glatt, Nathan Mundhenk, Jacob F Pettit, and Daniel Faissol. Discovering symbolic policies with deep rein- forcement learning. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning. volume 139 of Proceediings of Machine Learning Research, pp. PMLR, 18- 24 Jul 2021. URL
mlr. wttp:////..r.eeee/1/1/3/.3.
landajuela 21a 2tmmmll..lmmmmlmm.mmmmmm.mmmm11.
Kevin Leyton-Brown, Mark Pearson, and Yoav Shoham. Towards a universal test suite for combina- torial auction algorithms. In Proceedings of the 2nd ACM Conference on Electronic Commerce, pp. 66-76, 2000.
Xijun Li, Fangzhou Zhu, Hui-Ling Zhen, Weilin Luo, Meng Lu, Yimin Huang, Zhenan Fan, Zirui Zhou, Yufei Kuang, Zhihai Wang, et al. Machine learning insides optverse ai solver: Design principles and applications. arXiv preprint arXiv:2401.05966 2024.
Haoyang Liu, Yufei Kuang, Jie Wang, Xijun Li, Yongdong Zhang, and Feng Wu. Promoting general- ization for exact solvers via adversarial instance augmentation. arXiv preprint arXiv:2310.14161, 2023.
Songsong Liu, Jose M Pinto, and Lazaros G Papageorgiou. A tsp-based milp model for medium- term planning of single-stage continuous multiproduct plants. Industrial & Engineering Chem- istry Research, 47(20))7733-774 2008
Kefan Ma, Liquan Xiao, Jianmin Zhang, and Tiejun Li. Accelcrating an fpga-based sat solver by software and hardware co-design. Chinese Journal of Electronics, 28(5):953-96 2019.
Daniel J. Mankowitz, Andrea Michi, Anton Zhernov, Marco Gelmi, Marco Selvi, Cosmin Padu- raru, Edouard Leurent, Shariq Iqbal, Jean-Baptiste Lespiau, Alex Ahern, Thomas Koppe, Kevin Millikin, Stephen Gaffney, Sophie Elster, Jackson Broshear, Chris Gamble, Kieran Milan, Robert Tung. Minjae Hwang, Taylan Cemgil, Mohammadamin Barekatain, Yujia Li, Amol Mandhane. Thomas Hubert, Julian Schrittwieser, Demis Hassabis, Pushmeet Kohli, Martin Riedmiller, Oriol Vinyals, and David Silver. Faster sorting algorithms discovered using deep reinforcement learn- ing. Nature, 618(7964):577266 263,, 2023, doi: 10. 10.1038//4188666 023- -20-6-0033-000--99 06004-9.
Christopher W. F. Parsonson, Alexandre Laterre, and Thomas D. Barrett. Reinforcement learning for wranchandd-ouud optimisation using retrospective trajectories. AAAI Conference on Artificial Intelligence, volume 37 (4), pp. 4061-4069, 2023. URL. https::///// :tnp:://do1: /tt. 00r./10.11100000
aaai. v3714.3.... 25521
Max B Paulus and Andreas Krause. Learning to dive in branch and bound. arXiv preprint NXXV:23001.0943.. 2023.
Ethan Perez, Florian Strub, Harm de Vries, Vincent Dumoulin, and Aaron C. Courville, Film: Visual reasoning with a general conditioning layer. In Sheila A. Mcllraith and Kilian Q. Weinberger (eds.). Proceedings of the Thirty-Secone AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium
12

---

Published as a conference paper at ICLR 2024
Educational Advances in Artificial Intelligence (EAAI-18). New Orleans. Louisiana, USA, February 2-7, 2018, pp. 3942-3951. AAAI Press, 2018. doi: 10.1609/aaai.v321..11677 URL
https: / / //oi..... org/ 10. (0066099/aa0
Brenden K. Petersen. Deep symbolic regression: Recovering mathematical expresssons from data via policy gradients. CoRR, abs/1912.04871, 2019. URL http:::/aaax....r///bbbbb///////
04871
Brenden K Petersen, Mikel Landajuela Larma, Terrell N. Mundhenk, Claudio Prata Santiago, Soo Kyung Kim, and Joanne Taery Kim. Deep symbolic regression: Recovering mathematical expressions from data via risk-seeking policy gradients. International Conference on Learning
Learnin htt.:/rwwwe...et...ooooooooooooo
Representations, 2021.
https:
Pg2455. Hybrid learn to branch, 2023. Mybrrd- learn2branch Accessed: 2023-09-29.
URL http::///github.ccmm/pp22
Riccardo Poli, William B. Langdon, and Nicholas Freitag McPhee. A Field Guide to Ge-
netic Programming. lulu.com, 2008. ISBN 978-1-4092-0073-4
URL. http://www.
gl-fLeld-guide.ore org.uk/
Lara Scavuzzo, Feng Chen, Didier Chetelat, Maxime Gasse, Andrea Lodi, Neil Yorke- Smith, and Karen Aardal. Learning to branch with tree mdps. In S. Koyejo, S. Mo- hamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural In- formation Processing Systems, volume 35, pp. 18514-18526. Curran Associates, Inc., 2022. URL httpsss//prrceeedngs..eeeeeeeeee wttp:iisssccpppprr_reeeeeeeeeeee fttp Ei F117775544405532280000222222aaa2 ConerrCreeccceeeeccceccceeceeee,
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, abs/1 .004470 2017. URL http://arxiv. wwwpexivvvorggaooo abs/
1707 06347
Hongzhi Shi, Jingtao Ding, Yufan Cao, Li Liu, Yong Li, et al. Learning symbolic models for graph-structured physical mechanism. In The Eleventh International Conference on Learning Representations, 2022a.
Hongzhi Shi, Jingtao Ding, Yufan Cao, Li Liu, Yong Li, et al. Learning symbolic models for graph-structured physical mechanism. In The Eleventh International Conference on Learning Representations, 2022b.
Trevor Stephens and contributors. Gplearn: Genetic programming for symbolic regression in python, Year of access. URL bttps://ggttaii
com wtw.ituub..com/eeeetttteeeeeeeee cccom//teeeorrteeeeee/ggggg/pppp
Haoran Sun, Wenbo Chen, Hui Li, and Le Song. Improving learning to branch via reinforcement
learning. In Learning Meets Combinatorial Algorithms at NeurIPS2020, 2020. URL https:
//open net./ forum? d=z407 www.foomddd...m-eeee
Aviv Tamar, Yonatan Glassner, and Shie Mannor. Policy gradients value-at-risk. CoRR, abs/ 1od..4604... 2014. URL http:///wwx....o////////000 3862
Conditional
Zhihai Wang, Xijun Li, Jie Wang, Yufei Kuang, Mingxuan Yuan, Jia Zeng, Yongdong Zhang, and Feng Wu. Learning cut selection for mixed-integer linear programming via hierarchical sequence model. 2023.
David Williams. Probability with Martingales. Cambridge mathematical textbooks. Cambridge University Press, 1991. ISBN 978-0-521-40605-55
Giulia Zarpellon, Jason Jo, Andrea Lodi, and Yoshua Bengio. Parameterizing branch-and-boun search trees learn branching policies. Proceedings of the AAAI Conference on Artificial Intelli- gence, 35(5):3931 39399999999999 May 2021. URL httpt::t/////t aaai org wtgg/nndx..... phhp/AAI/ article/view/16112
13

---

Published as a conference paper at ICLR 2024
A RELATED WORK
A.1 MACHINE LEARNING FOR COMBINATORIAL. OPTIMIZATION
Existing research machine learning for combinatorial optimization (ML4CO) in exact solver mainly concentrates on leveraging deep models to (1) approximate some expert heuristics that suffer from heavy computational costs (Gasse al. 2019 Gupta et al. [2020] Zarpellon et al. 2022 Guptta 2022 or (2) improve some weak heuristics with unsatisfactory performance (Chmiela et al. Wang al., ).23). For the former category, [H al. (2014) learn a node selection policy by imitating the optimal policy given the optimal solutions; Gasse et al. (2019) and Gupta et al.
et al.
202 1
(2022) use graph neural networks as fast approximations for the time-consuming strong branching heuristics with imitation learning. For the latter, [Chmicla et al.] (202T) construct a schedule for collection of primal heuristics to obtain good primal solutions and learn a good schedule via reinforcement learning; Waag et al. (2023) leverage a sequential model to learn a cut selection policy by reinforcement learning. These approaches have achieved promising improvements in solving efficiency.
A.2 LEARNING TO BRANCH IN A BRANCH-AND-BOUUT SOLVER
During the solving process, branching policy key factor that influences the efficiency of the B&B solver. Traditional basic branching heuristics mainly include strong branching and pscudocost branching policies. The strong branching policy can produce the smallest B&B search trees but suffers from high computational costs. The pseducost branching policy uses much simpler pse- ducost score to evaluate the progress of each branching candidate but requires extensive engineering experience and significant manual tuning.
Recent works have leveraged machine learning to approximate the time-consuming traditional branching policy and speed up the branching module in a B&B solver. (Khalil et al. (016) for- mulate the branching variable selection problem as a ranking problem and train a variant of support vector machine (SVM) on the data collected from a strong branching expert for ranking. (Alvarez et al. 2017) uses ExtraTrees model to predict the branching scores. To capture the rich feature in- formation in the input data, researchers use deep models with GPU inference further enhance the solving performance. Based on the imitation-learning based approach, (Gasse et al.) (2099) repre- sent each subproblem the solving process as bipartite graph and propose a graph convolutional neural network (GCNN) model to mimic the strong branching policy; (Zarpellon et al. 2021) imi- tates the default branching policy (reliability pseudocost branching) with deep neural network and incorporates explicit parameterization of the state of the search tree with extra gating layers. For the wewreeemeeet--ennn-nbbbeee
methods, (Etheve et al. 2020) first leverage reinforcement learn- ing for branching with deep Q-learning. Other works utilize the GCNN to parameterize the value function or policy function ((Sun et al. (2020), (Scavuzzo et al. 2022) and (Parsonson et al. (2023). Though the existing works we mentioned above achieve high solving efficiency, they employ deep models and rely heavily on GPUs for fast inference.
However, modern exact CO solvers usually deployed CPU clusters. While existing CPU- friendly machine learning models such as Trees (Alvarez et al. 2017) suffer from unsatisfactory variable selection accuracy, the inference time of the deep models may become much longer on the CPU machines. Thus, the lightweight deployment of the deep models on CPUs becomes a significant topic (Gupta et al., 2020). To run the deep branching policy on the CPU machines more efficiently, Gupta et al. (2020) propose hybrid branching policy that uses an expressive graph neural network to branch at the root node of the branch-and-boume tree and a computationallfrient multi-layer perceptron at the other nodes. To step further, Symb4CO avoids running deep models on CPU machines in the inference time and leverages the expressive deep models to search the simple symbolic mathematical expressions, in which we achieve high inference efficiency.
A.3 MACHINE LEARNING FOR ALGORITHM DISCOVERY
Machine learning has the potential to discover implicit rules that are beyond human intuition from training data and construct algorithms that outperform handeraft programs. ML for algorithm dis- covery includes symbolic discovery, program search, etc. Specifically, Program search focuses on optimizing the computing stream of the algorithm, such Mankowitz al. (023) for discovering
14

---

Published as a conference paper at ICLR 2024
Table B7: The cross- cross-benchmark evaluation for learned policies in Table (Time: s). We surprisingly benchmark usually generalize well to another. A
found that symbolic policies trained potential reason is that the learned symbolic policies are very compact and their parameters are very sparse, which effectively improves the generalization ability of these policies.
Benchmark Policy From
SetCover
Cauctions
Facilitics
Indsct
RPB (Default)
Setcover
7.10
21.90
9.13
12.10
11.40
Cauctions
1.81
1.57
1.82
2.36
3.00
Facilities
46.44
65.07
37.76
38.40
54.05
Indset
22.28
22.16
66.08
29.21
42.69
faster sorting algorithms and Chen et al. (2023) for searching for an efficient optimization algo- rithm. Compared program search, the symbolic discovery framework aims searching the space of small mathematical expressions instead of computing streams (Petersen et al. 2021] Landajuela
al. 202T). The symbolic discovery framework is analogous an extreme model distillation tech- nique, extracting knowledge from black-box neural network to hard-code expressions. Evolution- ary algorithms, including genetic programming, are traditional approaches for symbolic discovery (Poli et al., 2008). Recently, deep learning has demonstrated its powerful representational capacity, offering a new approach to solving symbolic discovery problems.
B INPUT FEATURES
We the 91-dimension features in Gupta et al. (2020), which used the input of MLP in Gupta et al. (2020). These features can be roughly divided into two classes, i.e., the static ones that describe the MILP problem and the dynamic ones that describe the solving status. We list all the
features in Table B8
C IMPLEMENTATION DETALS
Algorithm Deep Symbolic Discovery for Exact Combinatorial Optimization Solver
Input: the sequential model pa. the library of tokens L, and the distribution of MILP instances I. Collect expert demonstration with strong branching:
Initial expert demonstration buffer: D x- 0.
while D < S do
Sample MILP instance I I. solve I with strong branching.
Collect variable features and SB scores: D + D (s U1 )
Here kG is the number of branching candidates at B&&B node end while
Train the sequential model po: for iteration= 1,2, ,N do Sample J symbolic functions using tokens in L: T1:J Po- // Calculate the fitness measure of each symbolic function for evaluation: for j 1,
do
r(T,) Mi JDD [ō (arg max1:k, T8() arg max1:1; u:)
end for
Train model: update pa via PPO by optimizing e(0
end for Output: Symbolic function Thest with highest r(-) on validation set.
Model Architecture and Hyperpaaaameters Symb4CO uses LSTM to generate symbolic branching
functions. The hyperparameters of Symb4CO are listed in Table C9 which roughly follows the setting in Petersen et al. 2021); Landajuela et al. (02T). All experiments
executed Intel Xeon Platinum 2z CPUs and NVIDIA Tesla 100 GPUs. All the other baselines are executed
using the implementation in previous research Gupta al. (2020) as mentioned in Section 5
15

---

Published as a conference paper at ICLR 2024
1.2
Symb4CO
normallzdd FS8 score
0.88
0.6
0.4
0.0
depth
Figure C3: The curve of FSB different depths the Medium dataset of the Setcover benchmark.
Constraints as Prior There are several types of constraints employed in Symb4CO, which serves priors to reduce the search space and accelerate the training procedure. These constraints include:
The hard length prior, which limits the output expressions to specific range by zeroing out the probabilities of tokens that would violate the constraint. Specifically, sets the probabilities of leaf nodes (i.e., tokens of variables and constants whose degree of children is zero) to zero if the output expression shorter than minimal length and sets probabilities of non-leaf nodes (i.e., tokens of mathematical operators) zero if the output expression is longer than expected. We set the minimal and the maximal length to 4 and 64, respectively.
Inverse operator constraints, which restrict the child of unary operator not to be the inverse its parent by zeroing out its probability. These inverse operators are the (exp, log) pair.
Non-trivia constraints, which ensures the symbolic tree to contain at least one input feature by zeroing out the probabilities of constants when there is only one empty leaf node left and all the other leaf nodes are constants.
The soft length prior, which limits the lengths of the initial outputs of RNN not to concen- trate extreme points by adding priori distribution to the outputs. Specifically, the values in the priori distribution depend on the current length of the expression, which encourages the probabilities of non-leaf nodes when the expression shorter than the given soft length prior (A = 20) and encourages the probabilities of leaf nodes when longer than the soft length prior. Intuitively, the motivation of the soft prior is similar to the entropy regularizer widely used in reinforcement learning.
The lengths of the learned symbolic policies are 45, 19, 55, and 49 on benchmarks Setcover, Cauc- tions, Facilities, and Indset, respectively. We further conduct ablation studies the maximal hard length constraint and the soft length prior Table C Results show that Symb4CO is relatively insensitive the soft length prior, while too short hard length constraint could cause decreased performance.
Symbolic Policy Deployment Observe that there is only small subset of active features in the symbolic policies. Thus, we reimplement a purely C-based feature extraction code with various macros to control whether each feature should be extracted. We also switch the branching policy to RPB when depth is larger than 16 on all benchmarks to gain further acceleration, as we observe that RPB for deep nodes is both precise and efficient (see Table C Table C. and [g analysis).
D DATA GENERATION
We generate the dataset following the process in Gasse et al. (2019); Gupta et al. (2020), using four benchmarks of NP-hard combinatorial problem families, i.c., set covering, combinatorial auction, capacitated facility location and maximum independent set. For each benchmark, we set three levels of difficulty for instances by increasing problem scales, i.e., easy, medium and hard. For Symb4CO,
16

---

Published as a conference paper at ICLR 2024
generate only ten easy instances for training and four easy instances for validation. In order to obtain our datasets of state-action pairs for training and validation, we solve the training instances with SCIP and record new states and strong branching decisions during the branch-and cess. We collect 1, 000 samples for training, and 400 for validation total. For other MI.-based approaches, generate 10, 000 training instances and 2, 000 validation instances attain 100, 000 and 20, 000 state-action pairs for training and validation on all benchmarks. All the methods are evaluated on 240 instances with the time limit of 3, 000s (80 easy instances, 80 medium instances, and 80 hard instances). The instance generation algorithms and hyperparameters for each bench- mark are listed in Table[D14]
pro-
E MORE DISCUSSIONS
Feature Selection Human designed features are widely used in learning- baanid approaches in tasks like branching Khalil al.] (2016), node selection He et al. (2014), and cut selection [Huang et al. (2022). Even the bipartite graph states employed in the branching task contain 25 human-designed features in the constraints, variables, and edges Gasse al. (2019). In fact, during our approach design, we did consider generating features automatically from bipartite graphs based on symbolic models for graph neural networks (GNNs) Cranmer al. 2020a Shi al. (002a)). However, we found three challenges that make the task non-trivial:
1. First, processing bipartite graphs via symbolic models requires complex computation by traversing the entire graph, and the complexity grows linearly with the number of layers consider. This might be extremely expensive for inference on purely CPU-based devices compared with human-designed features.
2. Second, existing approaches learn such symbolic models by symbolize the components in GNN one by one, which results in very high training overhead compared to the lightweight Symb4CO.
3. Finally, most experiments conducted in previous research [5.6] implicitly assume the mes- sage flow passed by GNN carries a specific physical mechanism, which ensures that the message-passingg function is sparse enough for symbolizing. However, the message flow in the branching task might not satisfy this assumption.
Cross Benchmark Generalization It is widely recognized that learning- approaches tend to fail on out of distribution data. However, we surprisingly found that symbolic policies trained on one benchmark can usually generalize well to another benchmark (see the bold values in Table B potential reason that the learned symbolic policies are very compact and their parameters are very sparse, which effectively improves the generalization ability of these policies.
Discussions on Limitations and Future Work We conclude three exciting challenges and their corresponding exciting future work based on the previous analysis:
1. Automated feature generation. Though the features used in this paper are simple to obtain and effective practice, the automated feature generation still promising future work to further help us reduce the domain knowledge for feature design, understand the underlying characteristics of this task, and deploy Symb4CO to more tasks this field.
2. beoshbbenchmark symbolic policy for general CO problems. Based on the results in Ta- wross-benchmart symbolic policy-though might
ble Bl we highly believe that training not achieve the best learning accuracy on specific data distributions to replace the SOTA human-designed scoring function in the RPB policy, is promising avenue for future work.
3. Graph inputs and GPU-based symbolic policies. Bipartite graph is widely used to formulate a series of combinatorial optimization (CO) problems, handling these inputs is further step towards general algorithm discovery system on CO solvers. Deploying symbolic policies on high-end GPUs (when available) can further accelerate the inference speed.
4. Deployment to satisiability (SAT) problems (Holden et al. 2021). Generally, both CO and SAT problems be tackled via generic branch-and bound solvers like SCIP. Thus, applying Symb4CO to SAT problems is quite an exciting and natural idea since they share many similarities in problem structures.
17

---

Published as a conference paper at ICLR 2024
Why Considering Purely CPU-Based Setting? There are two reasons that make symbolic policies necessary:
1. Ease for real-world applications. There are two ways to distribute the learning bearning-based based CO solvers, while neither of them are GPU-friendly:
(a) For deployment to personal users, we can not assume their accessibility to high-end GPU devices, especially for users from the field of traditional mathematical optimiza- tion.
(b) For deployment to cloud services, we note that the inference in branching is taken at significantly high frequency. Thus, when multiple MILPs are solved parallel, instead of packing the inputs into batch, networks for each separate job to avoid the severe blocking (see results reported in Gupta al. (0200) in Appendix 1), which results in high cost for cloud services.
have to initialize independent neural
2. The goal of automatic algorithm/principle discovery. Though the idea of incorporating MI. to modern CO solvers is widely accepted recent years, research that simply replaces the hard-coded components in CO solvers to "black-box" neural networks struggles to help us understand these tasks from the perspective of combinatorial optimization research. However, symbolic policies help further understand what matters in these tasks, and thus, help researchers to further discover new algorithms/principles for these problems.
Other reasons why symbolic policies without GPU are necessary are reported our main paper. In conclusion, compared to previous research, our work provides an entirely new perspective of the research machine learning for combinatorial optimization (ML4CO). We believe our work will strongly contribute to the wide application of learning- based approaches modern CO solvers.
Tackling Bipartite Graph Inputs Bipartite graph is a general way to represent MILP problems. Thus, natural idea for more general purpose is design symbolic policies that directly tackle the MILP problems with their bipartite graph representations. Specifically, following the GNN distillation approaches proposed by Cranmer et al. (2020b); Shi et al. (2022b).. Then, the deployment process is just similar to that in our proposed Symb4CO.
18

---

Published as a conference paper at ICLR 2024
Table B8: The 91 features used for branching candidates, following those proposed in previous
research (Gupta et al. 2020; Gasse et al. 2019) Khalil et al. 2016).
Index
Name
Short Description
0-3
Variable type
Binary, Integer, Continuous, Implied Integer
Normalized coefficient
Objective coefficient of the variahle normalized by the norm of its coefficients in the constraints
Specified bounds
Whether the variable has a lower bound Whether the variable has upper bound Whether the variable reaches its lower bound in the current LP so- lution
Specified bounds
Lower bound
Upper bound
Whether the variable reaches its upper bound in the current LP so- lution
Solution fractionality Categorical
Fractional part of the variable in the current LP solution Variable the lower bound, upper bound, between the bound
10-13
zero
14
Reduced cost
Amount by which objective coefficient the variable should de- crease so that the variable assumes positive value in the LP solu- tion
Age
Number of LP iterations since the last time the variable was hasic normalized by total number of I.P iterations
16
Solution value
Value of the variable in the current LP solution
17
Incumbent value
Value of the variable in the current best primal solution Average value of the variable in all of the previously observed fea- sible primal solutions
18
Average incumbent value
19-42
Statistics for active con- straint coefficients
An active constraint at node LP is one which is binding with equal- ity at the optimum. We consider 4 weighting schemes for an active constraint: unit weight, inverse of the sum of the coefficients of all variables in constraint, inverse of the of the coefficients of only candidate variables constraint,
constraint. Given the absolute value of the coefficients of the variable in the active constraints, we compute the sum, mean, stdev., max. and min. of those values, for each of the weighting schemes. We also compute the weighted number active constraints that the variable is in, with the same weightings A dynamic variant of statistics for constraint degrees. Here, the constraint degrees
cost
43-49
Statisties for constraint degrees
the current node's LP. The ratios of the static mean, maximum and minimum their dynamic counterparts are also features
50-52
Objective function co- efficients Infcasibility statistics
Value of the coefficient (raw, positive only, negative only)
53-56
Number and fraction of nodes for which applying SB to the variable led one (two) infeasible children (during data collection) Number of constraints that the variable participates in (with a non- zero coefficient)
Number of constraints
58-59
Min/max for ratios of constraint coefficients to RHS Min/max for one-to-all coefficient ratios
Minimum and maximum ratios across negative right-hand-sides (RHS)
60-67
The statistics are over the ratios a variable's coefficient, to the sum over all other variables' coefficients. for given constraint. Four versions of these ratios considered; positive coefficient to of positive coefficients Minimum and maximum ratios across positive right- right-hand-sides (RHS)
68-69
Min/max for ratios of constraint coefficients to RHS Pseudocosts
70-74
Upwards and downwards values, and their corresponding ratio, and product, weighted by the fractionality
75-78
Statistics for constraint degrees
The degree of a constraint the number of variables that participate in it. A variable may participate in multiple constraints, and statis- tics over those constraints' degrees are used. The constraint degree is computed the root I.P (mean, stdev., min, max)
79-88
Statistics for constraint coefficients
static version variable's 's positive (negative) coefficients the constraints it participates in (count, mean, stdev., min, max)
89-90
Slack and ceil distances
The distance to the nearest integer of the current value, the distance to the nearest integer that lager thab the current value
19

---

Published as a conference paper at ICLR 2024
Table C9: The hyperparameters for Symb4CO.
Parameter
Value
LSTM layers
2
LSTM hidden size
128
Batch size
500
Risk factor
0.2
Expression minimal length
4
Expression maximum length
64
Soft length prior A
20
Soft length prior o²
8
Hierarchical entropy regularizer
0.9
PPO learning rate PPO entropy coefficient
5e-5
5e-2
PPO epochs at each iteration
Optimizer
Adam (Kingma & Ba 2015
Number of training iterations for early stop
300
Table C10: Ablation studies on the maximal hard length constraint and the soft length prior. Results show that Symb4CO is relatively insensitive to the soft length prior, while too short hard length constraint could cause decreased performance.
Hyperparameters (on Setcover)
Imitation I Learning Accuracy
Default
47.7
Maximal Length = 16
43.3
Maximal Length = 32
45.1
Maximal Length- 128
47.4
Soft Length
47.4
Soft Length = 40
47.7
Table C11: The training cost of Symb4CO on each benchmark.
Benchmark
Time (h)
Iterations
Setcover 1.08
1087
Cauctions
1.62
1432
Facilities
1.87
1665
Indset
2.80
2312
Table C12: The decision time and the normalized FSB score of different policies, which accounts for our deployment of Symb4CO policies to first 17 layers.
Model:
Symb4CO
RPB
Depth
Normalized FSB score
Decision Time (ms)
Normalized FSB score of the PB function
Decision Time (ms)
0.728
56,8000
0.144
1300.5199
26.3000
0.154
$71.3723
8
0.853
14,1000
0.262
$2,0601
0.888
12,8486
0.309
27. 84.8
16
0.667
9.90125
0.667
8.5889
20

---

Published as a conference paper at ICLR 2024
Table C13: AllLayers).
The end-to-end performance of Symb4CO when employed in all layers (Symb4CO-
Setcover:
Easy
Medium
Hard
Model
Time
Nodes
Time
Nodes
Time
Nodes
RPB
11.40
212.5
100.32
6116.0
1911.32
117450.0
Symb4CO
7.10
304.7
86.92
5623.2
1894.38
129231.6
Symb-CCO-Alllaaeess
6.96
297.4
93.40
5587.6
1943.41
113149.5
Table D14: Details of instance generation algorithms.
Beuchmarks
Difficulty level
Goneration algorithm
Hyperparametors
Easy
columns
Set covering
Mediam
Balas & Ho 1980
1000 rows 1000 columas
Hard
2000 1000 columns
Easy
100 stems for 500 bids
Combinatorial aaction
Medium
Loyton-Brown 2000
Hard
300 items for 1500 bids
facilities 100 facilitics with 200 customers
customens
Capacitated facility location
Mediom
Comudjols al. 1991
Hard
100 facilities with 400 customers
Easy
750 nodes with affinity
Maximum indepeadent
Medium
Bergman
1000 nodes with affinity 4
Hard
1500 modes with aflinity 4
21


Reviews:
[{"review_id": "67nZdZlZ0z", "reviewer": "Reviewer_z5TX", "summary": "This paper introduce a neural-symbolic approach to discover branching heuristics for MILP solving. Instead of directly using a neural network as the branching heuristics, they propose to use a neural network to predict a symbolic expression, which is more efficient to invoke online.", "questions": "- In the experiments, are the proposed branching heuristics invoked at each node, or only the top node?\n- What is the cost of the training?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The idea of not directly using a neural network for branching prediction, but rather using it to produce a symbolic expression is quite interesting and plausible.\n- The paper shows a substantial performance gain over the other methods.", "weaknesses": "- The paper relies on manual feature extraction. This leaves open the question what are useful features, which is difficult to answer. Presumably the choice of the features are dependent on the particular benchmarks and can have significant impact on the performance. I get that the alternative deep representation makes the inference more expensive though.\n- It is unclear how the training instances are selected and how similar to the test/validation instances the training instances are.", "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": "", "extra_scores": {}}, {"review_id": "CocO36fJkU", "reviewer": "Reviewer_dfwS", "summary": "The paper introduces an approach that combines the advantages of using machine learning (ML) and human-designed policies in solving combinatorial optimization (CO) problems. Symb4CO leverages deep symbolic optimization to learn interpretable symbolic expressions, transforming complex ML models into compact and efficient decision-making policies. The key strengths of Symb4CO lie in its efficiency, both in terms of training and inference, making it suitable for practical deployment on CPU-based devices. The paper shows that Symb4CO outperforms existing ML-based and human-designed policies. \n\nNovelty:\nThe paper introduces the concept of using deep symbolic optimization for solving CO problems, specifically focusing on the branching task. This is a novel approach that combines symbolic representations with optimization tasks, making it distinct from traditional machine learning techniques applied to CO problems.It is designed to be highly efficient, particularly in terms of training and inference, and the learned symbolic policies are interpretable. The paper highlights the importance of these features for practical deployment in real-world applications. Symb4CO's ability to perform well on purely CPU-based devices is quite practical. Most previous ML approaches for CO problems require GPU acceleration, but Symb4CO demonstrates that it can achieve comparable performance with CPU-based resources. The paper explores the concept of using compact symbolic policies for CO tasks. This is in contrast to complex machine learning models, which are often resource-intensive. Symb4CO's approach leads to concise, one-line mathematical expressions for decision-making.\n\nImpact:\nThe impact of this work is significant, especially within the field of combinatorial optimization and machine learning. Symb4CO's ability to achieve competitive performance on CPU-based devices with limited training data can make it accessible to a broader range of real-world applications. The emphasis on interpretability in Symb4CO's learned policies addresses a critical concern. Symb4CO's success on CPU-based devices reduces the need for GPU resources. \n\nQuality of writing and experiments:\nThe quality of writing in the paper needs improvement. Here are some detailed comments:\n- Section 4.3 talks about the fitness function, which is a crucial part of the training pipeline. So, it would be helpful to expand on the explanation of Equation 2. \n- Since the authors use an FSB-based fitness function, why does the FSB model perform so poorly (Table 1) compared to their tool?\n- Table 2 mentions the use of one training instance. How was this training instance chosen? How do the results vary if a different training instance was chosen? Providing a standard deviation in Table 2 would be helpful. Similarly, how were the ten instances chosen (Section 5.1)?\n- Authors mention discovering more complex working flows like RPB can be an interesting future work. Since RPB is compared against in Table 1, why do the authors think RPB performs so poorly compared to Symb4CO?\n- In Section 5, what is the reason for using 1-shifted geometric mean?\n- The interpretability claim in Section 5.2 needs some clarity. E.g., \"RPB ... uses a scoring function with human-designed features and expressions rather than vanilla pseudocosts.\" Why is this relevant to the interpretability claim?\n- How do the authors ensure the output expression from the RNN (Figure 2) is syntactically correct?\n- Providing a concrete example and comparing the results with some of the other tools might be helpful to improve clarity.\n- RNNs are usually not considered suitable for long-term sequences. How did the authors tackle that problem? How long are the output expressions from the RNN model?\n- Part 3 in Figure 2 is challenging to understand. The fitness measure can include concrete values to improve clarity. \n\nAblation studies explore the choice of mathematical operators and constants. Nevertheless, I believe it is important to address the following questions as well:\n- Section 4.2 briefly mentions applying constraints during the training process. How is the length constraint implemented? Do the authors allow only a fixed length? Was there any ablation performed for the use of this constraint?\n- Section 3.2 talks about 80% masking, but Section 4.1 mentions using all 91 features. How is the masking performed during training and evaluation across different benchmarks? Were any ablation studies performed on a different subset of features?\n- How sensitive is the approach to different hyperparameter choices for the sequential model?\n- Comment on the scalability of the approach. Do medium and hard problems have significantly larger search spaces? \n\nAdditional comments:\n- Out of curiosity, did the authors explore the extent to which the learned symbolic policies generalize across different problem domains within combinatorial optimization? For example, test the policies trained on one benchmark on a different but related benchmark to assess their transferability.\n- The paper discusses the efficiency and interpretability of Symb4CO. Can the authors provide insights into any trade-offs when prioritizing efficiency and simplicity over complex but potentially more accurate models?\n\nMinor nitpick - Expand FSB in Figure 2 as it has not been used till page 3\n\nReview summary:\nThe paper introduces Symb4CO, a novel approach for solving combinatorial optimization problems by combining machine learning and interpretable symbolic expressions. It leverages deep symbolic optimization to generate efficient and interpretable decision-making policies. Symb4CO is highly efficient for inference, making it suitable for CPU-based devices. The paper provides a comprehensive experimental evaluation, demonstrating its superiority over existing methods. The key strengths include its innovative use of deep symbolic optimization, efficiency, interpretability, and the potential for real-world applications. However, the paper could benefit from improved clarity, expanded related work discussion, and addressing potential limitations. The ablation studies exploring mathematical operators and constants are valuable, but additional questions and considerations should be addressed for a more comprehensive understanding.", "questions": "- Out of curiosity, did the authors explore the extent to which the learned symbolic policies generalize across different problem domains within combinatorial optimization? For example, test the policies trained on one benchmark on a different but related benchmark to assess their transferability.\n- The paper discusses the efficiency and interpretability of Symb4CO. Can the authors provide insights into any trade-offs when prioritizing efficiency and simplicity over complex but potentially more accurate models?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Symb4CO is shown to be efficient, both in terms of training and inference, making it suitable for deployment in real-world scenarios on CPU-based devices.\n\n- The paper emphasizes the interpretability of Symb4CO's learned symbolic expressions.\n\n- The paper presents a thorough experimental evaluation, comparing Symb4CO with various baselines and showcasing its superior performance in terms of training efficiency, inference efficiency, and overall effectiveness.", "weaknesses": "- The paper could benefit from improved clarity and organization. I will expand more on this in the following few sections.\n\n- The discussion of related work is quite brief and could be expanded to provide a more comprehensive overview of existing approaches and how Symb4CO differentiates itself.\n\n- While the paper discusses the limitations of previous ML approaches, it needs to address the potential limitations of Symb4CO. A dedicated section on drawbacks or areas for future improvement would enhance the paper's completeness.", "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": "", "extra_scores": {}}, {"review_id": "ExpSiXmB9r", "reviewer": "Reviewer_hTDx", "summary": "The paper introduces Symb4CO, the first symbolic discovery framework, to learn high-performance symbolic policies on the branching task in CO solvers. Symb4CO's CPU-based strategies match the performance of top GPU-based methods. With efficient training, quick inference, and clear interpretability, Symb4CO offers a promising way to integrate machine learning into modern CO solvers.", "questions": "Please refer to the questions in the weakness section", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The problem the paper is trying to address is important. Indeed, we should have a light-weight machine learning approach to facilitate CO solvers. The directions that the author tries to improve, including requiring less training data and producing interpretable policies, are reasonable to me. \n2. The authors of Symb4CO apply reinforcement learning to make training efficient with much less data needed.", "weaknesses": "1. Symb4CO, although data efficient during the training, requires feature extraction by human. I have concerns about if the extracted features are expressive enough, and how much efforts does it take for these feature extractions. Does it really the so-called training efficient?\n2. From the experimental results, I can observe that GPU based GNN approach can make CO solvers perform faster than CPU based Symb4CO. The overall goal is to facilitate CO solvers in efficiency, if GPU based approach can facilitate it more, than why not prefer GPU based approach? Besides, today’s machine can make very fast GPU-CPU interactions. I think we should be open to bringing in machine learning models inside CO solvers (not just adding the learned interpretable policies inside CO solvers) and making use of GPU’s high computation to facilitate logical reasoning tools.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)