Paperlane

no. 17 · Wednesday 18 November 2026

Balancing Exploration and Exploitation in Constrained Combinatorial Optimization with U(1)-Symmetric Tensor Trains

Sergei Iudin, Mikhail Podobrii, Dmitry Zheltkov and Stanislav Moiseev

math.OC · code · 39 pp

Abstract

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. On assignment benchmarks, expressibility enhancement and diversity-aware selection improve mean solution quality over their respective baselines. The assignment-selected diversifying strategy also extends to nonpolynomial Set Partitioning, with larger relative gains observed in the higher-tensor-rank data families. Separate runtime benchmarks show substantial speedups over ConstrainTNet and PROTES on non-degenerate assignment workloads; comparisons with simulated annealing depend on constraint information and computational budget, but, overall, support the practicality of the current implementation.

code
github.com/antientropic-guy/OhMyU1_public
comments
39 pages, including supplementary material. Code: https://github.com/antientropic-guy/OhMyU1_public. Extends an earlier version presented at the non-archival CoLoRAI workshop at ICML 2026
fields
Optimization and Control
pdf ↗ page arXiv:2611.22557 ↗