Combinatorial optimization and reasoning with graph neural networks

Nowadays, combinatorial optimization (CO) is an interdisciplinary field spanning optimization, operations research, discrete mathematics, and computer science, with many critical real-world applications such as vehicle routing or scheduling; see [71] for a general overview. Intuitively, CO deals with selecting a subset from a finite set that optimizes a cost or objective function. Although many CO problems are hard from a complexity theory standpoint due to their discrete nature, many of them are routinely solved in practice. Historically, the optimization and theoretical computer science communities have been focusing on finding optimal [71], heuristic [12], or approximative [130] solutions for individual problem instances. However, in many practical situations of interest, one often needs to solve problem instances which share patterns and characteristics repeatedly.