Branch Ranking for Efficient Mixed-Integer Programming via Offline Ranking-based Policy Learning
This work addresses the efficiency of MIP solvers, which are crucial for optimization in operations research and engineering, by proposing a novel learning-based branching strategy that improves over state-of-the-art methods.
The authors tackled the problem of variable selection in mixed-integer programming (MIP) solvers by formulating it as an offline reinforcement learning problem, resulting in a method called Branch Ranking that outperforms existing heuristics and learning-based models in efficiency, robustness, and generalization to large-scale instances.
Deriving a good variable selection strategy in branch-and-bound is essential for the efficiency of modern mixed-integer programming (MIP) solvers. With MIP branching data collected during the previous solution process, learning to branch methods have recently become superior over heuristics. As branch-and-bound is naturally a sequential decision making task, one should learn to optimize the utility of the whole MIP solving process instead of being myopic on each step. In this work, we formulate learning to branch as an offline reinforcement learning (RL) problem, and propose a long-sighted hybrid search scheme to construct the offline MIP dataset, which values the long-term utilities of branching decisions. During the policy training phase, we deploy a ranking-based reward assignment scheme to distinguish the promising samples from the long-term or short-term view, and train the branching model named Branch Ranking via offline policy learning. Experiments on synthetic MIP benchmarks and real-world tasks demonstrate that Branch Rankink is more efficient and robust, and can better generalize to large scales of MIP instances compared to the widely used heuristics and state-of-the-art learning-based branching models.