SORREL: Suboptimal-Demonstration-Guided Reinforcement Learning for Learning to Branch
This addresses the problem of reducing reliance on expert demonstrations for data-driven MILP solvers, offering a more efficient approach for optimization tasks.
The paper tackles the challenge of learning branching heuristics for Mixed Integer Linear Program solvers without requiring high-quality demonstrations, by introducing SORREL, which uses suboptimal demonstrations and achieves improved branching quality and training efficiency over previous methods.
Mixed Integer Linear Program (MILP) solvers are mostly built upon a Branch-and-Bound (B\&B) algorithm, where the efficiency of traditional solvers heavily depends on hand-crafted heuristics for branching. The past few years have witnessed the increasing popularity of data-driven approaches to automatically learn these heuristics. However, the success of these methods is highly dependent on the availability of high-quality demonstrations, which requires either the development of near-optimal heuristics or a time-consuming sampling process. This paper averts this challenge by proposing Suboptimal-Demonstration-Guided Reinforcement Learning (SORREL) for learning to branch. SORREL selectively learns from suboptimal demonstrations based on value estimation. It utilizes suboptimal demonstrations through both offline reinforcement learning on the demonstrations generated by suboptimal heuristics and self-imitation learning on past good experiences sampled by itself. Our experiments demonstrate its advanced performance in both branching quality and training efficiency over previous methods for various MILPs.