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.
Copyright. All Rights Reserved.