CAMBranch: Contrastive Learning with Augmented MILPs for Branching
Authors: Jiacheng Lin
Meng XU
Zhihua Xiong
Huangang Wang
Venue: ICLR 2024 poster (2024)
Keywords: Contrastive Learning
Mixed Integer Programming
Machine Learning
Branching Stratigies
Data Augmentation
Primary area: representation learning for computer vision, audio, language, and other modalities
TL;DR: A data augmentation approach to acquire expert samples of Strong Branching for imitation learning.

Abstract: Recent advancements have introduced machine learning frameworks to enhance the Branch and Bound (B\&B) branching policies for solving Mixed Integer Linear Programming (MILP). These methods, primarily relying on imitation learning of Strong Branching, have shown superior performance. However, collecting expert samples for imitation learning, particularly for Strong Branching, is a time-consuming endeavor. To address this challenge, we propose \textbf{C}ontrastive Learning with \textbf{A}ugmented \textbf{M}ILPs for \textbf{Branch}ing (CAMBranch), a framework that generates Augmented MILPs (AMILPs) by applying variable shifting to limited expert data from their original MILPs. This approach enables the acquisition of a considerable number of labeled expert samples. CAMBranch leverages both MILPs and AMILPs for imitation learning and employs contrastive learning to enhance the model's ability to capture MILP features, thereby improving the quality of branching decisions. Experimental results demonstrate that CAMBranch, trained with only 10\% of the complete dataset, exhibits superior performance. Ablation studies further validate the effectiveness of our method.

Published as a conference paper at ICLR 2024
CAMBRANCH: CONTRASTIVE LEARNING WITH AUGMENTED MILPs FOR BRANCHING
Jiacheng Lin
Meng Xu²t
Zhihua Xiong?
Huangang Wang?1
University of Illinois Urbana- Champpaaanp
Tsinghua University
ABSTRACT
Recent advancements have introduced machine learning frameworks to enhance the Branch and Bound (B&B) branching policies for solving Mixed Integer Lin- ear Programming (MILP). These methods, primarily relying on imitation learning of Strong Branching. have shown superior performance. However, collecting ex- pert samples for imitation learning, particularly for Strong Branching, is a time- consuming endeavor. To address this challenge, we propose Contrastive Learning with Augmented MILPs for Branching (CAMBranch), a framework that gener- ates Augmented MILPs (AMILPss) by applying variable shifting to limited expert data from their original MILPs. This approach enables the acquisition of con- siderable number of labeled expert samples. CAMBranch leverages both MILPs and AMILPs for imitation learning and employs contrastive learning to enhance the model's ability to capture MILP features, thereby improving the quality branching decisions. Experimental results demonstrate that CAMBranch, trained with only 10% of the complete dataset, exhibits superior performance. Ablation studies further validate the effectiveness of our method.
INTRODUCTION
Mixed Integer Linear Programming (MILP) is a versatile tool for solving combinatorial optimization
problems, with applications across various fields (Bao & Wang 2017: Soylu et al. 2006 Godart
jet al. 2018 Almeida et al. 2006 Hait & Artigues 2011) 1). A promment approach for solving MILPs
the Branch-and-Boune and-conquer approach, iteratively resolving sub- sub-problems and progressively reducing the search space. Within the execution of the algorithm, one pivotal decision comes the fore: variable selection, also known as branching. Traditionally, variable selection relies heavily on expert-crafted rules rooted in substantial domain knowledge. However, recent developments have seen shift of focus towards the integration of machine learning based frameworks, aiming to enhance the B&B algorithm by replacing conventional, hand-coded heuristics (Gasse et al. 2019 Zarpellon et al., 2021 Nair et al. 2020 Lin et al.) (022). This transition marks a notable ad advancmment in the field, leveraging the power of machine learning and data-driven approaches to tackle complex problems more effectively. For a comprehensive overview of the notable developments in this emerging field,
(B&B) algorithm (Land & Doig 1960). This algorithm adopts divide-
refer to the survey provided in [engio et al. (202T).
The performance of the B&B algorithm hinges significantly upon its branching strategy, and sub- optimal branching decisions can exponentially escalate the computational workload. This predica- ment attracts researchers to explore the integration of machine learning (ML) techniques to enhance branching strategies. Notably, Gasse et al. (019) have trained branching policy models using imita- tion learning, specifically targeting Strong Branching (Applegate et al.) 11995). traditional strategy known for generating minimal branching search trees but with extremely low efficiency. By map- ping a MILP into bipartite, these branching policy models leverage Graph Convolution Neural Networks (GCNN) (Kipf & Welling 2017) to extract variable features and make variable selec-
* "This work completed during the master program Tsinghua University.
1 Equal contributions. Corresponding hgwang@ inghua, edu. cn.

---

Published as a conference paper at ICLR 2024
tion decisions. This approach has demonstrated superior performance in solving MILPs, marking significant milestone in the application of machine learning to MILP solving.
Despite making significant progress, significant challenge arises with the imitation learning paradigm mentioned above. The collection of expert samples for imitation learning requires solving numerous MILP instances using Strong Branching, which is computationally intensive and time- consuming. From our experiments, collecting 100k expert samples for four combinatorial opti- mization problems (Easy level) evaluated in (Gasse et al., 2019), namely the Set Covering Problem BALAS 1980). Combinatorial Auction Problem (Leyton-Brown et al. 2000), Capacitated Facility Location Problem (Cornuejols et al., 199I), and Maximum Independent Set Problem (Cire & Au- gusto 2015), took a substantial amount of time: 26.65 hours, 12.48 hours, 84.79 hours, and 53.45 hours, respectively. These results underscore the considerable effort and resources required for col- lecting a sufficient number of expert policy samples even on the Easy level instances. Importantly, as the complexity of MILPs scales up. the challenge of collecting an adequate number of samples for imitation learning within reasonable timeframe becomes increasingly impractical.
To address this issue, we present novel framework named Contrastive Learning with Augmented MILPs for Branching (CAMBranch). Our approach begins with the development of data aug- mentation technique for MILPs. This technique generates a set of Augmented MILPs (AMILPs) through variable shifting, wherein random shifts applied to each variable within MILP to pro- duce a new instance. This augmentation strategy enables the acquisition of a substantial number of labeled expert samples, even when expert data is limited. It eliminattes the need for extensive compu- tational efforts associated with solving numerous MILP instances, thereby mitigating the challenges related expert strategy sample collection. Next, building upon the work of Gasse al. (2019), we transform& MILP into a bipartite graph. By providing theoretical foundations and proots, we establish clear correspondence between an augmented bipartite graph (derived from an AMILP) and its corresponding original bipartite graph. These bipartite graph representations are then fed into Graph Convolutional Neural Networks (GCNNs) to extract essential features and make branching decisions. Finally, we employ contrastive learning between MILPs and corresponding AMILPs to facilitate policy network imitation learning. This choice is motivated by the fact that MILPs and their AMILP counterparts share identical branching decisions, enabling seamless integration of this learning approach. We evaluate our approach on four classical NP-hard combinatorial optimiza- tion problems, following the experimental setup described in Gasse al. (2019). The experimental results demonstrate the superior performance of our proposed CAMBranch, even if CAMBranch leverages only 10% of the data used in Gasse al. 2019).
PRELIMINARIES
2.1
MIXED INTEGER LINEAR PROGRAMMING (MILP)
The general definition form of a MILP problem instance MILP = (c, A, 4,,,4, is shown below
< min cFxxx x s.t. Ax < b, L< x u. xj E Z, Vj II
(1)
where A Rmxx is the constraint coefficient matrix in the constraint, E RD is the objective function coefficient vector, b E Rm represents the constraint right-hand side vector, while 1 E (R U [- and (IR U { (+00))" represent the lower and upper bound vectors for each variable, respectively. The set I is an integer set containing the indices of all integer variables.
In the realm of solving MILPs, the B&B algorithm serves the cornerstone of contemporary op- timization solvers. Within the framework of the B&B algorithm, the process involves branching, which entails a systematic division of the feasible solution space into progressively smaller subsets. Simultaneouslly. bounding occurs, which aims to establish either lower-bound or upper- bound tar- gets for solutions within these subsets. Lower bounds are calculated through linear programming (L.P) relaxations, while upper bounds are derived from feasible solutions to MILPs.
2.2 MILP BIPARTITE GRAPH ENCODING
Following Gasse et al. 2019), we model the MILP corresponding to each node in the B&B tree with bipartite graph, denoted by (G, C, E, V), where: (1) G represents the structure of the bipartite
2

---

Published as a conference paper at ICLR 2024
Table 1: An overview of the features for constraints, edges, and variables in the bipartite graph
(g. C, V) following Gasse et al. (2019).
Type
Feature
Description
obj_cos_sim
Cosine similarity between constraint cnefficients and objective function coefficients.
C
bius
Normalized right deviation term using constraint coefficients.
tight
Indicator of tightness the lincar programming (LP) solution.
dualsol_val
Normalized value of the dual solution.
age
age, which refers to number solver iterations performed on relaxation problem without finding integer solution.
E coef
Normalized constraint cnefficient for each constraint.
type
One-hot encoding representing type (binary variables, integer variables, implicit inte- ger variahles, and continuous variables).
coef
Nornalized objective function coefficients.
has /uub
Indicator for the lower/upper bound.
sol iss.... as.at.lb
The lower/upper bound is equal the solution value.
sol. frac
Fractionality of the solution value.
sstauu
The state of variables in the simplex base is encoded using one-hot encodin (lower, busic, upper. zero).
reduced_cost
Normalized reduced cost.
age
Normalized LP age.
vol.
Value of the solution.
inc. val lavg inc val
Valuc/Avcrage value in the incumbent solutions.
graph, that is, if the variable exists in the constraint j, then an edge (i. E E is connected between node and within the bipartite graph. & represents the set of edges within the bipartite graph. (2) C glC|xd stands for the features of the constraint nodes, with CC denoting the number of constraint nodes, and di representing the dimension of their features. (3) V giV[xd2 refers to the features of the variable nodes, with |V as the count of variable nodes, and d2 as the dimension of their features. (4) E E R|C| Vixds represents the features of the edges, with d3 denoting the dimension of edge features. Details regarding these features can be found in Table
Next, the input s, = (g. C, V) is then fed into GCNN which includes a bipartite graph convolu- tional layer. The bipartite graph convolution process involves information propagation from variable nodes to constraint nodes, and the constraint node features are updated by combining with variable node features. Similarly, the variable node updates its features by combining with constraint node features. For Vi E C,j E V, the process of message passing can be represented as
(L,))E
(K.))EE
ci =
Σ Bc(ci, e(g)
V'J = fy Vj. Σ gv(c, V..
(2)
where fc, fy, Bc. and gy are Multi-Layer Perceptron (MLP) (Orbach 1962) models with two activation layers that use the ReLU function (Agarap) 2018). After performing message passing Gilmer et al., 2017). a bipartite graph with the same topology is obtained, where the fcature val- ues of variable nodes and constraint nodes have been updated. Subsequently, an MLP layer used to score the variable nodes, and masked softmax operation is applied to obtain the probability distribution of each variable being selected. The process mentioned above can be expressed as P softmax (MMiiaaaxMM((()))) Here, P is the probability distribution of the output variables. During the training phase, GCNN learns to imitate the Strong Branching strategy. Upon completion of the training process, the model becomes ready for solving MILPs.
METHODOLOOGY
As previously mentioned, acquiring Strong Branching expert samples for imitation learning poses non-trivial challenge. In this section, we introduce CAMBranch, a novel approach designed to ad- dress this issue. Our first step involves the generation of Augmented MILPS (AMILPs) labeled with
3

---

Published as a conference paper at ICLR 2024
Strong Branching decisions, derived directly from the original MILPs. This augmentation process equips us with multiple expert samples essential for imitation learning, even when confronted with limited expert data. Subsequently, building upon the AMILPs, proceed to create their augmented bipartite graphs. Finally, since MILPs and corresponding AMILPs share branching decisions, we view them positive pairs. Leveraging the power of contrastive learning, train our model to boost performance.
3.1 AUGMENTED MIXED INTEGER LINEAR PROGRAMMING (AMILP)
To obtain AMILPs, we adopt variable shift from x defined in Eq. [ to á using a shift vector 8, denoted as & + where is shift vector. Note that if E 2, then s; ž; otherwise 8; E R. Based on this translation, we can derive a MILP from Eq Lq. To bring this model into standard form, we redefine the parameters as follows: b = As + b, i + 8, and u u Consequently, the final expression for the AMILP model is represented
min c ④ cTs s.t. At < b, iisssse E2 E VJEI d
(3)
Through this data augmentation technique, single MILP has the capacity to generate multiple AMILPs, It's worth noting that each MILP, along with its corresponding AMILPs, share identical variable selection decisions of the Strong Branching. We next present theorem to demonstrate this characteristic. To illustrate this distinctive characteristic, we begin by introducing lemma that elucidates the relationship between MILPs and AMILPs.
Lemma 3.1. For MILPs Eq. and their corresponding AMILPs 3). let the optimal solutions of the LP relaxation be denoted as x² and 5², respectively. direct correspondence exists between these solutions, demonstrating that x" = +
The proof of this lemma is provided in the Appendix. Building upon this lemma, we can initially establish the relationship between the optimal values of a MILP and its corresponding AMILP, denoted as c² x= = c² .t - c² 8. This equation signifies the equivalence their optimal values. With the above information in mind, we proceed to introduce the following theorem.
Theorem 3.1. Suppose that an AMILP instance is derived by shifting variables from its original MILP. When employing Strong Branching to solve these instances, it becomes evident that both the MILP and AMILP consistently produce identical variable selection decisions at each branching step within B&B.
Proof. In the context of solving a MILP M using Strong Branching, the process involves pre- branching all candidate variables at each branching step, resulting in sub-MILPs. Solving the linear programing (LP) relaxations of these sub-MILPs provides the optimal values, which act as potential lower bounds for M. The Strong Branching strategy chooses the candidate variable that offers the most substantial lower bound improvement as the branching variable for that step. Thus, the goal of this proof demonstrate that the lower bound increments after each branching step are equal when applying Strong Branching to solve both a MILP and its corresponding AMILP.
Given MILP's branching variable x; and its corresponding shifted variable of AMILP à = x;; + St. we perform branching operations on both variables. Firstly, we branch on I; to produce two subproblems for MILP, which are formulated as follows:
arg min {cT Tx Ax b,
x u,
&
[
E EZ EZ]
(4)
arg min {c x Ax
b, < x
u
x | 2 E Vj E I
(5)
where æi represents the value of variable x; in the optimal solution corresponding to the MILP LP relaxation. Likewise, we branch on the shifted variable ã., which generates two sub-problems for AMILP, as represented by the following mathematical expressions:
arg min(cc - ct s|A < b.i < a $ a. | EZ
(6)
arg mig [ cT Tl < <bi a a.aaa.
a. 13 eZ,jj
(7)
4

---

Published as a conference paper at ICLR 2024
where zt," represents the value of variable f; in the optimal solution corresponding to the AMILP LP relaxation.
According to Lemma 3.1 the LP relaxations of Eq.44) and 6) have optimal solutions that can be obtained through variable shifting and these two LP relaxations have equivalent optimal values. Similarly, the optimal values of the LP relaxations of Eq. ( and Eq.() are also equal. Thus, for it; and 2i, the lower bound improvements of the subproblems generated from MILP Eq.(T) and AMILP Eq. equivalent, demonstrating identical branching decisions. The proof is completed.
Based on Theorem 3.1 it is evident that the generated AMILPs are equipped with expert decision labels, making them readily suitable for imitation learning.
3.2 AUGMENTED BIPARTITE GRAPH
After obtaining the AMILP, the subsequent task involves constructing the augmented bipartite graph using modeling approach akin to the one introduced by Gasse et al. (201)). To achieve this, we leverage the above relationship between MILP and AMILP to derive the node features for the augmented bipartite graph from the corresponding node features of the original bipartite graph, as outlined in Table [ For a detailed overview the relationships between node features in the augmented and original bipartite graphs, please refer the Appendix.
3.2. CONSTRAINT NODE FEATURES
is worth noting that the AMILP derived from a tramslation transformation of the MILP, result- ing in certain invariant features: (1) cosine similarity between constraint coefficients and objective function coefficients; (2) tightness state of the LP relaxation solution within constraints; (3) LP age. Additionally, for the biay feature, representing the right-hand term, the transformed feature is b, + a, s. To obtain this term, consider the i-th constraint node, which corresponds to the i-th constraint of a. x < b, After translation, this constraint can be represented as a, & b; + a, leading to the bias feature b; + a? s. For dualsol val feature, we consider proposing the following theorem for the explanation.
Theorem 3.2. For MILPs Eq.(7) and AMILPs Bj let the optimal solution of the dual problem of the LP relaxations be denoted as y" and ÿ", respectively. Then, a direct correspondence exists between these solutions, indicating that y² =
The proof can be found in the Appendix. From Theorem 3.2
conclude that the dualsol _val feature of the augmented bipartite graph remains unchanged compared to the original bipartite graph. Thus, have successfully determined the constraint node features for the AMILP's bipartite graph through the preceding analysis.
3.2.2 EDGE FEATURES
Given that an AMILP generated from the original MIP through variable shifting, the coefficients of the constraints remain invariant throughout this transformation. Consequently, the values of the edge features the bipartite graph, which directly reflect the coefficients connecting variable nodes and constraint nodes, also remain unchanged.
3.2.3 VARIABLE NODE FEATURES
Similarly to constraint node features, several variable node features also remain unaltered during the transformation. These include (1) the variable type (i.e., integer or continuous); (2) the coefficients of variables corresponding to the objective function; (3) whether the variable has upper and lower bounds; (4) whether the solution value of a variable is within the bounds; (5) whether the solution value of a variable has a decimal part; (6) the status of the corresponding basic vector; (7) the age. For reduced.com features, we consider the following theorem for clarification.
Theorem 3.3. For MILPs Eq and their corresponding AMILPs E) consider the reduced cost corresponding to LP relaxations for a MILP, denoted as o,, and for an AMILP, denoted as o; Then, direct correspondence exists between these reduced costs, implying that a; δ:.
5

---

Published as a conference paper at ICLR 2024
The proof is provided in the Appendix. Moreover, the features sol_val, inc_val, and avg avg-inc-val all exhibit shifts in their values corresponding to the shift vector s. With all the above, we have successfully acquired all the features of the augmented bipartite graph.
3.3
CONTRASTIVE LEARNING
Contrastive learning has been widely adopted in various domains (He et al. 2020 Chen et al. 2020a
P. et al. 2020 Xu al., 2022 [ter et al. 2020 Giorgi et al. 2021 Yu al. 2022 The fundamen- tal idea behind contrastive learning is to pull similar data points (positives) closer together in the feature space while pushing dissimilar ones (negatives) apart. Within our proposed CAMBranch, we leverage this principle by viewing MILP and its corresponding AMILP as positive pairs while considering the MILP and other AMILPs within the same batch as negative pairs. This enables us to harness the power of contrastive learning to enhance our training process.
We initiate the process with MILP bipartite graph (Gor Cari E Von and its augmented coun- terpart (Gmgg Cang Emng V augg ). These graphs undergo processing with a GCNN, following the message passing illustrated in Eq. This results updated constraint and variable node features Con and V oni for the MILP, along with C.ang and V for the AMILP. Subsequently, we generate graph-level representations for both bipartite graphs. To achieve this, we conduct max and average pooling the constraint nodes and variable nodes, respectively. Merging these embeddings using an MLP yields pooled embeddings for constraint and variable nodes, denoted as ci o for the MILP and eg _ for the AMILP. These embeddings serve as inputs another MIP, resulting in graph-level embeddings Juri and Jaug for MILP and AMILP bipartite graphs, respectively. To train our model using contrastive learning, we treat gori and its corresponding Jaug as positive pairs, while considering other AMILPs in the same batch as negative samples. By applying infoNCE (van den Oord et 2018 loss, we have
Thanh
exp Mori (i) gang (i)
(iffNNC))
Σ log
(8)
exp (g (1) gang (i))
where Thatch represents the number samples training batch. gon and Jaug denote the nor- malized vectors of Joni and Joug. respectively. This contrastive learning approach enhances our model's ability to capture representations for MILPs, which further benefits the imitation learning process. The imitation learning process follows Gasse al. (2019). More details can be found in the Appendix
4 EXPERIMENT
We evaluate our proposed CAMBranch by fully following the settings in Gasse et al. (2019). Due to the space limit, we briefly introduce the experimental setup and results. More details are provided in the Appendix D
4.1 SETUP
Benchmarks. Following Gasse et al. (2019), we assess our method on four NP-hard problems, i.c.. Set Covering (BALAS 1980), Combinatorial Auction (Leyton- Brown al. 2000), Capacitated Fa- cility Location (Cornuejols et al. 1991), and Maximum Independent Set (Cire & Augusto 2015), Each problem has three levels of difficulty, that is, Easy, Medium, and Hard. We train and test mod- els on each benchmark separately. Through the experiments, we leverage SCIP 6.0.1 (Gleixner et al., 2018) as the backend solver and set the time limit as hour. See more details the supplementary materials.
Baselines. We compare CAMBranch with the following branching strategies: (1) Reliability Pseu- docost Branching (RPB) (Achtebeegg et al. 22055). state-of-the-art human -emaandesiined branching pol- icy and the default branching rule of the SCIP solver; (2) GCNN (Gasse et al. 2019), a state-of-the- art neural branching policy; (3) GCNN (10%), which uses only 10% of the training data from Gasse et al. (2019). This is done to ensure a complete comparison since CAMBranch also utilizes 10% of the data.
Data Collection and Split. The expert samples for imitation learning are collected from SCIP rollout with Strong Branching on the Easy level instances. Following Gasse al. 2019), we train

---

Published as a conference paper at ICLR 2024
GCNN with 100k expert samples, while CAMBranch is trained with 10% of these samples. Trained with Easy level samples, the models are tested on all three level instances. Each level contains 20 new instances for evaluation using five different seeds, resulting in 100 solving attempts for each difficulty level.
Metrics.
Following Gasse et al. (2019), our metries are standard for MILP benchmarking, including solving time, number nodes in the branch and bound search tree, and number of times each method achieves the best solving time among all methods (number of wins). For the first two metrics, smaller values are indicative of better performance, while for the latter, higher values are preferable.
4.2 EXPERIMENTAL RESULTS
To assess the effectiveness of our proposed CAMBranch, we conducted the evaluation from two aspects: imitation learning accuracy and MILP instance-solving performance. The former measures the model's ability to imitate the expert strategy, i.e., the Strong Branching strategy. Meanwhile, MILP instance-solving performance evaluates the quality and efficiency of the policy network's decisions, emphasizing critical metrics such as MILP solving time and the size of the B&B tree (i.c., the number of nodes) generated during the solving process.
4.2.1
IMITATION LEARNING ACCURACY
First, initiated our evaluation by comparing CAMBranch with baseline methods in terms of imitation learning accuracy. Following Gasse et al. (011), we curated a test set comprising 20k expert samples for each problem. The results are depicted in Figure Notably, CA.MBranch, trained with 10% of the full training data, outperforms GCNN (10%), ), demonstrating that our proposed data augmentation and contrastive learning framework benefit the imitation learning process. Moreover, CAMBranch's performance, while exhibiting a slight lag compared to GCNN (Gasse et al., (019) trained on the entire dataset, aligns with expectations, considering the substantial difference in the size of the training data. CAMBranch delivers comparable performance across three of the four problems, with the exception being the Set Covering problem.
4.2.2 INSTANCE SOLVING EVALUATION
Next, we sought to evaluate our proposed CAMBranch on MILP instance solving focusing on three key metrics: solving time, the number of B&B nodes, and the number of wins, as illustrated by T
GCNN
0.80
GCNN (10%)
0.75
CAMBranch (10%)
Solving time reflects the efficiency of each model in solving MILP instances. As evident in Table we observed that as problem com- plexity increases, the solving time also rises substantially, with an obvious gap between Easy and Hard levels. In the Easy level, all strategies exhibit similar solving time, with only maximum gap of about seconds. However, for the Medium and Hard levels, differ- ences become more significant. Notably, delving into each strategy, we found that, neural network-based policies consistently outper- form the traditional RPB, demonstrating the potential of replacing heuristic methods with machine learning-basee approaches. More- over, CAMBranch exhibits the fastest solving process most cases, particularly in challenging instances. For example, in the hard- level Capacitated Facility Location problem, CAMBranch achieved a solving time of 470.83 seconds, nearly 200 seconds faster than GCNN. Furthermore, CAMBranch outperforms GCNN (10%) across various instances, reaffirming the effectiveness of our CAMBranch framework.
Actumez
0.70
0.65
0.60
0.55
0.50
Set Goveni
Combrualbdal
Aurtion
Familly Location
Maxiram Indespendennt Set
Figure 1: Imitation learning accuracy on the test sets of ex- pert samples.
The number of B&B nodes serves as a measure of branching decision quality, with fewer nodes indicating better decision quality. Table 2 presents similar observations to solving time. CAM- Branch consistently outperforms GCNN in most cases, especially in challenging scenarios like the hard-level Maximum Independent Set problem. On average, CAMBranch generates fewer nodes than GCNN (10%), highlighting the efficacy of our data augmentation and contrastive learning net- work. However, it's worth noting that in some cases, RPB generates the fewest nodes, particularly in
7

---

Published as a conference paper at ICLR 2024
the Capacitated Facility Location problem. Nevertheless, this doesn't 'eesn't translate into shorter solving times, as certain RPB decisions are mine-consuming.
The number of wins quantifies the instances in which the model achieves the shortest solving time. Higher win counts indicate better performance. With this metric, we examined models at the in- stance level. From Table found that GCNN obtains the most times of getting the fastest solving process in the Set Covering problem and the Combinatorial Auction problem (Easy and Medium). However, for the remaining problems, CAMBranch leads in this metrie. Additionally, CAMBranch tends to optimally solve the highest number of instances, except in the case of Set Covering. These results underline the promise of our proposed method, especially in scenarios with limited training data. Collectively, CAMBranch's 's prominent performance across these three metrics underscores the importance of MILP augmentation and the effectiveness of our contrastive learning framework.
Policy evaluation terms of solving time, number of B&B nodes, and number of wins number of solved instances four combinatorial optimization problems. Each level contains 20 instances for evaluation using five different seeds, resulting in 100 solving attempts for each difficulty level. Bold CAMBranch numbers denote column- best results among neural policies.
Table 2:
Easy Wins
Medium Wins
Hard
Model
Time
Nodes
Time
Nodes
Time
Wins
Nodes
FSB
17.98
0/100
27
345.91
0/90
223
3600.00
RPR
7.82
4/100)
103
64.77
10/100
2587
1210.18
32 63
80599
GCNN
6.03
57/100
167
50.11
81/100
1999
1344.59
36/68
56252
GCNN (10%)
6.34
39/100
230
98.20
5/96
5062
2385.23
0/6
113344
CAMBranch (10%)
6.79
0/100
188
61.00
4/100
2339
1427.02
0/55
66943
Set Covering
FSB
4.71
0/100
10
97.6
0/100
90
1396.62
0/64
381
RPB
2.61
1/100
21
19.68
2/100
713
142.52
29/100
8971
GCNN
1.96
43/100
87
11.30
74/100
695
158.81
19/94
12089
GCNN (10%)
1.99
44/100
102
12.38
16/100
787
144.40
10/100
10031
CAMBranch (10%)
2.03
12/100
91
12.68
8/100
758
131.79
42/100
9074
Combinatorial Auction
FSR
34.94
0//(0)
54
242.51
0/100
114
995.40
0/82
84
RPB
30.63
9/100
79
177.25
2/100
196
830.90
2/93
178
GCNN
24.72
25/100
169
145.17
13/100
405
680.78
5/95
449
GCNN (10%)
26.30
15/100
180
124.49
48/100
406
672.88
11/95
423
CAMBranch (10%)
24.91
50/100
183
124.36
37/100
390
470.83
77/95
428
Capacitated Facility Location
28.85
10/100
19
1219.15
0/62
3600.00
RPB
10.73
11/100
78
133.30
5/100
2917
965.67
10/40
17019
GCNN
7.17
11/100
90
164.51
4/99
1020.58
21925
GCNN (10%)
7.18
26/100
103
122.65
8/89
3711
695.96
17034
CAMBranch (10%)
6.92
42/100
90
61.51
83/100
1479
496.86
33/40
10828
Maximum Independent Set
4.2.3 EVALUATION DATA COLLECTION EFFICIENCY
In this part, we compared the efficiency of expert sample collection for GCNN Gasse et al. (2019) and our proposed CAMBBranch. We focused on the Capacitated Facility Location Problem, which exhibits the lowest collection efficiency among the four MILP benchmarks and thus closely sim- ulates real-world MILPs by low data collection efficiency. Generating 100k expert samples using Strong Branching to solve the instances takes 84.79 hours. In contrast, if obtaining the same quan- tity of expert samples, CAMBranch requires 8.48 hours (collecting 10k samples initially) plus 0.28 hours (generating the remaining 90k samples based on the initial 10k), totaling 8.76 hours- an 89.67% time savings. This underscores the superiority of CAMBranch in data collection efficiency.
8

---

Published as a conference paper at ICLR 2024
CAMBranch w/o CL
CAMBranch
100
0.88
60
1.5k
200
60k
& Saleed
0.62
0.84
Time (3)
4-
40
1K
Nodes
150
100
2k
40k
40
60
0.58
0.80
20
500
20k
0.56
0.54
Easy
Medium
Hard
Easy
Medium
0
Hard
0
0.52
0.50
Easy
Marium
Herd
(b)
c
(d)
Figure 2: Ablation experiment results on CAMBranch (10%) for instance sol solving evaluation, includ-
ing solving time (a), number of nodes (b), and number of wins (c), addition imitation learning accuracy (d) for the Set Covering problem.
4.3 ABLATION STUDIES
To further validate the effectiveness of contrastive learning, we conducted ablation studies. Specifi- cally, we compared the performance of CAMBranch with contrastive learning to CAMBranch with- out contrastive learning but with data augmentation, denoted as CAMBranch w/o CL. These exper- iments were conducted on the Set Cover problem, and the results are displayed in Figure 2 It is evident from the results that integrating contrastive learning significantly enhances CAMBranch's performance, providing compelling evidence the efficacy this integration within CAMBranch.
4.4 EVALUATING CAMBRANCH ON FULL DATASETS
Previous experiments have showcased CAMBranch's superiority in data-scarce scenarios. To fur- ther explore CAMBranch's potential, we conducted evaluations on complete datasets to assess its performance with the entire training data. Table presents the results of instance-solving evalua- tions for the Combinatorial Auction problem. The outcomes reveal that when trained with the full dataset, CAMBranch (100%) surpasses GCNN (10%), CAMBranch (10%) and even GCNN (100%). Notably, CAMBranch exhibits the fastest solving time for nearly 90% of instances, underscoring its effectiveness. For Hard instances, CAMBranch (100%) demonstrates significant improvements across all instance-solving evaluation metrics. These findings affirm that our plug-and-play CAM- Branch is versatile, excelling not only in data-limited scenarios but also serving as a valuable tool for data augmentation to enhance performance with complete datasets.
Table 3: The results of evaluating the instance-solving performance for the Combinatorial Auction problem by utilizing the complete training dataset. Bold numbers denote the best results.
Easy
Medium
Hard
Model
Time
Wins
Nodes
Time
Wins
Nodes
Time
Wins
Nodes
GCNN (10%)
1.99
2/100
102
12.38
3/100
787
144.40
2/100
10031
GCNN (100%)
1.96
4/100
87
11.30
7/100
695
158.81
4/94
12089
CAMBranch (10%)
2.03
1/100
91
12.68
2/100
758
131.79
11/100
9074
CAMBranch (100%)
1.73
93/100
88
10.04
88/100
690
109.96
83/100
8260
CONCLUSION
In this paper. we have introduced CAMBranch, a novel framework designed to address the chal- lenge of collecting expert strategy samples for imitation learning when applying machine learning techniques to solve MILPs. By introducing variable shifting, CAMBraanh generates AMILPS from the original MILPs, harnessing the collective power both to enhance imitation learning. Our uti- lization of contrastive learning enhances the model's capability to capture MILP features, resulting in more effective branching decisions. We have evaluated our method on four representative combi- natorial optimization problems and observed that CAMBranch exhibits superior performance, when trained on only 10% of the complete dataset. This underscores the potential of CAMBranch, especially in scenarios with limited training data.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENT
This work supported by National Key R&D Program of China (Grant No.2021
REFERENCES
Tobias Achterberg, Thorsten Koch, and Alexander Martin. Branching rules revisited. Oper. Res. Lett. 33(1):22-54, 2005, doi: 10. 10.1016/f.011.20444444 2000004.00.. URL https://doi.or//11
1016/1 (erff.or..20000 2004. . 04. 002
Abien Fred Agarap. Deep learning using rectified linear units (relu). CoRR, abss/803.08335,220 2018. abs/ abs/ 08375
URL http:://axxxv..o//
Renato T. R. Almeida, Luiz C. de Calmon, Elias Olivieira, and Marcelo Eduardo Vieira Segatto.
Design of virtual topologies for large optical networks through efficient MILP formulation. doi: 00.10166..sn.2205.100. org/10. 005/100.0166..1. osn 2005. 10.002
Opt. Switch. Netw. 3(1):2-10 2006.
URL https://doi.
Alejandro Marcos Alvarez, Quentin Louveaux, and Louis Wehenkel. A machine learning- approximation of strong branching. INFORMS J. Comput., 29(1):185-195 195, 2017. doi: 10.1287/
ijoc.2016.0723.
2016.022222
David Applegate, Robert Bixby, Vašek Chvátal, and William Cook. Finding cuts in the TSP (A preliminary report), volume 95. Citeseer, 1995.
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saun- shi. A theoretical analysis of contrastive unsupervised representation learning. arXiv preprint arXiv: (00::992..0222 2019.
BALAS. Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study. Mathematical Programming Study, 12:37-60, 1980.
Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning branch. In Jennifer G. Dy and Andreas Krause (eds.). Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 353-362. PMLR, 2018. URL ottp://prrcceedings mww..ng.mm.....mmmmmmmm...m.mmmm wttpa//p/eeee////eeeeeeeeo.
html
Tianpeng Bao and Huangang Wang. Cyclic scheduling of multi-cluster tools based on mixed integer programming. IEEE Transactions on Semiconductor Manufacturing, 30(4):515 (055):555-525,00 2017.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimiza- tion: A methodological tour d'horizon. Eur. J. Oper. Res., 290(2))405-421, 2021. doi: 10.1016/j. ejor. ,063. URL httth:tts: /ttp::////ooieee wtt..r//...11/...jo.rr....
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. In Hugo Larochelle, Mare Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin (eds.). Advances in Neural Information Processing Systems 33: Annual Con- ference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. htRL:htss:// http::::::ppppocceeesssssssseeee neurissssngn.ssnns............. cc htte/apper//ee Dpaper/2000/hass 700ebb2b69F Se0238ff411 -fst html
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey E. Hinton. A simple framework for contrastive learning of visual representations. Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of ngs.
Machine Learning Research, pp. 1597-1607. PMLR, 2020a. URL http:://prpcseeeeee v 1etp/1999//0 chen220 html
ml p.p.prss/vll..
Ting Chen, Simon Komblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E. Hin- ton. Big self-supervised models are strong semi-supervised learners. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien
10

---

Published as a conference paper at ICLR 2024
Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12. 2020, virtual, 2020b. URL http:s/s/procceedig...eeeeeeteee
Fcbc95ccdd55 da 81 207c0c1 400c655 attteooottttcccsbbaataaatt.ttt. wwtppppe//ce////eeeeepppp 20sh//ah////h//////
Xinlei Chen and Kaiming He. Exploring simple siamese representation learning- In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2021, vir- mual, June 19-25. 2021, pp. 15750-15758, Computer Vision Foundation / IEEE, 2021. doi: 10.1099/CVPR44463322222000144
URL Exploring Sargg__imlleeee_ee Siamese
thecvf. . wwm wttp:///ooteee/////////////a////
Representation Lawioon___aainnn
CVPR Bttpang______________22_
html.
Xinlei Chen, Haoqi Fan, Ross B. Girshick, and Kaiming He. Improved baselines with momen-
tum contrastive learning. CoRR, abs/2003.04297, 2020c. URL
2003. 04297
Cire and Andre Augusto. Decision diagrams for optimization. Constraints, 20(4):494 495, 2015.
G. Comuejols, R. Sridharan, and J. M. Thizy. comparison of heuristics and relaxations for the capacitated plant location problem. European Journal of Operational Research, 50(3):280-297, 1991.
Santanu Dey, Yatharth Dubey, Marco Molinaro, and Prachi Shah. theoretical and computational analysis of full strong- branngbbanching... Mathematical Programming, pp. 1-34, 2023.
William Falcon and Kyunghyun Cho. A framework for contrastive self-supervised learning and designing A new approach. CoRR, abs/2009.00104,, 2020. 2020. httphttsss///xxiv.ooo abs/
20099. 00104
Hongchao Fang and Pengtao Xic. CERT: contrastive self-supervised learning for language under- standing. CoRR, Abs/2005,12276. 2020, htt.attpss//xxx..ooooo///// 1wt.000..1.66666
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric.
CoRR, abs/1 0044990 2019. URI.
02428
Gerald Gamrath, Timo Berthold, and Domenico Salvagnin. An exploratory computational anal- ysis of dual degeneracy in mixed-integer programming. EURO J. Comput. Optim.. 8(3); 241-261, 2020. doi: 10.100774116655-0000000333 s 613675-020-0011
URL bttps://aci.org//1
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- tion Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, www.ggs...er..p..... www.eeeww......ppe...ee cctppppepppp///////////////// pp. 15554 15566. 2019. URL (tt.590f33..33bbb-bbtttaa html ftssh//14c2267d844
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Doina Precup and Yee Whye Teh (eds.). Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 1263-1272. PMLR, 2017. URL httt:://proceedii/i
mlr. wwwps//e//ssppppeepppppp http//iiieerrrrrmmm 1tt.er11....llll....mmmm.
John M. Giorgi, Osvald Nitski, Bo Wang, and Gary D. Bader. Declutr: Deep contrastive learn- ing for unsupervised textual representations. In Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli (eds.), Proceedings of the 59th Annual Meeting of the Association for Com- putational Linguistics and the 11th International Joint Conference on Natural Language Pro- cessing, ACL/JCNLP 2021. (Volume 1: Long Papers), Virtual Event, August 1-6, 2021. pp. 879- 895. Association for Computational Linguistics, 2021. doi: 10. 10.18653/v1/20 1/2021 acl- long. 72. URL https:://of..rg/// http:/100.6653//11/1/ http:////ooooooo....../////////2 acl moce-llogg.77 ong.72 72

---

Published as a conference paper at ICLR 2024
Ambros Gleixner, Michael Bastubbe, Leon Eifler, Tristan Gally, Gerald Gamrath, Robert Lion Gottwald, Gregor Hendel, Christopher Hojuy, Thorsten Koch, Marco E. Lübbecke, Stephen J. Maher, Matthias Miltenberger, Benjamin Müller, Mare E. Pfetsch, Christian Puchert, Daniel Rehfeldt, Franziska Schlösser, Christoph Schubert, Felipe Serrano, Yuji Shinano, Jan Mer- lin Viernickel, Matthias Walter, Fabian Wegscheider, Jonas T. Witt, and Jakob Witzig. The SCIP Optimization Suite 6.0. Technical report, Optimization Online, July 2018. URL hhht:: html
// www. owt matiiiizaiion online wwgg DBB
Alexis Godart, Hervé Manier, Christelle Bloch, and Marie-Ange Manier. Milp for a variant of pickup & delivery problem for both passengers and goods transportation. In 2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pp. 2692-2698, IEEE, 2018.
Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H. Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Ávila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, Bilal Piot, Koray Kavukcuoglu, Rémi Munos, and Michal Valko. Bootstrap your own latent- A new approach to self-supervised learning. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Had- sell, Staria-Florina Balcan, and Hsuan- Tien Lin (eds.), Advances in Neural Information Process- ing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 2020, virtual, 2020. URL (ttphttss:: http:::ess///pccceeeeec.so
paper/2020/1 haaz////hh////// F3ada 701 42b 7631 922.89922999559 921199222559e-tttte2e 2at.aae6000044211111116666666660 neurips...............
html
Prateek Gupta, Maxime Gasse, Elias B. Khalil, Pawan Kumar Mudigonda, Andrea Lodi, and Yoshua Bengio. Hybrid models for learning to branch. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL hettps://proceeddnng: neurip........... cc pccpaperr/222/naatt Abst Abbrtaa html
Alain Hait and Christian Artigues. A hybrid cp/milp method for scheduling with energy costs. European Journal of Industrial Engineering, 5(4):471-489, 2011.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross B. Girshick. Momentum contrast for unsupervised visual representation learning. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020, pp. 9726- URL
9735. Computer Vision Foundation IEEE, 2020. doi: 10. 1009/CVP42200.200000000 https: http:::/ddoooooooo// /ttp:///da....o......1////////// 1ww.9/1/9/22200000 2020.00200000
Dan Iter, Kelvin Guu, Larry Lansing, and Dan Jurafsky. Pretraining with contrastive sentence objectives improves discourse performance of language models. In Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel R. Tetreault (eds.), Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL 2020, Online. July 5-10, 2020, pp. 4859-4870. Association for Computational Linguistics, 2020. doi: 10.18653/v1/20200
www.:aanl.mmmmm..mmmmmmm main.439. URL
/ww. /atrg//..18653/////
acl wacc-mmain... main.4... 439
Elias B. Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning com- binatorial optimization algorithms over graphs. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference ral Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 6348 6658, 2017. URL http:: htttt:::://proceedings.s. neur ips.ripp... www.eerripp....paae///////// pttpp/ppppp//1//aaat/t Abst .hmll
Neu-
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 on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA, pp. 724-731. AAAI Press, 2016. doi: 10.1609/aaii.veo. 1.t... URL
/ttps://doi.orge
1609/ aaai. 113001110080
Fatma Kiling-Karzan, George L. Nemhauser, and Martin W. P. Savelsbergh. information-basee branching schemes for binary linear mixed integer problems. Math. Program. Comput., (44):
12

---

Published as a conference paper at ICLR 2024
249-293, 2009. doi: 10.1000/112532-099000099 URL https:://ec..or//10..1 512532-009-0009-1
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 htth:
/larxiv.org/eae abs /taabs/1440 /112. 6980
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL https:: //openreview. net http://oommmmdddde/ee
AH Land and AG Doig, An automatic method of solving discrete programming problems. Econo- metrica, 28(3)497-5520, 1960.
Kevin Leyton-Brown, Mark Pearson, and Yoav Shoham. Towards universal test suite for com- binatorial auction algorithms. In Anant Jhingran, Jeff MacKie-Mason, and Doug J. Tygar (eds.), Proceedings of the 2nd ACM Conference on Electronic Commerce (EC-00), Minneapo- lis, MN, USA, October 17-20, 2000, pp. 66-76. ACM, 2000. doi: 10.1 10.1145/35281.3558799 URL https://doi. wwo.orggg/// 10. 1145/ 352871 352879
Jiacheng Lin, Jialin Zhu, Huangang Wang, and Tao Zhang. Learning to branch with tree-aware branching transformers. Knowl. Based Syst. 252: 109455, 2022. doi: 10. 101666..nosys.2022 109455. URL pnttps://doi.orre
6/ knosys. 2022. 109455
Michele Monaci Matteo Fischetti. Branching on nonchimerical fractionalities. Operations Research Letters, 159)):1,-164, 2012.
Tomás Mikolov, Ilya Sutskever, Kai Chen, Gregory S. Corrado, and Jeffrey Dean. Distributed representations of words and phrases and their compositionality. In Christopher J. C. Burges, Léon Bottou, Zoubin Ghahramani, and Kilian Q Weinberger (eds.), Advances in Neural Information Processing Systems 26: 27th Anmual Conference on Neural Information Processing Systems 2013. Proceedings of meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pp. 3111-3119, 2013. URL httpsss//pprroeeedsss.eeees//// http:///ee.ooaaaaaaaaaa/////////
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Bren- dan O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang. Ravichandra Addanki, Tharindi Hapuarachchi, Thomas Keck, James Keeling, Pushmeet Kohli, Ira Ktena, Yu- jia Li, Oriol Vinyals, and Yori Zwols. Solving mixed integer programs using neural networks. CoRR, abs/2012.13349, 2020. BtRhhtts::/ /ttp:///avvvvvviv https////axxxxx../r////.//// wttp///gg/.g/....e///// 203.
J Orbach. Principles of neurodynamics. perceptrons and the theory of brain mechanisms. Archives of General Psychiatry. 7(3):218-22) 219, 1962.
Khosla P., Teterwak P., and Wang C. Supervised contrastive learning. Advances in Neural Informa- tion Processing Systems, 33: 8168-66677177 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Z. Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library.
Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buuc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neurul Information Processing Systems 32: Annual Conference on Neural Information Pro- cessing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC. Canada, pp- 8035, 2019. URL bddca288 www.eeee222222220002022
wwtp:eee.e.pppppepeeeeeeeeeeeeee httpp//ape///////aaaaase. -bs.2:77777--btttttt.t.. html
Dean Pomerleau. Efficient training of artificial neural networks for autonomous navigation. Neural Comput., 3(1):88-1))) 97, 1991. doi: 11116///ncco.1991... URL httpt:::t////m //doi. orq/10. 10. 1991 1.1.9.......6
13

---

Published as a conference paper at ICLR 2024
Lara Scavuzzo, Feng Yang Chen, Didier Chételat, Maxime Gasse, Andrea Lodi, Neil Yorke-Smith, and Karen I. Aardal. Leamning to branch with tree mdps. In wwwps//ppere//////222/..m. hhash/
NeurIPS, 2022. URL httpt:::ppappe...et 756d74cd585 9288 -
Ahu Soylu, Cihan Oruç, Metin Turkay, Kaoru Fujita, and Tatsuyuki Asakura. Synergy analysis of collaborative supply chain management in energy systems using multi-perion milp. European Journal of Operational Research, 174(1):387-403, 2006.
Aäron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding. CoRR, abs/1 807. .0748, 2018. URL http::tttt//ttiii org. http//bs/18000 0077
Hanwen Xu, Jiacheng Lin, Addie Woicik, Zixuan Liu, Jianzhu Ma, Sheng Zhang, Hoifung Poon, Liewei Wang, and Sheng Wang. Pisces: A multi-modal data augmentation approach for drug combination synergy prediction. bioRxiv, pp. 2022-11, 2022.
Junliang Yu, Hongzhi Yin, Xin Xia, Tong Chen, Lizhen Cui, and Quoc Viet Hung Nguyen. Are graph augmentations necessary?: Simple graph contrastive learning for recommendation. En- rique Amigó, Pablo Castells, Julio Gonzalo, Ben Carterette, J. Shane Culpepper, and Gabriella Kazai (eds.), SIGIR '22: The 45th International ACM SIGIR Conference on Research and De- velopment in Information Retrieval, Madrid, Spuin, July 11 15, 2022, pp. 1294-1303, ACM, URL https: 444.0//2/44111143474444444
2022. doi: 10.1145744774555331997,
3531937
Giulia Zarpellon, Jason Jo, Andrea Lodi, and Yoshua Bengio. Parameterizing branch-and-bound search trees to learn branching policies. In Thirty-Fifth AAAI Conference on Artificial Intelligence AAAI 2021, Thirty- Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, AAAI Press, 2021. doi: 1.009/aaai.v35i0
Virtual Event, February 2-9, 2021, pp.
16512. https:/:::/// /oi. org.rr//... 0 aww.9//aaa...../..//.........../ v3515. 10651.1.112..... 6512
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. Neurocomputiing 519: 205-217, 2023, doi: 10. 10011/6..eccmm.222....0000 URL https: //t/i..or//1..10066
j n.neucom, 2022. 11. 1224
14

---

Published as a conference paper at ICLR 2024
Contents
Background
16
A.1
Branch and Bound (B&B)
16
Strong Branching
16
Proofs
16
Methodology Details
17
Overview Bipartite Graph Node Features
17
Contrastive Learning
18
Imitation Learning Training Procedure
19
D Experiment Details
19
D.I Experimental Settings
19
D.1.1 Data Collection and Split
19
D.1.2 Solver Configuration
19
D.1.3 Training Parameters
19
D.I.4
Metrics
20
D.2
Additional Results
20
D.2.1
Analysis Impact of Training Sample Ratios
20
D.2.2 Analysis of Training Overhead
21
Discussion
When to Use CAMBranch?
21
Relationship between Imitation Learning and Instance Evaluation
22
Related Work
23
MILP Formulation
23
15

---

Published as a conference paper at ICLR 2024
A BACKGROUND
A.1 BRANCH AND BOUND (B&B)
The B&B algorithm operates an iterative way at each node. commences with solving the LP relaxation of the original MILP problem Eq. { This LP relaxatio serves as lower bound estimate for the original MILP (T. the optimal solution æ" of this LP relaxation satisfies all the constraints in D. its objective value provides an upper bound estimate for the original problem. However, if x contains non-integer variables zj (where E Z), the algorithm proceeds by splitting the problem
into two sub- coab-probles,, each with additional constraints: Ij S [ and æ. 2 [a]]]
where [-] and
[.] represent the floor and ceiling functions, respectively.
Throughout this iterative process, any sub-problem that exceeds the upper bound estimate is pruned, eliminating the need for further branching. This pruning strategy significantly enhances computa- tional efficiency. The algorithm repeats the above process until either all nodes are pruned or the optimality gap reaches predetermined threshold. At this point, the global optimal solution, along with its corresponding objective value, is successfully obtained.
A.2 STRONG BRANCHING
The core idea behind the Strong Branching strategy (Applegate et al. 1995 is to identify the can- didate variable that, when chosen for branching, provides the maximum improvement in the lower bound of the problem. Specifically, this strategy involves pre-branching all candidate variables, solv- ing their respective Linear Programming (LP) relaxation problems, and then selecting the variable that contributes the most lower bound enhancement the actual branching variable. When pre- branching is applied to all available candidate variables, and each LP relaxation problem is solved optimality, this strategy known as Full Strong Branching (FSB), which the expert strategy for imitation learning in this paper. Essentially, Full Strong Branching can be seen as a greedy approach aimed identifying the locally optimal variable for branching.
Full Strong Branching often leads to the smallest branching search tree. However, it comes at a considerable computational cost. Consequently, several variants of Full Strong Branching have been developed to mitigate this computational burden. These variants involve selecting only a subset of candidate variables for branching or limiting the number of iterations during the solution of each LP relaxation problem. It's important to note that while these modifications enhance computational efficiency, they do not fundamentally reduce the computational complexity inherent the Strong Branching strategy.
B PROOFS
Lemma 3.1. For MILPs (Eq.(7) and AMILPs (Eq.3)), let the LP relaxation optimal solutions be denoted as x² and D*, respectively. Then, there exists a correspondence between these solutions such that x= = x= s.
Proof. The I.P relaxation problems of MILP and AMILP can be expressed as follows:
xx arg min {c Ax & 6, < x vu m
(9)
and
/" arg min { of
ct's A# < <
(10)
We now assume that = x= + 8, so that Eq. 9) can be written as
s arg
(c (TTTr: Ax < b,1 b
(11)
x
16

---

Published as a conference paper at ICLR 2024
which implies that
y = arg min (c" Ax < 0, u
= arg min {c (á - s) A( 8) < b, < -------- -
(12)
Ad v As +b, S arg min {c ã c² s
Clearly, Eq. 10 is equal to Eq. 12 that is, o x²' + 8.
Theorem 3.1. For MILPs Eq. and AMILPs Eq. let the optimal solution of the dual problem of the LP relaxation solution be denoted as y" and y respectively. Then, there exists a correspon- dence between these solutions such that y" ÿ"
Proof. By incorporating the boundary constraints of variable æ into the of other constraints, the MILP problem can be reformulated as the following LP relaxation form
arg min ax An S b)
(13)
x
We can obtain its dual problem as follows
y arg max y" + n A 0, 0}
(14)
Similarly, for AMILPs, we also combine the boundary constraints of variable S with other con- straints, then we have
arg mcincciaaa s|A - 6 As}
(15)
The dual problem this AMILP can be obtained as follows:
D" arg max "" As) ct c* + A
Ā = 0. 2 20
(16)
arg max 1- b + 0, 9 20 0}
According to (14 and 16. be inferred that the optimal solutions for the dual problem associated with LP relaxation of both MILP and AMILP is identical. The proof is completed.
Theorem 3.3. For MILPs Eq.D and their corresponding AMILPs Eq.3)) let the reduced cost corresponding to LP relaxations for MILP and an AMILP be denoted as and oú, respectively. Then, there is correspondence between these reduced costs such that o; = ō
Proof. Let's consider the variable Ty in the MILP. Its reduced cost, denoted dj, can be expressed as
J = B '
(17)
Here, B represents the matrix composed of the column vectors of the current basis, CB denotes the coefficient vector of the objective function at basic variables, and A, represents the jth column of the matrix Á. Similarly, for the AMILP, the reduced cost of variable å, denoted ãj. can be expressed in the same way:
6, = B B A =
(18)
This equality demonstrates that the reduced cost values for the variables in both the MILP and the AMILP are indeed equivalent. Hence, the proof is complete.
C METHODOLOGY DETAILS
C.I OVERVIEW OF BIPARTITE GRAPH NODE FEATURES
The relationships between MILP and AMILP node features illustrated in Table 4 for constraint nodes and Table variable nodes. Note that in Table the notation BB <+ Z denotes the potential mutual conversion between binary variables and integer variables.
17

---

Published as a conference paper at ICLR 2024
Table 4: Relationship between MILP and AMILP constraint node features.
Node feature of constraint
MILP
AMILP
obj-cos_sim
C₂
C₁
bias
C
C +
af
is is_tight
C
C
dualsol_val
C₁
C
age
C
C
Table 5: Relationship between MILP and AMILP variable node features.
Node feature variable j
MILP
AMILP
type
V
V J,1 or
IB
+
coef
V J.2
V12
has_lb
V 13
has_ub
V
V1,4
sol_is_at_lb
V,5
J.5
sol at ub
V,6
J.6
sol_frac
Vi77
Vj.7
basis_status
V888
V1.8
reduced.cost
V,9
1.9
age
V5,0
V1,10
sol val
V VJ,1
V Jan + 8j
inc_val
V ,,12
J.11 + 8g
avg inc val
V,,13
1,13 + 8)
C.2 CONTRASTIVE LEARNING
This section will provide details the forward propagation process. Specifically, once we have ac- quired the updated constraint and variable node features Cn and V for the MILP, along with aug and V aug for the AMILP, we can formulate the feature merging process as follows:
MLP (Concat (MaxPool (Cor) MeannPoo (Curi )))
(19)
Pri
MLP (Concat (MaxPool (Voc) MeanPool (V )))
(20)
C Caug
MLP (Concat (MaxPool (Camn)) MeanPool (Ciug))
(21)
9
MI.P (Concat (MaxPool (V ( MeanPool (V (V=ng)))
(22)
where Concat denotes the concatenation operation. The process of obtaining graph-level embed- dings can be formulated as follows:
geni MLP (Concat (ch, 2 )) Jaug MLP (Concat (cin U
(23)
where gon and Jaug represent the graph-level embeddings of the MILP bipartite graph and the AMILP bipartite graph, respectively. Once these graph-level embeddings are obtained, we proceed apply contrastive learning in the subsequent steps.
18

---

Published as a conference paper at ICLR 2024
C.3 IMITATION LEARNING TRAINING PROCEDURE
We employ behavior cloning Pomerleau 1991 to train the CAMBranch, focusing imitat- ing Strong Branching policies. Expert strategies are collected using the optimization suite SCIP Gleixner al. (018)) and are stored in dataset that consists of expert state-action pairs, denoted as
D ( a ) Within this dataset, S; (G, C, E, V). while a represents the branch decision of Strong Branching strategy under št. To optimize the network, cross-entropy is used as a supervised learning loss function
((sup)
Σ
log TH (a, s:)
(24)
(B..AT)ED
In addition, to enhance the consistency in the probability distribution of variable selection between the MILP and the AMILP, we incorporate consistency constraints. Specifically, extract the prob- ability distribution Pori and Paug of variables outputted by MILP and the AMILP, respectively. The aim is minimize the divergence between these two distributions, i.c.
((
PPor (1)
Paug (i))²
(25)
Finally, the final loss function by combining the three loss above is obtained
L = C (sup) A (infoNCE)) + 2g
(26)
Where \ and X2 are hyperparameters used to adjust the weights between loss functions.
D EXPERIMENT DETAILS
D.1 EXPERIMENTAL SETTINGS
In this paper, all experiments are run on a cluster with Intel(R) Xeon(R) Gold 5218 CPU 2.30GHz processors, 128GB RAM, and Nvidia RTX 2080Ti graphies cards.
D.1.1 DATA COLLECTION AND SPL.IT
In our experiments, we conducted systematic investigation of our model's performance by cate- gorizing each problem instance into three difficulty levels: Easy, Medium, and Hard, following the established settings used in Gasse et al. (2019). Additional information about the instance data split for each problem can be found in Gasse et al. (011)).
D.1.2 SOLVER CONFIGURATION
In our experiments, employed the open-soune solver SCIP (version 6.0.1) (Glexnner al. 2018) as our backend solver. We imposed a maximum solving time limit 3600 seconds, allowing cut generation operations solely at the root node while disabling solver restarts. To ensure fair com- parison among the methods, we maintained all other solver parameters at their default values Khalil
al. (2016) Kilinç-Karzan al. (2009); Matteo Fischetti (2012)
D.1.3 TRAINING PARAMETERS
In our experiments, we implemented models using PyTorch (Paszke et al. (019)) and PyTorrhh Geo- metric (Fey & Lenssen 2019). We utilized the Adam optimizer Kingma Ba (005) with 3 = 0.9 and B2 = 0.999. In case the model shows no significant improvement over a period of 10 epochs, we applied a learning rate reduction to 20% of its initial value. We set the hidden layer size of the GCNN network to 64. We conducted grid search for the learning rate, considering values from {1 x 10-3, 3 10 10-4, 4, x 10 10-4). Additionally, we selected the weight values \ = 0.05 and X2 = 0.01 for the loss function..
19

---

Published as a conference paper at ICLR 2024
1.1.4 METRICS
We evaluate performance using the shift geometrie mean (SGM) for solving time and the geometric mean of nodes for the number of B&B search tree nodes. The SGM is calculated for set of n numbers, denoted as 11,42..... fn- with 8 representing the shift. The SGM formula is given by SGM = VII.i, (4) - s. In this context, smaller values for the solving time and node count metrics indicate better performance, while a higher number of wins metric signifies superior performance. In this paper, is set to 1 for time and 100 for Nodes, following the previous work (Gasse et al.) 2019; Zarpellon al. 202I).
D.2 ADDITIONAL RESULTS
Our results are also presented in a tabular format, available in Tor imitation learning accuracy. Table 7 and Table 8 for the ablation study. Additionally, training sample ratio on performance. Given that our proposed CAMBranch requires additional computations compared the original GCNN in Gasse et al. (2019), we also evaluated the training overhead of these models.
delve into the influence of varying the
Table 6: Imitation learning accuracy the test sets of expert samples.
Mosid
Capaciaal Faillty
Bo093
sa/910
OCNN
70.35 0.58
05.09 0.14
00.40 = 0.00
66,95 = 0.32
93.79
0.16
27 = om
10:00:30 0.25
03.48 2012
055 2:00 1800
85,83 62) 0.2
GENN (00
58
1.39
CAMBuash
Table 7: Results of ablation experiments on imitation learning accuracy in Set Covering.
Type
acc @1
acc @5
acc @10
CAMBranch w/o CL (10%)
64.75 + 1.43
88.94 + 1.31
96.16 = 0.72
CAMBranch (10%)
65.27 + 3.92
89.46 + 2.98
96. 1.90
D.2.1 ANALYSIS OF IMPACT OF TRAINING SAMPLE RATIOS
To investigate the influence of training sample ratios, we conducted experiments using subsets com- prising 5%, 10%, and 20% of the training data for both GCNN and CAMBranch. We evaluated their performance on the Combinatorial Auction problem, and the results are summarized in Table Our observations indicate that as the problem's 's difficulty level increases, the performance differences among the training sample ratios become progressively obvious. Moreover, for both GCNN and CAMBranch, their best performances are consistently achieved when the training sample ratio is set at 20%, suggesting that leveraging a larger portion of data leads to performance improvement. Sim- ilar trends are evident on the Maximum Independent Set problem (Table especially in the Hard level instances. As shown in Table I0 the performance on Hard instances improves with larger sample sizes, with reduced solving time and lower number of nodes. Notably, CAMBranch (20%) achieved the highest number of solved instances in the Hard level, 49 instances in total, underscor- ing its superiority. Furthermore, the comparison between the two methods reveals that CAMBranch consistently outperforms GCNN across all three ratios, highlighting the superior capabilities of our proposed CAMBranch framework.
Table 8: Results of ablation experiments on instance solving evaluation in Set Covering.
Easy
Medium
Hard
Model
Time
Wins
Nodes
Time
Wins
Nodes
Time
Wins
Nodes
CAMBranch w/o CL (10%)
6,55
77/100
202
66.09
22/100
2788
1472.84
23/49 32/55
69215
CAMBranch (10%)
6.79
23/100
188
61.00
78/100
2339
1427.02
66943
20

---

Published as a conference paper at ICLR 2024
Table 9:
The results of sample ratio analysis the instance solving evaluation for Combinatorial
Auction.
Easy
Medium
Hard
Model
Time
Wins
Nodes
Time
Wins
Nodes
Time
Wins
Nodes
GCNN (5%)
1.61
37/100
95
10.66
7/100
803
117.90
5/100
10692
GCNN (10%)
1.99
1/100
102
12.38
0/100
787
144.40
0/100
10031
GCNN (20%)
1.66
15/100
94
9.81
51/100
796
107.02
27/100
9626
CAMBranch (5%)
1.61
38/100
97
10.64
12/100
825
121.81
2/100
10582
CAMBranch (10%)
2.03
0/100
12.68
0/100
758
131.79
2/100
9074
CAMBranch (20%)
1.68
9/100
91
9.92
30/100
762
103.38
64/100
9050
Table 10: The results of sample ratio analysis on the instance solving evaluation for Maximum Independent Set.
Easy
Medium
Hard
Model
Time
Wins
Nodes
Time
Wins
Nodes
Time
Wins
Nodes
GCNN (5%)
5.97
9/100
90
64.07
13/100
1824
607.48
2/39
16850
GCNN (10%)
7.18
0/100
51.40
37/100
1331
695.96
0/20
17034
GCNN (20%)
5.84
22/100
88
55.22
26/98
1534
465.00
16/43
12998
CAMBranch (5%)
5.85
65/100
70.91
3/100
1982
592.81
1/41
15480
CAMBranch (10%)
6,92
0/100
90
61.51
14/100
1479
496.86
1/40
10828
CAMBranch (20%)
6.19
4/100
95
68.47
7/100
2008
416.24
20/49
10455
D.2.2 ANALYSIS OF TRAINING OVERHEAD
Since our proposed CAMBranch introduces additional computation, we further assessed the training overhead of CAMBranch and GCNN proposed in Gasse al.) (2019). Table [1] demonstrates that, despite the introduced computation by CAMBranch, the observed difference in computational speed deemed acceptable meeeelmeeeeyeeeeeeeee matter of several milliseconds. In summary, the training overhead associated with CAMBranch is within acceptable bounds.
E DISCUSSION
E.
WHEN TO USE CAMBRANCH?
In this section, we further explore the scenarios in which CAMBranch is most effective. To this end, we conducted the following experiments on Combinatorial Auction Problem to analyze the relationships between performance and both the number of MILP instances and expert samples. The results of these experiments are detailed in Table
Impact of expert sample size. From experiment pairs (I, II,, (III, IV), and (V, VI), we delve into the relationship between performance and the number of expert samples, holding the number of MILP instances constant. The results indicate that increasing the number of expert samples generally enhances performance, as evident in pairs (I. II) and (III, IV). However, in scenarios with a relatively small number of instances, such as (V, VI), augmenting expert sample size may not necessarily lead to performance increase.
Influence of MILP instance count. Examining pairs (I. III. IV) and (II, IV, VD), we further explore the relationship between performance and the number MILP instances, maintaining a consistent expert sample size. The observations suggest general trend of performance improvement with an increase in the number of MILP instances.
Based on these observations, answer the question of when to CAMBranch, our initial clusion that CAMBranch demonstrates more potential when there is sufficient number of MILP instances, but not necessarily large scale. Using several hundreds of MILP instances can already
21

---

Published as a conference paper at ICLR 2024
Table 11: Results of training time per batch of GCNN and CAMBranch the Set Covering prob-
lem. Each batch contains 64 samples.
Model
Training time per batch (s)
CAMBranch (10%)
0.09666
GCNN (10%)
0.09216
Table 12:
Results for the impacts of expert sample size and MILP instance count.
Easy
Medium
Hard
Exp ID
Training Data
Time
Nodes
Time
Nodes
Time
Nodes
362 instances
I
2.03
91
12.68
758
131.79
9074
10k expert samples
388 instances 20k expert samples
II
1.68
91
9.92
762
103.38
9050
100 instances 10k expert samples
III
1.67
94
10.02
757
111.52
9242
100 instances 20k expert samples
IV
1.64
90
10.03
751
109.58
9195
50 instances 10k expert samples
V
3.25
98
20.58
796
158.24
9834
50 instances
VI
3.18
97
20.59
819
166.02
10892
20k expert samples
achieve superior performance. Moreover, increasing the number of expert samples provides benefits for performance, as supported by our empirical findings.
E.2 RELATIONSHIP BETWEEN IMITATION LEARNING AND INSTANCE EVALUATION
In Section we presented the results of various branching strategies. However, due to space limitations, we aim to delve deeper into these results this discussion section. Specifically, we'll focus on the relationship between the results of imitation learning accuracy and instance evaluation.
Regarding imitation learning accuracy, it's notable that CAMBranch doesn't consistently outperform GCNN in imitating the Strong Branching strategy. However, when shift attention to instance evaluation, CAMBranch exhibits superior performance in most cases, particularly on challenging explore
problems, with the exception of Set Covering. This intriguing observation prompts the underlying reasons. Analyzing CAMBranch's 's training signal, i.e., loss function, one possible explanation is that contrastive learning empowers CAMBranch transcend mere imitation of Strong Branching. While Strong Branching often results in the creation of the smallest B&B trees due to its tendency to produce high-quality branching decisions, it doesn't guarantee optimal branching strategy. Recent studies by Scavuzzo et al. (2022) Dey et al. (2023). ) and Gamrath et al. (2020) have even suggested that Strong Branching may underperform certain cases, falling short problem- specific rules.
Within our CAMBranch framework, the introduction of contrastive learning offers a key advan- tage. It enables CAMBranch to learn MILP representations better, allowing it to uncover alternative branching strategies beyond Strong Branching. This means that CAMBranch can now explore and learn from alternative policies that might yield better performance than Strong Branching, guided by the contrastive learning loss function. Essentially, our proposed framework serves as a pathway to learning potentially superior branching strategies, extending beyond the confines of merely imi- tating Strong Branching. Therefore, this will enhance decision decision-making capabilities the realm of MIL.P solving. We will delve deeper into this aspect in our future research.
22

---

Published as a conference paper at ICLR 2024
F RELATED WORK
Learning to branch. The integration of machine learning techniques into branching strategies has been topic of growing interest, with Gasse et al. (019) marking significant breakthrough in this domain, signifying a pivotal moment. Prior to this, conventional approaches in relevant literature (Khalil et al. 2016 Alvarez al. 2017: Balean al. 2018) often rely on extracting statistical features from MILPss Ps during the solving process. However, these feature extraction methods were deemed incomplete for capturing the full essence MILP problem instances. By contrast, the work of Gasse et al. (2019) introduced a novel perspective by leveraging bipartite graphs to create more accurate modeling of MILPs and trained models with imitation learning to approximate the Strong Branching. Subsequent research efforts predominantly build upon the foundations laid by Gasse (ct al. (2019). For instance, Cassaace,,Guptaaa et al. (2200) proposed a hybrid model tailored for efficient branch- ing on CPU-constrained machines. This model replaced computationally expensive graph networks with more lightweight Multilayer Perceptrons (MLPs), except at the root node. Meanwhile, Nair jet al. (2020) achieved notable enhancements in both runtime performance and the average primal- dual gap by introducing Neural Diving and Neural Branching techniques.
While these methods demonstrated impressive results, they neous MILPs, where training and test instances belong to the same problem class. In order to extend the applicability to heterogeneous MILPs, where problem instances vary across different classes, Zarpellon et al. (2021) and Lin et al. (2022) adopted approaches that parameterize the states of B&B search trees. They achieved this by imitating the SCIP default branching scheme known as RPB, suitable expert policy renowned for its effectiveness in guiding search trees. For more comprehen- sive insights into this field, readers can refer to related surveys by Khalil al. (2017) and Zhang et al. (2023).
primarily designed for homoge-
Contrastive learning. Contrastive learning has emerged as a powerful paradigm various ma- chine learning domains. It has been successfully applied in computer vision (Chen al. 2020a Falcon Cho 2020; He et al.) 2020 Chen et al.] [2020c]b) bb Caron et al.) 2020) Grill et al.
2020
Chen & He| 2021). natural language processing (Mikolov et al. 2013 Arora et al. 2019 Ieer al.
2020 Fang & Xie 2020 Giorgi et al. (02T). recommendation system YYu et al. 2022) and drug
discovery (Xu et al. (002). The core idea involves encouraging similarity between positive pairs
(similar data points) and pushing apart negative pairs (dissimilar data points) in a latent space. In this paper. CAMBranch leverages the contrastive learning paradigm to maximize the utilization of both MILPs and their corresponding AMILP data.
G MILP FORMULATION
Following Gasse et al. 2019), we evaluated the models on four combinatorial optimization prob- lems, i.e., Set Covering, Combinatorial Auction, Capacitated Facility Location, and Maximum In- dependent Set represent. These problem classes have served as standard benchmarks for evaluating the efficacy of optimization techniques in the research community. Despite considerable attention and research efforts, these problems remain computationally demanding, even for state-of-the solvers. In the following sections, we provide detailed descriptions of the MILP models for each of these problems.
(1) Set Covering: given a finite set 2I and its n subsets Si,..., Sn, the problem seeks to identify the minimum number of subsets that can be used to cover U completely.
minimize
(27)
subject to
Σ
2j > 1
Vu E U
(28)
je(1, jeles
I E [0
Vj E .n]
(29)
where each xy is decision variable. If the subset S, is chosen, then æ. otherwise x,
0.
23

---

Published as a conference paper at ICLR 2024
(2) Combinatorial Auction: consider scenario where there bids and available. Each item is associated with a subset Sj S [1....n) n representing the bidders interested in that particular item. The revenue generated by each bid i is denoted as bj. The Combinatorial Auction problem aims to allocate the bids to maximize the expected return.
maximize
rgbs
(30)
1=1
subject to
Σ iES,
Vj E , m}
(31)
24 E (0, vi f1, _n}
(32)
where each 2; a decision variable. bid n; is selected, then T; = 1, otherwise x; = 0.
(3) Capacitated Facility Location: assuming there satisfy customers at a minimum cost. Let Si denote the cost of building facility E {0, .m] and Ciş denote the transportation cost of products from facility to customer (0,...,m) The demand of customer j is dy > O, and the capacity of facility i is > 0.
facilities and customers, the goal is to
minimize
Cijthj
+
fixs
(33)
i=
j=1
m
subject
U/i
Vj E fl....,n ,n}
(34)
d & u fl, "1, m}
(35)
j=l
Vij
vi (1, (1,--., m). je tl. .n]
(36)
I2 E {0,
(1.
(37)
where each Boolean variable xj and each continuous variable Viy are decision variables. facility
j is built, I = otherwise zj 0. In addition, variable Vij represents the percentage of demand
d that is assigned to facility i.
(4) Maximum Independent Set: consider undirected graph G = E), wherein subset S E V of nodes deemed an independent set when no edges interconnect any couple nodes within S. The task at hand is to determine the largest possible number of independent sets in the graph G.
maximize
Σ Fe DEV
(38)
subject to
Iu + <1 1 v(u,u)
(39)
N. E (0.1) Vo
(40)
where each Boolean variable x, is decision variable. If node selected in the independent set, then F. 1, otherwise, Fy = 0.
24


Reviews:
[{"review_id": "R24dUnvATR", "reviewer": "Reviewer_vbTP", "summary": "The paper proposes a data-efficient imitation learning algorithm for learning a branching policy in B&B algorithm.\nThe proposed method augments demonstration data of Strong Branching decisions using mathematically complete rule and introduces contrastive learning by using the augmented data as positive samples.\nExperiment results demonstrate that the proposed method can significantly outperform existing imitation learning-based MILP solvers.", "questions": "What would be the intuition behind using shifted geometric mean for evaluation?  And what is the $s$ value for each metric?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed method of augmentation rule and contrastive learning idea is well-motivated, concise and effective.  \nThe performance improvement from previous method in low-data situations is significant.", "weaknesses": "The presentation of main result should be improved.\n- CAMBranch (100%) result should be discussed. Despite this work aiming in data scarce situation, understanding how it behaves with the full dataset is critical information, considering the results with 10% of data is not outperforming the baseline using full data.\nEven if CAMBranch using the full data can't outperform the baseline using full data, it is still beneficial to share this limitation with the community if proper discussion is provided.\nHowever, without the result, I am negative about introducing this method to the community as a MILP solver because it is unknown whether it limits the potential of imitation learning-based MILP methods.\n- The main results appear to be promising but could be presented better. Neither Figure 2-4 nor Table 5 looks optimal in their current forms.\n- The result of Table 8 deserves to be in main text, considering the goal of this work. Also, evaluation in another domain with more dramatic performance gap could be better for the comparison. The presentation also has room for improvement; it is hard to compare the metrics of models using the same amount of data.\n\nIf this concern is resolved I am willing to vote for accepting this paper.\nHowever, as it seems that a major revision is required, including the core results of the paper, I also agree if other reviewers or AC recommend submitting this work to next venue.", "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": "eAKTDVd6fy", "reviewer": "Reviewer_mGEq", "summary": "This paper proposes CAMBranch, which generates augmented MILPs with shifting variables and identical variable selection decisions, and uses contrastive learning ot use the augmented MILPs for learning to branch. Experiments demonstrate that CAMBranch can effectively improve the sample efficiency.", "questions": "1. Sometimes GCNN (10%) even outperforms GCNN (e.g., MIS in Figure 2). Why?\n2. See weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This paper identifies the challenge of  sampling time in Learn2Branch, which is meaningful.\n2. The augmentation strategy has a theoretical gurantee and is insightful.", "weaknesses": "1. CAMBranch does not perform well on relatively easy datasets. The improvement is not significant compared with GCNN baseline on many medium and hard datasets. Fow example, results in Table 8 do not reveal that CAMBranch consistently outperforms GCNN.\n2. The augmentation method is tailored for the branching task, while not easy to be transfered to other algorithms in B & B solvers. Therefore, the application is limited.\n3. Which sample ratio, with CAMBranch, leads to a comparative results with the model trained with the full dataset? What if use the full training dataset  with this augmentation? Will it stll bring improvement?\n4. How many instances does it need to generate 20k expert samples? The 10% means using 10% MILP instances or 10% expert samples? How many expert samples can one instance produce? Experiments should be conduct to investigate the effect of the number of MILP instances and the expert samples. Also, the accumulative time used in collecting the expert samples should be reported.", "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": "dPtd0Wt3pT", "reviewer": "Reviewer_8jS2", "summary": "The authors propose **CAMBranch** an innovative approach that seeks to enhance the efficiency of Branch and Bound (B&B) algorithms for solving Mixed Integer Linear Programming (MILP) problems. Traditional B&B methods, while reliable, can be computationally intensive, motivating the exploration of machine learning to improve branching decisions. In particular, **CAMBranch** employs a machine learning framework based on contrastive learning and uses Augmented MILPs (AMILPs) to inform its branching strategies.\n\nThe key innovation of in the work lies in its utilization of AMILPs, which are equipped with expert decision labels, making them suitable for imitation learning. This approach aims to mimic the performance of Strong Branching, a highly effective but computationally expensive B&B policy. By leveraging the relationships between MILP and AMILP, the method extracts and utilizes node features from an augmented bipartite graph to inform its branching decisions.\n\nThe strengths include its novel application of contrastive learning in the domain of optimization and its potential to significantly reduce the computational burden associated with Strong Branching. The use of AMILPs for imitation learning could lead to more efficient and informed branching strategies, potentially improving the overall performance of B&B algorithms.\n\nHowever, the success of the proposed algorithm hinges on the accuracy of the imitation learning model. If the model fails to capture the subtleties of Strong Branching, it could result in suboptimal decisions. Additionally, the integration of machine learning into B&B algorithms may introduce computational overhead, which could diminish the anticipated efficiency gains. Lastly, the generalizability of **CAMBranch** across diverse MILP problems remains to be thoroughly evaluated, as its effectiveness may vary depending on the problem's characteristics.", "questions": "1. **How does the model's architecture influence the quality of imitation learning?**\n   - The architecture of the neural network used for imitation learning plays a crucial role in its ability to capture the decision-making process of Strong Branching. How does the choice of architecture impact the model's ability to generalize across diverse MILP instances?\n\n2. **What is the impact of contrastive learning's positive and negative sample selection on the performance?**\n   - In contrastive learning, the selection of positive and negative samples is critical for learning meaningful representations. How does CAMBranch ensure the selection of informative positive and negative samples during training? Could the incorporation of hard negative mining or other advanced sampling strategies improve the model's performance?\n\n3. **How does the algorithm address the exploration-exploitation trade-off during the B&B process?**\n   - The Branch and Bound algorithm involves a delicate balance between exploring new branches and exploiting known promising paths. How does CAMBranch navigate this trade-off? Are there mechanisms in place to prevent premature convergence on suboptimal branches or to encourage exploration when necessary?\n\n4. **How does CAMBranch handle the interpretability and explainability of its branching decisions?**", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Strengths:\n\n* Innovation in Branch and Bound (B&B) Methods: The paper discusses recent advancements in machine learning frameworks to enhance B&B branching policies for solving Mixed Integer Linear Programming (MILP), indicating a focus on innovation and improvement of existing methods.\n* Potential for Improved Efficiency: If these machine learning-based methods can successfully imitate Strong Branching, they may offer more efficient alternatives to traditional B&B methods, which can be computationally intensive.", "weaknesses": "Potential weaknesses of CAMBRANCH:\n\n1. **Fidelity of Imitation Learning:** The effectiveness  is predicated on the assumption that imitation learning can closely approximate the decisions made by Strong Branching. However, Strong Branching is known for its nuanced decision-making process, which considers a multitude of factors and potential future states. Replicating this complexity through imitation learning is challenging. If the learning model fails to encapsulate the depth of Strong Branching's strategy, the resultant branching decisions could be significantly less efficient, negating the primary advantage of CAMBRANCH.\n\n2. **Computational Overhead of Machine Learning Integration:** While machine learning models offer the promise of improved decision-making, they also introduce computational overhead. Training models, especially those based on contrastive learning, require significant computational resources. Furthermore, the real-time application of these models within the iterative B&B process could lead to increased computational demands, potentially offsetting the efficiency gains from more informed branching.\n\n3. **Sensitivity to Hyperparameter Tuning:** Machine learning models, particularly those used in imitation learning, are sensitive to hyperparameter settings. The performance of CAMBRANCH could be highly dependent on the choice of learning rate, batch size, and other hyperparameters. Finding the optimal configuration can be a time-consuming process that requires extensive experimentation and computational resources.\n\n4. **Generalizability and Robustness Concerns:** The diversity of MILP problems poses a significant challenge to the generalizability of CAMBRANCH. Different MILP instances can vary drastically in terms of size, structure, and complexity. CAMBRANCH must demonstrate robust performance across a wide array of problems to be considered a viable alternative to existing B&B methods. Additionally, the model's robustness to adversarial inputs or unusual problem structures remains to be thoroughly evaluated.\n\nIn conclusion, while CAMBRANCH presents an innovative approach to improving B&B algorithms for MILP problems, its success is contingent upon overcoming the intricate challenges associated with imitation learning, computational efficiency, hyperparameter sensitivity, and the robustness of its application across diverse problem sets.", "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": "Qgc2zlgYR7", "reviewer": "Reviewer_EfKd", "summary": "Update on November 19:\n\nI raise 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---\nThis paper point out the shifting equivalence of the MILP problems. Then, the authors propose a contrastive learning approach based on the augmented MILP problems. Experiments demonstrate that CAMBranch achieves high performance with only 10% of the complete dataset.", "questions": "See weaknesses above.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Practical motivation. In practice, I found the similar problem that generating expert demonstration for industrial-level datasets is extremely time-consuming. Thus, the motivation of this paper is practical.\n2. Clear writing. The paper is clearly structured and easy to go through flow.\n3. Simple and effective approach. The idea of the shifting equivalence is simple and effective. Previous research uses GNN to tackle the symmetry in row and column orders. In this paper, the authors explicitly use the shifting equivalence via contrastive learning to enhance the training efficiency.", "weaknesses": "1. The illustration of experimental results requires to be improved. The bars missing detailed values on it. Compared with histograms, tables could be more compact for demonstration.\n2. Missing comparisons to other ML approaches. Employing auxiliary tasks is an effective way to improve the training efficiency. Empirically, I found the simple auxiliary task employed in [1] can efficiently promote the training efficiency. Thus, can you provide more results comparing this data augmentation approach to other auxiliary tasks? \n3. Marginal improvement in Figure 1. It seems the improvement of CAMBranch is not significant. Maybe a lighter GNN with fewer hidden layers and hidden nodes can achieve similar IL accuracy but requires less expert data.", "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)