Diffusion on a Continuous Latent Space for Contextual Combinatorial Optimization

We study the problem of generating diverse, high-quality solutions for contextual stochastic combinatorial optimization (CO) problems. Like decision-focused learning (DFL) and combinatorial optimization augmented machine learning (COAML), we work in the continuous latent space of cost vectors of a canonical Mixed Integer Linear Programming (MILP) formulation, and delegates feasibility to an exact CO oracle. Where these approaches predict a single cost vector, and therefore commit to a single decision, we learn a conditional \emph{distribution} over it: we target a Gibbs distribution over cost vectors, each draw of which is decoded into a feasible combinatorial solution. We obtain training samples from this target via a stochastic-localization Monte Carlo scheme, whose sampling process we amortize with a conditional Denoising Diffusion Probabilistic Model (DDPM), reducing inference cost to a handful of forward passes and a single oracle call. While a single DDPM draw remains competitive with standard baselines (Fenchel-Young Loss), it underperforms specialized expected-cost minimizers for single-point predictions. Instead, the primary advantage of our generative approach lies in capturing the mixture target $\rho_\beta(\cdot | x)$ to produce highly diverse solution set.