GenCO: Generating Diverse Designs with Combinatorial Constraints

Aaron M Ferber, Arman Zharmagambetov, Taoan Huang, Bistra Dilkina, Yuandong Tian

TL;DR

GenCO is a new generative framework that guarantees the designs it produces—like game levels or photonic circuits—strictly follow hard combinatorial rules. By embedding differentiable solvers directly into the training loop, GenCO ensures every generated output is provably feasible while maintaining high diversity and quality.

What Problem Does This Paper Address?

Deep generative models like GANs and VAEs are masters of "vibes"—they can generate realistic-looking faces or landscapes by mimicking a data distribution. However, they struggle with "logic." If you ask a standard GAN to generate a playable video game level, it might produce something that looks like a level but lacks a valid path from the start to the exit.

In industrial design, material science, and robotics, "looking right" isn't enough; the output must satisfy hard combinatorial constraints (e.g., a circuit must be manufacturable, or a path must exist). Previous attempts to solve this usually relied on "soft" penalties (which don't guarantee success) or post-processing "fixes" (which often result in repetitive, low-quality designs because the generative model wasn't aware of the fix during training).

Comparison of GenCO against existing generative and optimization approaches.

As shown above, existing methods force a trade-off between generation speed, feasibility guarantees, and the ability to model complex data distributions. GenCO aims to check all the boxes.

Methods

The authors propose GenCO (Generating Diverse Designs with Combinatorial Constraints). The core innovation is moving the "feasibility check" from a post-processing step into the heart of the training process.

The GenCO architecture pipeline.

The framework operates through a specialized pipeline:

  1. Latent Design Space: Instead of generating the final object $x$ directly, the generator $G_\theta$ produces a latent description $c$ (e.g., a cost map or a set of weights).
  2. Differentiable Solvers: This description $c$ is fed into a combinatorial solver $g(c)$—such as a Mixed Integer Linear Program (MILP) solver or a shortest-path algorithm. This solver outputs a solution $x$ that is guaranteed to be feasible.
  3. End-to-End Training: Crucially, the authors use techniques to backpropagate gradients through these discrete solvers. This allows the generator to learn how its latent descriptions $c$ affect the final, feasible output $x$.
  4. Dual Loss Functions: The model optimizes for two things simultaneously:
  5. Group Loss ($\mathcal{L}$): Ensures the population of generated designs matches the diversity and style of the training data (e.g., using a Wasserstein GAN loss).
  6. Individual Loss ($\mathcal{D}$): Optimizes for specific quality metrics, like minimizing the cost of a path or maximizing the efficiency of a photonic device.

Key Insights and Ideas

  • Training on Reality, Not "Soft" Guesses: By calculating the loss on the final feasible solution rather than an intermediate "soft" version, the generator learns the true landscape of valid designs.
  • The "Hiding" Problem: In previous methods, generators could "hide" from the discriminator by making tiny continuous changes that didn't actually change the discrete failure of the design. GenCO forces the generator to face the discrete reality, leading to much higher uniqueness.
  • Solver Agnostic: GenCO is flexible. It can work with GANs or VAEs and can incorporate various solvers (Gurobi, Dijkstra’s, etc.) as long as they can be differentiated or approximated.

Datasets and Key Results

The authors evaluated GenCO on three distinct domains, consistently outperforming baselines:

  • Zelda Game Levels: Based on a dataset of 50 human-crafted levels, the constraint is "playability" (a path must exist to the exit). GenCO produced 99.5% unique solutions, compared to just 52% for the standard "generate and fix" baseline.
  • Warcraft Maps: Using 10,000 terrain maps for path planning, the goal is to generate realistic maps where the shortest path from top-left to bottom-right is minimized. GenCO achieved a shortest path loss of 23.99, significantly better than the Ordinary GAN (36.45) and the "soft penalty" approach (35.61).
  • Photonic Device Design: On a dataset of 100 optimal solutions for light-routing devices with strict manufacturing rules, GenCO achieved a 100% uniqueness rate and an average solution loss of 0 (meaning perfect performance). In contrast, the VQVAE + post-process baseline struggled with high loss and redundant designs.

Limitations and Future Work

While powerful, GenCO has a few hurdles:

  • Computational Overhead: Running a combinatorial solver (like a MILP) inside every training iteration is slower than standard backpropagation.
  • Mathematical Formalism: The user must be able to express their constraints as a mathematical optimization problem that a solver can handle.

For future work, the authors suggest exploring "learning constraints from data" for domains where rules aren't easily written down as equations (e.g., aesthetic preferences or complex social fairness constraints). They also aim to improve the scalability of the differentiable solvers to handle even larger, more complex design spaces.

Summary updated

Abstract

Deep generative models like GAN and VAE have shown impressive results in generating unconstrained objects like images. However, many design settings arising in industrial design, material science, computer graphics and more require that the generated objects satisfy hard combinatorial constraints or meet objectives in addition to modeling a data distribution. To address this, we propose GenCO, a generative framework that guarantees constraint satisfaction throughout training by leveraging differentiable combinatorial solvers to enforce feasibility. GenCO imposes the generative loss on provably feasible solutions rather than intermediate soft solutions, meaning that the deep generative network can focus on ensuring the generated objects match the data distribution without having to also capture feasibility. This shift enables practitioners to enforce hard constraints on the generated outputs during end-to-end training, enabling assessments of their feasibility and introducing additional combinatorial loss components to deep generative training. We demonstrate the effectiveness of our approach on a variety of generative combinatorial tasks, including game level generation, map creation for path planning, and photonic device design, consistently demonstrating its capability to yield diverse, high-quality solutions that verifiably adhere to user-specified combinatorial properties.
BibTeX
@inproceedings{ferber2024genco,
  author = {Aaron M Ferber and Arman Zharmagambetov and Taoan Huang and Bistra Dilkina and Yuandong Tian},
  title = {{GenCO: Generating Diverse Designs with Combinatorial Constraints}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=DiyE6OOGBa},
}
Figure