A spatial branch-and-bound method for ReLU network-constrained problems

Abstract

Motivert av evnen kunstige nevrale nettverk har til data-dreven black-box modellering og bruken av spatial branch-and-bound (sBB) algoritmer til å løse ulineære optimaliseringsproblemer presenterer denne opgaven en metode for å inkludere ReLU nettverk-beskrankninger i en sBB løser. Andre forfattere har tidligere brukt mixed-integer linear programming (MILP) formuleringer av slike nettverk for å bygge inn ReLU nettverk-beskrankninger i større MILP problemer. Å anse disse nettverkene for å være ulineære funksjoner av inngangsvariablene og ikke MILP formuleringer har den fordelen at antallet variabler som påvirker utgangsverdien reduseres. For å teste om en sBB-tilnærming kan være fordelaktig sammenlignet med en MILP-tilnærming ble en sBB-løser implementert og en rekke tester blitt konstruert. Resultatene sammenligner ytelsen til sBB-løseren med en toppmoderne MILP-løser og viser at MILP-løseren har betraktelig bedre ytelse enn sBB-løseren med veldig få unntak.

Motivated by the data-driven black-box modeling abilities of artificial neural networks and the ability of spatial branch-and-bound (sBB) methods to solve nonlinear programs (NLP), this thesis presents a method for incorporating ReLU network-constraints into an sBB solver. Other authors have previously employed mixed-integer linear programming (MILP) formulations of ReLU networks to embed ReLU network-constraints into larger MILP problems. Considering these networks to be nonlinear functions of the input variables instead of MILPs has the benefit of reducing the number of variables on which the output of the networks depend. To examine if the sBB approach could have performance benefits over the MILP approach an sBB solver was implemented and a series of tests devised. The results compare the performance of the sBB solver to a state of the art MILP solver, and show that the MILP solver has a performance well ahead of the sBB solver with very few exceptions.