Egészértékű programozás támogatása mélytanulással

Témavezető:	Lukács András
	ELTE Matematikai Intézet, MI Kutatócsoport
email:	andras.lukacs@ttk.elte.hu

Témavezetők

• Madarasi Péter (ELTE TTK, Operációkutatási Tsz.)

Projekt leírás

A kombinatorikus optimalizálás egyik legfontosabb ága az egészértékű programozás (IP), amelynek módszereit az iparban, szolgáltatás szektorban évtizedek óta sikeresen használják. Az IP feladatok 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 projektben azt vizsgáljuk, hogy miként 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 [1]. A kutatás célja egy a Strong branching-et imitáló - a nagy nyelvi modellekben (LLM) is megjelenő - transformer architektúrát [2] használó, IP feladatok megoldását támogató módszer kidolgozása.

Kulcsszavak: kombinatorikus optimalizálás, egészértékű programozás, mélytanulás, transformerek

Előfeltételek

angol szakirodalom olvasása, Python ismeretek, előny egészértékű programozás ill. gépi/mély tanulás, Pytorch alapjainak ismerete

Hivatkozások

[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.

[2] Alammar, J.: The Illustrated Transformer. https://jalammar.github.io/illustrated-transformer/