GenCO: Generating Diverse Solutions to Design Problems with Combinatorial Nature

Aaron M Ferber, Arman Zharmagambetov, Taoan Huang, Bistra Dilkina, Yuandong TianSubmission to ICLR 2024 · Rejected

TL;DR

GenCO bridges the gap between deep generative models and combinatorial optimization by embedding differentiable discrete solvers directly into the training loop. Rather than generating final designs that require post-hoc repair, GenCO learns to generate problem parameters that project onto or optimize discrete constraints end-to-end. This approach yields high-fidelity, diverse designs that strictly adhere to hard combinatorial rules or minimize downstream combinatorial penalties.

What Problem Does This Paper Address?

Many real-world design problems—such as video game level generation, routing layouts, and circuit or photonic device design—demand two conflicting capabilities:

  1. Diversity and realism: Generating varied, authentic solutions that mimic complex data distributions (traditionally handled well by GANs and VAEs).
  2. Combinatorial feasibility: Adhering strictly to discrete logical constraints (e.g., ensuring a game level has a playable path from start to exit, or that physical manufacturing geometry is respected).

Existing approaches struggle with this intersection. Traditional mixed-integer programming (MIP) methods find valid solutions but fail to model data distributions or produce diverse unstructured outputs like images. Conversely, standard deep generative models easily generate invalid, unplayable, or unmanufacturable designs. Post-processing ("generate, then repair with a solver") creates severe mode collapse: many distinct continuous outputs end up repaired into the exact same discrete solution.

Methods

GenCO introduces a bi-objective training framework that incorporates a combinatorial solver into the generative learning pipeline via two paradigms:

[Noise ε] ──> [ Generator G(ε; θ) ] ──> [ Problem Representation c ]
                                                  │
                 ┌────────────────────────────────┴──────────────────┐
                 ▼                                                   ▼
       [ Combinatorial Solver ]                            [ Generative Loss ]
       (e.g., MILP / Dijkstra)                             (Discriminator / ELBO)
                 │                                                   │
                 ▼                                                   ▼
       [ Feasible/Optimal x* ] ─────────> [ Combined Loss & Backprop ]
  • Constrained Generation (Hard Constraints): The generator outputs an unconstrained continuous representation $c$. An embedded combinatorial solver acts as a projection layer, finding the nearest feasible discrete solution: $$\tilde{x} = \arg\max_{x \in \Omega} c^T x$$ The generative loss (e.g., GAN discriminator or VQ-VAE ELBO) is evaluated strictly on the feasible output $\tilde{x}$. Gradients flow backward through the discrete solver into the generator using differentiable solver techniques (such as blackbox combinatorial differentiation or identity-with-projection).

  • Penalized Generation (Soft Constraints): When constraints are preferences rather than strict rules (e.g., keeping path-traversal costs low), $c$ is passed to a solver (like Dijkstra’s shortest-path algorithm) to compute a downstream cost, which is added directly to the generator's objective function.

Datasets

The authors evaluated GenCO across three distinct benchmarks:

  • Zelda Game Level Generation: 50 human-designed tile-based Zelda levels (Zhang et al., 2020) with 8 discrete tile types (walls, player, key, exit, enemies). Validity requires a playable path from the player to the key and then to the exit.
  • Warcraft Path Planning: 10,000 $12 \times 12$ terrain map images from the Warcraft II tileset (Pogančić et al., 2020). The goal is to generate realistic terrain maps while minimizing the shortest-path cost from the top-left to the bottom-right corner.
  • Inverse Photonic Device Design (Appendix): 100 benchmark solutions for routing light wavelengths under strict silicon foundry fabrication rules, evaluated with non-linear Maxwell equation simulations (Schubert et al., 2022).

Key Insights and Ideas

  • End-to-End Training Prevents Mode Collapse: When a generative model is trained independently and "fixed" after generation, the generator learns to hide artifacts in continuous space that all snap to the same discrete state. Training end-to-end through the solver forces the generator to diversify within the actual feasible discrete space.
  • Discriminators Benefit from Feasibility: In adversarial training, evaluating the discriminator only on feasible outputs prevents it from wasting model capacity on trivial constraint checking (e.g., spotting missing keys), forcing it to learn subtle stylistic realism instead.
  • Targeted vs. Global Optimization: In the Warcraft task, simply penalizing expensive tiles globally led to uniform, bland maps. GenCO's solver-based penalty optimized edge weights along the actual shortest path, preserving terrain variety across the rest of the map.

Key Results

  • Zelda Levels: GenCO with an updating adversary achieved 99.5% unique levels out of 1,000 samples, compared to only 52.0% for the standard GAN + post-hoc MILP baseline, while achieving vastly superior adversary realism scores ($-10.10$ vs. $0.22$).
  • Warcraft Maps: GenCO reduced shortest-path traversal cost to 23.99 (compared to 36.45 for Ordinary GAN and 35.61 for a cost-penalized baseline) while maintaining low GAN loss ($0.6360$ vs. $0.6147$), achieving an optimal balance between map realism and efficient traversal.
  • Photonic Design: Paired with a VQ-VAE, GenCO generated 100% unique devices with 0 solution loss (perfect physical performance) and high data coverage ($0.738$), whereas post-hoc repair produced only $30.6\%$ unique devices with poor optical performance (loss of $1.244$).

Limitations and Future Work

  • Solver Runtime Overhead: Embedding mixed-integer linear programs or graph search algorithms inside every training iteration increases per-epoch wall-clock training time compared to standard deep learning models.
  • Reliance on Linear Approximations: The projection mechanism relies on linear surrogate representations ($c^T x$), which may require domain-specific formulations when dealing with complex non-linear constraints.
  • Scalability: Expanding beyond moderate grid sizes (e.g., $12 \times 12$ graphs or small game grids) to large-scale, high-resolution combinatorial systems remains an open engineering challenge.

Summary updated

Abstract

The generation of diverse but realistic objects that have combinatorial properties has various practical applications across several fields, including computer graphics, animation, industrial design, material science, etc. For instance, we might want to restrict the output of the generator so that it satisfies discrete constraints or encourage certain combinatorial properties as a penalty. However, existing generative models and optimization solvers often struggle to concurrently ensure solution diversity and uphold the underlying combinatorial nature. To address this, we propose $GenCO$, a novel framework that conducts end-to-end training of deep generative models integrated with embedded combinatorial solvers, aiming to uncover high-quality solutions aligned with nonlinear objectives. While structurally akin to conventional generative models, $GenCO$ diverges in its role - it focuses on generating instances of combinatorial optimization problems rather than final objects (e.g., images). This shift allows finer control over the generated outputs, enabling assessments of their feasibility and introducing an additional combinatorial loss component. We demonstrate the effectiveness of our approach on a variety of generative tasks characterized by combinatorial intricacies, including game level generation and map creation for path planning, consistently demonstrating its capability to yield diverse, high-quality solutions that reliably 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 Solutions to Design Problems with Combinatorial Nature}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=DiyE6OOGBa},
}
Figure