Learning Discrete Decisions for MIPs with Constraint-Aware Diffusion
Vincenzo Di Vito, Mehdi Taghizadeh, Deepjyoti Deka, Kaarthik Sundar, Ferdinando Fioretto
cs.LG
2026-08-13
CGD generates MIP binaries with constraint-aware graph diffusion, then solves the continuous subproblem. Up to 425× vs Gurobi on AC switching, 0.01% 9-bus gap.
Mixed-integer nonlinear programs glue two hard pieces together: a \(2^m\) search over binaries \(z\), and a nonconvex continuous program in \(x\). Transmission switching and discrete portfolio selection are built this way. Fix \(z\) and a standard NLP solver can recover \(x\). Flip one bit and that continuous problem can become empty. On the IEEE 9-bus network, opening all three lines at load bus 4 isolates the bus; the power-balance equations have no solution.
Learning-to-optimize has not split this cleanly. Policies stuffed into branch-and-bound (Neural Branching, Neural Diving) still search a discrete tree online. Direct predictors emit one assignment even when several near-optimal supports exist, and rounding a continuous relaxation can leave the combinatorial set. Graph diffusion solvers such as DIFUSCO can sample discrete structures, but they usually handle constraints with soft penalties or a terminal repair. An invalid discrete draw can make the downstream continuous problem infeasible.
Constrained Graph Diffusion (CGD), from the University of Virginia, MIT, and Los Alamos, learns only a conditional distribution over the discrete block. Continuous variables stay with a numerical solver. Training pairs are (instance parameters \(\xi\), reference binaries \(z^\star\)) from an exact solver; \(z^\star\) need not be globally optimal.
Generation has four stages:
Projection runs at every reverse step, not only at the end. When \(C\xi\) is convex, the operator is the nearest Euclidean point in the relaxation, and the induced reverse kernel is the closest fixed-variance kernel (in 2-Wasserstein distance) whose clean endpoint lies in \(C\xi\). That is a local improvement, not a claim that the noisy trajectory stays feasible or that CGD samples the constrained data law. Across the reported settings, per-step projection beats both no projection and final-step projection on downstream objective.
Training adds a feasibility regularizer to denoising score matching. For a fixed \((\xi, z^\star, t)\), the method draws \(K\) independent noises, averages the relaxed predictions, and treats the projection of that mean as a stop-gradient target. The denoising term keeps the model from collapsing onto arbitrary feasible points; the regularizer pushes the mean toward \(C\xi\). Hard rounding is not differentiated. ACOPF uses \(T=100\) and \(K=20\); the portfolio model uses \(T=30\) and \(K=8\) for the training penalty.
The projection is application-specific. For switching, each load-bearing component must reach a generator with enough active and reactive capacity; the projection itself is a MILP that minimizes Hamming edits and may leave load-free islands. For portfolios it projects onto \(z^\top P z \le \rho\) in the unit box. Neither condition is sufficient for downstream feasibility.
Two tasks: AC optimal power flow with transmission switching, and a mixed-integer Markowitz problem with a quadratic combinatorial budget. Baselines include CGD without projection, projection only at the last step, MLP, GNN, DIFUSCO, and LTO-MIP with differentiable integer correction. ACOPF labels come from Gurobi 13 (time limits 60/3600/3600 s on 9/197/500-bus, MIP gap \(10^{-4}\)). Portfolio labels come from ECOS branch-and-bound. Each grid has 10,000 instances with 1,000 held out; the \(n=50\) portfolio set has 12,000 instances with 1,200 held out.
| Network | Method | Hamming↓ | Exact recon.↑ | Downstream infeas.↓ | Obj. gap↓ |
| 9-bus | CGD | 0.57% | 79.43% | 0% | 0.01% |
| 9-bus | no projection | 3.86% | 55.59% | 7.55% | 0.55% |
| 9-bus | final-step proj. | 1.29% | 67.51% | 0% | 0.61% |
| 9-bus | DIFUSCO | 5.36% | 41.03% | 15.63% | 0.58% |
| 197-bus | CGD | 0.14% | 51.20% | 0% | 1.76% |
| 197-bus | MLP | 24.55% | 0% | 100% | n/a |
| 500-bus | CGD | 2.05% | 33.24% | 0% | 0.20% |
| 500-bus | DIFUSCO | 10.36% | 11.03% | 21.18% | 0.78% |
9-bus has 12 binaries and 172 continuous variables; 500-bus grows to 597 binaries and 8,651 continuous variables. MLP produces a 100% infeasible downstream rate on 197-bus and 500-bus. Per-step projection is not a cosmetic repair: on 9-bus, exact reconstruction rises from 67.51% (final-step) to 79.43%, and the objective gap falls from 0.61% to 0.01%. On 197-bus, dropping projection leaves 4.53% downstream infeasible and a 2.99% gap; CGD clears infeasibility and cuts the gap to 1.76%.
End-to-end time against the joint Gurobi MINLP:
| Network | Gurobi | CGD sampling | Cont. OPF | End-to-end | Speedup |
| 9-bus | 140.32 s | 0.03 s | 0.30 s | 0.33 s | 425.2× |
| 197-bus | 1741 s | 0.16 s | 79.09 s | 79.25 s | 22.0× |
| 500-bus | 1204.12 s | 0.11 s | 30.02 s | 30.13 s | 40.0× |
Sampling is cheap on the large nets; the continuous AC-OPF dominates. To reach the same 0.01% numerical level as CGD on 9-bus, Gurobi still needs 30.02 s on average, a 91× ratio.
For \(n=50\) portfolios, CGD records 8.21% Hamming, 54.31% exact reconstruction, zero quadratic violation, and a 4.92% gap (8.43% without projection; max violation 16.72). At \(n=150\) the GNN wins Hamming (12.18%) and exact reconstruction (47.82%) but violates the quadratic constraint and posts a 13.53% gap. CGD stays at zero violation and 6.56%, versus 10.39% for final-step projection. End-to-end times are 0.020 s and 0.025 s, 4.6× and 48.5× versus the joint MIQP. Growing from 50 to 150 assets barely moves CGD; the joint solver slows by more than 10×.
Warm-starting Gurobi with the CGD feasible point does not cut certification time in a useful way: 140.32 s to 98.60 s on 9-bus, 1741 s to 1783.54 s on 197-bus, 1204.12 s to 1213.45 s on 500-bus. The bottleneck is proving optimality.
If the same MINLP family is solved over and over (dispatch, real-time portfolios), amortizing the discrete block and leaving the continuous nonconvex piece to a solver is a practical split. Diffusion can represent several near-optimal discrete modes. Guiding the reverse trajectory is worth more than repairing the last sample: on 9-bus, final-step projection already hits 0% infeasibility, yet the gap stays at 0.61% until per-step projection brings it to 0.01%.
This is an incremental tool, not a drop-in solver. Someone still has to write a projection, training still needs solver labels, and the continuous subproblem remains nonconvex. The 40× speedup on 500-bus comes from skipping discrete branching; the AC-OPF itself still takes tens of seconds. Warm starts do not help certification. Use this when a feasible near-optimum without a MIP certificate is the product.
Load-relevant connectivity is necessary, not sufficient, for AC feasibility; downstream success is measured, not proved. Thresholding a relaxed feasible point need not land in the discrete set when slack cannot absorb the rounding displacement; the portfolio appendix states a sufficient certificate. CGD does not certify global optimality of the original MINLP, and the reference labels are best feasible solutions under a time limit.
Training stop-gradients through the projection, so nonconvex or approximate corrections lose the geometry in Proposition 1. Only two applications are tested. Constraints without a cheap projection need a new interface. Figure 1 draws an outer resample-on-failure loop; the main tables do not report how often that loop fires.
The 425.2× headline compares Gurobi-to-termination (certificate included) against CGD. The fairer same-quality number on 9-bus is 91×. Keep those two apart.