U(1)-对称张量链新框架:求解带硬约束的组合优化问题
Balancing Exploration and Exploitation in Constrained Combinatorial Optimization with U(1)-Symmetric Tensor Trains
搞优化或运筹的朋友可以看看这篇:用 U(1)-对称张量网络把硬约束直接编码进 TT 结构,在 assignment 任务上比 PROTES 和 ConstrainTNet 更快,解质量也有提升。如果常做调度、Set Partitioning 这类约束问题,值得复现试试。
arXiv 上的新论文提出基于 U(1)-对称张量网络(Tensor Train,TT)的约束组合优化通用框架,解决现有 TT 方法在可行解稀少时难以嵌入硬线性约束的难题。方法包含两个核心机制:一是针对稀疏对称张量的表达力增强机制,二是基于图的多样性度量,用于在训练过程中指导样本选择,平衡探索与利用。
在 assignment 基准上,表达力增强与多样性感知选择分别较各自基线提升了平均解质量;这种经 assignment 选出的多样化策略还能推广到非多项式的 Set Partitioning 问题,在高张量秩数据族上相对增益更大。运行时基准显示,该方法在非退化 assignment 负载上相比 ConstrainTNet 和 PROTES 有显著加速。
与模拟退火的对比取决于约束信息可得性与计算预算,但整体结果支持当前实现的实用性。这类基于对称张量网络的方法可在成本函数结构未知的情况下高效表示和探索高维离散空间,为调度、分配类约束优化提供了新工具。
Balancing Exploration and Exploitation in Constrained Combinatorial Optimization with U(1)-Symmetric 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. 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.
This report is categorized under AITOP's "Papers" desk. Key entities and technical topics under continuous tracking include Tensor Train, combinatorial optimization, tensor networks.
Source attribution: curated from arXiv cs.LG (@Sergei Iudin, Mikhail Podobrii, Dmitry Zheltkov, Stanislav Moiseev).