CAMBranch: Contrastive Learning with Augmented MILPs for Branching
Jiacheng Lin Meng Xu Zhihua Xiong Huangang Wang
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.