Branchelés az egészértékű programozásban gépi tanulással
| Témavezető: | Madarasi Péter |
| ELTE TTK, Operációkutatási Tsz. | |
| email: | madarasip@staff.elte.hu |
Témavezetők
- Lukács András (ELTE Matematikai Intézet, MI Kutatócsoport)
Projekt leírás
Az egészértékű programozási feladat egzakt megoldására szolgáló Branch&Bound algoritmus hatékonysága nagyban függ attól, hogy milyen stratégia szerint választjuk ki azt a törtváltozót, amely szerint a feladatot két diszjunkt részre bontjuk. A szakirodalomban több gyakorlatban hatékony heurisztikus algoritmus ismert, ilyen például a Strong branching, amely az LP optimum legnagyobb változását eredményező tört változót választja. A projekt célja annak a vizsgálata, hogy hogyan lehet egy ilyen stratégiát a gépi tanulás módszereivel kiváltani, illetve egy-egy nehezen kiszámolható stratégiát imitálni. A kutatás kiindulási pontja egy a Strong branching-et imitáló gráf konvolúciós hálókat használó megoldás [1].
Előfeltételek
[1] Gasse, M., Chételat, D., Ferroni, N., Charlin, L. and Lodi, A., 2019. Exact combinatorial optimization with graph convolutional neural networks. Advances in Neural Information Processing Systems, 32.