Learning Discrete Decisions for MIPs with Constraint-Aware Diffusion

arXiv:2608.13079v1 Announce Type: new Abstract: This paper proposes a novel learning-based approach to approximately solve instances of mixed-integer optimization problems. These problems are computationally challenging, as they require jointly determining discrete and continuous decisions while satisfying complex combinatorial constraints. The proposed method relies on a graph-based generative diffusion model that learns the discrete component of mixed-integer optimization problems while integrating a training-free feasibility projection operator directly into the reverse diffusion process to steer intermediate samples toward the feasible set throughout generation. Once the discrete decisions are generated, the remaining optimization reduces to a continuous problem that can be solved efficiently (relative to the original problem) using existing numerical methods. The resulting framework named Constrained Graph Diffusion (CGD), is problem-agnostic and can accommodate a broad class of mixed-integer optimization problems through suitable projection operators. We evaluate CGD on optimal transmission switching for ACOPF and discrete portfolio optimization, demonstrating substantial improvements in feasibility and solution quality over learning-based baselines while achieving speedups of up to 425imes over state-of-the-art numerical solvers for MINLPs.

Related

• Learning to Optimize at Scale: A Benders Decomposition-TransfORmers Framework for Stochastic Combinatorial Optimization
• Learning Discrete Diffusion of Graphs via Free-Energy Gradient Flows
• Global Convergence of Sampling-Based Nonconvex Optimization through Diffusion-Style Smoothing
• The Proxy Benders Decomposition

Source: arXiv cs.LG | 2026-08-14