GenCO: Generating Diverse Solutions to Design Problems with
  Combinatorial Nature
Aaron Ferber Arman Zharmagambetov Taoan Huang Bistra Dilkina Yuandong Tian
Generating diverse objects (e.g., images) using generative models (such as
GAN or VAE) has achieved impressive results in the recent years, to help solve
many design problems that are traditionally done by humans. Going beyond image
generation, we aim to find solutions to more general design problems, in which
both the diversity of the design and conformity of constraints are important.
Such a setting has applications in computer graphics, animation, industrial
design, material science, etc, in which we may want the output of the generator
to follow discrete/combinatorial constraints and penalize any deviation, which
is non-trivial with existing generative models and optimization solvers. 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.