Data-driven Mixed Integer Optimization through Probabilistic Multi-variable Branching

This paper introduces Probabilistic Multi-Variable Branching (PMVB), a simple yet highly flexible technique for accelerating mixed-integer optimization using data-driven machine learning models. At its core, PMVB employs a multi-variable cardinality branching procedure that partitions the feasible region with data-driven hyperplanes, requiring only two lines of code for implementation. Moreover, PMVB is model-agnostic and can be readily integrated with various machine learning approaches. Leveraging tools from statistical learning theory, we develop interpretable hyperparameter selection strategies to enhance its performance. Furthermore, we extend our approach to a data-free setting, where the root LP relaxation serves as a surrogate prediction model, and we provide theoretical analysis to justify this idea. We evaluate PMVB by incorporating it into state-of-the-art MIP solvers and conducting experiments on both classic benchmark datasets and real-world instances. The results demonstrate its effectiveness in significantly improving MIP-solving efficiency.