Exploration-Exploitation Generative Framework for Constrained Combinatorial Optimization with Tensor Trains

Tensor Train (TT) decomposition has emerged as a powerful tool for mitigating the curse of dimensionality in a variety of machine learning and combinatorial optimization tasks. Recent advances show that TT - based generative models can efficiently represent and explore high-dimensional discrete spaces, even when the cost function structure is unknown. However, incorporating hard linear constraints into TT - based optimization remains challenging, as existing interpolation and sampling approaches often fail when feasible points are rare. In this work, we develop a general TT - based framework for constrained combinatorial optimization built upon U(1) - symmetric tensor networks. Our method introduces an expressibility - enhancement mechanism for constructing sparse symmetric tensors and a graph - based diversity measure that guides sample selection during training. Experiments demonstrate that our Julia implementation significantly outperforms existing open - source libraries.