Model-to-Heuristic via Graph Convolutional Neural Networks: A Case Study on Vertex Cover

Greedy heuristics are a fundamental tool in combinatorial optimization, as they provide simple and scalable procedures for constructing feasible solutions. However, their performance strongly depends on the quality of the selection rule, which is usually handcrafted, problem-specific, and based on domain expertise. In this work, we propose Model-to-Heuristic, a methodological scheme in which the selection rule of a greedy algorithm is learned from optimal solutions generated by a mathematical model. Starting from an optimization model of the problem, we generate instances that can be solved to optimality within acceptable computational times. The resulting optimal solutions are then used to derive labels for training a neural network. Once trained, the network is embedded into a greedy procedure and used as a scoring function to guide the construction of feasible solutions. We test the proposed approach on the Minimum Vertex Cover problem. In particular, we train a Graph Convolutional Neural Network on graphs labelled through an integer programming formulation and use the learned model to guide the selection of vertices within a greedy heuristic. Computational experiments on BHOSLIB/FRB benchmark instances show that the learned greedy policy improves upon the classical maximum-degree greedy heuristic and reduces the aggregate gap to the optimum values. The evidence is limited to this benchmark family and baseline, but suggests that optimal solutions produced by exact models on tractable instances can provide useful information for designing learning-guided heuristics.