# CAMBranch: Contrastive Learning with
Augmented MILPs for Branching

Jiacheng Lin1,† Meng Xu2 Zhihua Xiong2 Huangang Wang2 1University of Illinois
Urbana-Champaign 2Tsinghua University This work was completed during the
master program at Tsinghua University.Equal contributions.Corresponding to
<EMAIL_ADDRESS>
###### 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 Contrastive Learning
with Augmented MILPs for Branching (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.

##  1 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 et al., 2018; Almeida et al.,
2006; Hait & Artigues, 2011). A prominent approach for solving MILPs is the
Branch-and-Bound (B&B) algorithm (Land & Doig, 1960). This algorithm adopts a
divide-and-conquer approach, iteratively resolving sub-problems and
progressively reducing the search space. Within the execution of the
algorithm, one pivotal decision comes to 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 a 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., 2022). This transition marks a notable
advancement 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,
refer to the survey provided in Bengio et al. (2021).

The performance of the B&B algorithm hinges significantly upon its branching
strategy, and suboptimal branching decisions can exponentially escalate the
computational workload. This predicament attracts researchers to explore the
integration of machine learning (ML) techniques to enhance branching
strategies. Notably, Gasse et al. (2019) have trained branching policy models
using imitation learning, specifically targeting Strong Branching (Applegate
et al., 1995), a traditional strategy known for generating minimal branching
search trees but with extremely low efficiency. By mapping a MILP into a
bipartite, these branching policy models leverage Graph Convolution Neural
Networks (GCNN) (Kipf & Welling, 2017) to extract variable features and make
variable selection decisions. This approach has demonstrated superior
performance in solving MILPs, marking a significant milestone in the
application of machine learning to MILP solving.

Despite making significant progress, a 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
optimization 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.,
1991), and Maximum Independent Set Problem (Cire & Augusto, 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 collecting 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 a reasonable timeframe becomes increasingly
impractical.

To address this issue, we present a novel framework named Contrastive Learning
with Augmented MILPs for Branching (CAMBranch). Our approach begins with the
development of a data augmentation technique for MILPs. This technique
generates a set of Augmented MILPs (AMILPs) through variable shifting, wherein
random shifts are applied to each variable within a MILP to produce a new
instance. This augmentation strategy enables the acquisition of a substantial
number of labeled expert samples, even when expert data is limited. It
eliminates the need for extensive computational efforts associated with
solving numerous MILP instances, thereby mitigating the challenges related to
expert strategy sample collection. Next, building upon the work of Gasse et
al. (2019), we transform a MILP into a bipartite graph. By providing
theoretical foundations and proofs, we establish a 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 a seamless integration of this learning approach. We evaluate our
approach on four classical NP-hard combinatorial optimization problems,
following the experimental setup described in Gasse et 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 et
al. (2019).

##  2 Preliminaries

###  2.1 Mixed Integer Linear Programming (MILP)

The general definition form of a MILP problem instance
$\operatorname{MILP}=(\bm{c},\bm{A},\bm{b},\bm{l},\bm{u},\bm{\mathcal{I}})$ is
shown below

$\displaystyle\min_{\bm{x}}\hskip
2.84544pt\bm{c}^{\mathrm{T}}\bm{x}~{}~{}~{}~{}\text{ s.t.
}\bm{A}\bm{x}\leqslant\bm{b},\hskip
2.84544pt\bm{l}\leqslant\bm{x}\leqslant\bm{u},\hskip
2.84544ptx_{j}\in\mathbb{Z},\hskip 2.84544pt\forall j\in\bm{\mathcal{I}}$ (1)

where $\bm{A}\in\mathbb{R}^{m\times n}$ is the constraint coefficient matrix
in the constraint, $\bm{c}\in\mathbb{R}^{n}$ is the objective function
coefficient vector, $\bm{b}\in\mathbb{R}^{m}$ represents the constraint right-
hand side vector, while $\bm{l}\in(\mathbb{R}\cup\\{-\infty\\})^{n}$ and
$\bm{u}\in(\mathbb{R}\cup\\{+\infty\\})^{n}$ represent the lower and upper
bound vectors for each variable, respectively. The set $\bm{\mathcal{I}}$ is
an integer set containing the indices of all integer variables.

In the realm of solving MILPs, the B&B algorithm serves as the cornerstone of
contemporary optimization 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. Simultaneously,
bounding occurs, which aims to establish either lower-bound or upper-bound
targets for solutions within these subsets. Lower bounds are calculated
through linear programming (LP) relaxations, while upper bounds are derived
from feasible solutions to MILPs.

Table 1: An overview of the features for constraints, edges, and variables in
the bipartite graph
$\mathbf{s}_{t}=(\mathcal{G},\mathbf{C},\mathbf{E},\mathbf{V})$ following
Gasse et al. (2019).

Type | Feature | Description
---|---|---
| obj_cos_sim |  Cosine similarity between constraint coefficients and objective function coefficients.
$\mathbf{C}$ | bias |  Normalized right deviation term using constraint coefficients.
| is_tight |  Indicator of tightness in the linear programming (LP) solution.
| dualsol_val |  Normalized value of the dual solution.
| age |  LP age, which refers to the number of solver iterations performed on the LP relaxation problem without finding a new integer solution.
$\mathbf{E}$ | coef |  Normalized constraint coefficient for each constraint.
| type |  One-hot encoding representing the type (binary variables, integer variables, implicit integer variables, and continuous variables).
| coef |  Normalized objective function coefficients.
| has_lb /_ub |  Indicator for the lower/upper bound.
$\mathbf{V}$ | sol_is_at_lb /_ub |  The lower/upper bound is equal to the solution value.
| sol_frac |  Fractionality of the solution value.
| basis_status |  The state of variables in the simplex base is encoded using one-hot encodin (lower, basic, upper, zero).
| reduced_cost |  Normalized reduced cost.
| age |  Normalized LP age.
| sol_val |  Value of the solution.
| inc_val /avg_inc_val |  Value/Average value in the incumbent solutions.

###  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 a bipartite graph, denoted by
$(\mathcal{G},\mathbf{C},\mathbf{E},\mathbf{V})$, where: (1) $\mathcal{G}$
represents the structure of the bipartite graph, that is, if the variable $i$
exists in the constraint $j$, then an edge $(i,j)\in\mathcal{E}$ is connected
between node $i$ and $j$ within the bipartite graph. $\mathcal{E}$ represents
the set of edges within the bipartite graph. (2)
$\mathbf{C}\in\mathbb{R}^{|\mathbf{C}|\times d_{1}}$ stands for the features
of the constraint nodes, with $|\mathbf{C}|$ denoting the number of constraint
nodes, and $d_{1}$ representing the dimension of their features. (3)
$\mathbf{V}\in\mathbb{R}^{|\mathbf{V}|\times d_{2}}$ refers to the features of
the variable nodes, with $|\mathbf{V}|$ as the count of variable nodes, and
$d_{2}$ as the dimension of their features. (4)
$\mathbf{E}\in\mathbb{R}^{|\mathbf{C}|\times|\mathbf{V}|\times d_{3}}$
represents the features of the edges, with $d_{3}$ denoting the dimension of
edge features. Details regarding these features can be found in Table 1.

Next, the input
$\mathbf{s}_{t}=(\mathcal{G},\mathbf{C},\mathbf{E},\mathbf{V})$ is then fed
into GCNN which includes a bipartite graph convolutional 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 $\forall
i\in\mathcal{C},j\in\mathcal{V}$, the process of message passing can be
represented as

$\displaystyle\mathbf{c}_{i}^{\prime}=\mathbf{f}_{\mathcal{C}}\left(\mathbf{c}_{i},\sum_{j}^{(i,j)\in\mathcal{E}}\mathbf{g}_{\mathcal{C}}(\mathbf{c}_{i},\mathbf{v}_{j},\mathbf{e}_{i,j})\right)~{}~{}~{}~{}~{}~{}\mathbf{v}_{j}^{\prime}=\mathbf{f}_{\mathcal{V}}\left(\mathbf{v}_{j},\sum_{i}^{(i,j)\in\mathcal{E}}\mathbf{g}_{\mathcal{V}}(\mathbf{c}_{i},\mathbf{v}_{i},\mathbf{e}_{i,j})\right)$
(2)

where $\mathbf{f}_{\mathcal{C}}$, $\mathbf{f}_{\mathcal{V}}$,
$\mathbf{g}_{\mathcal{C}}$, and $\mathbf{g}_{\mathcal{V}}$ 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 feature
values of variable nodes and constraint nodes have been updated. Subsequently,
an MLP layer is used to score the variable nodes, and a masked softmax
operation is applied to obtain the probability distribution of each variable
being selected. The process mentioned above can be expressed as
$\bm{P}=\operatorname{softmax}(\operatorname{MLP}(\mathbf{v}))$. Here,
$\bm{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.

##  3 Methodology

As previously mentioned, acquiring Strong Branching expert samples for
imitation learning poses a non-trivial challenge. In this section, we
introduce CAMBranch, a novel approach designed to address this issue. Our
first step involves the generation of Augmented MILPs (AMILPs) labeled with
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, we proceed to create their augmented
bipartite graphs. Finally, since MILPs and corresponding AMILPs share
branching decisions, we view them as positive pairs. Leveraging the power of
contrastive learning, we train our model to boost performance.

###  3.1 Augmented Mixed Integer Linear Programming (AMILP)

To obtain AMILPs, we adopt variable shift from $\bm{x}$ defined in Eq.(1) to
$\hat{\bm{x}}$ using a shift vector $\bm{s}$, denoted as
$\hat{\bm{x}}=\bm{x}+\bm{s}$, where $\bm{s}$ is a shift vector. Note that if
$x_{i}\in\mathbb{Z}$, then $s_{i}\in\mathbb{Z}$; otherwise
$s_{i}\in\mathbb{R}$. Based on this translation, we can derive a MILP from
Eq.(1). To bring this model into standard form, we redefine the parameters as
follows: $\hat{\bm{b}}=\bm{A}\bm{s}+\bm{b}$, $\hat{\bm{l}}=\bm{l}+\bm{s}$, and
$\hat{\bm{u}}=\bm{u}+\bm{s}$. Consequently, the final expression for the AMILP
model is represented as:

$\displaystyle\min_{\hat{\bm{x}}}\hskip
2.84544pt\bm{c}^{\mathrm{T}}\hat{\bm{x}}-\bm{c}^{\mathrm{T}}\bm{s}~{}~{}~{}~{}{\rm{s.t.}}~{}\bm{A}\hat{\bm{x}}\leq\hat{\bm{b}},\hskip
2.84544pt$ $\displaystyle\hat{\bm{l}}\leq\hat{\bm{x}}\leq\hat{\bm{u}},\hskip
2.84544pt\hat{x}_{j}\in\mathbb{Z},~{}\forall j\in\mathcal{I}$ (3)

Through this data augmentation technique, a 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 a theorem to demonstrate this
characteristic. To illustrate this distinctive characteristic, we begin by
introducing a lemma that elucidates the relationship between MILPs and AMILPs.

######  Lemma 3.1.

For MILPs Eq.(1) and their corresponding AMILPs Eq.(3), let the optimal
solutions of the LP relaxation be denoted as $\bm{x}^{*}$ and
$\hat{\bm{x}}^{*}$, respectively. A direct correspondence exists between these
solutions, demonstrating that $\hat{\bm{x}}^{*}=\bm{x}^{*}+\bm{s}$.

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
$\bm{c}^{\mathrm{T}}\bm{x}^{*}=\bm{c}^{\mathrm{T}}\hat{\bm{x}}^{*}-\bm{c}^{\mathrm{T}}\bm{s}$.
This equation signifies the equivalence of 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 $\mathcal{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 $\mathcal{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 is to
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 a MILP’s branching variable $x_{i}$ and its corresponding shifted
variable of AMILP $\hat{x}_{i}=x_{i}+s_{i}$, we perform branching operations
on both variables. Firstly, we branch on $x_{i}$ to produce two subproblems
for MILP, which are formulated as follows:

$\displaystyle\underset{\bm{x}}{\arg\min}\left\\{\bm{c}^{\mathrm{T}}\bm{x}\mid\bm{A}\bm{x}\leqslant\bm{b},\bm{l}\leqslant\bm{x}\leqslant\bm{u},x_{i}\leqslant\left\lfloor
x_{i}^{*}\right\rfloor,x_{j}\in\mathbb{Z},\forall
j\in\bm{\mathcal{I}}\right\\}$ (4)
$\displaystyle\underset{\bm{x}}{\arg\min}\left\\{\bm{c}^{\mathrm{T}}\bm{x}\mid\bm{A}\bm{x}\leqslant\bm{b},\bm{l}\leqslant\bm{x}\leqslant\bm{u},x_{i}\geqslant\left\lceil
x_{i}^{*}\right\rceil,x_{j}\in\mathbb{Z},\forall
j\in\bm{\mathcal{I}}\right\\}$ (5)

where $x_{i}^{*}$ represents the value of variable $x_{i}$ in the optimal
solution corresponding to the MILP LP relaxation. Likewise, we branch on the
shifted variable $\hat{x}_{i}$, which generates two sub-problems for AMILP, as
represented by the following mathematical expressions:

$\displaystyle\operatorname*{arg\,min}_{\hat{\bm{x}}}\\{\bm{c}^{\mathrm{T}}\hat{\bm{x}}-\bm{c}^{\mathrm{T}}\bm{s}|\bm{A}\hat{\bm{x}}\leq\hat{\bm{b}},\hat{\bm{l}}\leq\hat{\bm{x}}\leq\hat{\bm{u}},\hat{x}_{i}\leq\lfloor\hat{x}_{i}^{*}\rfloor,\hat{x}_{j}\in\mathbb{Z},\forall
j\in\mathcal{I}\\}$ (6)
$\displaystyle\operatorname*{arg\,min}_{\hat{\bm{x}}}\\{\bm{c}^{\mathrm{T}}\hat{\bm{x}}-\bm{c}^{\mathrm{T}}\bm{s}|\bm{A}\hat{\bm{x}}\leq\hat{\bm{b}},\hat{\bm{l}}\leq\hat{\bm{x}}\leq\hat{\bm{u}},\hat{x}_{i}\geq\lceil\hat{x}_{i}^{*}\rceil,\hat{x}_{j}\in\mathbb{Z},\forall
j\in\mathcal{I}\\}$ (7)

where $\hat{x_{i}}^{*}$ represents the value of variable $\hat{x_{i}}$ in the
optimal solution corresponding to the AMILP LP relaxation.

According to Lemma 3.1, the LP relaxations of Eq.(4) and Eq.(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.(5) and Eq.(7) are also equal. Thus, for
$\hat{x}_{i}$ and ${x}_{i}$, the lower bound improvements of the subproblems
generated from MILP Eq.(1) and AMILP Eq.(3) are 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 a modeling approach akin to the one introduced
by Gasse et al. (2019). 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 1. For a detailed overview of the relationships between node
features in the augmented and original bipartite graphs, please refer to the
Appendix.

####  3.2.1 Constraint Node Features

It is worth noting that the AMILP is derived from a translation transformation
of the MILP, resulting 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 bias feature, representing the right-hand term, the
transformed feature is $b_{i}+\bm{a}_{i}^{\mathrm{T}}\bm{s}$. To obtain this
term, consider the $i$-th constraint node, which corresponds to the $i$-th
constraint of $\bm{a_{i}}^{\mathrm{T}}\bm{x}\leqslant b_{i}$, After
translation, this constraint can be represented as
$\bm{a}_{i}\hat{\bm{x}}\leqslant b_{i}+\bm{a}_{i}^{\mathrm{T}}\bm{s}$, leading
to the bias feature $b_{i}+\bm{a}_{i}^{\mathrm{T}}\bm{s}$. For dualsol_val
feature, we consider proposing the following theorem for the explanation.

######  Theorem 3.2.

For MILPs Eq.(1) and AMILPs Eq.(3), let the optimal solution of the dual
problem of the LP relaxations be denoted as $\bm{y}^{*}$ and
$\hat{\bm{y}}^{*}$, respectively. Then, a direct correspondence exists between
these solutions, indicating that $\bm{y}^{*}=\hat{\bm{y}}^{*}$.

The proof can be found in the Appendix. From Theorem 3.2, we can conclude that
the dualsol_val feature of the augmented bipartite graph remains unchanged
compared to the original bipartite graph. Thus, we 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 is 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 in 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 LP age. For reduced_cost
features, we consider the following theorem for clarification.

######  Theorem 3.3.

For MILPs Eq.(1) and their corresponding AMILPs Eq.(3), consider the reduced
cost corresponding to LP relaxations for a MILP, denoted as $\sigma_{i}$, and
for an AMILP, denoted as $\hat{\sigma}_{i}$. Then, a direct correspondence
exists between these reduced costs, implying that
$\sigma_{i}=\hat{\sigma}_{i}$.

The proof is provided in the Appendix. Moreover, the features sol_val,
inc_val, and 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 et al., 2022; Iter et al., 2020;
Giorgi et al., 2021; Yu et al., 2022). The fundamental 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 a 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 a MILP bipartite graph
$\left(\mathcal{G}_{\text{ori }},\mathbf{C}_{\text{ori
}},\mathbf{E}_{\text{ori }},\mathbf{V}_{\text{ori }}\right)$ and its augmented
counterpart $\left(\mathcal{G}_{\text{aug }},\mathbf{C}_{\text{aug
}},\mathbf{E}_{\text{aug }},\mathbf{V}_{\text{aug }}\right)$. These graphs
undergo processing with a GCNN, following the message passing illustrated in
Eq.(2). This results in updated constraint and variable node features
$\mathbf{C}_{\text{ori }}^{\prime}$ and $\mathbf{V}_{\text{ori}}^{\prime}$ for
the MILP, along with $\mathbf{C}_{\text{aug }}^{\prime}$ and
$\mathbf{V}_{\text{aug }}^{\prime}$ for the AMILP. Subsequently, we generate
graph-level representations for both bipartite graphs. To achieve this, we
conduct max and average pooling on the constraint nodes and variable nodes,
respectively. Merging these embeddings using an MLP yields pooled embeddings
for constraint and variable nodes, denoted as $\bm{c}_{\text{ori
}}^{\mathcal{G}},\bm{v}_{\text{ori }}^{\mathcal{G}}$ for the MILP and
$\bm{c}_{\text{ori }}^{\mathcal{G}},\bm{v}_{\text{ori }}^{\mathcal{G}}$ for
the AMILP. These embeddings serve as inputs to another MLP, resulting in
graph-level embeddings $\bm{g}_{\text{ori}}$ and $\bm{g}_{\text{aug}}$ for
MILP and AMILP bipartite graphs, respectively. To train our model using
contrastive learning, we treat $\bm{g}_{\text{ori }}$ and its corresponding
$\bm{g}_{\mathrm{aug}}$ as positive pairs, while considering other AMILPs in
the same batch as negative samples. By applying infoNCE (van den Oord et al.,
2018) loss, we have

$\mathcal{L}^{(\text{infoNCE })}=-\sum_{i=1}^{n_{\text{batch
}}}\log\left(\frac{\exp\left(\tilde{\bm{g}}_{\text{ori
}}^{\mathrm{T}}(i)\cdot\tilde{\bm{g}}_{\text{aug
}}(i)\right)}{\sum_{j=1}^{n_{\text{batch
}}}\exp\left(\tilde{\bm{g}}_{\text{ori
}}^{\mathrm{T}}(i)\cdot\tilde{\bm{g}}_{\text{aug }}(j)\right)}\right)$ (8)

where $n_{\text{batch }}$ represents the number of samples in a training
batch. $\tilde{\bm{g}}_{\text{ori }}$ and $\tilde{\bm{g}}_{\text{aug }}$
denote the normalized vectors of $\bm{g}_{\text{ori }}$ and
$\bm{g}_{\mathrm{aug}}$, 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 et al. (2019). More details can be found in the Appendix
C.3.

##  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.e., Set Covering (BALAS, 1980), Combinatorial Auction
(Leyton-Brown et al., 2000), Capacitated Facility 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
models 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
1 hour. See more details in the supplementary materials.

Baselines. We compare CAMBranch with the following branching strategies: (1)
Reliability Pseudocost Branching (RPB) (Achterberg et al., 2005), a state-of-
the-art human-designed branching policy 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 et al. (2019), we train 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 metrics are standard for MILP
benchmarking, including solving time, number of 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.e., the number of nodes) generated during
the solving process.

####  4.2.1 Imitation Learning Accuracy

First, we initiated our evaluation by comparing CAMBranch with baseline
methods in terms of imitation learning accuracy. Following Gasse et al.
(2019), we curated a test set comprising 20k expert samples for each problem.
The results are depicted in Figure 1. Notably, CAMBranch, 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., 2019) 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

Figure 1: Imitation learning accuracy on the test sets of expert samples.

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 Table 2.

Solving time reflects the efficiency of each model in solving MILP instances.
As evident in Table 2, we observed that as problem complexity 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 a maximum gap of about 5 seconds. However, for the Medium and Hard
levels, differences become more significant. Notably, delving into each
strategy, we found that, neural network-based policies consistently outperform
the traditional RPB, demonstrating the potential of replacing heuristic
methods with machine learning-based approaches. Moreover, CAMBranch exhibits
the fastest solving process in 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.

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. CAMBranch 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 network. However, it’s worth noting that in some cases, RPB generates
the fewest nodes, particularly in the Capacitated Facility Location problem.
Nevertheless, this doesn’t translate into shorter solving times, as certain
RPB decisions are time-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 instance level. From Table 2, we 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 metric.
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 prominent performance across these three
metrics underscores the importance of MILP augmentation and the effectiveness
of our contrastive learning framework.

Table 2: Policy evaluation in terms of solving time, number of B&B nodes, and
number of wins over number of solved instances on 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.

| Easy | Medium | Hard
---|---|---|---
Model | Time | Wins | Nodes | Time | Wins | Nodes | Time | Wins | Nodes
FSB | 17.98 | 0/100 | 27 | 345.91 | 0/90 | 223 | 3600.00 | - | -
RPB | 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 |
FSB | 34.94 | 0/100 | 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 |
FSB | 28.85 | 10/100 | 19 | 1219.15 | 0/62 | 81 | 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 | 5041 | 1020.58 | 0/17 | 21925
GCNN (10%) | 7.18 | 26/100 | 103 | 122.65 | 8/89 | 3711 | 695.96 | 2/20 | 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 of Data Collection Efficiency

In this part, we compared the efficiency of expert sample collection for GCNN
in Gasse et al. (2019) and our proposed CAMBranch. We focused on the
Capacitated Facility Location Problem, which exhibits the lowest collection
efficiency among the four MILP benchmarks and thus closely simulates 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 quantity 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.

###  4.3 Ablation Studies

To further validate the effectiveness of contrastive learning, we conducted
ablation studies. Specifically, we compared the performance of CAMBranch with
contrastive learning to CAMBranch without contrastive learning but with data
augmentation, denoted as CAMBranch w/o CL. These experiments 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 of the
efficacy of this integration within CAMBranch.

Figure 2: Ablation experiment results on CAMBranch (10%) for instance solving
evaluation, including solving time (a), number of nodes (b), and number of
wins (c), in addition to imitation learning accuracy (d) for the Set Covering
problem.

###  4.4 Evaluating CAMBranch on Full Datasets

Previous experiments have showcased CAMBranch’s superiority in data-scarce
scenarios. To further explore CAMBranch’s potential, we conducted evaluations
on complete datasets to assess its performance with the entire training data.
Table 3 presents the results of instance-solving evaluations 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
CAMBranch 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.

Model | Easy | Medium | Hard
---|---|---|---
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

##  5 Conclusion

In this paper, we have introduced CAMBranch, a novel framework designed to
address the challenge of collecting expert strategy samples for imitation
learning when applying machine learning techniques to solve MILPs. By
introducing variable shifting, CAMBranch generates AMILPs from the original
MILPs, harnessing the collective power of both to enhance imitation learning.
Our utilization 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 combinatorial optimization
problems and observed that CAMBranch exhibits superior performance, even when
trained on only 10% of the complete dataset. This underscores the potential of
CAMBranch, especially in scenarios with limited training data.

## acknowledgement

This work is supported by National Key R&D Program of China (Grant
No.2021YFC2902701).

## References

  * Achterberg et al. (2005) Tobias Achterberg, Thorsten Koch, and Alexander Martin.  Branching rules revisited.  _Oper. Res. Lett._ , 33(1):42–54, 2005.  doi: 10.1016/j.orl.2004.04.002.  URL https://doi.org/10.1016/j.orl.2004.04.002.
  * Agarap (2018) Abien Fred Agarap.  Deep learning using rectified linear units (relu).  _CoRR_ , abs/1803.08375, 2018.  URL http://arxiv.org/abs/1803.08375.
  * Almeida et al. (2006) Renato T. R. Almeida, Luiz C. de Calmon, Elias Olivieira, and Marcelo Eduardo Vieira Segatto.  Design of virtual topologies for large optical networks through an efficient MILP formulation.  _Opt. Switch. Netw._ , 3(1):2–10, 2006.  doi: 10.1016/j.osn.2005.10.002.  URL https://doi.org/10.1016/j.osn.2005.10.002.
  * Alvarez et al. (2017) Alejandro Marcos Alvarez, Quentin Louveaux, and Louis Wehenkel.  A machine learning-based approximation of strong branching.  _INFORMS J. Comput._ , 29(1):185–195, 2017.  doi: 10.1287/ijoc.2016.0723.  URL https://doi.org/10.1287/ijoc.2016.0723.
  * Applegate et al. (1995) David Applegate, Robert Bixby, Vašek Chvátal, and William Cook.  _Finding cuts in the TSP (A preliminary report)_ , volume 95.  Citeseer, 1995.
  * Arora et al. (2019) Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saunshi.  A theoretical analysis of contrastive unsupervised representation learning.  _arXiv preprint arXiv:1902.09229_ , 2019.
  * BALAS (1980) E BALAS.  Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study.  _Mathematical Programming Study_ , 12:37–60, 1980.
  * Balcan et al. (2018) Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik.  Learning to 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 http://proceedings.mlr.press/v80/balcan18a.html.
  * Bao & Wang (2017) Tianpeng Bao and Huangang Wang.  Cyclic scheduling of multi-cluster tools based on mixed integer programming.  _IEEE Transactions on Semiconductor Manufacturing_ , 30(4):515–525, 2017.
  * Bengio et al. (2021) Yoshua Bengio, Andrea Lodi, and Antoine Prouvost.  Machine learning for combinatorial optimization: A methodological tour d’horizon.  _Eur. J. Oper. Res._ , 290(2):405–421, 2021.  doi: 10.1016/j.ejor.2020.07.063.  URL https://doi.org/10.1016/j.ejor.2020.07.063.
  * Caron et al. (2020) 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, 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 https://proceedings.neurips.cc/paper/2020/hash/70feb62b69f16e0238f741fab228fec2-Abstract.html.
  * Chen et al. (2020a) Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey E. Hinton.  A simple framework for contrastive learning of visual representations.  In _Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event_ , volume 119 of _Proceedings of Machine Learning Research_ , pp. 1597–1607. PMLR, 2020a.  URL http://proceedings.mlr.press/v119/chen20j.html.
  * Chen et al. (2020b) Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E. Hinton.  Big self-supervised models are strong semi-supervised learners.  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_ , 2020b.  URL https://proceedings.neurips.cc/paper/2020/hash/fcbc95ccdd551da181207c0c1400c655-Abstract.html.
  * Chen & He (2021) Xinlei Chen and Kaiming He.  Exploring simple siamese representation learning.  In _IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2021, virtual, June 19-25, 2021_ , pp. 15750–15758. Computer Vision Foundation / IEEE, 2021.  doi: 10.1109/CVPR46437.2021.01549.  URL https://openaccess.thecvf.com/content/CVPR2021/html/Chen_Exploring_Simple_Siamese_Representation_Learning_CVPR_2021_paper.html.
  * Chen et al. (2020c) Xinlei Chen, Haoqi Fan, Ross B. Girshick, and Kaiming He.  Improved baselines with momentum contrastive learning.  _CoRR_ , abs/2003.04297, 2020c.  URL https://arxiv.org/abs/2003.04297.
  * Cire & Augusto (2015) Cire and Andre Augusto.  Decision diagrams for optimization.  _Constraints_ , 20(4):494–495, 2015.
  * Cornuejols et al. (1991) G. Cornuejols, R. Sridharan, and J. M. Thizy.  A comparison of heuristics and relaxations for the capacitated plant location problem.  _European Journal of Operational Research_ , 50(3):280–297, 1991.
  * Dey et al. (2023) Santanu S Dey, Yatharth Dubey, Marco Molinaro, and Prachi Shah.  A theoretical and computational analysis of full strong-branching.  _Mathematical Programming_ , pp. 1–34, 2023.
  * Falcon & Cho (2020) William Falcon and Kyunghyun Cho.  A framework for contrastive self-supervised learning and designing A new approach.  _CoRR_ , abs/2009.00104, 2020.  URL https://arxiv.org/abs/2009.00104.
  * Fang & Xie (2020) Hongchao Fang and Pengtao Xie.  CERT: contrastive self-supervised learning for language understanding.  _CoRR_ , abs/2005.12766, 2020.  URL https://arxiv.org/abs/2005.12766.
  * Fey & Lenssen (2019) Matthias Fey and Jan Eric Lenssen.  Fast graph representation learning with pytorch geometric.  _CoRR_ , abs/1903.02428, 2019.  URL http://arxiv.org/abs/1903.02428.
  * Gamrath et al. (2020) Gerald Gamrath, Timo Berthold, and Domenico Salvagnin.  An exploratory computational analysis of dual degeneracy in mixed-integer programming.  _EURO J. Comput. Optim._ , 8(3):241–261, 2020.  doi: 10.1007/s13675-020-00130-z.  URL https://doi.org/10.1007/s13675-020-00130-z.
  * Gasse et al. (2019) Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi.  Exact combinatorial 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 on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , pp. 15554–15566, 2019.  URL https://proceedings.neurips.cc/paper/2019/hash/d14c2267d848abeb81fd590f371d39bd-Abstract.html.
  * Gilmer et al. (2017) 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 http://proceedings.mlr.press/v70/gilmer17a.html.
  * Giorgi et al. (2021) John M. Giorgi, Osvald Nitski, Bo Wang, and Gary D. Bader.  Declutr: Deep contrastive learning 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 Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, ACL/IJCNLP 2021, (Volume 1: Long Papers), Virtual Event, August 1-6, 2021_ , pp. 879–895. Association for Computational Linguistics, 2021.  doi: 10.18653/v1/2021.acl-long.72.  URL https://doi.org/10.18653/v1/2021.acl-long.72.
  * Gleixner et al. (2018) Ambros Gleixner, Michael Bastubbe, Leon Eifler, Tristan Gally, Gerald Gamrath, Robert Lion Gottwald, Gregor Hendel, Christopher Hojny, Thorsten Koch, Marco E. Lübbecke, Stephen J. Maher, Matthias Miltenberger, Benjamin Müller, Marc E. Pfetsch, Christian Puchert, Daniel Rehfeldt, Franziska Schlösser, Christoph Schubert, Felipe Serrano, Yuji Shinano, Jan Merlin Viernickel, Matthias Walter, Fabian Wegscheider, Jonas T. Witt, and Jakob Witzig.  The SCIP Optimization Suite 6.0.  Technical report, Optimization Online, July 2018.  URL http://www.optimization-online.org/DB_HTML/2018/07/6692.html.
  * Godart et al. (2018) 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.
  * Grill et al. (2020) 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 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 https://proceedings.neurips.cc/paper/2020/hash/f3ada80d5c4ee70142b17b8192b2958e-Abstract.html.
  * Gupta et al. (2020) 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 https://proceedings.neurips.cc/paper/2020/hash/d1e946f4e67db4b362ad23818a6fb78a-Abstract.html.
  * Hait & Artigues (2011) 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.
  * He et al. (2020) 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–9735. Computer Vision Foundation / IEEE, 2020.  doi: 10.1109/CVPR42600.2020.00975.  URL https://doi.org/10.1109/CVPR42600.2020.00975.
  * Iter et al. (2020) 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/2020.acl-main.439.  URL https://doi.org/10.18653/v1/2020.acl-main.439.
  * Khalil et al. (2017) Elias B. Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song.  Learning combinatorial 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 on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA_ , pp. 6348–6358, 2017.  URL https://proceedings.neurips.cc/paper/2017/hash/d9896106ca98d3d05b8cbdf4fd8b13a1-Abstract.html.
  * Khalil et al. (2016) 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/aaai.v30i1.10080.  URL https://doi.org/10.1609/aaai.v30i1.10080.
  * Kilinç-Karzan et al. (2009) Fatma Kilinç-Karzan, George L. Nemhauser, and Martin W. P. Savelsbergh.  Information-based branching schemes for binary linear mixed integer problems.  _Math. Program. Comput._ , 1(4):249–293, 2009.  doi: 10.1007/s12532-009-0009-1.  URL https://doi.org/10.1007/s12532-009-0009-1.
  * Kingma & Ba (2015) Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In Yoshua Bengio and Yann LeCun (eds.), _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_ , 2015.  URL http://arxiv.org/abs/1412.6980.
  * Kipf & Welling (2017) Thomas N. Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  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/forum?id=SJU4ayYgl.
  * Land & Doig (1960) AH Land and AG Doig.  An automatic method of solving discrete programming problems.  _Econometrica_ , 28(3):497–520, 1960.
  * Leyton-Brown et al. (2000) Kevin Leyton-Brown, Mark Pearson, and Yoav Shoham.  Towards a universal test suite for combinatorial auction algorithms.  In Anant Jhingran, Jeff MacKie-Mason, and Doug J. Tygar (eds.), _Proceedings of the 2nd ACM Conference on Electronic Commerce (EC-00), Minneapolis, MN, USA, October 17-20, 2000_ , pp. 66–76. ACM, 2000.  doi: 10.1145/352871.352879.  URL https://doi.org/10.1145/352871.352879.
  * Lin et al. (2022) 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.1016/j.knosys.2022.109455.  URL https://doi.org/10.1016/j.knosys.2022.109455.
  * Matteo Fischetti (2012) Michele Monaci Matteo Fischetti.  Branching on nonchimerical fractionalities.  _Operations Research Letters_ , 40(3):159–164, 2012.
  * Mikolov et al. (2013) 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 Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States_ , pp. 3111–3119, 2013.  URL https://proceedings.neurips.cc/paper/2013/hash/9aa42b31882ec039965f3c4923ce901b-Abstract.html.
  * Nair et al. (2020) Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O’Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, Ravichandra Addanki, Tharindi Hapuarachchi, Thomas Keck, James Keeling, Pushmeet Kohli, Ira Ktena, Yujia Li, Oriol Vinyals, and Yori Zwols.  Solving mixed integer programs using neural networks.  _CoRR_ , abs/2012.13349, 2020.  URL https://arxiv.org/abs/2012.13349.
  * Orbach (1962) J Orbach.  Principles of neurodynamics. perceptrons and the theory of brain mechanisms.  _Archives of General Psychiatry_ , 7(3):218–219, 1962.
  * P. et al. (2020) Khosla P., Teterwak P., and Wang C.  Supervised contrastive learning.  _Advances in Neural Information Processing Systems_ , 33:18661–18673, 2020.
  * Paszke et al. (2019) 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.  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 on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , pp. 8024–8035, 2019.  URL https://proceedings.neurips.cc/paper/2019/hash/bdbca288fee7f92f2bfa9f7012727740-Abstract.html.
  * Pomerleau (1991) Dean Pomerleau.  Efficient training of artificial neural networks for autonomous navigation.  _Neural Comput._ , 3(1):88–97, 1991.  doi: 10.1162/neco.1991.3.1.88.  URL https://doi.org/10.1162/neco.1991.3.1.88.
  * Scavuzzo et al. (2022) Lara Scavuzzo, Feng Yang Chen, Didier Chételat, Maxime Gasse, Andrea Lodi, Neil Yorke-Smith, and Karen I. Aardal.  Learning to branch with tree mdps.  In _NeurIPS_ , 2022.  URL http://papers.nips.cc/paper_files/paper/2022/hash/756d74cd58592849c904421e3b2ec7a4-Abstract-Conference.html.
  * Soylu et al. (2006) Ahu Soylu, Cihan Oruç, Metin Turkay, Kaoru Fujita, and Tatsuyuki Asakura.  Synergy analysis of collaborative supply chain management in energy systems using multi-period milp.  _European Journal of Operational Research_ , 174(1):387–403, 2006.
  * van den Oord et al. (2018) Aäron van den Oord, Yazhe Li, and Oriol Vinyals.  Representation learning with contrastive predictive coding.  _CoRR_ , abs/1807.03748, 2018.  URL http://arxiv.org/abs/1807.03748.
  * Xu et al. (2022) 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.
  * Yu et al. (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.  In Enrique 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 Development in Information Retrieval, Madrid, Spain, July 11 - 15, 2022_ , pp. 1294–1303. ACM, 2022.  doi: 10.1145/3477495.3531937.  URL https://doi.org/10.1145/3477495.3531937.
  * Zarpellon et al. (2021) 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, Virtual Event, February 2-9, 2021_ , pp. 3931–3939. AAAI Press, 2021.  doi: 10.1609/aaai.v35i5.16512.  URL https://doi.org/10.1609/aaai.v35i5.16512.
  * Zhang et al. (2023) Jiayi Zhang, Chang Liu, Xijun Li, Hui-Ling Zhen, Mingxuan Yuan, Yawen Li, and Junchi Yan.  A survey for solving mixed integer programming via machine learning.  _Neurocomputing_ , 519:205–217, 2023.  doi: 10.1016/j.neucom.2022.11.024.  URL https://doi.org/10.1016/j.neucom.2022.11.024.

1Contents

##  Appendix A Background

###  A.1 Branch and Bound (B&B)

The B&B algorithm operates in an iterative way at each node. It commences with
solving the LP relaxation of the original MILP problem Eq. (1). This LP
relaxation serves as a lower bound estimate for the original MILP (1). If the
optimal solution $\bm{x}^{*}$ of this LP relaxation satisfies all the
constraints in (1), its objective value provides an upper bound estimate for
the original problem. However, if $\bm{x}^{*}$ contains non-integer variables
$x_{j}^{*}$ (where $j\in\mathcal{I}$), the algorithm proceeds by splitting the
problem into two sub-problems, each with additional constraints:
$x_{j}\leq\left\lfloor x_{j}^{*}\right\rfloor$ and $x_{j}\geq\left\lceil
x_{j}^{*}\right\rceil$, where $\left\lfloor.\right\rfloor$ and
$\left\lceil.\right\rceil$ 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 computational efficiency. The
algorithm repeats the above process until either all nodes are pruned or the
optimality gap reaches a 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 candidate 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, solving their
respective Linear Programming (LP) relaxation problems, and then selecting the
variable that contributes the most to lower bound enhancement as the actual
branching variable. When pre-branching is applied to all available candidate
variables, and each LP relaxation problem is solved to optimality, this
strategy is known as Full Strong Branching (FSB), which is the expert strategy
for imitation learning in this paper. Essentially, Full Strong Branching can
be seen as a greedy approach aimed at 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 in the Strong
Branching strategy.

##  Appendix B Proofs

Lemma 3.1. For MILPs (Eq.(1)) and AMILPs (Eq.(3)), let the LP relaxation
optimal solutions be denoted as $\bm{x}^{*}$ and $\hat{\bm{x}}^{*}$,
respectively. Then, there exists a correspondence between these solutions such
that $\hat{\bm{x}}^{*}={\bm{x}}^{*}+\bm{s}$.

###### Proof.

The LP relaxation problems of MILP and AMILP can be expressed as follows:

$\displaystyle\bm{x}^{*}=\underset{\bm{x}}{\arg\min}\left\\{\bm{c}^{\mathrm{T}}\bm{x}\mid\bm{A}\bm{x}\leqslant\bm{b},\bm{l}\leqslant\bm{x}\leqslant\bm{u}\right\\}$
(9)

and

$\displaystyle\hat{\bm{x}}^{*}=\underset{\hat{\bm{x}}}{\arg\min}\left\\{\bm{c}^{\mathrm{T}}\hat{\bm{x}}-\bm{c}^{\mathrm{T}}\bm{s}\mid\bm{A}\hat{\bm{x}}\leqslant\hat{\bm{b}},\hat{\bm{l}}\leqslant\hat{\bm{x}}\leqslant\hat{\bm{u}}\right\\}$
(10)

We now assume that $\bm{y}={\bm{x}}^{*}+\bm{s}$, so that Eq.(9) can be written
as

$\displaystyle\bm{y}-\bm{s}=\underset{\bm{x}}{\arg\min}\left\\{\bm{c}^{\mathrm{T}}\bm{x}\mid\bm{A}\bm{x}\leqslant\bm{b},\bm{l}\leqslant\bm{x}\leqslant\bm{u}\right\\}$
(11)

which implies that

$\displaystyle\bm{y}$
$\displaystyle=\underset{\bm{x}}{\arg\min}\left\\{\bm{c}^{\mathrm{T}}\bm{x}\mid\bm{A}\bm{x}\leqslant\bm{b},\bm{l}\leqslant\bm{x}\leqslant\bm{u}\right\\}+\bm{s}$
(12)
$\displaystyle=\underset{\bm{x}}{\operatorname{\arg\min}}\left\\{\bm{c}^{\mathrm{T}}(\hat{\bm{x}}-\bm{s})\mid
A(\hat{\bm{x}}-\bm{s})\leqslant b,\bm{l}\leqslant\hat{\bm{x}}-\bm{s}\leq
u\right\\}+\bm{s}$
$\displaystyle=\underset{\bm{x}+\bm{s}}{\operatorname{\arg\min}}\left\\{\bm{c}^{\mathrm{T}}\hat{\bm{x}}-\bm{c}^{\mathrm{T}}\bm{s}\mid
A\hat{\bm{x}}\leq As+b,\bm{l}+\bm{s}\leqslant\hat{\bm{x}}\leqslant
u+\bm{s}\right\\}$

Clearly, Eq.(10) is equal to Eq.(12), that is,
$\hat{\bm{x}}^{*}={\bm{x}}^{*}+\bm{s}$. ∎

Theorem 3.1. For MILPs Eq.(1) and AMILPs Eq.(3), let the optimal solution of
the dual problem of the LP relaxation solution be denoted as $\bm{y}^{*}$ and
$\hat{\bm{y}}^{*}$, respectively. Then, there exists a correspondence between
these solutions such that $\bm{y}^{*}=\hat{\bm{y}}^{*}$.

###### Proof.

By incorporating the boundary constraints of variable $\bm{x}$ into the set of
other constraints, the MILP problem can be reformulated as the following LP
relaxation form

$\displaystyle\bm{x}^{*}=\arg\min_{\bm{x}}\\{\bm{c}^{\mathrm{T}}\bm{x}|\bar{\bm{A}}\bm{x}\leq\bm{b}\\}\
$ (13)

We can obtain its dual problem as follows

$\displaystyle\bm{y}^{*}=\arg\max_{\bm{y}}\\{-\bm{y}^{\rm T}\bm{b}|\bm{c}^{\rm
T}+\bm{y}^{\rm T}\bm{\bar{A}}=\bm{0},\bm{y}\geq\bm{0}\\}$ (14)

Similarly, for AMILPs, we also combine the boundary constraints of variable
$\hat{\bm{x}}^{*}$ with other constraints, then we have

$\displaystyle\bm{\hat{x}}^{*}=\arg\min_{\hat{x}}\\{\bm{c}^{\rm
T}\hat{\bm{x}}-\bm{c}^{\rm
T}\bm{s}|\bar{\bm{A}}\hat{\bm{x}}\leq\bm{b}+\bar{\bm{A}\bm{s}}\\}$ (15)

The dual problem of this AMILP can be obtained as follows:

$\displaystyle\hat{\bm{y}}^{*}$
$\displaystyle=\arg\max_{\hat{\bm{y}}}\\{-\hat{\bm{y}}^{\rm
T}(\bm{b}+\bar{\bm{A}}\bm{s})-\bm{c}^{\rm T}\bm{s}|\bm{c}^{\rm
T}+\hat{\bm{y}}^{\rm T}\bm{\bar{A}}=\bm{0},\hat{\bm{y}}\geq\bm{0}\\}$ (16)
$\displaystyle=\arg\max_{\hat{\bm{y}}}\\{-\hat{\bm{y}}^{\rm
T}\bm{b}|\bm{c}^{\rm T}+\hat{\bm{y}}^{\rm
T}\bm{\bar{A}}=\bm{0},\hat{\bm{y}}\geq\bm{0}\\}$

According to Eq.(14) and Eq.(16), it can 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.(1) and their corresponding AMILPs Eq.(3), let the
reduced cost corresponding to LP relaxations for a MILP and an AMILP be
denoted as $\sigma_{i}$ and $\hat{\sigma}_{i}$, respectively. Then, there is a
correspondence between these reduced costs such that
$\sigma_{i}=\hat{\sigma}_{i}$.

###### Proof.

Let’s consider the variable $x_{j}$ in the MILP. Its reduced cost, denoted as
$\sigma_{j}$, can be expressed as

$\sigma_{j}=c_{j}-\bm{c}_{\bm{B}}^{\mathrm{T}}\bm{B}^{-1}\hat{\bm{A}}_{j}$
(17)

Here, $\bm{B}$ represents the matrix composed of the column vectors of the
current basis, $\bm{c}_{\bm{B}}$ denotes the coefficient vector of the
objective function at basic variables, and $\hat{\bm{A}}_{j}$ represents the
$j$th column of the matrix $\hat{\bm{A}}$. Similarly, for the AMILP, the
reduced cost of variable $\hat{\bm{x}}$, denoted as $\hat{\sigma}_{j}$, can be
expressed in the same way:

$\hat{\sigma}_{j}=c_{j}-\bm{c}_{\bm{B}}^{\mathrm{T}}\bm{B}^{-1}\hat{\bm{A}}_{j}=\sigma_{j}$
(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. ∎

##  Appendix C Methodology Details

###  C.1 Overview of Bipartite Graph Node Features

The relationships between MILP and AMILP node features are illustrated in
Table 4 for constraint nodes and Table 5 for variable nodes. Note that in
Table 5, the notation $\mathbb{B}\leftrightarrow\mathbb{Z}$ denotes the
potential mutual conversion between binary variables and integer variables.

Table 4: Relationship between MILP and AMILP constraint node features. Node feature of constraint $i$ | MILP | AMILP
---|---|---
obj_cos_sim | $\mathbf{C}_{i,1}$ | $\mathbf{C}_{i,1}$
bias | $\mathbf{C}_{i,2}$ | $\mathbf{C}_{i,2}+\bm{a}_{i}^{\mathrm{T}}\bm{s}$
is_tight | $\mathbf{C}_{i,3}$ | $\mathbf{C}_{i,3}$
dualsol_val | $\mathbf{C}_{i,4}$ | $\mathbf{C}_{i,4}$
age | $\mathbf{C}_{i,5}$ | $\mathbf{C}_{i,5}$
Table 5: Relationship between MILP and AMILP variable node features. Node feature of variable $j$ | MILP | AMILP
---|---|---
type | $\mathbf{V}_{j,1}$ | $\mathbf{V}_{j,1}\hskip 2.84544pt{\rm or}\hskip 2.84544pt\mathbb{B}\leftrightarrow\mathbb{Z}$
coef | $\mathbf{V}_{j,2}$ | $\mathbf{V}_{j,2}$
has_lb | $\mathbf{V}_{j,3}$ | $\mathbf{V}_{j,3}$
has_ub | $\mathbf{V}_{j,4}$ | $\mathbf{V}_{j,4}$
sol_is_at_lb | $\mathbf{V}_{j,5}$ | $\mathbf{V}_{j,5}$
sol_is_at_ub | $\mathbf{V}_{j,6}$ | $\mathbf{V}_{j,6}$
sol_frac | $\mathbf{V}_{j,7}$ | $\mathbf{V}_{j,7}$
basis_status | $\mathbf{V}_{j,8}$ | $\mathbf{V}_{j,8}$
reduced_cost | $\mathbf{V}_{j,9}$ | $\mathbf{V}_{j,9}$
age | $\mathbf{V}_{j,10}$ | $\mathbf{V}_{j,10}$
sol_val | $\mathbf{V}_{j,11}$ | $\mathbf{V}_{j,11}+s_{j}$
inc_val | $\mathbf{V}_{j,12}$ | $\mathbf{V}_{j,11}+s_{j}$
avg_inc_val | $\mathbf{V}_{j,13}$ | $\mathbf{V}_{j,13}+s_{j}$

###  C.2 Contrastive Learning

This section will provide details the forward propagation process.
Specifically, once we have acquired the updated constraint and variable node
features $\mathbf{C}_{\text{ori }}^{\prime}$ and
$\mathbf{V}_{\text{ori}}^{\prime}$ for the MILP, along with
$\mathbf{C}_{\text{aug }}^{\prime}$ and $\mathbf{V}_{\text{aug }}^{\prime}$
for the AMILP, we can formulate the feature merging process as follows:

$\bm{c}_{\text{ori
}}^{\mathcal{G}}=\operatorname{MLP}\left(\operatorname{Concat}\left(\operatorname{MaxPool}\left(\mathbf{C}_{\text{ori
}}^{\prime}\right),\operatorname{MeanPool}\left(\mathbf{C}_{\text{ori
}}^{\prime}\right)\right)\right)$ (19) $\bm{v}_{\text{ori
}}^{\mathcal{G}}=\operatorname{MLP}\left(\operatorname{Concat}\left(\operatorname{MaxPool}\left(\mathbf{V}_{\text{ori
}}^{\prime}\right),\operatorname{MeanPool}\left(\mathbf{V}_{\text{ori
}}^{\prime}\right)\right)\right)$ (20)
$\bm{c}_{\mathrm{aug}}^{\mathcal{G}}=\operatorname{MLP}\left(\operatorname{Concat}\left(\operatorname{MaxPool}\left(\mathbf{C}_{\mathrm{aug}}^{\prime}\right),\operatorname{MeanPool}\left(\mathbf{C}_{\mathrm{aug}}^{\prime}\right)\right)\right)$
(21)
$\bm{v}_{\mathrm{aug}}^{\mathcal{G}}=\operatorname{MLP}\left(\operatorname{Concat}\left(\operatorname{MaxPool}\left(\mathbf{V}_{\mathrm{aug}}^{\prime}\right),\operatorname{MeanPool}\left(\mathbf{V}_{\mathrm{aug}}^{\prime}\right)\right)\right)$
(22)

where ${\rm Concat}$ denotes the concatenation operation. The process of
obtaining graph-level embeddings can be formulated as follows:

$\displaystyle\bm{g}_{\text{ori
}}=\operatorname{MLP}\left(\operatorname{Concat}\left(\bm{c}_{\text{ori
}}^{\mathcal{G}},\bm{v}_{\text{ori
}}^{\mathcal{G}}\right)\right)~{}~{}~{}~{}~{}\bm{g}_{\text{aug
}}=\operatorname{MLP}\left(\operatorname{Concat}\left(\bm{c}_{\mathrm{aug}}^{\mathcal{G}},\bm{v}_{\text{aug
}}^{\mathcal{G}}\right)\right)$ (23)

where $\bm{g}_{\text{ori}}$ and $\bm{g}_{\text{aug}}$ 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 to
apply contrastive learning in the subsequent steps.

###  C.3 Imitation Learning Training Procedure

We employ behavior cloning Pomerleau (1991) to train the CAMBranch, focusing
on imitating Strong Branching policies. Expert strategies are collected using
the optimization suite SCIP Gleixner et al. (2018) and are stored in a dataset
that consists of expert state-action pairs, denoted as
$\mathcal{D}=\left(\mathbf{s}_{i},\mathbf{a}_{i}^{*}\right)_{i=1}^{N}$. Within
this dataset, $\mathbf{s}_{i}=(\mathcal{G},\mathbf{C},\mathbf{E},\mathbf{V})$,
while $\mathbf{a}_{i}^{*}$ represents the branch decision of Strong Branching
strategy under $s_{t}$. To optimize the network, cross-entropy is used as a
supervised learning loss function

$\mathcal{L}^{(\text{sup
})}=-\frac{1}{N}\sum_{\left(\mathbf{s}_{i},\mathbf{a}_{i}^{*}\right)\in
D}\log\pi_{\theta}\left(\mathbf{a}_{i}^{*}\mid\mathbf{s}_{i}\right)$ (24)

In addition, to enhance the consistency in the probability distribution of
variable selection between the MILP and the AMILP, we incorporate consistency
constraints. Specifically, we extract the probability distribution
$\bm{P}_{\text{ori }}$ and $\bm{P}_{\text{aug }}$ of variables outputted by
MILP and the AMILP, respectively. The aim is to minimize the divergence
between these two distributions, i.e.

$\mathcal{L}^{(\text{Aux })}=\sum_{i=1}^{n_{\text{batch
}}}\left(\bm{P}_{\text{ori }}(i)-\bm{P}_{\mathrm{aug}}(i)\right)^{2}$ (25)

Finally, the final loss function by combining the three loss above is obtained

$\mathcal{L}=\mathcal{L}^{(\text{sup})}+\lambda_{1}\mathcal{L}^{(\text{infoNCE)
}}+\lambda_{2}\mathcal{L}^{(\text{Aux})}$ (26)

Where $\lambda_{1}$ and $\lambda_{2}$ are hyperparameters used to adjust the
weights between loss functions.

##  Appendix 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 graphics
cards.

####  D.1.1 Data Collection and Split

In our experiments, we conducted a systematic investigation of our model’s
performance by categorizing 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. (2019).

####  D.1.2 Solver Configuration

In our experiments, we employed the open-source solver SCIP (version 6.0.1)
(Gleixner et al., 2018) as our backend solver. We imposed a maximum solving
time limit of 3600 seconds, allowing cut generation operations solely at the
root node while disabling solver restarts. To ensure a fair comparison among
the methods, we maintained all other solver parameters at their default values
Khalil et al. (2016); Kilinç-Karzan et al. (2009); Matteo Fischetti (2012).

####  D.1.3 Training Parameters

In our experiments, we implemented models using PyTorch (Paszke et al., 2019)
and PyTorch Geometric (Fey & Lenssen, 2019). We utilized the Adam optimizer
Kingma & Ba (2015) with $\beta_{1}=0.9$ and $\beta_{2}=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 a grid search for the learning
rate, considering values from $\\{1\times 10^{-3},5\times 10^{-4},1\times
10^{-4}\\}$. Additionally, we selected the weight values $\lambda_{1}=0.05$
and $\lambda_{2}=0.01$ for the loss function.

####  D.1.4 Metrics

We evaluate performance using the shift geometric 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 a set of $n$ numbers, denoted as
$t_{1},t_{2},\ldots,t_{n}$, with $s$ representing the shift. The SGM formula
is given by $\mathrm{SGM}=\sqrt[n]{\prod_{i=1}^{n}(t_{i}+s)}-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, $s$ is set to 1 for time and 100 for Nodes,
following the previous work (Gasse et al., 2019; Zarpellon et al., 2021).

###  D.2 Additional Results

Our results are also presented in a tabular format, available in Table 6 for
imitation learning accuracy, Table 7 and Table 8 for the ablation study.
Additionally, we delve into the influence of varying the training sample ratio
on performance. Given that our proposed CAMBranch requires additional
computations compared to the original GCNN in Gasse et al. (2019), we also
evaluated the training overhead of these models.

Table 6: Imitation learning accuracy on the test sets of expert samples.

Model | Set Covering | Combinatorial Auction | Capacitated Facility Location | Maximum Independent Set
---|---|---|---|---
acc@1 | acc@5 | acc@10 | acc@1 | acc@5 | acc@10 | acc@1 | acc@5 | acc@10 | acc@1 | acc@5 | acc@10
GCNN | 70.39 $\pm$ 0.28 | 93.09 $\pm$ 0.14 | 98.40 $\pm$ 0.09 | 68.95 $\pm$ 0.32 | 92.79 $\pm$ 0.16 | 97.87 $\pm$ 0.09 | 61.70 $\pm$ 0.23 | 95.48 $\pm$ 0.12 | 99.68 $\pm$ 0.01 | 80.70 $\pm$ 0.72 | 92.78 $\pm$ 0.19 | 95.83 $\pm$ 0.22
GCNN (10 %) | 58.98 $\pm$ 0.69 | 82.97 $\pm$ 0.52 | 91.61 $\pm$ 0.44 | 64.44 $\pm$ 0.90 | 90.37 $\pm$ 0.17 | 96.70 $\pm$ 0.08 | 59.20 $\pm$ 0.21 | 95.10 $\pm$ 0.08 | 99.68 $\pm$ 0.02 | 75.36 $\pm$ 0.45 | 90.84 $\pm$ 0.39 | 94.39 $\pm$ 0.30
CAMBranch | 65.27 $\pm$ 3.92 | 89.46 $\pm$ 2.98 | 96.14 $\pm$ 1.90 | 67.85 $\pm$ 0.97 | 91.52 $\pm$ 0.50 | 97.14 $\pm$ 0.39 | 60.50 $\pm$ 0.30 | 95.24 $\pm$ 0.13 | 99.64 $\pm$ 0.01 | 80.38 $\pm$ 0.11 | 92.34 $\pm$ 0.20 | 95.47 $\pm$ 0.20

Table 7: Results of ablation experiments on imitation learning accuracy in Set Covering. Type | $\operatorname{acc}@1$ | $\operatorname{acc}@5$ | $\operatorname{acc}@10$
---|---|---|---
CAMBranch w/o CL (10%) | 64.75 $\pm$ 1.43 | 88.94 $\pm$ 1.31 | 96.16 $\pm$ 0.72
CAMBranch (10%) | 65.27 $\pm$ 3.92 | 89.46 $\pm$ 2.98 | 96.14 $\pm$ 1.90
Table 8: Results of ablation experiments on instance solving evaluation in Set
Covering.

Model | Easy | Medium | Hard
---|---|---|---
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 | 69215
CAMBranch (10%) | 6.79 | 23/100 | 188 | 61.00 | 78/100 | 2339 | 1427.02 | 32/55 | 66943

####  D.2.1 Analysis of Impact of Training Sample Ratios

To investigate the influence of training sample ratios, we conducted
experiments using subsets comprising 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 9. Our observations
indicate that as the problem’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.
Similar trends are evident on the Maximum Independent Set problem (Table 10),
especially in the Hard level instances. As shown in Table 10, the performance
on Hard instances improves with larger sample sizes, with reduced solving time
and a lower number of nodes. Notably, CAMBranch (20%) achieved the highest
number of solved instances in the Hard level, 49 instances in total,
underscoring 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 9: The results of sample ratio analysis on the instance solving
evaluation for Combinatorial Auction.

Model | Easy | Medium | Hard
---|---|---|---
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 | 91 | 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.

Model | Easy | Medium | Hard
---|---|---|---
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 | 103 | 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 | 92 | 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

Table 11: Results of training time per batch of GCNN and CAMBranch on the Set Covering problem. Each batch contains 64 samples. Model | Training time per batch (s)
---|---
CAMBranch (10%) | 0.09666
GCNN (10%) | 0.09216

Since our proposed CAMBranch introduces additional computation, we further
assessed the training overhead of CAMBranch and GCNN proposed in Gasse et al.
(2019). Table 11 demonstrates that, despite the introduced computation by
CAMBranch, the observed difference in computational speed is deemed
acceptable—merely a matter of several milliseconds. In summary, the training
overhead associated with CAMBranch is within acceptable bounds.

##  Appendix E Discussion

###  E.1 When to Use CAMBranch?

Table 12: Results for the impacts of expert sample size and MILP instance
count.

Exp ID | Training Data | Easy | Medium | Hard
---|---|---|---|---
Time | Nodes | Time | Nodes | Time | Nodes
I |  362 instances 10k expert samples | 2.03 | 91 | 12.68 | 758 | 131.79 | 9074
II |  388 instances 20k expert samples | 1.68 | 91 | 9.92 | 762 | 103.38 | 9050
III |  100 instances 10k expert samples | 1.67 | 94 | 10.02 | 757 | 111.52 | 9242
IV |  100 instances 20k expert samples | 1.64 | 90 | 10.03 | 751 | 109.58 | 9195
V |  50 instances 10k expert samples | 3.25 | 98 | 20.58 | 796 | 158.24 | 9834
VI |  50 instances 20k expert samples | 3.18 | 97 | 20.59 | 819 | 166.02 | 10892

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 12.

##### 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 a performance increase.

##### Influence of MILP instance count.

Examining pairs (I, III, IV) and (II, IV, VI), we further explore the
relationship between performance and the number of MILP instances, maintaining
a consistent expert sample size. The observations suggest a general trend of
performance improvement with an increase in the number of MILP instances.

Based on these observations, to answer the question of when to use CAMBranch,
our initial conclusion is that CAMBranch demonstrates more potential when
there is a sufficient number of MILP instances, but not necessarily too large
scale. Using several hundreds of MILP instances can already 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 4.2, we presented the results of various branching strategies.
However, due to space limitations, we aim to delve deeper into these results
in 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 we shift our attention to instance evaluation, CAMBranch
exhibits superior performance in most cases, particularly on challenging
problems, with the exception of Set Covering. This intriguing observation
prompts us to explore the underlying reasons. Analyzing CAMBranch’s training
signal, i.e., loss function, one possible explanation is that contrastive
learning empowers CAMBranch to 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 an 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 in certain cases, falling short of problem-
specific rules.

Within our CAMBranch framework, the introduction of contrastive learning
offers a key advantage. 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 imitating Strong
Branching. Therefore, this will enhance decision-making capabilities in the
realm of MILP solving. We will delve deeper into this aspect in our future
research.

##  Appendix F Related Work

##### Learning to branch.

The integration of machine learning techniques into branching strategies has
been a topic of growing interest, with Gasse et al. (2019) marking a
significant breakthrough in this domain, signifying a pivotal moment. Prior to
this, conventional approaches in relevant literature (Khalil et al., 2016;
Alvarez et al., 2017; Balcan et al., 2018) often rely on extracting
statistical features from MILPs during the solving process. However, these
feature extraction methods were deemed incomplete for capturing the full
essence of 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 et al. (2019). For instance, Gupta et
al. (2020) proposed a hybrid model tailored for efficient branching on CPU-
constrained machines. This model replaced computationally expensive graph
networks with more lightweight Multilayer Perceptrons (MLPs), except at the
root node. Meanwhile, Nair et 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 were primarily
designed for homogeneous 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, a suitable expert policy renowned for its
effectiveness in guiding search trees. For more comprehensive insights into
this field, readers can refer to related surveys by Khalil et al. (2017) and
Zhang et al. (2023).

##### Contrastive learning.

Contrastive learning has emerged as a powerful paradigm in various machine
learning domains. It has been successfully applied in computer vision (Chen et
al., 2020a; Falcon & Cho, 2020; He et al., 2020; Chen et al., 2020c; b; Caron
et al., 2020; Grill et al., 2020; Chen & He, 2021), natural language
processing (Mikolov et al., 2013; Arora et al., 2019; Iter et al., 2020; Fang
& Xie, 2020; Giorgi et al., 2021), recommendation system (Yu et al., 2022) and
drug discovery (Xu et al., 2022). 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.

##  Appendix G MILP Formulation

Following Gasse et al. (2019), we evaluated the models on four combinatorial
optimization problems, i.e., Set Covering, Combinatorial Auction, Capacitated
Facility Location, and Maximum Independent 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-art 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 $\mathcal{U}$ and its $n$ subsets
$S_{1},\cdots,S_{n}$, the problem seeks to identify the minimum number of
subsets that can be used to cover $\mathcal{U}$ completely.

$\text{ minimize }\quad\quad\sum_{j=1}^{n}x_{j}$ (27)

$\text{ subject to }\sum_{j\in\\{1,\cdots,n\\}\mid v\in S_{j}}x_{j}\geqslant
1\quad\forall v\in\mathcal{U}$ (28)

$x_{j}\in\\{0,1\\}\quad\forall j\in\\{1,\cdots,n\\}$ (29)

where each $x_{j}$ is a decision variable. If the subset $\mathcal{S}_{j}$ is
chosen, then $x_{j}=1$; otherwise $x_{j}=0$.

(2) Combinatorial Auction: consider a scenario where there are $n$ bids and
$m$ available. Each item is associated with a subset
$S_{j}\subseteq\\{1,\cdots n\\}$ representing the bidders interested in that
particular item. The revenue generated by each bid $i$ is denoted as $b_{i}$.
The Combinatorial Auction problem aims to allocate the bids to maximize the
expected return.

$\text{maximize}\quad\sum_{i=1}^{n}x_{i}b_{i}$ (30)

$\text{ subject to }\quad\sum_{i\in S_{j}}x_{i}\leqslant 1\quad\forall
j\in\\{1,\cdots,m\\}$ (31)

$x_{i}\in\\{0,1\\}\quad\forall i\in\\{1,\cdots,n\\}$ (32)

where each $x_{i}$ is a decision variable. If bid $x_{i}$ is selected, then
$x_{i}=1$, otherwise $x_{i}=0$.

(3) Capacitated Facility Location: assuming there are $m$ facilities and $n$
customers, the goal is to satisfy customers at a minimum cost. Let $f_{i}$
denote the cost of building facility $i\in\\{0,\cdots,m\\}$ and $c_{ij}$
denote the transportation cost of products from facility $i$ to customer
$j\in\\{0,\cdots,n\\}$. The demand of customer $j$ is $d_{j}>0$, and the
capacity of facility $i$ is $u_{i}>0$.

$\text{minimize}\quad\sum_{i=1}^{m}\sum_{j=1}^{n}c_{ij}y_{ij}+\sum_{i=1}^{m}f_{i}x_{i}$
(33) $\text{ subject to }\quad\sum_{i=1}^{m}y_{ij}=1\quad\forall
j\in\\{1,\cdots,n\\}$ (34)

$\displaystyle\sum_{j=1}^{n}d_{i}y_{ij}\leqslant u_{i}x_{i}\quad\forall
i\in\\{1,\cdots,m\\}$ (35)

$\displaystyle y_{ij}\geqslant 0\quad\forall i\in\\{1,\cdots,m\\},\quad
j\in\\{1,\cdots,n\\}$ (36)

$\displaystyle x_{j}\in\\{0,1\\}\quad\forall j\in\\{1,\cdots,n\\}$ (37)

where each Boolean variable $x_{j}$ and each continuous variable $y_{ij}$ are
decision variables. If facility $j$ is built, $x_{j}=1$, otherwise $x_{j}=0$.
In addition, variable $y_{ij}$ represents the percentage of demand $d_{j}$
that is assigned to facility $i$.

(4) Maximum Independent Set: consider an undirected graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, wherein a subset $S\in\mathcal{V}$ of
nodes is deemed an independent set when no edges interconnect any couple of
nodes within $\mathcal{S}$. The task at hand is to determine the largest
possible number of independent sets in the graph $\mathcal{G}$.

$\text{maximize}\quad\sum_{v\in\mathcal{V}}x_{v}$ (38)

$\text{ subject to }\quad x_{u}+x_{v}\leqslant
1\quad\forall(u,v)\in\mathcal{E}$ (39)

$x_{v}\in\\{0,1\\}\quad\forall v\in\mathcal{V}$ (40)

where each Boolean variable $x_{v}$ is a decision variable. If node
$v\in\mathcal{V}$ is selected in the independent set, then $x_{v}=1$,
otherwise, $x_{v}=0$.