Balancing Exploration and Exploitation in Constrained Combinatorial Optimization with U(1)-Symmetric Tensor Trains
Authors: Sergei Iudin, Mikhail Podobrii, Dmitry Zheltkov, Stanislav Moiseev
Organizations: Moscow Independent Research Institute of Artificial Intelligence (MIRAI), Russian Federation · Institute of Numerical Mathematics RAS, Russian Federation · T-Technologies.
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.
Figures & tables
Figure 1: One step of the EELS algorithm for γ=1 .
Figure 2: Example problem, where EELS reveals new samples, while standard approaches do not find any new feasible solutions. a) Charge graph of the problem. Cyan paths correspond to the training data, green and yellow lines show new feasible samples after local search. Red charge is a "newborn" charge. b) TT and the link charges nodes, obtained from the training data (black) and found by local search (red). c) Problem constraints and initial feasible dataset. d) Four illustrated feasible samples; the constraint has six feasible binary solutions in total. The sample color in X matches the color of the corresponding path in the graph.
Figure 3: One two-site training update, following Lopez-Piqueres et al. (2023) . Lines are tensor indices; connected lines are contracted. Orange marks the canonical center. In (b), the physical legs are fixed to the training sample by Kronecker deltas; the dashed slot is not a tensor. In (d), factors are reshaped into TT cores. The leftward update instead puts Σq into the left core.
Figure 4: Number of unique samples in TT for different U(1) -symmetric TT building strategies on the assignment problem.
Figure 5: Comparison of U(1) -symmetric TT building strategies on random problems with N binary variables, m linear equalities and constraints matrix sampled from uniform distribution in range [−r,r] . (a) Number of samples dependency on training dataset size. (b) Wall time to build initial U(1) -symmetric TT. (c),(d) Sample-count ratio versus matrix sparsity.
Objective
W/T/L
Mean (%)
Median (%)
Raw p
Holm p
Linear
125/116/9
3.1
0.0
2×10−19
3.9×10−19
Quadratic
128/100/22
3.1
0.2
1.4×10−15
1.4×10−15
Table 1: Persistent-TT EELS versus Method (ii), with Best Cost selection in both arms: 250 paired instances per objective. W/T/L denotes EELS wins, exact ties, and losses. Means and medians refer to the paired relative improvement R (%). Holm correction covers the two one-sided tests; percentages are rounded to one decimal place.
Figure 6: EELS ( γ=1 ) versus Method (ii), both with Best Cost selection and persistent learned amplitudes. Each box contains 50 paired instances. Purple curves mark group medians and orange curves group arithmetic means. Box edges are the 25th and 75th percentiles; whiskers extend to the most extreme observations within 1.5 interquartile ranges of the box. Outliers are shown individually. Both panels use identical axes. Positive values favor EELS.
Figure 7: ADD versus Best Cost on the parameter-screening instances. Columns show linear (left) and quadratic (right) objectives; rows show GDF ( wfilter=0.4 ), Mixed Selection ( wmix=0.4 ), and Weighted Rank ( wrank=0.35 ). Each box contains 50 paired relative improvements at the indicated number of binary variables. Positive values favor ADD. Box edges are the first and third quartiles; whiskers extend to observations within 1.5 interquartile ranges and remaining observations are shown as points. Green curves with diamond markers and orange curves with circle markers show group medians and arithmetic means, respectively. All panels share axis limits. Each displayed weight maximizes mean relative improvement within its strategy on these same instances.
Figure 8: EELS ( γ=1 ) versus Best Cost with a 200 s budget per arm: linear (left) and quadratic (right) assignment, 50 paired instances per size. Boxes show quartiles and medians; whiskers extend to observations within 1.5 interquartile ranges, with other observations plotted individually. The labelled curves show group medians and means. Positive relative improvement favors EELS. Both panels share axis limits. The training protocol and paired tests are given in Sections 4.5 and 2 .
Figure 9: ADD–GDF ( wfilter=0.4 ) versus Best Cost with a 200 s budget per arm: linear (left) and quadratic (right) assignment, 50 paired instances per size. Boxes show quartiles and medians; whiskers extend to observations within 1.5 interquartile ranges, with other observations plotted individually. The labelled curves show group medians and means. Positive relative improvement favors ADD. Both panels share axis limits. The training protocol and paired tests are given in Sections 4.5 and 2 .
Figure 10: Transfer of assignment-selected GDF ( wfilter=0.4 ) to entropic Set Partitioning. Each locality group contains 135 paired tasks, balanced across nine (m,n) combinations. Top: maximum internal rank of the full structural indicator, on a logarithmic axis. Thin gray intervals show minima–maxima; thick purple intervals show the arithmetic mean ± sample SD; hollow points mark means. These describe task dispersion, not uncertainty in the mean. The orange line uses the independent top axis and gives exact row-major assignment ranks for n=12,…,16 ; horizontal positions do not identify matched tasks across families. Bottom: relative final-cost improvement 100(CBestCost−CADD)/∣CBestCost∣ . Boxes span the first and third quartiles, with median lines; whiskers reach the most extreme observations within 1.5 interquartile ranges and other observations are points. Green diamonds and orange circles denote group medians and means. Positive values favor ADD. Training uses data-built TTs, not the full indicators whose ranks are shown above.
Figure 11: ADD–GDF versus Best Cost on entropic Set Partitioning at 10 s per arm, with 135 pairs per locality group. Boxplot conventions and the relative-improvement definition match Figure 10 . Curves show group medians and means; positive values favor ADD.
Comparison
Objective
Seconds
W/T/L
Mean (%)
Median (%)
Raw p
Holm p
ADD: assignment
Linear
200
179/58/13
3.1
2.4
8.9×10−31
1.2×10−29
ADD: assignment
Quadratic
200
158/41/51
3.8
2.7
1.6×10−18
1.7×10−17
EELS: assignment
Linear
200
120/122/8
2.7
0.0
7.5×10−18
7.5×10−17
EELS: assignment
Quadratic
200
113/112/25
3.6
0.0
9.6×10−16
7.7×10−15
ADD: Set Partitioning
Entropic
10
244/656/45
1.0
0.0
6.0×10−27
7.7×10−26
Table 2: Paired equal-time comparisons with Best Cost. W/T/L denotes wins, exact ties and losses. One-sided paired Wilcoxon signed-rank tests use objective values; descriptive gains are relative percentages. Holm correction covers all 15 pooled tests (five comparisons at three budgets), including those not selected for this table. Assignment rows contain 250 pairs each; Set Partitioning contains 945.
Figure 12: Mean relative improvement over Best Cost versus elapsed-time budget: ADD assignment, EELS assignment, and ADD entropic Set Partitioning. Bars are asymmetric pointwise 95% paired-bootstrap intervals, stratified by problem size and, for Set Partitioning, by (m,n,W) . Checkpoints share runs and are not independent repetitions.
Figure 13: Entropic Set Partitioning: mean ADD gain against the mean maximum rank of the full indicator, one point per locality group and 135 pairs per point. Colors denote elapsed-time budgets; bars are pointwise stratified paired-bootstrap 95% intervals. Lines connect group summaries and do not represent a fitted causal relationship.
Figure 14: Mean feasible-objective gain versus optimization time at n=14 ( N=196 ), with 40 paired tasks per panel and a 200-second nominal budget. Top: assignment; bottom: spatial Set Partitioning. Left: quadratic cost; right: entropic risk. Gain is 100(C0−Cbest)/∣C0∣ per task, then averaged. Shading gives pointwise asymmetric 95% bootstrap intervals for the mean, not task standard deviations. The same initial data are used by all four methods; penalized or infeasible costs never enter the ordinate. EELS and full-indicator TT use the reset/rebuild protocol described in Supplementary Section S3, not persistent-amplitude training.
Figure 15: The same n=14 , 200-second runs as Figure 14 , plotted against cumulative objective calls (logarithmic axis). Calls include the initial evaluations, duplicates, and infeasible penalty-SA points. Each method stops at the smallest final call count among its 40 tasks (endpoint marker); no stopped trajectory is extrapolated. Comparisons are meaningful only on overlapping query ranges. Confidence intervals and gain normalization match Figure 14 . These curves describe query efficiency under time-based cooling, rather than a fixed-query benchmark.
Figure 16: Median wall time for one right–left training sweep and 400 sequential samples on the assignment problem. Both methods receive the same training matrix and start from the same exact uniform feasible state. Initial-state construction is excluded. Both OhMyU1 samplers are shown. The degeneracy of the block dim(V(ck))=1 for each link index.
Figure 17: Exact-indicator benchmarks, with no training or finite-data initialization. (a) The two PROTES curves count float64 coefficients in dense TT cores with uniform or minimal variable ranks; the scalar-block U(1) curve counts only allowed coefficients. Markers measure the complete Julia object, including charges and dictionaries, through n=16 . These are storage sizes, not peak training memory. (b) Median sampling throughput over three seeds; shading shows the observed minimum–maximum range. Each trial accumulates at least one second of timed generation in batches of 100. Counts include repeated draws. Construction, canonicalization, compilation, and diagnostic bookkeeping are excluded. Complete dense models are actually constructed only for 4≤n≤10 ; complete U(1) models are constructed through n=16 . The distributions and binary variable order are identical. Both OhMyU1 sampling backends are shown.
Strategy
Weight
W/T/L
Win (%)
Mean (%)
Median (%)
W
p
Holm (12)
Holm (24)
GDF
wfilter=0.4
235/14/1
94.0
6.9
5.9
27963
9.5×10−41
1×10−39
2.2×10−39
GDF
wfilter=0.3
239/10/1
95.6
6.5
6.0
28908
2.4×10−41
2.8×10−40
5.6×10−40
GDF
wfilter=0.2
232/18/0
92.8
5.8
5.1
27028
4.1×10−40
4.1×10−39
9.1×10−39
Weighted Rank
wrank=0.35
222/21/7
88.8
5.6
5.0
26207
6.8×10−39
5.5×10−38
1.4×10−37
Weighted Rank
wrank=0.5
227/15/8
90.8
5.5
5.0
27531
1.7×10−39
1.5×10−38
3.5×10−38
Weighted Rank
wrank=0.7
225/18/7
90.0
4.9
4.2
26746
1.5×10−38
1.1×10−37
2.9×10−37
Table S1: Linear: every strategy and weight. All rows contain 250 pairs against Best Cost. W/T/L denotes wins/ties/losses for ADD; win rate, mean and median gains are percentages. Holm (12) and Holm (24) adjust the one-sided baseline comparisons within this objective and across both objectives, respectively.
W
Maximum internal rank
Mean internal rank
5
24.0±0.2
17.2±0.8
6
48±1
31±2
8
180±10
100±10
10
660±80
300±40
12
(2.3±0.4)×103
900±200
15
(12±3)×103
(3.0±0.8)×103
Table S3: Exact-indicator ranks in the fixed locality grid: mean ± sample SD over all 135 instances at each span.
W
W/T/L
Mean
95% interval
Median
Holm p
5
3/132/0
0.0
[0.0, 0.1]
0.0
0.125
6
14/121/0
0.3
[0.1, 0.5]
0.0
1.2×10−4
8
27/107/1
0.6
[0.3, 0.9]
0.0
4.1×10−6
10
44/91/0
1.7
[1.2, 2.2]
0.0
3.4×10−13
12
63/69/3
2.5
[1.9, 3.2]
0.0
1.1×10−10
15
75/56/4
3.1
[2.5, 3.8]
1.1
1.5×10−12
Table S4: ADD transfer: 135 pairs per locality. Relative gains and pointwise bootstrap intervals are percentages. W/T/L denotes wins, exact ties and losses; Holm adjustment covers seven one-sided Wilcoxon tests.
Family
Objective
n
Informed SA
Penalty SA
EELS
Full TT
Assignment
Quadratic
10
73.5 / 368.6
24.7 / 103.9
52.4 / 1.6
71.3 / 1.2
Assignment
Quadratic
12
102.8 / 303.3
15.8 / 70.1
55.5 / 0.92
85.1 / 0.34
Assignment
Quadratic
14
132.9 / 252.5
9.8 / 48.1
45.9 / 0.53
75.2 / 0.064
Assignment
Entropic
10
93.3 / 125.2
27.7 / 62.7
76.4 / 1.7
92.7 / 1.2
Assignment
Entropic
12
115.6 / 108.1
18.6 / 45.1
73.9 / 0.98
109.5 / 0.35
Assignment
Entropic
14
141.1 / 95.6
11.7 / 32.4
54.6 / 0.57
106.2 / 0.067
Table S5: 200-second endpoints. Each cell is mean feasible-objective gain (%) / mean objective calls (millions), over 40 tasks. Means include unsuccessful runs.
Family
Objective
n
EELS (%)
W/T/L
Holm p
Full TT (%)
W/T/L
Holm p
Assignment
Quadratic
10
23.3
40/0/0
6.5×10−11
38.5
40/0/0
6.5×10−11
Assignment
Quadratic
12
35.0
39/0/1
6.5×10−11
60.7
40/0/0
6.5×10−11
Assignment
Quadratic
14
33.5
40/0/0
6.5×10−11
60.0
40/0/0
6.5×10−11
Assignment
Entropic
10
38.3
40/0/0
6.5×10−11
51.3
40/0/0
6.5×10−11
Assignment
Entropic
12
48.4
38/1/1
6.5×10−11
78.8
40/0/0
6.5×10−11
Assignment
Entropic
14
41.2
39/0/1
6.5×10−11
87.9
40/0/0
6.5×10−11
Table S6 : Paired improvements over penalty SA at 200 seconds: mean 100(Cpenalty−CTT)/∣Cpenalty∣ (%), wins/ties/losses, and one-sided Wilcoxon p after Holm correction over all 72 TT–penalty comparisons (including 10 and 50 seconds).
Figure S1 : Additional size n=10 ( N=100 ): 200-second runs, 40 tasks per panel. Gain versus optimization time; conventions match Figure 14 of the main article. Top: assignment; bottom: strip Set Partitioning. Left: quadratic; right: entropic. All four methods use matched initial data; TT amplitudes are reset/rebuilt each iteration. Shading denotes pointwise 95% bootstrap intervals for mean per-task gain.
Figure S2 : Additional size n=10 ( N=100 ): 200-second runs, 40 tasks per panel. Gain versus objective calls; conventions and common-support truncation match Figure 15 of the main article. Top: assignment; bottom: strip Set Partitioning. Left: quadratic; right: entropic. All four methods use matched initial data; TT amplitudes are reset/rebuilt each iteration. Shading denotes pointwise 95% bootstrap intervals for mean per-task gain.
Figure S3 : Additional size n=12 ( N=144 ): 200-second runs, 40 tasks per panel. Gain versus optimization time; conventions match Figure 14 of the main article. Top: assignment; bottom: strip Set Partitioning. Left: quadratic; right: entropic. All four methods use matched initial data; TT amplitudes are reset/rebuilt each iteration. Shading denotes pointwise 95% bootstrap intervals for mean per-task gain.
Figure S4 : Additional size n=12 ( N=144 ): 200-second runs, 40 tasks per panel. Gain versus objective calls; conventions and common-support truncation match Figure 15 of the main article. Top: assignment; bottom: strip Set Partitioning. Left: quadratic; right: entropic. All four methods use matched initial data; TT amplitudes are reset/rebuilt each iteration. Shading denotes pointwise 95% bootstrap intervals for mean per-task gain.
n
Train L
Sample L
Total L
Train T
Sample T
Total T
ConstrainTNet
4
0.0025
0.0033
0.0058
0.0024
0.0004
0.0028
1.2
5
0.0061
0.0059
0.012
0.0058
0.0008
0.0066
2.2
6
0.013
0.0096
0.023
0.013
0.0018
0.015
3.4
7
0.028
0.013
0.041
0.028
0.0042
0.032
5.2
8
0.059
0.019
0.078
0.055
0.0091
0.064
8.5
9
0.15
0.029
0.18
0.14
0.021
0.16
14
Table S7: Median times (seconds) for one training sweep and 400 serial samples. L and T denote legacy and table. Total is the sum of the two kernel medians. ConstrainTNet measurements are retained; both OhMyU1 variants use the same inputs. Construction, warm-up, and copying are excluded.
Figure S5 : The same data-initialized comparison at n=8 ( N=64 ), with a 50-second budget and three matched instance/seed pairs for each objective. Dots are individual counts of new distinct feasible points; orange bars and red diamonds show the arithmetic mean and median of the original counts. Both panels use the same log10(1+z) ordinate and limits. All five PROTES configurations and both EELS sampling backends are reported, not only the best observed configuration. These are trained, time-limited runs, unlike the untrained full-indicator sampling experiment in Figure 17 of the main article.
Configuration
Rank
k
ktop
g
Learning rate
e
Initial updates
default
5
100
10
1
0.05
1
4
rank20
20
100
10
1
0.05
1
4
slow10
5
100
10
10
0.01
1
40
batch400
10
400
40
10
0.01
1
10
fit20
5
100
10
1
0.05
20
80
Table S8: PROTES settings. k is the input/generated batch size, ktop the elite count, g the number of Adam steps per accepted batch, and e the number of passes through the initial 400 observations. The last column is the number of initial Adam updates, (400/k)eg .
Configuration
Objective
New points
Generated draws (range)
default
linear
0, 0, 0
3.3M–3.4M
default
quadratic
0, 0, 0
3.1M–3.4M
rank20
linear
0, 0, 0
1.2M–1.5M
rank20
quadratic
0, 0, 0
1.4M–1.6M
slow10
linear
13, 9, 4
3M–3.1M
slow10
quadratic
6, 3, 6
2.7M–2.9M
Table S9: Recorded 50-second PROTES runs at n=8 . Triples are new distinct feasible points in seed order j=0,1,2 ; ranges cover the three runs. Generated counts include infeasible draws.
n
Objective
j
Budget (s)
Iterations
Draws
New points
4
linear
0
5
38/39
380K
0
4
quadratic
0
5
39/40
390K
0
5
linear
0
5
25/26
260K
6
5
quadratic
0
5
26/27
270K
3
6
linear
0
5
16/17
170K
418
6
quadratic
0
5
15/16
160K
406
Table S10: Recorded EELS workloads with the legacy sampler. Iterations are completed/started outer iterations; the last started iteration may be interrupted. All generated draws counted here are feasible. Novelty excludes the initial observations.
n
Objective
j
Budget (s)
Iterations
Draws
New points
4
linear
0
5
90/91
900K
0
4
quadratic
0
5
74/74
740K
0
5
linear
0
5
42/43
430K
6
5
quadratic
0
5
43/44
440K
3
6
linear
0
5
18/19
180K
418
6
quadratic
0
5
20/21
210K
406
Table S11: EELS workloads with the table sampler under the same inputs and budgets as the legacy runs. Iterations are completed/started; novelty excludes initial observations. All counted draws are feasible.
Configuration
Generated draws (range)
default
34K–390K
rank20
54K–140K
slow10
28K–260K
batch400
78K–470K
fit20
120K–340K
Table S12: PROTES 5-second screen: workload ranges over the 14 size/objective pairs per configuration. Each pair uses one seed. Exact per-instance counts and times are stored in the results snapshot.
Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.
We introduce the tubal tensor train (TTT) decomposition, a tensor-network model that combines the t-product algebra of the tensor singular value decomposition (T-SVD) with the low-order core structure of the tensor train (TT) format. For an order-(N+1) tensor with a distinguished tube mode, the proposed representation consists of two third-order boundary cores and N−2 fourth-order interior cores linked through the t-product. As a result, for bounded tubal ranks, the storage scales linearly with the number of modes, in contrast to direct high-order extensions of T-SVD. We present two computational strategies: a sequential fixed-rank construction, called TTT-SVD, and a Fourier-slice alternating scheme based on the alternating two-cores update (ATCU). We also state a TT-SVD-type error bound for TTT-SVD and illustrate the practical performance of the proposed model on image compression, video compression, tensor completion, and hyperspectral imaging.
Lab of Machine Learning and Knowledge Representation, Innopolis University, Innopolis, Russia · Innopolis University, Innopolis, Russia · Skolkovo Institute of Science and Technology, Center for Artificial Intelligence Technology, Moscow, Russia +1
Tensor networks are powerful formats for compressing large-scale data. However, their application to general data processing has been limited by the difficulty of performing nonlinear operations. Here, we introduce iterative tensor network transformations (ITNTs), a general algorithmic framework for the element-wise evaluation of elementary and nonlinear filtering functions on data encoded as tensor trains (TTs), a class of tensor networks. Our approach operates entirely in the compressed domain, enabling efficient computation on exponentially large datasets while maintaining a controlled computational cost. We demonstrate its power in two key areas: (I) evaluating highly nonlinear elementary and filtering functions on a 3D reactive flow field, enabling high-fidelity reaction rate computation and region filtering, and (II) finding extrema in complex optimization problems, such as solving Max-SAT instances on spaces up to 270 configurations. These results establish ITNT as a foundational tool that provides tensor network methods with the capability for general-purpose data science and large-scale optimization.
Xiao Wang, Tomohiro Hashizume, Pia Siegl +1
Clarendon Laboratory, University of Oxford, Parks Road, Oxford OX1 3PU, United Kingdom · The Hamburg Centre for Ultrafast Imaging, Luruper Chaussee 149, Hamburg 22761, Germany. · Institute for Quantum Physics, University of Hamburg, Luruper Chaussee 149, Hamburg 22761, Germany +1
Tensor-train (TT) compression reduces neural-network parameters, but the latency of a tensorized layer is set by its contraction order and its mapping onto hardware: a contraction path with fewer multiply-accumulate operations (MACs) is not necessarily faster on a systolic array. We present a deployment-constrained, latency-guided design space exploration (DSE) framework for fixed-rank tensorized neural networks (TNNs) under a fixed processing-element (PE) budget. Using MAC-guided path pruning, it evaluates feasible combinations of contraction paths, three PE-array partitions, and input-, output-, and weight-stationary dataflows. By minimizing the sum of inference and training latency estimates, it selects a single physical PE partition shared across layers and both modes, while allowing layer- and mode-specific paths and dataflows. On ResNet-18 and ViT-Ti/4, 25%-50% of the layers select a path other than the minimum-MAC one, the best dataflow varies across layers and models, and on a representative ViT layer the latency-selected candidate reduces simulated latency by 23.5% relative to the minimum-MAC candidate. Deployed on a Xilinx VU9P FPGA accelerator that supports both inference and training, the complete TT+INT8 system achieves 3.28x-4.00x inference and 3.42x-3.85x training speedups over dense implementations with the same PE budget.
Jinsong Zhang, Minghe Li, Jiayi Tian +2
Department of Electrical and Computer Engineering, University of California, Santa Barbara, USA