Lookback for Learning to Branch
The expressive and computationally inexpensive bipartite Graph Neural
Networks (GNN) have been shown to be an important component of deep learning
based Mixed-Integer Linear Program (MILP) solvers. Recent works have
demonstrated the effectiveness of such GNNs in replacing the branching
(variable selection) heuristic in branch-and-bound (B&B) solvers. These GNNs
are trained, offline and on a collection of MILPs, to imitate a very good but
computationally expensive branching heuristic, strong branching. Given that B&B
results in a tree of sub-MILPs, we ask (a) whether there are strong
dependencies exhibited by the target heuristic among the neighboring nodes of
the B&B tree, and (b) if so, whether we can incorporate them in our training
procedure. Specifically, we find that with the strong branching heuristic, a
child node's best choice was often the parent's second-best choice. We call
this the "lookback" phenomenon. Surprisingly, the typical branching GNN of
Gasse et al. (2019) often misses this simple "answer". To imitate the target
behavior more closely by incorporating the lookback phenomenon in GNNs, we
propose two methods: (a) target smoothing for the standard cross-entropy loss
function, and (b) adding a Parent-as-Target (PAT) Lookback regularizer term.
Finally, we propose a model selection framework to incorporate
harder-to-formulate objectives such as solving time in the final models.
Through extensive experimentation on standard benchmark instances, we show that
our proposal results in up to 22% decrease in the size of the B&B tree and up
to 15% improvement in the solving times.