Influence branching for learning to solve mixed-integer programs online
This work addresses the challenge of efficiently solving MIPs in online settings with varying parameters, though it appears incremental as it builds on existing online learning approaches.
The authors tackled the problem of solving mixed-integer programs (MIPs) online by introducing influence branching, a graph-oriented variable selection strategy optimized with Thompson sampling, achieving results comparable to state-of-the-art online learning methods.
On the occasion of the 20th Mixed Integer Program Workshop's computational competition, this work introduces a new approach for learning to solve MIPs online. Influence branching, a new graph-oriented variable selection strategy, is applied throughout the first iterations of the branch and bound algorithm. This branching heuristic is optimized online with Thompson sampling, which ranks the best graph representations of MIP's structure according to computational speed up over SCIP. We achieve results comparable to state of the art online learning methods. Moreover, our results indicate that our method generalizes well to more general online frameworks, where variations in constraint matrix, constraint vector and objective coefficients can all occur and where more samples are available.