MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers
Mixed-integer programming (MIP) technology offers a generic way of
formulating and solving combinatorial optimization problems. While generally
reliable, state-of-the-art MIP solvers base many crucial decisions on
hand-crafted heuristics, largely ignoring common patterns within a given
instance distribution of the problem of interest. Here, we propose MIP-GNN, a
general framework for enhancing such solvers with data-driven insights. By
encoding the variable-constraint interactions of a given mixed-integer linear
program (MILP) as a bipartite graph, we leverage state-of-the-art graph neural
network architectures to predict variable biases, i.e., component-wise averages
of (near) optimal solutions, indicating how likely a variable will be set to 0
or 1 in (near) optimal solutions of binary MILPs. In turn, the predicted biases
stemming from a single, once-trained model are used to guide the solver,
replacing heuristic components. We integrate MIP-GNN into a state-of-the-art
MIP solver, applying it to tasks such as node selection and warm-starting,
showing significant improvements compared to the default setting of the solver
on two classes of challenging binary MILPs.