  Primal heuristics are important for solving mixed integer linear programs,
because they find feasible solutions that facilitate branch and bound search. A
prominent group of primal heuristics are diving heuristics. They iteratively
modify and resolve linear programs to conduct a depth-first search from any
node in the search tree. Existing divers rely on generic decision rules that
fail to exploit structural commonality between similar problem instances that
often arise in practice. Therefore, we propose L2Dive to learn specific diving
heuristics with graph neural networks: We train generative models to predict
variable assignments and leverage the duality of linear programs to make diving
decisions based on the model's predictions. L2Dive is fully integrated into the
open-source solver SCIP. We find that L2Dive outperforms standard divers to
find better feasible solutions on a range of combinatorial optimization
problems. For real-world applications from server load balancing and neural
network verification, L2Dive improves the primal-dual integral by up to 7%
(35%) on average over a tuned (default) solver baseline and reduces average
solving time by 20% (29%).
