Balancing Exploration and Exploitation in Constrained Combinatorial Optimization with U(1)-Symmetric Tensor Trains
Organizations: Moscow Independent Research Institute of Artificial Intelligence (MIRAI), Russian Federation · Institute of Numerical Mathematics RAS, Russian Federation · T-Technologies.
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.
Figures & tables
| Objective | W/T/L | Mean (%) | Median (%) | Raw | Holm |
|---|---|---|---|---|---|
| Linear | 125/116/9 | 3.1 | 0.0 | ||
| Quadratic | 128/100/22 | 3.1 | 0.2 |
| Comparison | Objective | Seconds | W/T/L | Mean (%) | Median (%) | Raw | Holm |
|---|---|---|---|---|---|---|---|
| ADD: assignment | Linear | 200 | 179/58/13 | 3.1 | 2.4 | ||
| ADD: assignment | Quadratic | 200 | 158/41/51 | 3.8 | 2.7 | ||
| EELS: assignment | Linear | 200 | 120/122/8 | 2.7 | 0.0 | ||
| EELS: assignment | Quadratic | 200 | 113/112/25 | 3.6 | 0.0 | ||
| ADD: Set Partitioning | Entropic | 10 | 244/656/45 | 1.0 | 0.0 |
| Strategy | Weight | W/T/L | Win (%) | Mean (%) | Median (%) | Holm (12) | Holm (24) | ||
|---|---|---|---|---|---|---|---|---|---|
| GDF | 235/14/1 | 94.0 | 6.9 | 5.9 | 27963 | ||||
| GDF | 239/10/1 | 95.6 | 6.5 | 6.0 | 28908 | ||||
| GDF | 232/18/0 | 92.8 | 5.8 | 5.1 | 27028 | ||||
| Weighted Rank | 222/21/7 | 88.8 | 5.6 | 5.0 | 26207 | ||||
| Weighted Rank | 227/15/8 | 90.8 | 5.5 | 5.0 | 27531 | ||||
| Weighted Rank | 225/18/7 | 90.0 | 4.9 | 4.2 | 26746 |
| Maximum internal rank | Mean internal rank | |
|---|---|---|
| 5 | ||
| 6 | ||
| 8 | ||
| 10 | ||
| 12 | ||
| 15 |
| W/T/L | Mean | 95% interval | Median | Holm | |
|---|---|---|---|---|---|
| 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 | |
| 8 | 27/107/1 | 0.6 | [0.3, 0.9] | 0.0 | |
| 10 | 44/91/0 | 1.7 | [1.2, 2.2] | 0.0 | |
| 12 | 63/69/3 | 2.5 | [1.9, 3.2] | 0.0 | |
| 15 | 75/56/4 | 3.1 | [2.5, 3.8] | 1.1 |
| Family | Objective | 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 |
| Family | Objective | EELS (%) | W/T/L | Holm | Full TT (%) | W/T/L | Holm | |
|---|---|---|---|---|---|---|---|---|
| Assignment | Quadratic | 10 | 23.3 | 40/0/0 | 38.5 | 40/0/0 | ||
| Assignment | Quadratic | 12 | 35.0 | 39/0/1 | 60.7 | 40/0/0 | ||
| Assignment | Quadratic | 14 | 33.5 | 40/0/0 | 60.0 | 40/0/0 | ||
| Assignment | Entropic | 10 | 38.3 | 40/0/0 | 51.3 | 40/0/0 | ||
| Assignment | Entropic | 12 | 48.4 | 38/1/1 | 78.8 | 40/0/0 | ||
| Assignment | Entropic | 14 | 41.2 | 39/0/1 | 87.9 | 40/0/0 |
| 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 |
| Configuration | Rank | Learning rate | 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 |
| 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 |
| Objective | 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 |
| Objective | 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 |
| Configuration | Generated draws (range) |
|---|---|
| default | 34K–390K |
| rank20 | 54K–140K |
| slow10 | 28K–260K |
| batch400 | 78K–470K |
| fit20 | 120K–340K |
Combinatorial Optimization
Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.
See all 412 papers