Learning Discrete Decisions for MIPs with Constraint-Aware Diffusion

This paper proposes Constrained Graph Diffusion (CGD), a novel learning-based approach to approximately solve mixed-integer optimization problems (MIPs/MINLPs). The method addresses problems of the form:

min x,z f(x, z) s.t. g(x, z) ≤ 0, x ∈ X ⊆ R n, z ∈ 0, 1 m

where no convexity or linearity assumptions are made on f or g. The paper notes that two distinct sources of difficulty compound: (1) Combinatorial structure: the binary variables z induce a search space of size 2 m... (2) Nonconvexity: the objective f and the constraints g are nonlinear and nonconvex.

The central premise is that if the optimal combinatorial structure could be identified directly, the mixed-integer problem would collapse to a much easier continuous solve. The framework decomposes the problem as follows:

• Discrete component: A graph-based generative diffusion model learns the discrete decision variables z

• Continuous component: Once z is fixed, the remaining problem reduces to a continuous optimization problem solved with standard numerical methods

The key innovation is integrating a training-free feasibility projection operator directly into the reverse diffusion process to steer intermediate samples toward the feasible set throughout generation.

The reverse diffusion process operates in continuous space, so CGD uses an antipodal embedding: y0 = e(z⋆):= 2z⋆ − 1 ∈ −1, +1 m which preserves Hamming geometry through ∥e(z) − e(z′)∥22 = 4 dH(z, z′).

At each reverse timestep t, the denoiser predicts noise, reconstructs the clean embedded signal, and applies a tanh map to bound estimates in [−1, 1] m. The relaxed decision is then projected onto the continuous relaxation of the combinatorial feasible set:

Cξ = u ∈ [0, 1] m: h̃(u; ξ) ≤ 0, Cξ ∩ 0, 1 m = Zξ

The projection solves: ΠCξ(v) ∈ arg min u∈Cξ ∥u − v∥22

The corrected decision is reinserted into the reverse process via a consistent noise estimate. The paper proves (Proposition 1) that the projection residual measures relaxed infeasibility and points along its gradient, while the correction itself cannot increase the distance to any feasible reference decision.

After the terminal reverse step, a recovery map Rξ converts the continuous estimate to binary decisions via thresholding: T(u)i:= 1 ui ≥ 1/2. The paper proves (Corollary 3) that dH(T(u), z⋆) ≤ 4∥u − z⋆∥22 and that projection improves this bound.

The continuous completion solves Problem (2) with z fixed using standard nonlinear programming solvers.

Training uses a combined objective: L(θ) = LDSM(θ) + λ E(ξ,z⋆),t [lfeas(t, ξ, z⋆)] where the feasibility loss uses Monte Carlo averaging over K perturbed states and a stop-gradient projection target.

Evaluated on IEEE 9-, 197-, and 500-bus systems with 12 to 597 binary variables and 172 to 8,651 continuous variables. Results show:

• Discrete quality: CGD achieves the lowest Hamming distance and highest exact reconstruction across all networks (79.43% exact reconstruction on 9-bus, 51.20% on 197-bus, 33.24% on 500-bus)

• Feasibility: CGD produces zero infeasible downstream solves on all three networks

• Objective quality: CGD achieves objective gaps of 0.01%, 1.76%, and 0.20% on the 9-, 197-, and 500-bus benchmarks respectively

• Speedups: "CGD reduces total runtime from 140.32 to 0.33 s on the 9-bus system, from 1,741.00 to 79.25 s on the 197-bus system, and from 1,204.12 to 30.13 s on the 500-bus system. These values correspond to 425.2×, 22.0×, and 40.0× speedups."

Evaluated on n = 50 and n = 150 assets. Results show:

• For n = 50: CGD achieves 8.21% Hamming distance, 54.31% exact reconstruction, zero constraint violations, and 4.92% objective gap

• For n = 150: CGD achieves 15.84% Hamming distance, 44.16% exact reconstruction, zero constraint violations, and 6.56% objective gap

• Speedups of 4.6× (n=50) and 48.5× (n=150) over GUROBI joint MIQP

The paper demonstrates that "enforcing feasibility throughout the reverse diffusion process improves both discrete prediction accuracy and downstream feasibility relative to post-processing, unconstrained diffusion, and existing learning-based baselines. The authors also note that projection throughout denoising changes which feasible support is generated, rather than only whether the terminal support passes the quadratic test."

The paper concludes that decoupling the combinatorial and continuous components substantially reduces computational cost while maintaining low objective gaps and highlights the promise of constraint-aware generative models as a scalable paradigm for solving large-scale mixed-integer optimization problems with complex combinatorial structure.

Improvements to AI Systems Based on This Paper:

1. Constraint-Aware Generative Solver for Nonconvex Mixed-Integer Problems

• What it does: The AI system can directly generate high-quality discrete decisions (binary variables) for large-scale nonconvex mixed-integer nonlinear programs (MINLPs) without relying on convex relaxations or exhaustive search.

• Specific capability: Given a problem instance (e.g., power grid switching, portfolio selection), the system outputs a near-optimal binary support in milliseconds, then hands off to a standard continuous solver. This reduces solve time by 20–425× compared to commercial solvers (GUROBI, SCIP) while maintaining objective gaps below 2% on benchmarks up to 597 binary variables and 8,651 continuous variables.

2. Training-Free Feasibility Projection Embedded in Diffusion Sampling

• What it does: The system enforces hard combinatorial constraints (e.g., line-switching limits, cardinality constraints) during every step of the generative denoising process, not just at the end.

• Specific capability: The AI system can produce zero infeasible solutions on test instances, eliminating the need for expensive repair heuristics or repeated solver calls. This is achieved via a differentiable projection operator that steers intermediate noisy samples toward the feasible set, with a theoretical guarantee that projection never increases distance to any feasible reference solution.

3. Graph-Based Discrete Structure Learning with Hamming-Geometry Preservation

• What it does: The system learns the combinatorial structure of the problem as a graph diffusion process, using an antipodal embedding that preserves Hamming distances exactly.

• Specific capability: The AI can generalize across problem sizes (e.g., from 9-bus to 500-bus power systems) and problem types (power flow, portfolio optimization) by learning the underlying graph topology and constraint interactions, achieving 33–79% exact binary reconstruction without retraining on each new instance.

4. Hybrid Generative-Numerical Optimization Pipeline

• What it does: The system decomposes the mixed-integer problem into a generative discrete predictor and a deterministic continuous solver, avoiding the need for end-to-end differentiable optimization.

• Specific capability: The AI can handle nonconvex objectives and constraints (e.g., AC power flow equations, quadratic portfolio risk) that are intractable for learning-based end-to-end methods. It achieves this by only learning the discrete decisions, while the continuous subproblem is solved exactly with mature nonlinear programming tools.

5. Feasibility-Augmented Training Objective

• What it does: The system is trained with a combined loss that includes a Monte Carlo estimate of feasibility violation during denoising, in addition to standard denoising score matching.

• Specific capability: The AI learns to generate discrete decisions that are not only close to the optimum but also structurally feasible, even when training data contains suboptimal or infeasible examples. This improves robustness and reduces the need for large curated datasets of optimal solutions.

6. Scalable Decision Support for Real-Time Operations

• What it does: The system provides a fast, approximate solver that can be used in time-critical applications where exact solvers are too slow.

• Specific capability: For example, in power grid operations, the AI can propose transmission switching configurations in under 1 second (vs. 140 seconds for exact solvers) on a 9-bus system, and in 30 seconds (vs. 20 minutes) on a 500-bus system, enabling real-time reconfiguration during contingencies or market clearing.

7. Uncertainty-Aware Discrete Prediction

• What it does: The diffusion model provides a distribution over possible binary decisions, not just a single point estimate.

• Specific capability: The system can generate multiple diverse, feasible candidate solutions (e.g., different switching configurations) with associated likelihoods, allowing operators to explore trade-offs (cost vs. robustness) or to feed a portfolio of candidates into a verification step.

8. Transferable Feasibility Projection for New Constraints

• What it does: The projection operator is defined by the constraint set itself (via a relaxed indicator function), not by learned parameters.

• Specific capability: The AI can adapt to new or modified constraints (e.g., adding a new line limit or changing a cardinality bound) at inference time without retraining, because the projection is computed analytically from the current constraint set. This makes the system practical for dynamic environments where constraints change frequently.

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 425 times over state-of-the-art numerical solvers for MINLPs.