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

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