Generative Large Neighborhood Search: Scalable Set Cover Optimization via Discrete Diffusion

The Set Cover Problem poses a fundamental scalability challenge for combinatorial optimization due to its sparse and non-local structure. While Graph Neural Networks provide effective representations for such structured problems, existing neural approaches typically deploy them as one-shot predictors or within sequential construction pipelines, inheriting inductive biases toward local and incremental decisions. As a result, these formulations struggle to capture the joint dependencies required for globally valid improvements at scale. We introduce Generative Large Neighborhood Search (GLNS), a framework that leverages discrete diffusion models to learn conditional distributions over effective local search neighborhoods. GLNS parameterizes a Diffusion-Guided Neighborhood Repair policy that constructs structurally coherent sub-problems by extracting uncertainty and sensitivity signals from the denoising process. This adaptive formulation enables robust neighborhood selection across problem distributions, without retraining, and avoids the ordering biases inherent to autoregressive decoding. The policy is trained with a reward-weighted objective to directly optimize downstream solver improvement. Empirically, GLNS generalizes robustly across diverse large-scale Set Cover datasets without retraining, substantially reducing optimality gaps relative to state-of-the-art neural baselines, while delivering strong performance under tight wall-clock budgets and consistently outperforming commonly used heuristics under equal compute constraints.