Constrained Graph Diffusion, 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, is proposed.
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 $425\times$ over state-of-the-art numerical solvers for MINLPs.
Combinatorial optimization (CO) problems have widespread applications in science and engineering, but they present significant computational challenges. Recent advancements in generative models, particularly diffusion models, have shown promise in bypassing traditional optimization solvers by directly generating near-optimal solutions.
However, existing diffusion solvers are highly sensitive to the quality of the training dataset, particularly the number of problem instances for training and the optimality of their labels. Notably, we observe an exponential scaling law between the performance of diffusion-based solvers and the number of near-optimally labeled instances needed. When training instances are scarce or sub-optimally labeled, diffusion-based solvers suffer significant performance degradation.
To enhance the robustness of diffusion solvers to dataset quality, we propose a robust diffusion solver for combinatorial optimization capable of learning from sub-optimally labeled instances follows a two-stage generate-then-decode framework, integrating an objective-guided diffusion model, further reinforced by classifier-free guidance, to produce solutions that surpass the optimality of the training dataset.
Experiments demonstrate the improved robustness in \myalg compared to the diffusion-based solver baseline, in a range of combinatorial optimization benchmark tasks such as TSP (Traveling Salesman Problem) and MIS (Maximum Independent Set).
Hui Yuan, Zhigang Hua, Zi-Hao Li et al.· Proceedings of the Thirty-Fi...· 0 citations
Distributed constraint optimization problems (DCOPs) provide a popular framework for distributed decision making under limited communication, but many real-world instances are too large to solve monolithically. We address this challenge from two complementary directions. We revisit the connection between DCOPs and potential games, and adapt modern online learning algorithms for equilibrium finding to DCOPs. We show that these algorithms are competitive with representative incomplete DCOP algorithms. We then turn to decomposition frameworks for large-scale DCOPs, motivated by large-scale decentralized satellite scheduling. We propose a new framework that separates a DCOP into two interacting subproblems: a high-level meta-DCOP for task allocation, and independent local optimization problems for scheduling. To couple the two levels, we develop a novel iterative pricing method that updates the meta-level utilities using feedback from the local optimizers. Combining our online learning methods with our iterative pricing framework, we obtain near-optimal performance on real-world decentralized satellite scheduling problem instances, fulfilling over 99% of observation requests compared with 87% for state-of-the-art baselines.
Itai Zilberstein, Pranav Rajbhandari, Steve A. Chien et al.· arXiv.org· 0 citations
This letter proposes a learning method for real-time solution of receding-horizon mixed-integer nonlinear programs (RH MINLPs) in dynamic energy supply systems. Conventional MINLP solvers incur high computational costs. Although machine learning (ML) approximations can reduce the cost, existing approaches struggle to satisfy temporally coupled hard constraints solely through the forward pass, as required in industrial applications. To address this issue, we propose a two-stage architecture. First, RH MINLP is reformulated via backward recursion to decouple temporal dependencies into local allocation tasks. Second, a specialized neural network (NN) architecture embeds structural correction mechanisms into differentiable layers, thereby satisfying hard constraints during the forward pass without the need for external solvers. The proposed NN comprises a scalable binary-constraint layer and a continuous-allocation layer. A case study on a district cooling system demonstrates that the proposed method enables large-scale end-to-end training and generates feasible operational plans in real time.
Morimasa Okamoto, Yasuaki Wasa· IEEE Control Systems Letters· 0 citations
Many operational problems are constrained sequential decision processes with large, combinatorial action spaces and interdependent feasibility constraints. Mixed-integer linear programs (MILPs) handle such constraints flexibly but scale poorly in stochastic environments. Deep reinforcement learning (DRL) promises scalable decision rules, but existing methods either penalize constraints rather than enforce them, or rely on feasibility mechanisms that break down once constraints interact. We bridge this gap by embedding a differentiable convex optimization module inside the policy: a neural network proposes continuous action targets, a quadratic program projects them onto the relaxed feasible set, and a dual-informed integer mapping restores integrality while preserving feasibility. Given a differentiable simulator, the policy trains end to end from sampled trajectories using pathwise gradients, while handling hard constraints with similar flexibility to MILPs. We show that our feasibility enforcement has bounded error relative to an exact integer projection and ensures the entire feasible action space is reachable. We apply the method to multi-echelon production-inventory planning under shared resource and material constraints. Our policy attains an average optimality gap below 1% on small instances. It further outperforms state-of-the-art echelon base-stock policies by up to 9.75% and a rolling-horizon multi-stage stochastic program by at least 7.7% in larger networks. On an industry-scale case study from ASML, it reduces average cost by up to 3.22% relative to the best-known benchmark policy. The savings are largest where planning is hardest: in tightly capacitated systems with high demand variability. More broadly, our work shows that DRL can deliver economically significant savings in sequential decision problems with interdependent hard constraints, which are widespread in practice.
P. Helm, John C. Doerr, Joren Gijsbrechts et al.· 0 citations
Sequential reinforcement learning (RL) solvers and global diffusion model (DM) solvers for neural combinatorial optimization exhibit complementary failure modes under an optimization-regret view. The former enjoys small marginal regret in the early construction stage, but suffers from horizon-wise compounding errors with super-linear regret growth; the latter avoids horizon compounding but incurs linear or sublinear regret w.r.t. the dimension of the remaining unsolved subspace. We propose Hybrid Neural Solver for Combinatorial Optimization (HyCO), a hybrid inference algorithm that constructs a solution prefix with an RL solver and adaptively switches to a conditional DM to complete the remaining decisions. To characterize why such hybridization helps, when to trigger the handover, and how to realize it in practice, we first develop a unified error-scaling theoretical framework and prove that, under explicit error-scaling assumptions, i) the hybrid structure achieves strictly lower expected regret than either backbone alone, and ii) there exists a unique optimal trigger step that minimizes the hybrid regret. We then design a lightweight adaptive trigger that combines policy entropy and RL-DM disagreement to detect trajectory-level signals of the regime shift as a practical proxy, since the optimal trigger step is defined at the expected-regret level and is not directly computable on individual trajectories. Experimental results on diverse benchmarks demonstrate that HyCO achieves consistent improvements over both backbones and support the empirical effectiveness of adaptive triggering.
Yu-Heng Li, Dian-Qiang Yang, Hai-Peng Chen et al.· 0 citations
This work proposes Double-Channel Graph Attention (DCGA), an end-to-end reinforcement learning framework that isolates network reachability and demand-service logic into separate graph channels and constructs valid routes using a simulator-coupled, constraint-informed decoder.
Hao Sun, Fang He, Congyuan Ji et al.· arXiv.org· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
