Lifted branching: Learning to improve branching strategies

Branch-and-bound (B&B) is a widely used algorithm for solving mixed-integer linear programs (MILPs). One of the elements of its efficiency is the branching strategy. While strong branching empirically produces small B&B trees, its high computational cost makes it impractical for real-world applications. Recent advances in machine learning explored imitation learning to replicate the effectiveness of strong branching. However, these approaches are limited to mimicking existing strategies rather than discovering new ones. In this work, we propose lifted branching, a novel framework that iteratively improves an existing branching strategy by using imitation learning to learn from an improved version of the strategy. Lifted branching is designed to generate smaller B&B trees while avoiding the computational overhead of strong branching, making it suitable for offline training and efficient real-time deployment. We demonstrate the effectiveness of our approach through extensive experiments on four different problem classes, showing that our learned lifted branching models can outperform state-of-the-art strategies, such as reliability pseudo-branching and learned strong branching, depending on the problem of interest.