Vágásgenerálá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)
Projekt leírás
Az egészértékű programozási feladat egzakt megoldására szolgáló Branch&Cut algoritmus hatékony implementációi a részfeladatok LP-relaxáltjait megengedett vágásokkal erősítik. Amikor az aktuális bázismegoldás nem egész, mindig tudunk találni a relaxáltat erősítő vágást, például egy Gomory vagy egy Klikk vágást generálva. A hatékonyság szempontjából fontos kérdés, hogy milyen, mennyi és pontosan melyik vágásokat adjuk hozzá egy-egy részfeladat megoldásakor, amit valamilyen heurisztikus algoritmus segítségével határoznak meg a solverek. A projekt célja ezeket a heurisztikákat gépi tanulással gyorsítani, javítani. A kutatás kiindulási pontja egy a Gomory-vágások generálását reinforcement learning-gel optimalizáló módszer [1].
Hivatkozások
[1] Tang, Y., Agrawal, S. and Faenza, Y., 2020, November. Reinforcement learning for integer programming: Learning to cut. In International conference on machine learning (pp. 9367-9376). PMLR.