Exploring the Capabilities and Limitations of Neural Methods in the Maximum Cut

The use of Neural Networks (NN) within Combinatorial Optimization (CO) marks a significant shift in the paradigm, moving towards automatically learning heuristic strategies in deterministic and local search frameworks. NNs are capable of learning relevant patterns and symmetries of various CO problems. Despite their potential, the practical application of NNs in both academic and real-world optimization problems has not yet reached the levels of traditional exact solvers or metaheuristic approaches. This study primarily focuses on the Maximum Cut problem to investigate the capabilities and limitations of NN models within the CO domain. We introduce a series of research questions aimed at examining the generalization capabilities, reliability, and computational costs associated with these models. Our findings reveal that: (1) NN models exhibit better modeling capabilities and generalizability when trained on a diverse set of instances, (2) the model’s level of uncertainty can act as an indicator of its performance, and (3) employing a unified representation framework, wherein models concurrently learn from diverse tasks or instance types offers a significant training-speedup.