Towards Imitation Learning to Branch for MIP: A Hybrid Reinforcement Learning based Sample Augmentation Approach
Authors: Changwen Zhang
Wenli Ouyang
Hao Yuan
Liming Gong
Yong Sun
Ziao Guo
Zhichen Dong
Junchi Yan
Venue: ICLR 2024 poster (2024)
Keywords: hybrid RL
Sample Augmentation
Learning to branch
Imitation learning
Primary area: optimization

Abstract: Branch-and-bound (B\&B) has long been favored for tackling complex Mixed Integer Programming (MIP) problems, where the choice of branching strategy plays a pivotal role. Recently, Imitation Learning (IL)-based policies have emerged as potent alternatives to traditional rule-based approaches. However, it is nontrivial to acquire high-quality training samples, and IL often converges to suboptimal variable choices for branching, restricting the overall performance. In response to these challenges, we propose a novel hybrid online and offline reinforcement learning (RL) approach to enhance the branching policy by cost-effective training sample augmentation. In the online phase, we train an online RL agent to dynamically decide the sample generation processes, drawing from either the learning-based policy or the expert policy. The objective is to strike a balance between exploration and exploitation of the sample generation process. In the offline phase, a value function is trained to fit each decision's cumulative reward and filter the samples with high cumulative returns. This dual-purpose function not only reduces training complexity but also enhances the quality of the samples. To assess the efficacy of our data augmentation mechanism, we conduct comprehensive evaluations across a range of MIP problems. The results consistently show that it excels in making superior branching decisions compared to state-of-the-art learning-based models and the open-source solver SCIP. Notably, it even often outperforms Gurobi.

Published as a conference paper at ICLR 2024
TOWARDS IMITATION LEARNING TO BRANCH FOR MIP: A HYBRID REINFOR LEARNING BASED SAM- PLE AUGMENTATION APPROACH
Changwen Zhang, Wenli Ouyang; Hao Yuan, Liming Gong, Yong Sun AI Lab, Lenovo Research (zhangew5, ouyangwil, yuanhac4 gongim3, sunyong4 / (eLenovo.com com
Ziao Guo, Zhichen Dong, Junchi Yan
Department of Computer Science and Engineering, Shanghai Jiao Tong University {2iac. gue, niconi19, yanjuncii junchi jsjtu. edu. cn
ABSTRACT
Branch-and-bound bound (B&B) has long been favored for tackling complex Mixed Integer Programming (MIP) problems, where the choice of branching strategy plays pivotal role. Recently, Imitation Learning (IL)-based policies have emerged potent alternatives to traditional rule- blse approaches. However, it is nontrivial to acquire high-qualig training samples, and IL often converges suboptimal variable choices for branching. restricting the overall performance. In response to these challenges, propose novel hybrid online and offline reinforcement learning (RL.) approach to enhance the branching policy by cost-effective training sample augmentation. In the online phase, we train an online RL agent dynamically decide the sample generation processes, drawing from either the learning- policy or the expert policy. The objective is to strike balance between exploration and exploitation of the sample generation process. In the offline phase, a value function is trained to fit each decision's cumulative reward and filter the samples with high cumulative returns. This dual-purpose function not only reduces training complexity but also enhances the quality of the samples. assess the efficacy our data augmentation mechanism, conduct comprehensive evaluations across a range of MIP problems. The results consistently show that it excels in making superior branching decisions compared to state-of-the-ar learning-base based models and the open-source solver SCIP. Notably, it even often outperforms Gurobi.
INTRODUCTION
As general formulation and long-standing challenge. Mixed Integer Programming (MIP) (Zhang al., 2023) spreads wide applications ranging from manufacturing (Artigues et al., 2009) route planning (Halim & Ismail, 2019). Many exact algorithms (Lomnicki, 1965) have been proposed, with common adoption of branch and bound (Brucker et al., 1994). recursively divides the solution space into search tree and calculates the relaxation and boundary to prune the subtrees proved not to contain the optimal solution. At each iteration, two important decisions need to be made, including node selection and variable selection, which determine the next node to evaluate and select the variables to partition the search space. In this paper, we will focus on variable selection.
Variable selection decisions often rely heuristics from domain experts (Achterberg et al., 2005b), like strong branching, active constraint (AC) (Patel & Chinneck, 2007), pseudo cost branching (PC) (Hendel, 2015), reliability pseudo cost branching (RB). However, the expert rule- based policies can often only find the locally best variable to branch on (Achterberg et al., 2005a). For example, for the most famous expert strong branching, it targets to select the variables that deliver the best one-step progress in the dual bound improvements, which has been proved not always the "golden standard' (Dey et al., 2021: Qu et al., 2022a). So, Glankwamdee & Linderoth (201)) 1) proposed
Challenges:
"Correspondence author. The work was partly supported by NSFC (92370201, 62222607).

---

Published as a conference paper at ICLR 2024
the lookahead branching, which considered more dual bound information from deeper levels to deal with the potential local search limitations of strong branching. While in general, these effective approaches were usually computationally expensive. In this respect, increasing number of studies are resorting to a learning-based branching strategy (Balcan et al., 2018), in which imitation learning (II.) on strong branching (Hussein et al., 2017) has shown superiority. However, strong branching cannot produce completely reliable labels due to the dual degeneracy (Cao et al., 2022b; Gamrath al., 2020b) in the LP solution, which may cause the product score of strong branching to combine the improvements of the two child nodes close to zero. In addition, IL- IL-basedd branching approaches usually require a large amount of training data and GPU resources for training.
To tackle the aforementioned challenges, we propose an innovative hybrid approach that combines online and offline RI. techniques to enhance the training samples for branching policy learning. It involves two distinct phases. In the online phase, we leverage an online RI agent, acting as dynamic collector. Its primary role to guide decisions regarding the choice of sample generation processes. These processes draw from two potential sources: the learning-based policy and the expert policy. Contrasting with solely relying on expert knowledge, the samples could be generated by the learning-bas based policy with the hope of bolstering exploration in unfamiliar scenarios, thereby enhancing the performance of IL. The intuition is that learning- basedd policy (Gasse et al., 2019) can deliver a smaller B&B tree than strong branching in some instances, shown in the Appendix A.6. Besides, Oh et al. (2018) has proved that past good experiences can add exploration for imitation learning and may find a potentially better policy than only imitating the expert policy. The offline phase involves training an offline agent. This offline agent is tasked with fitting the cumulative reward function for each decision made. It operates as a filter, sifting through the generated samples to identify those with superior cumulative returns. These high-quality samples are then earmarked for training the branching policy. By doing so, we not only expect to improve the performance of the branching policy but also minimize the overall training cost. The highlights of this paper are:
1) We propose an iterative collection and filtering framework that leverages combination of online and offline RI. techniques to enhance the training samples. The online RL agent serves as a collector responsible for determining the sample generation process, and choosing between the learning-base policy and the expert policy. The offline RL agent functions filter, identifying samples with high cumulative returns. This framework enhances the efficacy (inference performance) and efficiency (training complexity) of the learning- based branching methods. 2) Extensive experiments on MIP show that it consistently outperforms the default heuristic policy adopted in open-source solver SCIP. Compared with learning-basee algorithms, including the best-performing methods in the Machine Learning for Combinatorial Optimization (ML4CO) 2021 competition", our method can further enhance the branching policy, illustrating its effectiveness as a plugin orthogonal to peer methods.
Difference to existing works: Table 1 compares our approach with existing works in detail. The most critical difference is the hybrid sample collection and filtering scheme with online and offline RL agents. Peer works mainly depend on either the expert-based samples (Gasse et al., 2019; Cao et al., 2022a), or the pure self-generated samples with RL manner (Parsonson al., 2023; Scavuzzo et al., 2022). To combine the best of the two worlds, Qu et al. (2022b) tries to mix the generated samples that lead to high performance with expert demonstration data within the training, purely by predefined hyperparameter Go- In this paper, we propose to train an online RL to adaptively and dynamically mix the best of two worlds, which is more reasonable and adaptive. In addition, we also proposed new offline RL agent to further filter the mixed generated samples, minimizing the overall training costs and enhancing performance to some extent.
2 PRELIMINARIES AND RELATED WORK where is the decision variables of total size and m denote the number of constraints and decision variables, respectively. denotes the number of integer variables, and the remaining m
Preliminaries: Mixed integer programming (MIP) can be defined with three elements: optimization objectives, decision variables, and constraints, which can be given by:
arg min c x|AAx < b, < x < u. Z X
x
'Offline RL is a filtration mechanism similar to (Chen et al., 2020).
2

---

Published as a conference paper at ICLR 2024
Table 1: Comparing our method with peer works.
Sample Collection
Referenees
Filtering
Iterative method
Training
Expert based
Self-generater
mix
samples
samples
Gasse et al. (2019)
Yes
No
No
Imitation
al. (2022a)
Yes
Yes
Imitation
Pursonson et al. (2023)
No
Yes
No
RL
Scavuzzo et al. (2022)
No
Yes
No
RI.
Pre-defined
Qu et al. (2022b)
Yes
Yes
distribution
No
RL
HRI--Aug(Ours)
Yes
Yes
Online agent
Offline agent
Yes
RL Imitation
variables are continuous. The objective is to minimize c x with the constraints Ax S b, where A E IR** represents the constraint coefficient, and b E R denotes the hight-hand--e vector. The x satisfying all the constraints and minimizing the objective is the optimal solution.
The flow of the B&B can be depicted as follows. Firstly, the raw MIP can be defined as the root node of search tree. recursively selects a node from the search tree by the node selection rule and then selects a variable to decompose the selected node. When branching on variable 2;, the optimal solution x is first computed by imposing a linear programming relaxation, and the relaxed objective value can be defined as the dual bound. If a does not meet the integrity constraint, the variable a;; needs to be branched, decomposing the MIP from the current node into two sub-problems by adding two new constraints 2; 2 [ and T; [ The iterations continue until convergence time up.
Branching policy for branch and bound: Expert rule-based branching policies are widely adopted in MIP solvers, including strong branching (Applegate et al., 1995), active constraint (Patel & Chinneck, 2007) etc, which are generally difficult to design, and can usually find suboptimal variables to branch on. Furthermore, some of them can be extremely consucon,,,,ng like strong branching.
Learning-bast based policies were recently devised to replace the above expert rule-based policies, such as imitation learning on some best-performing expert rule-based policies, like strong branching (Applegate et al., 1995; Gasse et al., 2019; Alvarez et al., 2014; Gupta et al., 2020) and active constraint (Patel & Chinneck, 2007). Gasse et al. (2019) first proposed utilize bipartite graph convolutional neural network (GCNN) to approximate strong branching decisions by IL. To make the expert samples closer to real-world applications and further improve the performance, Cao et al. (2022b) proposed a Dagger-like method to enhance the sample collection phase. These methods deliver better performance and efficiency. In addition, RL-based methods are also recently studied, which may produce even better branching policies compared with expert rule-based policies. Scavuzzo al. (2022) proposed a new tree Markov Decision Process, a more suitable framework for learning to branch. Parsonson al. (2023) proposed the retro-branching approach, by learning from deconstructing trajectories within the sub-trees to enhance the branching policy.
In general, purely exploiting what expert policies know limits the performance of imitation learning in some cases. While RL, free from expert rules, may be challenging in training, especially for some large-scale problems. Note the conducted extensive experiments Appendix A.5, revealing the limitation of RL-based approaches. In this paper, we propose hybrid approach that embeds RL into imitation learning enhance the training samples, balancing between exploiting what experts know and exploring potential high-reward unknowns.
the RL-based methods in
Training set augmentation with RL. Recently, RL-based data augmentation approaches have been widely studied. Wang et al. (2018) developed a monotonic advantage re-weighted IL strategy to enhance policy learning. Peng al. (2019) proposed an ddvantage-weightee regression- based scheme for offline RL. Chen et al. (2020) proposed the Best-Action Imitation Learning (BAIL) approach, utilizing the V function select actions for imitation learning that promised to high high-performing. With similar insights, Qu et al. (2022a) tends to utilize BAII. to improve the quality of expert samples for imitation learning. In general, these RL--based methods mainly rely on Monte Carlo return with discount factor. However, in the branching scenario, the dual bound may remain unchanged for hundreds or even thousands of iterations, which means that the discount factor will interfere with the accurate evaluation of the samples. In this respect, we deal with the above issue by setting the discount factor as to calculate the actual Monte Carlo return.
Imitation learning and self-imitation learning: Imitation learning (IL) has been widely adopted in machine learning for combinatorial optimization, including solving MIP (Zhang et al., 2023). As a special case for II., the main idea of self-II. (Oh et al., 2018; Gangwani et al., 2018; Guo et al., 2019;
3

---

Published as a conference paper at ICLR 2024
Data Augmentation
Online Training
Environment
Online Agent
Online Agent
Interast
Interact
Reeard
Graek
Expirt
Kopert
OCNS Bicl
Expart
Expert Experience
Past Experience
Expert
GCNN R
Offfine Agent
Offline Agent
Raamm graph feetuee
YLS
Rg 2 faury (s))
Upditc
Duffer
assclc vpirlo
GCNN
GONN Training
Bipartiic GCNN
Offine Training
Overview of the proposed HRI.-Aug. It is new iterative approach hybrid with online and offline agents. An online agent is used to decide the sample generation processed from GCNN T or experts to augment the training samples with higher cumulative rewards. An offline agent is devised to reduce the generated samples and further enhance the sample quality. The samples will be finally fed into GCNN iteratively for branching policy learning.
Figure 1:
Zhu al., 2014) learn the agent's past experiences indirectly drive exploration. It is believed that the policy can be learned iteratively from the agent without any feedback from an external expert. It shows that past good experiences are helpful on hard exploration tasks and achieved good results in the Mujoco (Todorov et al., 2012). But in the branching scenario, each branching may have hundreds of thousands of candidate variables, which means there large state-actions space and it is a well-known difficulty for RL (Ecoffet et al., 2021), I), so we will use the online RI. agent to adaptively choose samples generation processes, either from learning-base policy or the expert policy, with the aim of leveraging the strengths of both approaches.
3 METHODOL.OGY
Fig. depicts our approach with notations throughout this paper as listed in Table
3.1 APPROACH OVERVIEW
Our approach, named Hybrid Reinforcement Learning for Training Set Augmentation (HRI--ug)) is hybrid online and offline approach to enhance the training samples towards branching policy learning. The innovation lies in the introduction of the data augmentation scheme, as meticulously designed for the realm of imitation learning. It comprises three components: online Reinforcement Learning (RL) agent, an offline RL agent, and an imitation learning- based policy, as shown in Fig 1. The hybrid online and offline data augmentation scheme generates high-quality samples for the IL-based GCNN network iteratively until the stop condition is met.
The Online RL Agent is utilized to select better samples from the expert policy or learning-based based policy at each variable selection decision. It plays a pivotal role by facilitating profound exploration of uncharted scenarios. By striking a balance between exploration and exploitation, it effectively steer clear of local optimal solutions for branching variables.
The Offtine RL Agent evaluates the cumu- lative rewards of generated samples from the online phase, and filtering the high-
Table 2: Description of the notations in the paper.
of offline reinfercement learning nodo
state of online reinforcement learning at node action of anline reinforcement learning node
quality samples for subsequent policy train- ing. As will be seen from our ablation study, it improves training efficiency.
St
scores for brunching variables given by expert at mode for branching variables given by learned policies node hipanite gruph features node?
O,
H.
cumulative reward at mode
reward Te
The Imitation learning-based policy is trained with the generated samples from the hybrid online and offline agent. can be regarded crucial validation of our data augmentation framework. It emerges pivotal component capable of supplanting expert-based policies within solvers, akin to SCIP as
policy trained by imitation learning at the i-th iteration cundidate branching variable set at mode hyper-parameter controlling the ratio selected samples offinee agent parameterized by f.a
fea:
fo..
online agent purumeterized by 6.n
discount factor for Monte Carlo Return calculation
4

---

Published as a conference paper at ICLR 2024
exemplified in this study. GCNN is selected as the backbone. We take comprehensive tests on the generalization capabilities of our framework to other approaches, and the details are given in Sec. 4.4.
3.2 ONLINE RL PIIASE
Imitation learning- based models have shown their superior performance over expert rule-based policies (Gasse et al., 2019). However, its performance largely depends on high-quality expert samples, which are difficult to collect. Recently, self-imitation learning has proved that using past good experiences to explore new behaviors may find a potentially better policy (Oh et al., 2018). However, the optimization may be completely aimless at the early training stage when starting from scratch, which may hurt the performance and greatly increase the complexity.
An intuitive idea is combine the best of the two worlds: expert rules and past good policies, which requires an approach to decide the sample generation processes, denoted as the online phase in this paper. However, it is difficult evaluate the branching decisions, making it challenging task to choose samples from expert rules or learning-basee policies. Moreover, in the branching scenario, samples are collected by iterative variable selection decisions, and the current decision largely depends on the former actions and states, making it sequential decision problem. In this respect, we tend to define the online phase as a Markov Decision Process (MDP) and model the sample generation process with RI.
Firstly, we define the online RL phase as a sam- ple selector and collector at each branching node. In this respect, the action af was defined as the sample generation decision from expert rules or past learned policies at each node t, which is discrete action space, only with two actions. The state se is formulated as sf = ST Ot),
152
2.4
125
Munberr
Figure 2: Example of the dual bound changes on a balanced item placement instance.
where St denotes the expert score for variables, and the S/ is the score from learned policies. O, denotes the bipartite graph feature, and the details of features are listed in Table 11 in the Appendix. Secondly, it is essential to drive effective evaluation for samples. We utilize the dual bound changes as the reward rt. and Fig. depicts an example on an MIP instance. The dual bound may remain unchanged for hundreds of steps. This reveals that it may require thousands of or even longer steps to accurately evaluate the cumulative reward. However, with the discount factor y < 1, the reward may have little contribution to the cumulative reward after thousands of branches, which can cause an inaccurate evaluation of the action. Hence we set 7 = 1, and the cumulative reward Re at node is:
R₂
Σ Tv
where f_, is the final expanded node in an episode. With the above definition, we can train the online RL agent with the advantage actor-critic method (ActorCritic). The agent dynamically decides sample generation processes, either from the expert rule or the GCNN policy π;-1- In the training phase, GCNN policy _, is iteratively optimized and the online RL agent relies this evolving GCNN to construct the input states. This introduces a potential challenge, as the previously trained online agent may become unreliable due the evolving policy. To address this issue, we utilize the up-to-date - to train the online agent. With the online update mechanism, we can optimize the online sample collection agent and obtain past good experiences, to achieve better exploration.
3.3 OFFLINE RL. PHASE
With the online sample collection agent, we can easily obtain hybrid samples from both the expert rule and the GCNN policy. However, with the iterative sample generation process, the training samples constantly accumulate and require huge computing resources for imitation learning. In this respect, batch deep reinforcement learning (BDRL) (Fujimoto et al., 2018; Chen et al., 2020) was proposed to strive for both simplicity and performance by selecting high-quality samples with offline methods. In this paper, we leverage similar ideas and develop an offline RL agent to approximate the cumulative reward and reduce the data scale by filtering samples, thus reducing the training complexity.
For branching, the action af is defined as the variable selection from the candidate branching variable set. The states for the offline learning phase node can be defined as sf (Ot, At), where A,
5

---

Published as a conference paper at ICLR 2024
denotes the candidate branching variable set, O₂ is the bipartite graph feature. The discount factor is still set as y = 1, with the cumulative reward defined as Eq. 2, to evaluate the quality of the samples.
With the above definition, let offline agent denoted by neural network characterized by fott (w, b). foft take the {{O,, A,, Rt),t = 1, 2, ..., m) collected from the online RL phase as input and output real number to fit the cumulative reward, thereby obviating the need for exploration. Then the offline agent is regarded as a X-regularized upper envelope for the following constrained optimization problem Eq. 3. This concept arises due to the inequality Se (Or, A.) 2 RG, and this prompts us to define Sa (O,, Ag) as the "upper envelope". a construct geared towards aligning the envelope as closely as feasible with Re. Then the offline RL agent is used to select high-quality samples generated in the online phase. With the approximate cumulative reward generated from the offline agent, we can select the high-quality samples by Eq. 4, where 2 is tappe-paramettr, controlling the ratio of the selected data samples, foon denotes the offline agent.
XHIII
Lf (O), - -R,} + ||W!| s.t. foom (O,, 2 RG, t= 1, 2, m
(3)
R 2 zʃoua (Oz, At)
(4)
Note that the offline RL agent undergoes training solely during the first iteration, as empirical evidence suggests that its performance is already satisfactory at that point.
3.4 HYBRID TRAINING PIPELINE
The hybrid online and offline RL agents are combined as a hybrid pipeline to further enhance the branching policy via training set augmentation, whose details are given in Algorithm 1. It operates iteratively to collect training samples, with each iteration involving the incremental training of the foundational GCNN model. For efficiency, the frequuecy of the online RL training will be controlled by the hyperparameter Freq (see Line 6), and the offline RL agent is exclusively trained during the first iteration. In particular, the online agent will employ the most current GCNN policy for its training every time when the conditions in Line 6 are met. In the training phase for the online agent fe... will collect the bipartite graph features O₁, along with the scores (S S!.) from the expert rule and the GCNN policy T as the states in Line 7. Afterward, the samples generated from the online phase (see Line 9-13) are used train the offline agent fe.. at the first iteration in Line 15, which is capable of selecting samples with high cumulative rewards and will be applied for all the successive iterations. Finally, the generated samples are further aggregated train the GCNN policy Tú used for subsequent training. The pipeline persists until it reaches the iteration limit N.
EXPERIMENTS
We compare competing learning- based approaches and SCIP's default branching rule. We run all the experiments Intel(R) Xeon(R) Silver 4210 2.20GHz CPU and an NVIDIA A100 GPU.
4.1 EXPERIMENTAL PROTOCOLS
Dataset. We perform evaluation on popular binary integer programming problems: set covering, combinatorial auctions, maximum independent set, and capacitated facility location. Instance generation completely refers to (Gasse et al., 2019), and their variable and constraint sizes are listed in Table 3. For each problem, we generate 10,000 instances for training, 4,000 for validation, and 40 for testing. The test instances are all generated via different random seeds. The training and validation are performed on the Easy instances (see Table 3), and we also generated 40 Medium and Hard testing instances for each problem to further test the generalization ability. Besides, we conduct experiments on more difficult MIP problems from the ML4CO 2021 competition (ML4CO datasets) (Gasse et al., 2022), including Balanced Item Placement (1,083 columns, 195 rows), Workload Apportionment (61,000 columns, 64,314 rows), and Anonymous, which is from the MIRPLIB library (PAP, 2014) and inspired by real- world applications of large-scale problems.
Hyperparameters. All models are trained with Ecole (Prouvost et al., 2020). To verify the effect of different branching strategies, we disable SCIP's ' heuristic and default restart policy. In the training phase, we collect 10,000 training and 4,000 validation samples at each iteration, and the training iterations N 20, 50 for binary integer programming problem and ML4CO datasets respectively, the frequency of training the online RL agent Freq = 5. At each iteration, the embedding size for the offline agent is 64, and the hidden layer size for both online and offline RL is set to 1 128. We set

---

Published as a conference paper at ICLR 2024
the discount factor to I, and use Adam optimizer with learning rate 3 10-3 to train both RL agents.
We use SCIP 7.0.3 as the backend solver, with a time limit of 1 hour for binary integer programming problems which are the same as (Gasse et al., 2019), and 900 seconds for ML4CO datasets.
Evaluation. As discussed above, for each binary integer programming problem, eval- uation is performed on different difficulty levels (Easy, Medium, Hard), each with 40 instances using five different seeds, which amounts to a total of 200 solving attempts per method to report aggregated results over the same instance. We use similar metrics as those in (Gasse et al., 2019), including the 1-shifted geometric mean of the solving time to measure the solving efficiency (Time), the final node counts the solved instances
Algorithm 1 Hybrid for the training set augmentation to enhance branching for B&B-basee MIP.
Input: Training instances;
Number of samples generated each iteration C; The total number of algorithm iterations N: The frequency of training the online RL agent Freq; Initial branching policy Tu:
Collect all samples generated in each iteration D Collect the samples generated in the i-th iteration D: Output: Branch policy based on Hybrid RL NT;
1: Let = 1;
2: Let D=0;
3: while i is do
among all baselines (Nodes), and the number of times each branching policy delivers the fastest solving time, over the number of in- stances solved to optimal (Wins). Note that we also report the average per-instance stan- dard deviation.
4:
Let D; /
5:
Let = 1;
6:
if i== 1 or i % Freq= == then
7:
fe.. ActorCritic(ss expert)
8:
end if
9:
while S C do
10:
O,, A,, R4, St. ST (5
As it is too large to solve in reasonable time, we evaluate methods with similar met- rics as in ML4CO 2021 competition: average
11:
D. D; (Ot, At, Re, St];
1=1+1:
13:
end while
Dual and dualbound within the solving time limit. DualGap for each instance is:
14:
if i== then
15: foaa BDRL(D.);
end if
DualGap(t) = Id(t)) p-1
17: Remove samples from D; as Eq. 4;
(5)
mar ( (p*1)
18:
D = Du:
19:
GCNN(D);;
where d(1)* is the best dual bound time / and p² is the best known solution value for the instance. We also compare the cumulative reward within the fixed time bound by Eq. 6, where TeTx: xx is instance-specific constant w.r.t. the optimal objective c x².
20: i=
21: end while
- d(t)'tt
Te Texx- x-
(6)
4.2 COMPARATIVE EXPERIMENT
Baselines. We compare method with four baselines: 1) SCIP (v7.0.3) (Gamrath et al., 2020a):
State-of-the-art open-source solver with hybrid expert branching rules, named reliable pseudo cost branching. 2) GUROBI (v9.5.0): State-of-the-art commercial solver with hybrid expert branching rules which is known often much more effective than open-source solver. 3) GCNN (Gasse et al., 2019): An IL-bdsed model with graph convolutional networks for scoring. 4) MLACO-KIDA (Cao et al., 2022a): a Dagger-like (Ross et al., 1984) method based on IL, which is the best-performing method in the MI4CO 2021 competition.
Training. For iterative- based methods, including our proposed hybrid framework and MLACO- -IDAA, we generate 10,000 and 4,000 samples for training and validation at each iteration, respectively. As for the IL-based GCNN, we generate 100,000 samples for training and 40,000 samples for validation. Note that on the MIACO datasets, we will use the model published by ACO-KIDA''ss author on balanced item placement and anonymous problems, and reproduce MLACO-KIDA using the source code for the Workload Apportionment problem. The accuracy on testing instances for different problems is listed in Table 4, where (acc@n) denotes the accuracy of the selected branching variable by branching policy rules for sample generation, ranking top n among the predictions.
Comparative analysis. Table 5 depicts the overall performance on four binary integer programming problems. For the easy instances, learning- based methods significantly outperform the expert rule- based policies, showing the effectiveness of the II. framework. Our method shows consistently higher
7

---

Published as a conference paper at ICLR 2024
Table 3: The type and protocol of the binary integer programming problem.
Difficully
Combinatorial
Auction
Sat Covering
Independent Set
Capaciiate Facirliyy
columns
rows
columns
rows
columns
rows
columns
JOwS
Easy
300
1000
500
1948
10201
Medium
1000
383
1000
1000
1000
3957
20100
20301
Hard
1500
591
1000
2000
1500
5938
40100
40501
Table 4: Evaluation of three II.-based methods by accuracy @: on the test sets of seven problems.
Methods
Combinatonal Auction
Set Coveting
Independent
Cipacliaed Facitity
liem Placement
Workloud Apportonment
Anurymoux
e10
9810
#19
110
GURN
0.02
0.97
0.56
0.99
0.48
0.85
0.56
0.99
0.77
0.99
0.28
0.4
0.50
0.7
KIDA
0.58
0.6
0.85
0.97
0.41
0.86
0.56
0.99
0.25
0.78
HRRE-AE
0.55
0.96
0.52
0.97
0.40
0.85
0.56
0.99
0.75
0.99
0.42
0.88
0:48 0.89
Table 5: Instances are evaluated based solving time, the number of wins (fastest method) versus
the number of solved instances, and the number of nodes generated by B&B (lower is better).
Mathads
Time
Win-siied
Easy
Nodkokk
WirdSeiwed
Medium
Nedesw
Time
WinSolved
Hard
Nodloo
SCIP
242 = 15.25%
107200
11.38 = 10026
12,22
= 12335c
17200
26,
205.02 09
8.70%
32000
300 1007 = 1013
OCNN
7.78%
47/200
692000
1049
5.89
79200
00 61.5
KIDA
9.00%
65/200
77.98
8.02%
21
65/200
1064 76 5.65
237.10
6.25%
16200
27264.35
HRL-Asg
1.8 9.44
78/200
37.40
21.27
10.75%
71/200
1053 7.28%
222.758
100200
24218.31
5.419
Combinatorial Auction
Methods
Time
Essy
Nodool
Time
Malium Wis/Soheed
Nodes
Time
WiwS-bvod
Hand
Nuded
SCIP
12.18
9444
3/33
H1S
1685 5 0016
18.055
553A7
5.20
52174
90192 SS E 5.8TA
OCNN 7.88
8 5.54%
28/380
19L47
14 699
34.95
7.51%
702000
692 89
10.15
$29.44
7.44
10/120
54442 69 + 9.99
KIDA
7,89
8.00%
7W200
193.47
A 14.71%
25.47
+ 10.74%
55/200
706.31
15.11%
536.01
2 4.33%
54170
$3880 34 A 7,00%
HRE.Aug
8.15 8356
45/330
201.5
+ 15655
34.44 4 8.36%
15/000
67576
11A78
R15.22
= X106
5407M0
54K35
74 74++ 7.56%
Set Coverinn
Mathods
WintSalval
Nicksk
WanSSevool
Nislos
Time
WintSeheal
Narksö
ScIp
192200
72.11
47.55%
131
31417
17500
110.00
2043.03
16377
0/22
GCNN
7,35
14.38%
60/200
80.25
32.02%
56.85
15.29%
39/000
532.34
767.05
10/182
8519,8 28.92%
KIDА
7.30 2096
ST/000
64.20
91 31.01%
52.88
14.50%
K2/200
48
18.99
627.15
18019
489189
8058 94 14.709
TRRI
7.34
K7.30
T 20415
32.55
17:30%
757200
193376
597.79
1477%
BIAKC T 27.79%
Maximum Independent
Methods
Time
Win/Sabood
Eass
Mediam WinSSbbed
Time
WindSobeal 37191
Hard
Naslook
SCIP
96.29 = 15%
277200
S910T =: 31.3%
JUG 17,80%
41/200
921.8
2239% 758.5e 23.
WIRT7
GCNN
60.89
60220
1100.35 37.27%
29.52%
47/200
137409
31.99%
760.84
23%17%
KIDM
00.64
52/200
100601
140302
22.011
796.1
Capacitated facility location
Table 6: Eperiment on the dataset of the MIACO 2021 competition.
Methods
placement Dual Gap
Worklnad
Apportionment Dual Gup
anonymous Dual Gap
Dual Bound
Reward
Dual Bound
Reward
Dual Bound
Reward
SCIP
5,25
63.24%
699.36
3.17%
29926.57
52.10%
GCNN
5.18
61.19%
4387
701.82
2.84%
631127
31011.52
46.75%
27344112
KIDA
8.719
38.18%
7532
701.79
2.84%
631147
31102.45
46.16%
27548468
HRL-Ang
8.725
34.16%
7538
701.80
2.84%
631203
31170.81
45.64%
27672243
solving efficiency with quite close performance for easy problems. Interestingly, the results reveal that there is no direct connection between the final node counts and the solving time.
Table 6 gathers the results for ML4CO datasets. ML4CO-KIDA significantly outperforms GCNN, which reveals that iterative-based methods may deal with some challenges faced by pure IL models. Among all the competing baselines, our hybrid framework consistently dominates the others, illus- trating the effectiveness of online RL which can drive much deeper exploration from the iteratively updated policies. Notably, the ablation study shows our proposed method can even outperform Gurobi on item placement problems, purely assisted by the open-source solver SCIP.
Generalization analysis. We further test our method on some difficult instances (Medium and Hard) to evaluate the generalization ability, and the overall results gathered in Table 5. As can be seen, the default SCIP branching strategies significantly underperform the learning-based policies on solving time, revealing the limitations of the expert rules, especially on large-scale instances. Similarly, our proposed method consistently outperforms the competing baselines in terms of solving efficiency, showing a better generalization ability to larger instances.
4.3 ABLATION STUDY
We present an ablation study to verify the effectiveness of the online RL agent and offline RL agent. Specifically, we evaluate our method and ML4CO-KIDE with different iteration steps.
In Table 7 and Table 8, the training time is categorized into sample generation time and model training time. For the training sample generation time, our approach closely aligns with that of MI ACACCO-IDA
8

---

Published as a conference paper at ICLR 2024
Table Ablation study on Combinatorial Auction.
HRRL-Aug
XLLCOOKIDA
iteration
Samples
Samples generation time
Training time
Samples
Samples gencration time
Training time
7,067
29 min
19
10K
35 min
11
70,620
65 min
100K
71 min
127.757
98 min
129 min
200K
111 min
175 min
30
194,683
143 min
201 min
300K
149 män
266 min
268,013
189
257 min
400K
191
359 min
Table 8: Ablation study on anonymous. MCACO-KI
HRI.-Aug
iteration
Samples
Samples generation time
Training time
Samples
Samples generation time
Training time
1
6,627
1.78 hours
1.36 hours
10K
1.68 hours
0.26 hours
10
68,235
19.30 hours
9.57
100K
16.67 hours
6.27 bours
20
136.756
38.92 hours
18. 28 hours
200K
40.35 hours
29.45 hours
20,3754
58.31 hours
27.32 hours
300K
96 hours
bours
40
27,1761
77.09 hours
36.33 hours
400K
83.85 hours
59,20 bours
Table 10: Further validating the generalizability of HRRL-Aug in Combinatorial Auction.
Methods
WinSSolved
SELF
Nodest
Time
WinSaaved
CNN
Nodest
WinSoovee
RSN
Nodest
SCIP
117200
2.34 30.0%
25:00
21.38
1.50
7.71%
83/200
98.63
8.88%
6.99
9.02%
188
1.25%
73/00
94.0 8.73%
Oun
1.99 681
106200
100.89 1 9.25%
1.3 x 630%
103/00
100.8 3.42%
136 33.00
102200
91.9 1 9.188
on both the combinatorial auction and anonymous problem. However, with our newly incorporated offline RL agent, the training sample size of our proposed HRL-Aug reduced by around 30% each iteration compared with MLACO-KIDA, In general, the overall model training time was reduced by 28%, and 38% on combinatorial auction and anonymous problems, respectively, thus illustrating the efficacy and essential role of the offline RL agent.
Table 9 ablates the effect of online/offline RL for item placement. HRL-Aug-on means disabling the offline agent, and thus the training samples are not filtered by their qualities. HRL-Aug-off means disabling the online agent, and thus the expert experience is only considered. The results suggest that the online part is more important, and both parts have positive effects.
Table 9: Results on item placement.
Methods
Dual Bound
Dual Gap
Reward
GCNN
5.183
61.19%
4387
GUROBI
8.522
36.65%
HRL-Aug-off
7.245
43.49%
5983
HRL-Aug-on
8.417
37.35%
7241
HRR--Au
8,725
34.16%
7538
4.4 GENERALIZABILITY OVER VARIABLE SELECTION POLICY EMBODIMENT
To assess our methodology's network wise generalization, we position it within the framework of combinatorial auction problem. The validation process was rigorously executed on set of easy-level problems, comprising 40 instances. Each instance underwent testing under five seeds. To verify the adaptability and generalization potential of our approach across diverse network architectures, we replaced GCNN with alternative models such as the Multilayer Perceptron (MLP, input features=17, hidden size=64, output features=1), Convolutional Neural Networks (CNN, input channels=17, output channels=64, kernel size=3), and Recurrent Neural Network (RNN, input size=17, hidden sizc=64, num layers=1, sequence length=500) variable selection policies for both method and MILACO-KIDA. A comprehensive depiction of performance metrics has been thoughtfully compiled and presented in Table 10. The outcomes unequivocal
approach consistently outperforms both ML4CO-KIDA and SCIP. This observation substantiates the inherent model-agnostic nature of our methodology, emphasizing its versatility and effectiveness across various scenarios.
CONCLUSION AND OUTLOOK
We have proposed hybrid online and offline RL approach to enhance the branching policy via efficient training set augmentation. Hybrid agents perform in an iterative manner, with an online RL agent deciding sample generation, either from the expert rule or learning-based policy, and an offline RL agent further filtering the generated samples with high cumulative returns. Experiments on different MIP problems show its effectiveness, even achieving superior performance over the leading commercial solver in some cases. HRL-Aug also shows superior generalization ability. Future work may combine learning to presolve (Liu et al., 2024) and instance generation (Wang et al., 2023; Li et al., 2023) with learning-based solvers in synergetic manner.

---

Published as a conference paper at ICLR 2024
REFERENCES
Mirplib a library of maritime inventory routing problem instances: Survey, core model, and benchmark results. European Journal of Operational Research, 235(2):350-366, 2014. ISSN 0377-2217. Maritime Logistics.
Tobias Achterberg, Thorsten Koch, and Alexander Martin. Branching rules revisited. Operations Research Letters, 33(1):42-54, 2005a. ISSN 0167-6377.
Tobias Achterberg, Thorsten Koch, and Alexander Martin. Branching rules revisited. Operations Research Letters, 33(1):42-54, 2005b.
Alejandro Marcos Alvarez, Quentin Louveaux, and Louis Wehenkel. A supervised machine learning approach to variable branching branch-and-bound. ECML, 2014.
David Applegate, Robert Bixby, Vašek Chvátal, and William Cook. Finding cuts in the tsp (a preliminary report). Technical report, 1995.
Christian Artigues, Michel Gendreau, Mariin Rousseau, and Adrien Vergnaud. Solving integrated employee timetabling and job-shop scheduling problem via hybrid sanchhanddboundd Computers & Operations Research, 36(8):3330-2344) 2009.
Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning branch. In ICML, 2018.
Peter Brucker, Bernd Jurisch, and Bernd Sievers. A branch and bound algorithm for the job-shop scheduling problem. Discrete applied mathematics, 49(1-3):107-127, 1994.
Zixuan Cao, Yang Xu, Zhewei Huang, and Shuchang Zhou. MI4co-kida: Knowledge inheritance in dataset aggregation. arXiv preprint arXiv:2201. 2022a.
Zixuan Cao, Yang Xu, Zhewei Huang, and Shuchang Zhou. M14co-kida: Knowledge inheritance in dataset aggregation. arXiv preprint urXiv:2201.10:222 2022b.
Xinyue Chen, Zijian Zhou, Zheng Wang, Che Wang, Yanqiu Wu, and Keith Ross. Bail: Best-action imitation learning for batch deep reinforcement learning. NeurIPS, 2020.
Santanu S. Dey. Yatharth Dubey, Marco Molinaro, and Prachi Shah, A theoretical and computational analysis of full grrong-branching arXiv e-prints, 2021.
Adrien Ecoffet, Joost Huizinga. Joel Lehman, Kenneth O. Stanley, and Jeff Clune. First return, then explore. Nature, 590(7847):580-55 feb 2021.
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. 2018
Gerald Gamrath, Daniel Anderson, Ksenia Bestuzheva, Wei-Kun Chen, Leon Eifler, Maxime Gasse, Patrick Gemander, Ambros Gleixner, Leona Gottwald, Katrin Halbig, al. The scip optimization suite 7.0. 2020a.
Gerald Gamrath, Timo Berthold, and Domenico Salvagnin. An exploratory computational analysis of dual degeneracy in mixed- integer programming, EURO Journal on Computational Optimization, (3):241-266 2020b. ISSN 2192-4406.
Tanmay Gangwani, Qiang Liu, and Jian Peng. Learning self-imitating diverse policies. arXiv preprint arXiv: 10309, 2018.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combina- torial optimization with graph convolutional neural networks. NewrIPS, 2019.
Maxime Gasse, Simon Bowly, Quentin Cappart, Jonas Charfreitag, Laurent Charlin, Didier Chételat, Antonia Chmiela, Justin Dumouchelle, Ambros Gleixner, Aleksandr M. Kazachkov, Elias Khalil, Pawel Lichocki, Andrea Lodi, Miles Lubin, Chris J. Maddison. Morris Christopher, Dimitri J. Papageorgiou, Augustin Parjadis, Sebastian Pokutta. Antoine Prouvost, Lara Scavuzzo, Giulia Zarpellon, Linxin Yang, Sha Lai, Akang Wang, Xiaodong Luo, Xiang Zhou, Haohan Huang,
10

---

Published as a conference paper at ICLR 2024
Shengcheng Shao, Yuanming Zhu, Dong Zhang, Tao Quan, Zixuan Cao. Yang Xu, Zhewei Huang. Shuchang Zhou, Chen Binbin, He Minggui, Hao Hao, Zhang Zhiyu, An Zhiwu, and Mao Kun. The machine learning for combinatorial optimization competition (ml4co): Results and insights. In Douwe Kiela, Marco Ciccone, and Barbara Caputo (eds.), Proceedings of the NeurlPS 2021 Competitions and Demonstrations Track, volume 176 of Proceedings of Machine Learning Research, pp. 220-231. PMLR, 06-14 Dec 2022.
Wasu Glankwamdee and Jeff Linderoth. Lookahead branching for mixed integer programming, In International Conference on Supercomputing, 2011.
Yijie Guo, Jongwook Choi, Marein Moczulski, Samy Bengio, Mohammad Norouzi, and Honglak Lee. Self-imitation learning via trajectory-condttooned policy for hard-exploration tasks. 2019.
Prateek Gupta, Maxime Gasse, Elias Khalil, Pawan Mudigonda, Andrea Lodi, and Yoshua Bengio. Hybrid models for learning to branch. NeurIPS, 2020.
Hanif Halim and IJAoCMiE Ismail. Combinatorial optimization: comparison of heuristic algo- rithms in travelling salesman problem. Archives of Computational Methods in Engineering, 26(2): 367-380, 2019.
Gregor Hendel. Enhancing mip branching decisions by using the sample variance of pseudo costs. In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 2015.
A. Hussein, M. M. Gaber, E. Elyan, and C. Jayne. Imitation learning: survey of learning methods. ACM Computing Surveys, 50(2), 2017.
Yang Li, Xinyan Chen, Wenxuan Guo, Xijun Li, Wanqian Luo, Junhua Huang, Hui-Ling Zhen, Mingxuan Yuan, and Junchi Yan. Hardsatgen: Understanding the difficulty of hard sat formula generation and a strong dimcuure-hardness-ave baseline. In Proceedings of the ACM SIGKDD International Conference Knowledge Discovery and Data Mining (KDD), 2023.
Chang Liu, Zhichen Dong, Haobo Ma, Weilin Luo, Bowen Pang. Xijun Li, Jia Zeng, and Junchi Yan. L.2p-mip: Learning presolve for mixed integer programming. In ICLR, 2024.
ZA Lomnicki. A "branch-and-bouud -boundd algorithm for the exact solution of the three-machine scheduling problem. Journal of the operational research society, 16(1):89-100, 1965.
Junhyuk Oh, Yijie Guo, Satinder Singh, and Honglak Lee. Self- imitatiittion learning. In ICML, 2018.
Christopher WF Parsonson, Alexandre Laterre, and Thomas D Barrett Reinforcement learning for branch-and -nn-d optimisation using retrospective trajectories. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 4061-4069, 2023.
Jagat Patel and John W Chinneck. Active-constrain variable ordering for faster feasibility of mixed integer linear programs. Mathematical Programming, 110(3):445-474, 2007.
Xue Bin Peng, Aviral Kumar, Grace Zhang, and Sergey Levine. Advantage-weighted regression: Simple and scalable off-policy reinforcement learning. arXiv preprint arXiv: 1970.00/77, 2019.
Antoine Prouvost, Justin Dumouchelle, Lara Scavuzzo, Maxime Gasse, Didier Chételat, and Andrea Lodi. Ecole: A gym-like library for machine learning combinatorial optimization solvers. arXiv preprint ar arXiv:2011.06069 2020.
Qingyu Qu, Xijum Li, and Yunfan Zhou. Yordle: An efficient imitation learning for branch and bound. arXiv preprint XXx::2202.0199 2022a.
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 branch, 2022b.
Stéphane Ross, Geoffrey Gordon, and J. Andrew Bagnell. A reduction of imitation learning and structured prediction no-regret online learning. In AISTATS, 1984.

---

Published as a conference paper at ICLR 2024
Lara Scavuzzo, Feng Chen, Didier Chételat, Maxime Gasse, Andrea Lodi, Neil Yorke-Smith, and Karen Aardal. Learning to branch with tree mdps. Advances in Neural Information Processing Systems, 35:18514 1175514-1856, 2022.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In JEEE/RSJ international conference on intelligent robots and systems, 2012.
Jie Wang, Zijie Geng, Xijun Li, Jianye Hao, Yongdong Zhang, and Feng Wu. G2milp: Learning to generate mixed-integer linear programming instances for milp solvers. In NeurIPS, 2023.
Qing Wang, Jiechao Xiong, Lei Han, Han Liu, Tong Zhang, et al. Exponentially weighted imitation learning for batched historical data. NeurIPS, 2018.
Jiayi Zhang, Chang Liu, Xijun Li, Hui-Ling Zhen, Mingxuan Yuan, Yawen Li, and Junchi Yan. A survey for solving mixed integer programming via machine learning. Neurocomputing, 519: 205-217, 2023.
Zhuangdi Zhu, Kaixiang Lin, Bo Dai, and Jiayu Zhou. Self-adaptive imitation learning: Learning tasks with delayed rewards from sub-optimal demonstrations. In AAAI, 2014.
12

---

Published as a conference paper at ICLR 2024
A APPENDIX
A.1
THE FEATURE OF GCNN
The bipartite graph features used throughout this paper are listed in Table 11.
Table 11: Description of the constraint, edge, and variable features in the GCNN
Name
Feature
Description
obj_cos_siig
Cosine similarity with the objective.
bias
Bias value, normalized with constraint coefficients.
Constraint features
is_ s_tight
Tightness indicator I.P solution.
dualsol_ val
Dual solution value, normalized.
age
LP age, normalized with total number of LPs.
Edge features
coef
Constraint coefficient, normalized per constraint.
type
Type (binary, integer, impl. integer, continuous) as one-hot encoding. Ohjective coefficient, normalized.
coef
hasib
Lower bound indicator.
has ju_
Upper bound indicator.
sol_is_at_ _is_a__l____ lb
Solution value equals lower bound.
sol at
Solution value equals upper bound. Solution value fractionality.
Variable features
sol frac
basis status
Simplex basis status (lower, basic, upper, zero) as a one-hot encoding. Reduced cost, normalized.
reduced_com cost
age
LP age. normalized. Solution value.
val
inc_val avg ine_val val
Value in incumbent. Average value in incumbents.
A.2 BRANCHING
Branching is the core of the branch-and-bound algorithm, and designing effective strategies was critical to mixed Integer programming (MIP) solving right from the beginning.
The overall pipeline for branching is listed as follows:
Algorithm 2 Generie branching (variable selection)
1: Input: Current subproblem Q with optimal linear programming (LP) solution i é. XMIP
2: Output: An index j of an integer variable zj with the fractional LP value & & Z.
3: Let F {j f|2 e 2} be the set of branching candidates.
4: For all camdidates
value xy 5: return index F with mazze (ex)
calculate
There many rule-based expert strategies, such as strong branching (Applegate al., 1995), active constraint (Patel & Chinneck, 2007), and so on. For example, the widely utilized strong branching will select the fractional variable with the best dual bound improvement to branch on, listed as Eq.
8j marlto, - Co,Rot {o}
where sy denotes the score for each fractional candidate Q, represents the left subproblem by adding the trivial inequality < [ I. and Q3 represents the right subproblem by adding the trivial inequality zj 2 [ ]. ė denotes the objective value the LP relaxations.
For the GCNN policy, each variable selection iteration, it will get the input features listed in Table 11, and predict sj for each fractional candidate variable. Then it will select an index j E with 8j marker (88) ) as the branching variable.
13

---

Published as a conference paper at ICLR 2024
A.3 DIFFERENCE IN METHODOLOGY AND PERFORMANCE WITH ML4CO-KIDA (CAO ET AL., 2022A)
KIDA is a Dagger-like method based on II.. Though interacting with the solver with 95% probability of using model ;1 and 5% probability of using Strong Branching in the solving process, it only collected training samples from Strong Branching. While in our paper, there are the following major differences, which are also our contributions:
1) In the solving process, the variable selection from m;-1 or strong branching was not decided by pre-defined parameters (95% vs 5% in KIDA). We proposed online RL agent to dynamically determine the selection and may generate more reasonable samples. You can see Section 3.2 for details.
2) Different from KIDA, samples from strong branching and -; will both be collected by the decision from the online agent.
3) We devised an extra offline learning phase to filter higher cumulative reward samples, which can significantly reduce the training complexity and may improve imitation learning performance to some extent.
Besides, the data augmentation mechanism in the proposed methodology can be segmented into collectors and filters. The KIDA has no filtering phase. Key distinctions exist in the collection phase:
Selection Mechanism: In the case of KIDA, its selector operates under the influence of a Bernoulli distribution, wherein a hyperparameter is determined based on an in-depth grasp of domain expertise. Nonetheless, this approach grapples with manageability issues, particularly when the decision problem grows in complexity. Our approach takes different path, circumventing this challenge. We leverage an online reinforcement learning agent that imbibes knowledge from data iteratively, thereby gradually converging toward an optimal distribution. This distribution is notably more intricate than the Bernoulli model, especially tailored to effectively tackle intricate decision problems.
2) Collection Mechanism: In the realm of KIDA, its collector solely acquires samples from the expert policy of strong branching. This policy, albeit optimal at the immediate juncture, might not necessarily hold the same effectiveness over extended trajectory. Our approach, the other hand, goes beyond this confined paradigm. We amass samples not just from the expert policy, but also from the model policy. This judicious balance between exploitation and exploration forms the bedrock of our imitation learning, propelling us to converge toward the zenith of the optimal distribution. This distribution, then, serves as the compass guiding our branching decisions, distinctly setting apart from KIDA.
A.4 FURTHER DISCUSSION ON THE NOVELTY OF OUR DATA AUGMENTATION FRAMEWORK FOR IMITATION LEARNING
Our primary innovation lies in the introduction of the data augmentation Framework, which is meticulously designed for the realm of imitation learning. This framework comprises three pivotal components: an online Reinforcement Learning (RL) agent, an offline RL agent, and an imita- tion lcarning-based policy. Refer to Figure for a comprehensive depiction of this framework's architecture and functionality.
1) The Online RL Agent:
The online RL agent plays a pivotal role by facilitating the profound exploration of uncharted scenarios. By striking a balance between exploration and exploitation, it effectively steers clear of local optimal solutions for branching variables. Consequently, the presence of the online agent substantially enhances the overall effectiveness of imitation learning.
2) The Offline RI Agent: As evidenced by Table and Table 8, the primary advantage of the offline RL agent lies in its ability to enhance the efficiency of imitation learning. Remarkably, it accomplishes this by reducing the model training time by approximately 30%, so the model training time reduced by 28%, and 38% in combinatorial auction and anonymous problem respectively. Thereby illustrating the efficacy and efficiency of the offline RL agent.
3) The Imitation learning- based policy: A crucial validation of our proposed Data Augmentation Framework (HRL-Aug) unfolds within the context of branching scenarios. At the core of this validation lies the deployment of an imitation learning-based policy. This policy, meticulously learned
14

---

Published as a conference paper at ICLR 2024
Table 12: Compare with the RL for branching method.
Easy Win/Solved
Methods
Time
Nodes#
Time
Win/Solved
Nodes#
121.78
5.53%
17200
+ 12.91%
Scavuzzo et al. (2022)
8.88 + 96%
8/200
1215.20 + 26.00%
63.05 = 18.24%
0/200
6192. 78 +: 825
Parsonson al. (2023)
8.86 9.60%
2/200
496.3 = 16.92%
50.67 12.08%
0/200
2585.4 + 14.68%
HRL-Ang
5.40 8.84%
186200
149.34 = 7.37%
19.54
1997000
555.61 6.52%
Set Covering
through the imitation learning process, emerges as pivotal component capable of supplanting expert-based policies within solvers, akin to SCIP as exemplified in this study.
Our main contribution is the novel data augmentation framework for imitation learning. We have indeed undertaken comprchensive tests on the generalization capabilities of our proposed framework. Specifically, we have replaced the learning-based Graph Convolutional Network (GCN) with alterna- tive architectures, such as Multi-Layer Perceptrons (MLPs), Convolutional Neural Networks (CNNs), and Recurrent Neural Networks (RNNs) shown in section 4.4. Our approach consistently outper- forms both ML4CO-KE -IDDA and SCIP. This observation substantiates the inherent model-agnostic nature of our methodology, emphasizing its versatility and effectiveness across various scenarios.
A.5 COMPARE WITH RL FOR BRANCHING METHOD
Recently RL-based methods have been proposed to enhance the branching policies, which do not rely on the expert rule, and might find better policy for branching. To further validate the effectiveness of our method, we conducted an experiment in the set covering to compare with two RL-based methods, including Scavuzzo et al. (2022) and Parsonson et al. (2023). We use similar metrics as those in Gasse et al. (2019) and set SCIP's parameter the same with Scavuzzo et al. (2022), Note that the model published by Parsonson et al. (2023) and Scavuzzo et al. (2022), their model is trained in the 500 rows, 1000 columns, and 400 rows, 750 columns covering problem respectively. Then, evaluation is performed for E5sy(500 rows, 1000 columns) and Medium (1000 rows, 1000 columns) on 40 generated instances using five different seeds, which amounts to total of 200 solving attempts per method. As shown in Table 12, the results show that our method is obviously better than the RL-based method both in solving time and nodes.
A.6 COMPARE THE NUMBER OF NODES SOLVED TO OPTIMAL BETWEEN GCNN (GASSE ET AL., 2019) AND STRONG BRANCHING.
Strong Branching the most efficient branching strategy in terms of the number of nodes in the B&B tree. To verify whether the learned GCNN (Gasse al., 2019) achieve smaller B&B tree than strong branching or not, we perform experiments on the combinatorial auction problem with 200 easy difficulty instances, shown in Table 13.
Specifically, we compare the number of nodes each branching policy solved to optimal-Wins (Nodes). The Win (Nodes) shows that the GCNN (Gasse et al., 2019) can perform better than Strong Branching in some instances. empirically verifies that the quality of variable selection in strong branching can be further improved.
Table 13: Compare the node counts
when solved to optimal.
Methods GCNN
Winst Nodes)
40/200
Strong Branching
174/200
15


Reviews:
[{"review_id": "zScUKKqTLG", "reviewer": "Reviewer_f3Ne", "summary": "This paper studies the use of imitation learning (IL) and Reinforcement Learning (RL) to tackle Mixed Integer Programming (MIP) problems. The main contribution of the paper is a framework that is specifically designed for MIP problems. Empirical results on a number of MIP problems show that the proposed method can achieve good performance with reduced model training time.", "questions": "- How time consuming is strong branching compared to your method? Can you provide a wall-clock time comparison? \n- It is a bit unclear to me how exactly does the online agent decide whether to use the learned policy or expert policy? \n- Page 5, section 3.3, \"batch DRL\" is a general concept and is essentially the same as \"offline DRL\", which is initially discussed in some earlier papers (e.g. \"Off-policy deep reinforcement learning without exploration\" by Fujimoto et al.). The method in Chen et al., 2020 (Best Action Imitation Learning) is one of the imitation learning methods to tackle the batch/offline DRL problem. You might want to change the writing here to be more accurate. \n- What is the \"ActorCritic\" algorithm you are using? \n- Table 6 why there is no highlight on the best performing method for each task? Or the values are not related to performance?- Typically RL agents can take time to train, why is it the case that the proposed method, despite its complexity and a multi-stage/agent setup, can reduce training time compared to other methods?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "**originality**\n- The paper's main novelty is a new framework that is designed to use IL and RL to tackle MIP problems. \n\n**quality**\n- The overall presentation is good\n- The paper discusses related works in a fairly clear manner\n\n**clarity**\n- Overall the paper is clear and easy to follow, however, the explanation on how the agent works can be improved\n\n**significance**\n- The paper studies how IL and RL can be applied to the MIP problems, which seems to be an important research direction\n- The improved training time and better performance can be a significant result.", "weaknesses": "Discussion on the proposed method:\n- I find the writing on how the proposed method works is a bit confusing, this might be partly due to the complexity of the problem. For example, what exactly actor critic method did you use in the online setting (for example, A type of SAC? DQN?)? And how exactly does the online RL agent decide whether to use the expert or to use the learned policy? (if for example, you say the action space is discrete, with 2 actions, one to choose the expert and the other to choose the learned policy for the online RL agent and it is a Q-learning type of agent, then it becomes much clearer) Currently I don't fully follow what is happening here. (also see questions)\n- Another concern is the proposed method seems to only apply to only the MIP problems, and although the empirical results are interesting, it is a little unclear to me how much technical novelty is in the design of this framework and whether the contributions in this paper is significant enough.", "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": "1PoTdYtmGx", "reviewer": "Reviewer_Gdrc", "summary": "This paper presents a hybrid RL approach for variable selection in mixed integer programming (MIP). The proposed approach uses online RL to select between a rule-based expert and imitation learning based policy. The data collected from this online agent is filtered by a mechanism referred to as the offline agent and sent to a GCNN-based imitation-learning agent. This process repeats iteratively for a number of iterations. Results are presented on a number of integer programming problems and compared to an open-source and commercial solver with expert branching rules and two imitation learning methods. The proposed method outperforms the baselines on most domains and an ablation shows the importance of the proposed sub components.", "questions": "My questions mostly relate to the RL part of the proposed approach.\n\n1. What agent was used to train RL online? Was it a REINFORCE-like algorithm or something more complex? This may be important because the convergence guarantees of RL algorithms are often made in the discounted setting with \\gamma < 1. It is also important to specify the precise algorithm used for reproducibility. \n2. I’m confused as to the ‘Offline RL’ agent. To me, offline RL implies learning a policy i.e. an action selection mechanism - using fixed trajectories of data that were generated by some behavior policy (or policies). In the paper, what is described is more of a filtration mechanism where effectively a function is fit to returns generated in the first iteration and then subsequently used to threshold the trajectories to sample. Could the authors clarify this point?\n3. There are a number of choices made in the paper whose impact is not clear. For example, the filtration mechanism parameters are fit on the first iteration and kept constant after. Equation 4 uses a \\lambda parameter to regularize the fit.The online agent is trained every 5 iterations (Freq). Some unspecified choice of `z’ defines how the trajectories are sub-sampled. It is not clear to me how important any of these choices are. Ideally the paper would include ablations on these but I can understand the difficulty of presenting so much information with a page limit. If the authors could indicate why these choices were made (with possible empirical evidence in the Appendix), I think it would make the paper stronger.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Overall the results in the paper look strong. I do not have much experience with the MIP problem and cannot comment on the baselines but from the presentation they seem relevant and appropriate. From an RL and algorithmic perspective there are some additional ablations that could be interesting, but the presented ablations seem reasonable to me.", "weaknesses": "To me, the primary weakness in the current draft is the presentation. The ordering of the Tables in the Experiments section are confusing - tables are introduced and described in a non-sequential order and there are typos and odd sentences in the text that make the descriptions hard to follow at times. For example Table 3 and 4 show the Ablation results of comparing HRL-Aug to ML4CO-KIDA while the main results are presented later in Table 7 and 8. Just re-ordering the Table sequences would make it much easier to read.\n\nI have a number of questions and clarifications relating to the algorithm which I will described under `Questions` but could also count as weaknesses. \n\nApart from that there are a few typos and textual clarifications I will list below:\n\n    1. Page 4 sentence 1: ‘Framework’ should be ‘framework’.\n    2. Section 3.3: off-policy methods should be ‘offline methods’.\n    3. Section 4.1: Dataset has `We’ appear in many places which should be `we’. \n    4. Section 4.4 mentions: “We genuinely appreciate the collaborative effort of the reviewers and their invaluable role in shaping our work’. This is an awkward phrase that isn’t warranted before the review process? To me, it seems likely this is a vestige of a resubmission.", "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": "lzgl9tAqdQ", "reviewer": "Reviewer_pX8W", "summary": "Update on November 20:\n\nI raised my score to 6 based on the authors' responses. I am willing to keep discussing with the authors and the other reviewers to achieve a fully discussed final score.\n\n\n---\nThis paper proposes a novel iterative collection and filtering framework to leverage a combination of online and offline RL techniques. Experiments show it consistently outperforms the previous SOTA approaches. Moreover, the authors claim that the proposed approach can be regard as a plugin orthogonal to peer methods.", "questions": "1. Is the online RL training necessary? Intuitively, using an offline-trained policy to collect data and then update the policy with the collected data iteratively seems to be enough. Why is the online updating of the policy during data collection necessary?\n2. What is the dual bound change when a child node is infeasible? In SCIP, the solver add the objective and the current global primal bound to the constraints, making the infeasible child appears in high frequency. Thus, in the calculation of FSB scores, the score of infeasible child is set to a dynamic large value. How about that in this paper?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1. The experiment is thorough. The authors provide very detailed empirical results to demonstrate the effect of the proposed approach.\n2. Clear writing, the paper is clearly structured and easy to go through flow.\n3. The proposed approach is technically sound. The employment of RL in this task is technically sound.", "weaknesses": "1. Concerns about the motivation. Personally, I am not convinced about the motivation to introducing RL in the branching task. As reported in some previous work [1,2], the number of expanding nodes of FSB is significantly less than that of SOTA ML approaches, indicating that *FSB is a good enough expert policy to imitate*. Instead, the bottleneck in this topic may mainly lie in the low IL accuracy. The lower accuracy may due to the unsatisfactory model structure or the insufficient information in the widely-used bipartite graph states (observations, more precisely). However, currently I found no definitive answer about that in recent researches. The ablation study in a recent research [3] gives clues that the historical information is effective as the process is a POMDP. Thus, in my personal opinion, the latter reason seems closer to the truth. Thus, based on these results, I think all researches that proposing more complex online RL framework is somewhat incremental, as improving the IL accuracy seems to be the key.\n2. Concerns about the unnecessary complexity for introducing RL. Though usually higher asymptotic performance, many RL approaches are usually sensitive to the hyperparameters, making their application requiring much manual tunings. I am doing research in both RL and CO, empirically, I found their combinations can be fragile. In this paper, the online RL is mainly used for data collection. However, as far as I know, RL approaches are usually sensitive to the data distribution due to the deadly triad. For example, TD3 [4] may fail in MuJoCo tasks when the initial 20k random steps of data collection is turned off; BCQ [5] may fail when the offline data are collected with hybrid policies. Thus, in real-world CO tasks, I prefer use simple GNN+IL approach rather than other complex but fragile approaches, even if they claim higher performance in the four synthetic benchmarks. For this paper, I am concerned about the complexity for introducing RL.\n3. More explanations is required. In this paper, the RL based approach achieves lower IL accuracy while higher e2e performance. Thus, I am interested in what kind of multi-step information it learns from the input states. I believe this is more meaningful than simply reporting performance improvements, as it can guide us in designing better input features as mentioned in Point 1. If only the approach is given but the explanations is missed, then this paper is more like just a application of existing RL approaches to a new \"Atari\".\n4. Limited improvement compared to ML4CO-KIDA. The performance of HRL-Aug reported in Table 7 seems to be marginal to ML4CO-KIDA.\n\nAnyway, the comments above may be too tough for studies in this research field. Thus, if the other reviewers all give more  positive scores, I will be willing to keep discussing with the authors and the other reviewers to achieve a fully discussed score.\n\n[1] Gasse, Maxime, et al. \"Exact combinatorial optimization with graph convolutional neural networks.\" Advances in neural information processing systems 32 (2019).\n\n[2] Gupta, Prateek, et al. \"Hybrid models for learning to branch.\" Advances in neural information processing systems 33 (2020): 18087-18097.\n\n[3] Seyfi, Mehdi, et al. \"Exact Combinatorial Optimization with Temporo-Attentional Graph Neural Networks.\" Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Cham: Springer Nature Switzerland, 2023.\n\n[4] Fujimoto, Scott, Herke Hoof, and David Meger. \"Addressing function approximation error in actor-critic methods.\" International conference on machine learning. PMLR, 2018.\n\n[5] Fujimoto, Scott, David Meger, and Doina Precup. \"Off-policy deep reinforcement learning without exploration.\" International conference on machine learning. PMLR, 2019.", "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)