Machine Learning for Optimization Problems

Project Description: We use deep learning to mainly address graph theoretic optimization problems. In particular, we are developing a number of graph embedding methods that attempt at capturing essential structural information, depending on the problem in hand. In the work published so far, we have adopted a recent approach for representing instances of a graph theoretic problem (as vectors) and we introduced a training scenario that uses the notion of an obstruction set, based on the work of Robertson and Seymour in their seminal work on the Graph Minor Theorem. Preliminary results on the Vertex Cover problem are very promising. The new graph embedding (or mapping) method is currently being used in a number of related project.

PI: Faisal N. Abu-Khzam

Publications:

F. N. Abu-Khzam, M.M. Abd El-Wahab, M. Haidous, and N. Yosri. Learning from obstructions: An effective deep learning approach for minimum vertex cover, in Annals of Mathematics and Artificial Intelligence (2022).
https://doi.org/10.1007/s10472-022-09813-2