Ablating a Graph Neural Network for Branching in Mixed-Integer Linear Programming

Abstract

Denne oppgaven evaluerer ablasjoner av et grafkonvolusjonelt nevralt nettverk for maskinlæringsassistert forgrening foreslått av Gasse et al. (2019) for mer effektiv løsning av blandede heltallsproblemer (MILP). Effektive MILP-løsningsalgoritmer er viktige for optimering i sanntid i mange industrier, blant annet produksjon, logistikk, transport og energiproduksjon. Reduksjon i beregningstid ved å kombinere maskinlæring og branch-and-bound-løsningsalgoritmen kan forbedre disse algoritmene uten å ofre de sterke fordelene til global optimering. I 2019 ble pålitelige resultater med forbedring over de beste forgreningsstrategiene i åpen-kildekodeløsere vist, og i 2020 ble disse metodene utvidet til rent CPU-baserte modeller. Forskjellige nettverkstopologier og datasett for både GPU og CPU har blitt foreslått, men kompromisset mellom nøyaktighet og effektivitet for modellene på forskjellig maskinvare er for det meste uutforsket. For å adressere dette blir to grafkonvolusjonale nevralnett og tre flerlagsperceptroner trent gjennom imitasjonslæring av strong branching-algoritmen på genererte MILP-problemer i det nye rammeverket Ecole. Modellene blir deretter inkorporert i optimaliseringsløseren SCIP og evaluert på testproblemer. Alle modeller viser nær høyeste effektivitet mot sammenlignbare algoritmer på GPU. Modellene med grafkonvolusjoner viser et mye mer betydelig effektivitetstap enn modellene uten når beregningene gjennomføres på CPU.

This thesis evaluates ablations of a graph convolutional neural network for machine learning aided branching proposed by Gasse et al. (2019) for faster solving of mixed-integer linear programming (MILP) problems. Efficient MILP solution algorithms are important for real-time optimization in various industries, including industrial production, logistics, transportation, and energy production. Reduced computation time via merging machine learning with the branch-and-bound solution algorithm can improve these algorithms without sacrificing the strong benefits of global optimization. In 2019, reliable results of improvement over top branching policies in open-source solvers were shown, and in 2020 these methods have been expanded to purely CPU-based solutions. Different network topologies and feature sets on both GPUs and CPUs have been presented, however, the trade-off between accuracy and efficiency with these models on varying hardware is still mostly unexplored. In order to address this, two variants of graph convolutional neural networks and three multi-layer perceptron configurations are trained via imitation learning on the strong branching algorithm with generated MILP problems using the new framework Ecole. The models are then incorporated into the SCIP optimization solver and evaluated on test problems. All models show near state-of-the-art efficiency when run on the GPU. The models containing graph convolutions show a considerably larger reduction in efficiency than the MLPs when run on the CPU.