Two Optimization Problems on Graphs and Why ML-based Optimization Underperforms

Tina Eliassi-Rad
Northeastern University
Computer Science & Network Science

I will describe two graph problems where ML-based optimization underperforms compared to traditional optimization approaches (such as simulated annealing and integer programming). The first problem is the Force Path Cut problem, where an adversary removes edges from a graph to make a given path the shortest between its terminal nodes. The second problem is the Hypergraph Discovery problem, in which teams of agents (represented by vertices) are formed to perform tasks (represented by hyperedges). Each agent has a finite amount of energy to expend, and each task requires a certain amount of energy to complete. I will discuss my conjectures about the poor performance of ML-based optimization on these problems.

Presentation (PDF File)

Back to Artificial Intelligence and Discrete Optimization