Symmetric Tensor Networks for Constrained Combinatorial Optimization and Generative Modeling (Part I)

Constrained combinatorial optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In some heuristic solvers, these are typically addressed by introducing certain Lagrange multipliers in the cost function, by relaxing them in some way, or worse yet, by generating many samples and only to keep valid ones, which leads to very expensive and inefficient searches. In this work, we encode these constraints directly into symmetric tensor networks (TNs) and leverage their applicability as quantum-inspired generative models to assist in the search of solutions to combinatorial optimization problems This allows us to exploit the generalization capabilities of TN generative models while constraining them so that they only output feasible samples.

In part I, we discuss how to incorporate these constraints directly into TN probabilistic models and how to train them so as to only generate valid samples. We argue that our constrained TN generative model is optimal, in that it captures the constraints efficiently while reducing number of parameters and computational costs.

In part II, we apply this formalism to typical constrained problems arising in the domains of generative modeling and combinatorial optimization using symmetric Matrix Product States and show how these can outperform the vanilla (unconstrained) implementations.