Abstract
Deep generative models like GANs and VAEs excel at creating unstructured data but struggle with design problems requiring strict adherence to combinatorial constraints. We introduce GenCO (Generative Combinatorial Optimization), a framework that ensures 100% feasibility by embedding differentiable combinatorial solvers directly into the generative process. GenCO maps latent design descriptions to a feasible manifold, allowing for end-to-end training that optimizes for both population-level diversity and individual solution quality. Our results across gaming, pathfinding, and physics-based design tasks demonstrate that GenCO significantly outperforms traditional generative baselines in both feasibility and uniqueness.
Introduction
The application of generative AI to industrial engineering, material science, and game development is often hindered by the requirement for outputs to satisfy discrete, hard rules. For instance, a generated video game level is useless if it is not playable, and a photonic device is unmanufacturable if it violates minimum feature size constraints.
Standard generative models typically treat these constraints as soft penalties in the loss function. This often results in "hallucinated" solutions that appear plausible but are functionally invalid. Existing alternatives, such as post-processing "fixing" methods or pure optimization, either sacrifice diversity or are too slow for real-time generation.
As shown in the table above, GenCO is the first approach to provide fast solution generation, guaranteed feasibility, and the ability to model data distributions while optimizing nonlinear objectives.
Methodology
The core innovation of GenCO is the integration of a differentiable combinatorial solver $g$ as a layer within the neural network.
The Generative Pipeline
Instead of generating the final object $x$ directly, the generator $G_\theta$ produces a latent design description $c$. This description is then passed to a solver $g$, which outputs a guaranteed feasible solution $x = g(c)$. By definition, $x$ belongs to the feasible set $\Omega$.
Training and Loss Functions
To enable backpropagation through the discrete solver, GenCO utilizes differentiable optimization techniques (e.g., blackbox differentiation). The model is trained using a dual-loss objective:
- Group Loss ($\mathcal{L}$): Ensures the generated population matches the training data distribution, typically implemented via a Wasserstein GAN (WGAN) discriminator.
- Individual Loss ($\mathcal{D}$): Optimizes specific performance metrics for each design, such as path length or physical optimality.
Experimental Evaluation
We evaluated GenCO on three distinct tasks:
- Zelda Level Generation: Generating playable levels from 50 human-crafted examples.
- Warcraft Map Generation: Creating realistic terrain maps optimized for shortest-path traversal.
- Inverse Photonic Design: Designing devices that satisfy manufacturing constraints while maximizing light intensity.
Key Results
GenCO demonstrated superior performance across all benchmarks:
- Diversity: In the Zelda task, GenCO achieved a 99.5% uniqueness rate, whereas a standard GAN followed by a MILP-fixer managed only 52%. This suggests that training with the solver in the loop prevents the "collapse" where many latent points map to the same discrete solution.
- Quality: For Warcraft maps, GenCO reduced the Shortest Path (SP) loss to 23.99, a 35% improvement over ordinary GANs (36.45).
- Optimality: In photonics, GenCO reached perfect optimality (average loss of 0) with 100% unique solutions, a feat baselines failed to replicate.
Conclusion and Future Work
GenCO bridges the gap between the flexibility of generative models and the rigor of combinatorial optimization. By training on the feasible manifold, it ensures that every generated design is valid and high-quality. Future research will focus on improving the scalability of the integrated solvers and extending the framework to handle implicit or "fuzzy" constraints.
Summary updated