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

摘要

This paper introduces Probabilistic Multi-Variable Branching (PMVB), a simple and effective technique for accelerating mixed-integer optimization using data-driven machine learning models. At its core, PMVB employs a multi-variable branching procedure that partitions the feasible region via data-driven hyperplanes and requires only two lines of code to implement. Moreover, PMVB is model-agnostic and compatible with a wide range of machine learning models. Leveraging tools from statistical learning theory, we develop interpretable hyperparameter selection strategies and propose several extensions to further enhance performance. We evaluate PMVB by integrating it into state-of-the-art MIP solvers and conducting experiments on both classical benchmark datasets and real-world instances. The results demonstrate the effectiveness of PMVB in improving MIP-solving efficiency.