betaFeedback

WorksMathematics

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

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.

Introduction

Tensor Train (TT) decomposition has become a powerful tool in the domains of Artificial Intelligence and Combinatorial Optimization in recent years. The idea of squeezing high-dimensional data via tensor train decomposition originated in the field of quantum mechanics ([1, 26]), where many-dimensional systems naturally arise from particle interactions. In 2011, Oseledets formalized the approach and brought these ideas into computational mathematics ([21]). To date, TT decomposition was applied to low-rank network layer approximation ([20]), LLM fine-tuning ([27]), optimization ([3, 18]), options pricing ([4]), and some others ([7, 11, 25, 24])

This paper focuses on applications of TT in combinatorial optimization. In comparison to classical mixed-integer linear programming (MILP) TT is not limited to linear cost functions and does not use any integrality relaxation. In comparison to Constraint Programming (CP) solvers ([6]) and QAOA ([8]), the cost function structure may be unknown. Compared with Bayesian optimization ([12]), TT can offer favorable scaling when the required ranks remain moderate .

We know two paradigms for TT-based optimization. First, we may request cost function values at specific grid points, then interpolate the entire landscape using a low TT-rank assumption ([28, 23]). Second, we may apply a generative approach ([5]): based on some data, learn a probability distribution that encourages low-cost values, and store it as TT. Then we may sample new data from it and use the data for further training until a stopping criterion is reached. TT-format speeds up both the training and sampling phases, making high-dimensional distribution tractable.

The challenge of applying TT to combinatorial optimization appears when variables are constrained to a feasible region (e.g., by linear equalities). In such a case, building a TT surrogate for the cost function is difficult due to a large fraction of infeasible grid points. The probability of finding any feasible point is small, and interpolation based on infeasible points is not informative. On the contrary, even a straightforward generative approach may be pre-trained on feasible data, and in a sampling phase, all infeasible samples may be eliminated. However, if the constraints are hard to satisfy, the algorithm’s efficiency may decrease significantly. To address the challenge of constraint embedding, the authors in Nakada et al., [19] used the method of nilpotent matrices. While effective for some practical cases, it is not generalizable to arbitrary linear equations because of exponential scaling with the number of constraints. In Ryzhakov & Oseledets, [22], the authors represent the method of exact constraints encoding, but only for constraints that have a particular structure, which is consistent with the tensor train linear topology and locality of interactions. The paper Lopez-Piqueres et al., [17] suggests using U(1)U(1)-symmetric tensor networks for problems with linear constraints. The available feasible dataset was used to build a sparse probability distribution tensor, assigning zero probability to all infeasible vectors. Later, an exact framework for incorporating any linear inequalities into a symmetric TT structure was developed Lopez-Piqueres & Chen, [16], with a code available on git Lopez-Piqueres, [15].

Main contributions. We developed a library for constrained optimization, using tensor trains. Our approach is based on a generative U(1)U(1)-symmetric paradigm, which accommodates arbitrary integer linear equalities, although computational cost depends on the resulting charge structure. Two major contributions expand the paradigm: i) We suggested the expressibility enhancement step, increasing feasible dataset exploitation. Thus, instead of only two strategies of building a sparse U(1)U(1)-symmetric tensor from the feasible data, as in the pioneer paper, we suggest a family of such strategies, controlled by a parameter (exploitation power). The tested enhancement improves mean assignment solution quality over the original construction. ii) We represented a sparse symmetric tensor train as a graph of U(1)U(1) charges, and suggested a graph diversity measure, which helps to choose which samples to use for training on the next algorithm iteration (increasing exploration). The assignment-selected diversifying strategy also improves mean quality on entropic Set Partitioning, with benefits concentrated in higher-tensor-rank data families. Our Julia implementation achieves 77–448× speedups over ConstrainTNet Lopez-Piqueres, [15] on the specified non-degenerate assignment kernel benchmark, depending on size and sampling backend.

Problem Statement

We consider a similar class of optimization problems as in Lopez-Piqueres et al., [17]:

{C(x)→min⁡,Ax=b,x∈{0,1}N,(1)\begin{cases} C(x) \to\min,\\ Ax=b,\\ x \in\{0,1\}^{N}, \tag*{(1)} \end{cases}

where C:{0,1}N→RC:\{0,1\}^{N}\to\mathbb{R} is a black-box objective function, AA and bb are integer-valued. We emphasize that the domain of the xx variable may be, in principle, any finite integer domain; also, AA and bb may be rational, if they are obtained from an integer by dividing by some scaling factor.

Generic black-box solvers can struggle with hard constraints. E.g., Simulated Annealing (SA) Kirkpatrick et al., [13] requires a random step implementation that maintains feasibility. Or constraints may be implemented as penalties of the form λ∥Ax−b∥22\lambda\lVert Ax-b\rVert_{2}^{2}, but this may be even more problematic, because of the necessity to choose a value for λ\lambda and probably a low fraction of feasible solutions evaluated. In this work, we assume that some feasible data for hard constraints is available. This may be due to one of the following reasons: i) There is a feasible dataset sampler available, which may produce diverse feasible samples using some knowledge about the matrix AA and vector bb. The optimization itself may still be very challenging due to the black-box function C(x)C(x), which, in the worst case, takes a long time to evaluate. ii) Feasible space may be explored in some other way, e.g., with a random search / MILP / CP solver, etc.

Tensor Train Generative Modeling

Algorithm 1 describes a family of generative optimization procedures based on tensor-train (TT) probability models. The method maintains a distribution Pθ(x)P_{\theta}(x) for an integer vector x=(x1,…,xN)x=(x_{1},\ldots,x_{N}):

πθ(x)=∑α1,…,αN−1Gα1,x1,α1(1)Gα1,x2,α2(2)⋯GαN−1,xN,1(N),\pi_{\theta}(x)=\sum_{\alpha_{1},\ldots,\alpha_{N-1}}G^{(1)}_{\alpha_{1},x_{1},\alpha_{1}}G^{(2)}_{\alpha_{1},x_{2},\alpha_{2}}\cdots G^{(N)}_{\alpha_{N-1},x_{N},1},
Pθ(x)=∣πθ(x)∣2/ZθorPθ(x)=πθ(x).(2)P_{\theta}(x)=|\pi_{\theta}(x)|^{2}/Z_{\theta}\quad\text{or}\quad P_{\theta}(x)=\pi_{\theta}(x). \tag*{(2)}

The first choice is a Born machine; the second requires a nonnegative, normalized TT. The implementations considered below use the Born rule. An initial feasible dataset supplies a starting model and a best-so-far solution. At each iteration, the model generates candidates, a selection policy constructs the next training set, and a weighted likelihood update biases the model toward promising solutions. The incumbent is maintained separately from training data and is never discarded by diversification.

Selection and memory. The candidate pool may contain only current TT samples, or also externally generated feasible points and retained data. The selection policy may favor low cost, charge diversity, or their combination; it also specifies whether initial points or a history participate. Neither elite-only selection nor cumulative retention is intrinsic to the framework. For finite computational cost, experiments specify a selection quota and a memory policy explicitly.

Optional diversification. Before fitting the selected data, an operator DtD_t may leave the TT unchanged, reset its amplitudes, or apply a preliminary sweep with equal sample weights. The last choice flattens the empirical training target; a single sweep does not guarantee a uniform model over its entire feasible support. Diversification can be periodic or triggered by stagnation. It must preserve feasibility and provide nonzero support for positive-weight training points. These options define different algorithms, not interchangeable implementations of the same experiment. With DtD_t equal to the identity, learned amplitudes persist across iterations. The comparison in § 3.2 uses this choice; in § 2.5, algorithm rebuilds the model after selection, while the SA comparison in § 4.1 uses the explicitly stated reset/rebuild variant. The schematic loop can be cyclically organized as train–sample–select when the initial dataset is trained before the first sampling phase.

For the constrained problem (1), it is much more effective to initialize the tensor with some sparse structure, with zero probabilities for vectors that violate constraints. It helps avoid generating such samples that violate the problem’s hard constraints. For this purpose, we exploit properties of U(1)U(1)-symmetry. Let us define it carefully, but first, give some preliminary definitions. We consider a tensor πx1…xN\pi_{x_1\ldots x_N} for which the following holds:

  • Each index xkx_k has one of two possible orientations (directions): xk∈Iinx_k \in I_{\mathrm{in}} or xk∈Ioutx_k \in I_{\mathrm{out}}. We call IinI_{\mathrm{in}} a set of incoming indices and IoutI_{\mathrm{out}} a set of outgoing indices.

  • Each value of index xkx_k may be decomposed into the pair of values (cxk,tcxk)(c_{x_k},t_{c_{x_k}}), where we call cxkc_{x_k} a charge index, and tcxkt_{c_{x_k}} a degeneracy index. In this paper, the charges may be integers or integer vectors. More formally, for each kk linear space V(k)V^{(k)} (associated with index xkx_k) is a direct sum of charge subspaces:

V(k)=⨁ckV(ck).(3)V^{(k)} = \bigoplus_{c_k} V^{(c_k)}. \tag*{(3)}

Let Cin=∑xi∈IincxiC_{\mathrm{in}} = \sum_{x_i \in I_{\mathrm{in}}} c_{x_i}, and Cout=∑xi∈IoutcxiC_{\mathrm{out}} = \sum_{x_i \in I_{\mathrm{out}}} c_{x_i}. We say that the set of index values (x1,…,xN)(x_1,\ldots,x_N) conserves the charge cc if Cin−Cout=cC_{\mathrm{in}} - C_{\mathrm{out}} = c. Finally, we call the tensor πx1…xd\pi_{x_1\ldots x_d} U(1)U(1)-symmetric if the following holds for some charge cc and all possible values of indices (x1,…,xN)(x_1,\ldots,x_N):

πx1…xN=(Pc1…cN)tc1…tcNδCin,Cout+c,(4)\pi_{x_1\ldots x_N} = \left(P_{c_1\ldots c_N}\right)_{t_{c_1}\ldots t_{c_N}} \delta_{C_{\mathrm{in}},C_{\mathrm{out}}+c}, \tag*{(4)}

where δi,j\delta_{i,j} is the Kronecker delta symbol, ck=cxk ∀kc_k = c_{x_k}\ \forall k and Pc1…cN\mathcal{P}_{c_1\ldots c_N} is a tensor indexed only by charges. Informally, that means that π\pi becomes block-sparse. If πx1,…,xN\pi_{x_1,\ldots,x_N} is U(1)U(1)-symmetric, then πx1,…,xN=0\pi_{x_1,\ldots,x_N}=0 for all sets of values (x1,…,xN)(x_1,\ldots,x_N) that do not conserve the charge cc. In such cases, cc is called a flux of the tensor. We will also call (4) a charge conservation law.

Algorithm 1Generative optimization with a tensor train
Require:Initial feasible data T0\mathcal{T}_0, sampling budget KK, iteration budget TT, selection/memory policy St\mathcal{S}_t, optional diversification Dt\mathcal{D}_t
1:Initialize PθP_\theta and incumbent x⋆x^\star from T0\mathcal{T}_0; initialize history state HH
2:for t=1,…,Tt=1,\ldots,T do
3:Sample KK candidates from PθP_\theta; optionally augment the pool from available feasible-data sources
4:Evaluate candidates as prescribed; update x⋆x^\star using evaluated feasible points
5:(Tnew,H)←St(candidates,T0,H)(\mathcal{T}_{\mathrm{new}},H) \leftarrow\mathcal{S}_t(\text{candidates},\mathcal{T}_0,H)
6:θ←Dt(θ,Tnew,H)\theta\leftarrow\mathcal{D}_t(\theta,\mathcal{T}_{\mathrm{new}},H) {Identity if omitted}
7:Assign normalized weights wiw_i to x(i)∈Tnewx^{(i)} \in\mathcal{T}_{\mathrm{new}}
8:Update θ\theta by minimizing −∑x(i)∈Tnewwilog⁡Pθ(x(i))-\sum_{x^{(i)}\in\mathcal{T}_{\mathrm{new}}} w_i\log P_\theta(x^{(i)})
9:end for
10:return x⋆x^\star

Table 1.

Generative modeling with U(1)U(1)-symmetry

The rigorous description of a generative algorithm based on U(1)U(1)-symmetric tensor trains may be found in Lopez-Piqueres et al., [17]. All crucial steps from Algorithm 1 remain the same, but require less memory for storing PθP_\theta, as only nonzero blocks are stored. Also, the big saving of computational resources takes place while calculating the gradients of L(θ)\mathcal{L}(\theta) and applying gradient descent steps, because all these operations are done on sparse tensors.

In detail, we describe only initialization from the training data. The idea is to associate each variable xix_i in problem (1) with a charge xiA⃗ix_i\vec{A}_i, where A⃗i\vec{A}_i is the ii-th column of the constraints matrix AA. Then, the probability amplitude π(x)\pi(x) is given as a symmetric TT with the flux bb, and each TT-core G(k)G^{(k)} is a U(1)U(1)-symmetric tensor of rank 3. Then, for each TT-core, we choose the direction of the indices. Left (virtual) link index αk−1∈Iin\alpha_{k-1}\in I_{\mathrm{in}}, (site) index xk∈Ioutx_k\in I_{\mathrm{out}}, right (virtual) link index αk∈Iout\alpha_k\in I_{\mathrm{out}}:

Tensor-train core diagram

Figure 1.

By convention, we put the flux on the 1-st TT-core, on the first virtual index of G(1)G^{(1)}. Thus, the example TT, which encodes the probability distribution for the problem with 4 binary variables, is:

One step of the EELS algorithm

Figure 1 (PDF p. 4). One step of the EELS algorithm for γ=1\gamma= 1.

The charge conservation law (4) is then equivalent to constraints in (1), because it says, that P(x)≠0P(x) \ne0 only if

b⃗−x1A⃗1−x2A⃗2−x3A⃗3−x4A⃗4=0⃗.\vec{b} - x_1\vec{A}_1 - x_2\vec{A}_2 - x_3\vec{A}_3 - x_4\vec{A}_4 = \vec{0}.

Building on an exact symmetric TT for the problem (1) may be exponentially hard, because it requires an exponentially large number of link charges (thus, exponentially large rank of tensor train). In Lopez-Piqueres et al. [17], heuristic strategies are suggested, which limit the minimum required rank to construct a symmetric tensor train, but also build only the approximation of the required tensor. The two constructions are described below. We chose Method (ii) (the most expressive) for this paper as the baseline:

Method (i): Given the feasible dataset T\mathcal{T}, for each x∈Tx \in\mathcal{T}, we calculate all the link charges cαkc_{\alpha_k} by propagating: c1=b⃗c_1 = \vec{b}, cαi=cαi−1−xiA⃗ic_{\alpha_i} = c_{\alpha_{i-1}} - x_i\vec{A}_i. It requires ∣b⃗∣∣T∣(N−1)|\vec{b}||\mathcal{T}|(N - 1) operations, where ∣T∣|\mathcal{T}| is the number of (unique) feasible samples, and ∣b⃗∣|\vec{b}| is the number of equalities in the problem. Then, we initialize each TT-core G(k)G^{(k)} with non-zero blocks for subspace with charges (cαk−1,xkA⃗k,cαk)(c_{\alpha_{k-1}},x_k\vec{A}_k,c_{\alpha_k}).

Method (ii): Given the feasible dataset T\mathcal{T}, for each x∈Tx \in\mathcal{T}, we calculate all the link charges cαkc_{\alpha_k} by propagating: c1=b⃗c_1 = \vec{b}, cαi=cαi−1−xiA⃗ic_{\alpha_i} = c_{\alpha_{i-1}} - x_i\vec{A}_i. It requires ∣b⃗∣∣T∣(N−1)|\vec{b}||\mathcal{T}|(N - 1) operations, where ∣T∣|\mathcal{T}| is the number of (unique) feasible samples, and ∣b⃗∣|\vec{b}| is the number of equalities in the problem. Then, for each G(k)G^{(k)}, we search for consistent (with the left link charges cαk−1c_{\alpha_{k-1}} and right link charges cαkc_{\alpha_k}) site charges cxk∈{0⃗,A⃗k}c_{x_k} \in\{\vec{0},\vec{A}_k\}. This step requires checking for all cαk−1c_{\alpha_{k-1}} and cxkc_{x_k}, if (cαk−1−cxk)∈⋃αk{cαk}(c_{\alpha_{k-1}} - c_{x_k}) \in\bigcup_{\alpha_k}\{c_{\alpha_k}\}. We store ⋃αk{cαk}\bigcup_{\alpha_k}\{c_{\alpha_k}\} as a hash-table based type, thus all the checks take O(N∣b⃗∣∣T∣)O(N|\vec{b}||\mathcal{T}|) operations on average, and O(N∣b⃗∣∣T∣2)O(N|\vec{b}||\mathcal{T}|^2) in the worst case (many hash collisions). TT-rank grows with the dataset size as O(∣T∣)O(|\mathcal{T}|).

The process of building a nonzero subspace of the tensor train may be interpreted as building a directed acyclic charge graph, with nodes corresponding to link charges, edges corresponding to values of xix_i, and paths in this graph from the initial node b⃗\vec{b} to the final node 0⃗\vec{0} corresponding to feasible solutions to Ax=bAx=b. For instance, look at the Figure 2 (a). In these terms, the algorithm of encoding constraints in U(1)U(1)-symmetric TT is expressive if it generates many feasible paths in the charge graph.

Charge graph, tensor-train link charges, problem constraints, and feasible samples

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\mathcal{X} matches the color of the corresponding path in the graph.

Training the symmetric Born machine

We use the Born parametrization Pθ(x)=πθ(x)2/ZθP_\theta(x)=\pi_\theta(x)^2/Z_\theta with real TT cores and Zθ=∑xπθ(x)2Z_\theta= \sum_x \pi_\theta(x)^2. Training follows the two-site, DMRG-like likelihood optimization of Lopez-Piqueres et al. [17], Sec. IV B. For a fixed selected dataset T={x(s)}s=1M\mathcal{T} = \{x^{(s)}\}_{s=1}^{M} (the selected Tnew\mathcal{T}_{\mathrm{new}} in Algorithm 1, with retention determined by the experiment), define

ws=exp⁡[−(C(x(s))−Cmin⁡)/τ]∑r=1Mexp⁡[−(C(x(r))−Cmin⁡)/τ],τ>0,(5)w_s = \frac{\exp[-(C(x^{(s)}) - C_{\min})/\tau]}{\sum_{r=1}^{M}\exp[-(C(x^{(r)}) - C_{\min})/\tau]}, \qquad\tau> 0, \tag*{(5)}

where Cmin⁡=min⁡x∈TC(x)C_{\min} = \min_{x\in\mathcal{T}} C(x) is a numerical shift that cancels in the ratio. The training objective is

L=log⁡Zθ−2∑s=1Mwslog⁡∣πθ(x(s))∣.(6)\mathcal{L} = \log Z_\theta- 2\sum_{s=1}^{M} w_s \log\left|\pi_\theta(x^{(s)})\right|. \tag*{(6)}

The data and weights are held fixed throughout the inner training sweeps. This objective fits the reweighted empirical distribution; it does not require evaluating CC outside the selected data during a sweep.

Merge and differentiate. Put the TT in mixed canonical form with the orthogonality center at site kk (or k+1k+1 for a leftward update). Contract the shared bond of the two adjacent cores:

Baijb(k)=∑cGaic(k)Gcjb(k+1).(7)B^{(k)}_{aijb} = \sum_c G^{(k)}_{aic}G^{(k+1)}_{cjb}. \tag*{(7)}

Here i,ji,j are physical values and a,b,ca,b,c are virtual indices, including their charge and degeneracy labels. All cores outside this pair are isometries. Writing ∥⋅∥F\|\cdot\|_F for the Frobenius norm, we have Zθ=∥B(k)∥F2Z_\theta= \|B^{(k)}\|_F^2. Let La(s)L_a^{(s)} and Rb(s)R_b^{(s)} be the contractions of the fixed sample with the cores strictly to the left and right of the pair, respectively. Removing the pair leaves the sample environment

Eaijb(s)=La(s)Rb(s)δi,xk(s)δj,xk+1(s)∂πθ(x(s))∂Baijb(k).(8)E^{(s)}_{aijb} = L_a^{(s)} R_b^{(s)} \delta_{i,x_k^{(s)}} \delta_{j,x_{k+1}^{(s)}} \frac{\partial\pi_\theta(x^{(s)})}{\partial B^{(k)}_{aijb}}. \tag*{(8)}

For real parameters the gradient and local update are

∇BL=2BZθ−2∑s=1MwsE(x(s))πθ(x(s)),B~=B−η∇BL,(9)\begin{aligned} \nabla_B \mathcal{L} &= \frac{2B}{Z_\theta} - 2\sum_{s=1}^{M} w_s \frac{E(x^{(s)})}{\pi_\theta(x^{(s)})},\\ \widetilde{B} &= B - \eta\nabla_B \mathcal{L}, \tag*{(9)} \end{aligned}

where η\eta is the learning rate and the amplitudes and environments are evaluated before the update. In particular, the norm term must be retained even if the state was normalized before training.

Split and sweep. Reshape B~\widetilde{B} with row index (a,i)(a,i) and column index (j,b)(j,b). Charge conservation separates this matrix into blocks labeled by the intermediate residual charge q=ca−iA⃗k=cb+jA⃗k+1q = c_a - i\vec{A}_k = c_b + j\vec{A}_{k+1}. For each retained charge compute B~q=UqΣqVqT\widetilde{B}_q = U_q\Sigma_qV_q^T, truncate within the block, and reshape back to cores. On a rightward pass use (Uq,ΣqVqT)(U_q,\Sigma_qV_q^T); on a leftward pass use (UqΣq,VqT)(U_q\Sigma_q,V_q^T). Thus the orthogonality center moves one site and forbidden charge sectors remain zero (Figure 3). One full sweep visits k=1,…,N−1k=1,\ldots,N-1 and then k=N−1,…,1k=N-1,\ldots,1. Repeat for the prescribed number of sweeps, normalize the center core, and sample sequentially

Two-site training update

Figure 3. One two-site training update, following Lopez-Piqueres et al. [17]. 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\Sigma_q into the left core.

from the trained model.

Specialization used here. During a training sweep, our current kernels keep the existing charge sets fixed and retain only the largest singular value in each block, i.e., virtual charge degeneracy one. This does not mean total TT rank one: the bond dimension is the number of retained charges. Consequently, training changes weights on the existing charge graph.

Expressibility Enhancement Local Search (EELS)

We noticed that all methods for building symmetric TT from data, as suggested in [17], may fail for the same reason. Methods take link charges only from the data but do not apply any strategy to search for unknown charges. If the training data is too small or not diverse enough, then the required link charges, which encode near-optimal solutions, simply do not appear in TT. Moreover, this disadvantage may not be compensated during the training step, because the charge structure pre-defines all samples, which may be sampled from symmetric TT in principle, and the learning procedure updates only the probabilities of principally possible samples.

For example, look at the combinatorial problem and dataset T\mathcal{T} on Figure 2 (c). Method (ii) fails to find any new samples that do not appear in T\mathcal{T}. On Figure 2 (a), black circles are the link charges obtained from T\mathcal{T}, and cyan arrows are all paths in the graph, which encode the dataset samples. Obviously, no new path exists through the black charges, which satisfy the charge conservation law cαk+1=cαk−xk+1c_{\alpha_{k+1}} = c_{\alpha_k} - x_{k+1} on each edge; thus, no new samples were obtained in TT.

We propose a new parameterized family of methods for initializing symmetric TT, called Expressibility Enhancement Local Search (EELS). First, we initialize symmetric TT with Method (ii). Then, we apply the expressibility enhancement phase. The Figure 1 illustrates the main idea of this phase: we fix the kk-th link of TT, and then search for such charges cnewc_{\mathrm{new}}, which i) do not appear at the k+1k+1-th link; ii) may connect the charges at the kk-th link with the charges at the (k+2)(k+2)-th link, satisfying charge conservation law for some xk+1,xk+2x_{k+1}, x_{k+2}. Thus, we "jump" over the k+1k+1-th link, and conduct a local search in a charge graph, finding such cαkc_{\alpha_k}, xk+1x_{k+1}, xk+2x_{k+2}, which satisfy the U(1)U(1)-symmetry. Sometimes this procedure spawns new charges, which may be assigned to the k+1k+1-th link. The length of the "jump" may be regulated with the parameter γ\gamma, which is equal to the number of links we jump over. At the Figure 1, γ=1\gamma= 1, and the Algorithm 2 also provides the detailed description for γ=1\gamma= 1. Method (ii) may be associated with γ=0\gamma= 0. For γ>1\gamma> 1, we search for new charges at the links k+1k+1, k+2k+2, ..., k+γk+\gamma simultaneously, by considering all possible combinations of cαkc_{\alpha_k}, xk+1x_{k+1}, ..., xk+γ+1x_{k+\gamma+1}, thus, the complexity of the

algorithm is O(2γ+1∣T∣∣b∣(N−γ))O\left(2^{\gamma+1}|\mathcal{T}||b|(N-\gamma)\right) on average. Figure 2 shows that even for γ=1\gamma=1, our expressibility enhancement procedure may find some new charges, and thus, new paths in the charge graph, corresponding to feasible samples.

We emphasize that EELS is not a regular local search, which may be applied to the data samples to obtain new solution candidates. It acts more like a crossover operator, entangling all the samples from T\mathcal{T}. On Figure 2(a), EELS obtains the solution, which takes the first bit of the solution 1100, and the last bit from the solution 0011, and the bits 00 in the middle are found using the charge conservation law. Similarly, EELS also finds a feasible solution, taking the first bit from 0011 and the last bit from 1100, filling the middle with a guess of 11. For large datasets, EELS may generate new feasible candidates by mixing all samples from T\mathcal{T}, producing unpredictable bit concatenations with some "guessed" fillers.

Amplification of Data Diversity (ADD)

EELS from Section 3.3 is useful when we lack training data or want to better exploit existing data. In this section, we consider the special case of constraints Ax=bAx=b when a

Algorithm 2 EELS algorithm, γ=1\gamma=1

Require: C1,…,CN−1C_1,\ldots,C_{N-1} - Sets of link charges, defined from data; A,bA,b - constraints for the problem; G(1),…,G(N)G^{(1)},\ldots,G^{(N)} - TT-cores;

  1. cα0←b⃗c_{\alpha_0}\leftarrow\vec{b}, cαN←0⃗c_{\alpha_N}\leftarrow\vec{0}

  2. for k=1k=1 to N−2N-2 do

  3.     for cαk∈Ckc_{\alpha_k}\in C_k do

  4.         for xk+1∈{0,1}x_{k+1}\in\{0,1\} do

  5.             cnew←cαk−xk+1A⃗k+1c_{\mathrm{new}}\leftarrow c_{\alpha_k}-x_{k+1}\vec{A}_{k+1}

  6.             for xk+2∈{0,1}x_{k+2}\in\{0,1\} do

  7.                 if cnew−xk+2A⃗k+2∈Ck+2c_{\mathrm{new}}-x_{k+2}\vec{A}_{k+2}\in C_{k+2} then

  8.                     cαk+2=cnew−xk+2A⃗k+2c_{\alpha_{k+2}}=c_{\mathrm{new}}-x_{k+2}\vec{A}_{k+2}

  9.                     Ck+1.add⁡(cnew)C_{k+1}.\operatorname{add}(c_{\mathrm{new}})

  10.                     Insert new nonzero blocks:

  11.                     G(k+1)←(cαk,xk+1A⃗k+1,cnew)G^{(k+1)}\leftarrow(c_{\alpha_k},x_{k+1}\vec{A}_{k+1},c_{\mathrm{new}})

  12.                     G(k+2)←(cnew,xk+2A⃗k+2,cαk+2)G^{(k+2)}\leftarrow(c_{\mathrm{new}},x_{k+2}\vec{A}_{k+2},c_{\alpha_{k+2}})

  13.                 end if

  14.             end for

  15.         end for

  16.     end for

  17. end for

feasible dataset sampler is available, or it is easy to construct a large dataset T\mathcal{T} using extra knowledge. Such situations include, for instance, cardinality constraints ∑i=1Nxi=κ\sum_{i=1}^{N} x_i = \kappa. In this case, because tensor train optimization trains on the fly, we probably should not use the entire available data but rather pick a good, diverse subset. Otherwise, the complexity of the training step may be (too) large.

We formulate a problem as follows. Let T\mathcal{T} be a data, available at the tt-th iteration of the Algorithm 1. This data includes samples from TT and other feasible solutions generated by the feasible data sampler. How to choose a subset T′⊂T\mathcal{T}^{\prime} \subset\mathcal{T}, such that ∣T′∣=μ<∣T∣\lvert\mathcal{T}^{\prime}\rvert= \mu< \lvert\mathcal{T}\rvert, to achieve exploration-exploitation trade-off, and keep the complexity of the training step manageable? We need to define the measure of the sample’s novelty relative to what the generative scheme has already explored. To do this, we give a formal definition of the charge graph for the problem (1), which we discuss informally in § 2.4. Let ∣b∣=m\lvert b\rvert= m be the number of equalities in problem (1) and NN the number of binary variables. Let consider a DAG D=(V,E,ω,ξ)D = (V,E,\omega,\xi), with ω:V→Rm\omega: V \to\mathbb{R}^{m} and ξ:E→{{0},{1},{0,1}}\xi: E \to\{\{0\},\{1\},\{0,1\}\}. Here ω(v)\omega(v) is a charge of the vertex vv, and the set of all vertices consists of several layers: V=L0⊔L1⊔⋯⊔LNV = L_0 \sqcup L_1 \sqcup\cdots\sqcup L_N. We call such a graph a charge graph of problem (1) if all of the following stand:

  1. ∣L0∣=∣LN∣=1\lvert L_0\rvert= \lvert L_N\rvert= 1, ω(v0∈L0)=b⃗\omega(v_0 \in L_0) = \vec{b}, ω(vN∈LN)=0⃗\omega(v_N \in L_N) = \vec{0}

  2. (u,v)∈E⇒u∈Li,v∈Li+1(u,v) \in E \Rightarrow u \in L_i, v \in L_{i+1} for some ii

  3. If uk∈Lku_k \in L_k, and vk+1∈Lk+1v_{k+1} \in L_{k+1}, then ω(uk)−ω(vk+1)=0⃗\omega(u_k) - \omega(v_{k+1}) = \vec{0} or ω(uk)−ω(vk+1)=Ak+1\omega(u_k) - \omega(v_{k+1}) = A_{k+1}, where Ak+1A_{k+1} is a kk-th column of the matrix AA

  4. ξ(e(uk,vk+1))={0,1}\xi(e(u_k,v_{k+1})) = \{0,1\}, if Ak+1=0⃗A_{k+1} = \vec{0}, else ξ(e(uk,vk+1))={0}\xi(e(u_k,v_{k+1})) = \{0\} if ω(uk)=ω(vk+1)\omega(u_k) = \omega(v_{k+1}), or ξ(e(uk,vk+1))={1}\xi(e(u_k,v_{k+1})) = \{1\} if ω(uk)−ω(vk+1)=Ak+1\omega(u_k) - \omega(v_{k+1}) = A_{k+1}.

Charge graph on Figure 2(a) satisfies all conditions from the definition. On each path pp with edges (e1,…,eN)(e_1,\ldots,e_N) from v0∈L0v_0 \in L_0 to vN∈LNv_N \in L_N, we define the operation of feasible subset evaluation: F(p)=ξ(e1)×⋯×ξ(eN)F(p) = \xi(e_1) \times\cdots\times\xi(e_N), where "×\times" is the Cartesian product. We call a charge graph full if the set F(D)=⋃p∈P(D)F(p)F(D) = \bigcup_{p \in P(D)} F(p) coincides with all the solutions of Ax=bAx = b, where P(D)P(D) is a set of all the paths from v0v_0 to vNv_N. We define the width of the charge graph as ∣D∣=max⁡k=0N(∣Lk∣)\lvert D\rvert= \max_{k=0}^{N}(\lvert L_k\rvert).

The search for the full graph charge may be exponentially hard, and the same is true for storing such a graph. That is why Method (ii) from § 2.2 builds only a subgraph H⊂DH \subset D with a limited width ∣H∣≤∣T∣\lvert H\rvert\leq\lvert\mathcal{T}\rvert. The goal of the U(1)U(1)-generative approach is to find such H⊂DH \subset D, that x∗∈F(H)x^{*} \in F(H) for the optimal solution x∗x^{*} of problem (1). For the ADD selection-and-rebuild variant of Algorithm 1, the graph HH is rebuilt from the selected feasible data after external candidates are introduced. This makes the choice of samples control the charge topology as well as the training weights. The articles Alcazar et al., [2] and Lopez-Piqueres et al., [17] suggest only the selection of samples with the best cost function C(x)C(x), or picking up some rare samples from SS for diversity. We suggest using graph distance as a diversity measure. Let S=(VS,ES,ωS,ξS)\mathcal{S} = (V^{S}, E^{S}, \omega^{S}, \xi^{S}) be a charge graph for some feasible solution s=(x1,…,xN)s = (x_1,\ldots,x_N). Let VS=⨆k=1N{vk}V^{S} = \bigsqcup_{k=1}^{N} \{v_k\}. On each step of the generative optimization, we store a charge graph of already seen samples H\mathcal{H}, as the sets of charges for each vertex layer: CkH=⋃v∈LkH{ωH(v)}C_k^{\mathcal{H}} = \bigcup_{v \in L_k^{\mathcal{H}}} \{\omega^{\mathcal{H}}(v)\}. Then the graph distance between S\mathcal{S} and H\mathcal{H} is:

ρ(S,H)=∑k=1N−1(1−χ(ωS(vk)∈CkH)),(10)\rho(\mathcal{S},\mathcal{H}) = \sum_{k=1}^{N-1} \left(1 - \chi(\omega^{S}(v_k) \in C_k^{\mathcal{H}})\right), \tag*{(10)}

where χ(⋅)\chi(\cdot) is an indicator function of the condition in brackets. Thus, we count the number of new charges that appear in the solution ss and were not previously seen by the algorithm. In § 3 we discuss how to balance this novelty measure with exploitation of the near-optimal samples.

Results

We used DeepSeek-V4.1-Flash to help write the scripts that plot benchmark results from the saved experiment outputs.

Comparison of EELS with other methods

We may compare the expressibility of the methods of building U(1)U(1)-symmetric tensor trains by fixing the dataset T\mathcal{T}, defining all link charges degeneracy ranks in (3) dim⁡(Vck)=1\dim(V^{c_k}) = 1 and then, calculating the number of nonzero elements. If we initialize G(k)(αk−1,xk,αk)=1G^{(k)}(\alpha_{k-1},x_k,\alpha_k) = 1 for all positions, preserving U(1)U(1)-symmetry, then π(x)=1\pi(x) = 1 for all xx, conserving charge bb. Thus, the number of unique samples in tensor train is just a Frobenius norm squared, which may be calculated efficiently in TT-format.

Figure 5 shows the group of experiments for the problem (1) with the random matrices AA of size m×nm \times n and random vector bb, both sampled from the uniform distribution on [−r,r][-r,r]. Figure 5a shows the dependency of the number of unique samples in U(1)U(1)-symmetric TT as the function of training dataset size. With EELS, the number of unique samples grows as ∼∣T∣5\sim\lvert\mathcal{T}\rvert^{5} for r=1r = 1, while applying only the baseline method (Method (ii) from § 2.2) encodes only ∼∣T∣4\sim\lvert\mathcal{T}\rvert^{4} possible feasible solutions. EELS improves the baseline with a small increase in computational time to build an initial U(1)U(1)-symmetric TT, as shown in Figure 5b. Other experiments on Figure 5 demonstrate that the benefit Figure 6. EELS (γ=1\gamma= 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 5. Comparison of U(1)U(1)-symmetric TT building strategies on random problems with NN binary variables, mm linear equalities and constraints matrix sampled from uniform distribution in range [−r,r][-r,r]. (a) Number of samples dependency on training dataset size. (b) Wall time to build initial U(1)U(1)-symmetric TT. (c),(d) Sample-count ratio versus matrix sparsity.

Figure 6. (a) Linear objective.

ObjectiveW/T/LMean (%)Median (%)Raw ppHolm pp
Linear125/116/93.10.02×10−192 \times10^{-19}3.9×10−193.9 \times10^{-19}
Quadratic128/100/223.10.21.4×10−151.4 \times10^{-15}1.4×10−151.4 \times10^{-15}

Table 1 (PDF p. 9). 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 RR (%). Holm correction covers the two one-sided tests; percentages are rounded to one decimal place.

Figure 6b. (b) Quadratic objective.

of using EELS depends a lot on the sparsity of the matrix AA, the number of constraints, and the value of parameter rr. Generally, if rr is big, or the number of constraints is huge, then it is hard to satisfy the if-condition in line 7 of Algorithm 2, and EELS spawns only a small fraction of new link charges cnewc_{\mathrm{new}}, if it spawns any at all. In contrast, if the matrix AA is sparse, EELS may be an efficient strategy for several dozen constraints. For example, we consider an assignment problem [14]. This is NP-hard problem for a quadratic/black-box oracle C(x)C(x). The constraints matrix of size 2n×n22n \times n^2 is given by the rule:

{Aj,(i−1)n+j=1,∀i,j=1,…,nAn+i,(i−1)n+j=1,∀i,j=1,…,nelseAk,m=0,(11)\begin{cases} A_{j,(i-1)n+j}=1, & \forall i,j=1,\ldots,n \\ A_{n+i,(i-1)n+j}=1, & \forall i,j=1,\ldots,n \\ \text{else} \quad A_{k,m}=0, \tag*{(11)} \end{cases}

and bi=1b_i=1 ∀i=1,…,2n\forall i=1,\ldots,2n. The density of matrix AA scales as O(1n)O\left(\frac{1}{n}\right). Figure 4 shows the group of experiments with the assignment problem. The total number of feasible samples grows monotonically with the problem size as n!n!; however, for large problems, building symmetric TT methods struggle to find new feasible samples when the training data is insufficiently expressive. That is why the number of samples in TT saturates and then decreases. The peak of saturation shifts to the right as the initial dataset size grows. EELS provides approximately 3 − 6 times more samples at the peak point than Method (ii) from § 2.2.

Number of unique samples in TT for different U(1)-symmetric TT building strategies on the assignment problem

Figure 4. Number of unique samples in TT for different U(1)U(1)-symmetric TT building strategies on the assignment problem.

EELS impact on optimization results

To test whether enhanced expressibility translates into lower objective values, we compare EELS with γ=1\gamma= 1 against Method (ii), using Best Cost selection in both arms. For each of the linear and quadratic objective families, we use 50 assignment instances at each n∈{12,13,14,15,16}n \in\{12,13,14,15,16\}: 250 paired comparisons with N=n2∈{144,169,196,225,256}N = n^2 \in\{144,169,196,225,256\} binary variables.

For each pair, 400 feasible assignments are drawn uniformly from random permutations. Both arms receive the same deduplicated, cost-sorted initial matrix. Both initialize their TT once, with EELS applied only at initialization in the enhanced arm. Each of 20 outer iterations first draws 10,000 samples, then trains the existing TT on the best at most 400 distinct assignments from each new batch alone. Training uses one complete right–left sweep, learning rate 0.05, and virtual charge degeneracy one. Boltzmann weights use the standard deviation of the current elite costs as temperature, with uniform weights when this deviation is zero. Learned amplitudes and structural charge sets persist across iterations. Initial and historical points are not merged into subsequent training batches; the best evaluated solution is retained separately. No external data, restarts, or subsequent TT reinitializations are used.

For best recorded costs CiiC_{\mathrm{ii}} and CEELSC_{\mathrm{EELS}}, define

R=100Cii−CEELS∣Cii∣.(12)R = 100\frac{C_{\mathrm{ii}}-C_{\mathrm{EELS}}}{\lvert C_{\mathrm{ii}}\rvert}. \tag*{(12)}

All baseline costs are nonzero; positive RR favors EELS. Figure 6 shows the distributions by size, including group medians and arithmetic means. A one-sided paired Wilcoxon signed-rank test is applied to unscaled final costs, pooled over the five sizes within each objective. Table 1 reports raw pp-values and Holm adjustment across the two objective-level comparisons.

The mean improvement is 3.1% for linear and 3.1% for quadratic objectives, with 125 and 128 wins out of 250 pairs, respectively. Both advantages remain significant after the Holm correction. However, there are 116 and 100 exact ties, and the pooled medians are only 0.0% and 0.2% after rounding. Thus the improvement is heterogeneous, not a uniform gain on every instance. These results support the one-time expressibility enhancement under equal sampling and iteration settings. Improvements also persist at a fixed 200 s budget (Figure 8 and § 4).

Figure 8. EELS (γ=1\gamma= 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 § 4 and Table 2.

ADD impact on optimization results

We use graph distance (Equation (10)) to balance cost-based selection with exploration of the charge graph. Assignment admits a simple uniform feasible sampler based on random permutations, so this experiment examines which available data to learn from, rather than how to obtain feasible data. In the ADD variant of Algorithm 1, we reconstruct the TT from the selected data at every outer iteration. We compare the following selection rules on a candidate pool SS, with selection quota μ\mu and charge history H\mathcal{H}:

  1. Best Cost: select the μ\mu candidates with lowest cost.

  1. Best Cost + Graph Distance Filter (GDF): first select (1−wfilter)μ(1-w_{\mathrm{filter}})\mu candidates by cost, then select up to wfilterμw_{\mathrm{filter}}\mu lowest-cost remaining candidates satisfying ρ(S,H)>0\rho(S,\mathcal{H})>0. If no such candidates remain, use Best Cost as a fallback.

  1. Mixed Selection: select wmixμw_{\mathrm{mix}}\mu candidates with largest graph distance and fill the remaining quota by cost from the other candidates.

  1. Weighted Rank: select the μ\mu candidates with smallest rC+wrankrρr_C+w_{\mathrm{rank}}r_\rho, where rank one denotes lowest cost or largest graph distance, respectively.

The history stores charge sets at each TT link. Computing one graph distance requires O(∣b∣(N−1))O(|b|(N-1)) operations on average with hashed charge sets; history storage is an additional cost of the diversity-aware rules.

For each of the linear and quadratic objectives we use 50 instances at each n∈{12,13,14,15,16}n\in\{12,13,14,15,16\}, with N=n2N=n^2 binary variables. Every configuration receives the same 1K initial feasible assignments for each instance, verified by stored hashes. Each run performs 20 outer iterations, one training sweep per iteration, learning rate 0.05 and bond degeneracy one. After training a newly initialized TT, we draw 10K TT samples, deduplicate them together with 50 retained elite assignments, and supplement the pool with fresh uniform feasible samples to reach 20K candidates. Each rule selects up to μ=103\mu=10^3 candidates; retaining the 50 elites can increase the next training set to at most 1.05K distinct assignments. No worst-sample retention, EELS enhancement or barrier filter is used. All methods, including Best Cost, receive external candidates.

We evaluate wmix,wfilter∈{0.1,0.2,0.3,0.4}w_{\mathrm{mix}},w_{\mathrm{filter}}\in\{0.1,0.2,0.3,0.4\} for Mixed Selection and GDF, and wrank∈{0.1,0.35,0.5,0.7}w_{\mathrm{rank}}\in\{0.1,0.35,0.5,0.7\} for Weighted Rank. For each strategy and objective, we select the weight with the largest mean per-instance relative improvement R=100(∣CBestCost−CADD∣/∣CBestCost∣)R=100(|C_{\mathrm{BestCost}}-C_{\mathrm{ADD}}|/|C_{\mathrm{BestCost}}|). Figure 7 shows all six selected configurations; the complete grid and paired statistics are in Supplementary Section S1.

Figure 7. ADD versus Best Cost on the parameter-screening instances. Columns show linear (left) and quadratic (right) objectives; rows show GDF (wfilter=0.4w_{\mathrm{filter}} = 0.4), Mixed Selection (wmix=0.4w_{\mathrm{mix}} = 0.4), and Weighted Rank (wrank=0.35w_{\mathrm{rank}} = 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.

All three strategies improve on Best Cost at their selected weights. The mean gains for Mixed Selection, Weighted Rank and GDF are, respectively, 2.8%, 5.6% and 6.9% for linear objectives, and 2.7%, 5.9% and 6.6% for quadratic objectives. GDF with wfilter=0.4w_{\mathrm{filter}}=0.4 gives the largest mean improvement in both families. It wins, ties and loses on 235/14/1 linear instances and 209/26/15 quadratic instances; its pooled median improvements are 5.9% and 6.2%. One-sided paired Wilcoxon tests on raw final costs give p=9.5×10−41p=9.5\times10^{-41} and p=2×10−34p=2\times10^{-34}, respectively; Holm adjustment over all 24 baseline comparisons gives 2.2×10−392.2\times10^{-39} and 3.5×10−333.5\times10^{-33}. The mean linear improvement of GDF increases from 2.5% at n=12n=12 to 11.2% at n=16n=16; its quadratic mean improves from 3.8% to 7.9%. This pattern is consistent with a benefit from charge-space exploration as problem size grows.

A separate held-out comparison also supports the selected GDF rule at a fixed 200 s budget (Figure 9 and § 4). These are within-benchmark comparisons with weights selected on the same instances. They support GDF with wfilter=0.4w_{\mathrm{filter}}=0.4 as a practical choice for this setting.

Figure 9. ADD–GDF (wfilter=0.4w_{\mathrm{filter}} = 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 § 4 and Table 2.

ADD transfer to nonpolynomial Set Partitioning

To study a feasible space distinct from assignment, consider a collection of tiles Sj⊆{1,…,m}S_j\subseteq\{1,\ldots,m\}, one per binary variable xjx_j. Set Partitioning selects disjoint tiles covering every element exactly once: Auj=1{u∈Sj}A_{uj}=1\{u\in S_j\} and Ax=1Ax=1. Singleton tiles guarantee feasibility. We use N=n2N=n^2 variables; here nn is a size label, not the number of equalities or binary variables. An exact counting sampler generates uniform feasible covers, without solving the objective or constructing the TT; its recurrence is given in Supplementary Section S2.

For transfer of the assignment-selected ADD rule, the fixed

locality grid has m∈{18,19,20}m \in\{18, 19, 20\}, n∈{13,14,15}n \in\{13, 14, 15\} and W∈{5,6,8,10,12,15,18}\mathcal{W} \in\{5, 6, 8, 10, 12, 15, 18\}. Tiles have one to four elements and span at most W\mathcal{W} consecutive element positions. Each (W,m,n)(\mathcal{W}, m, n) cell contains 15 instances: 945 in total, or 135 for each W\mathcal{W}. A fixed spatial variable order processes tiles by their smallest element, with the corresponding singleton last. It allows completed element constraints to leave the active frontier. Small W\mathcal{W} therefore limits the number of simultaneous charge states; increasing W\mathcal{W} broadens the exact-indicator rank profiles. Mean maximum ranks range from 24.0 at W=5\mathcal{W} = 5 to 19,962.3 at W=18\mathcal{W} = 18 over the balanced parameter grid (Supplementary Table S3). These are full-indicator ranks, not the ranks of a TT learned from 500 points. Locality also changes the feasible covers, so rank is a descriptive covariate rather than an isolated causal treatment.

The nonpolynomial objective is a linear cost plus entropic scenario risk:

Cent(x)=cTxs+τlog⁡[132∑a=132exp⁡(WaTxτs)],s=m.(13)C_{\mathrm{ent}}(x) = \frac{c^{\mathsf{T}}x}{s} + \tau\log\left[\frac{1}{32}\sum_{a=1}^{32}\exp\left(\frac{W_a^{\mathsf{T}}x}{\tau s}\right)\right], \qquad s = \sqrt{m}. \tag*{(13)}

with τ=0.5\tau= 0.5, independent cj∼U[−1,1]c_j \sim U[-1,1] and Waj∼N(0,1)W_{aj} \sim N(0,1). The second term smoothly emphasizes adverse scenario costs; the factor 1/321/32 makes it an empirical exponential-utility risk rather than a sum depending on scenario count. Log-sum-exp is evaluated stably. The transfer protocol fixes GDF at wfilter=0.4w_{\mathrm{filter}} = 0.4, selected on assignment, and compares it with Best Cost using matched initial and external feasible draws, without retuning on this grid (Supplementary § 8). Each pair uses 500 initial feasible draws, 15 iterations, and 5K TT plus 5K fresh external draws per iteration. Both methods rebuild the TT after selection and train with one full sweep, learning rate 0.05 and charge degeneracy one, using the table sampler. The budgets match iterations and requested samples.

Transfer and rank dependence. Across all 945 pairs, ADD wins on 305 tasks, ties on 628 and loses on 12. Mean relative improvement is 1.6% (stratified bootstrap 95% interval 1.4–1.8%); the median is 0.0%. Thus the assignment-selected rule transfers to a nonpolynomial objective and different constraint matrices, but its benefit is concentrated in a subset of tasks. In Figure 10, the mean gain rises from less than 0.1% at W=5\mathcal{W} = 5 to 3.1% at W=15\mathcal{W} = 15, then levels off at 2.9% for W=18\mathcal{W} = 18. The paired one-sided Wilcoxon tests support an advantage for every group from W=6W = 6 onward after Holm correction across seven groups, but not for W=5W = 5 (Supplementary Table S4).

Figure 10. Transfer of assignment-selected GDF (wfilter=0.4w_{\mathrm{filter}} = 0.4) to entropic Set Partitioning. Each locality group contains 135 paired tasks, balanced across nine (m,n)(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 ±\pm 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,…,16n = 12, \ldots, 16; horizontal positions do not identify matched tasks across families. Bottom: relative final-cost improvement 100(CBestCost−CADD)/∣CBestCost∣100(C_{\mathrm{BestCost}} - C_{\mathrm{ADD}})/|C_{\mathrm{BestCost}}|. 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.

This pattern is consistent with the limitation of cost-only selection: it can repeatedly favor already represented charge paths and neglect structurally novel candidates. A larger charge graph is harder to cover with a fixed training quota, plausibly aggravating this limitation. Best Cost consequently falls further behind ADD on average in the higher-rank families, where the diversity filter can help compensate for incomplete exploration. The positive rank–gain association persists within each fixed (m,n)(m, n) group. We therefore infer greater usefulness of ADD in the higher-rank families studied. The improvement also persists at a fixed 10 s budget (Figure 11 and § 4).

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.

Improvement under fixed time budgets

The preceding comparisons fix the sampling and iteration settings. We add equal-time comparisons to account for the cost of diversity filtering and TT training. Each arm runs on one pinned CPU with one Julia and BLAS thread.

Paired arms share their initial feasible sample and execute sequentially, with their order alternated across instances. Checkpoints at 10, 50 and 200 s belong to the same continuous run; only improvements completed before the corresponding deadline are retained. Loading, warm-up and common input preparation are excluded, whereas initial objective evaluation, TT construction and optimization are timed. There is no fixed iteration cap.

For ADD assignment, the initial and retained training quotas are 1K, with 10K TT draws and a candidate pool of 20K completed from the external feasible sampler; 50 elites are retained. A new TT is built each iteration. The selected rule is GDF with wfilter=0.4w_{\mathrm{filter}} = 0.4; the comparison uses 250 held-out instances per objective, balanced over n=12,…,16n = 12, \ldots, 16. For EELS, the initial quota is 400, each iteration draws 10K samples and trains on at most 400 best unique current samples. The TT is initialized once, with or without one-time EELS (γ=1\gamma= 1), and its learned amplitudes persist; there are no external samples or restarts. Each objective again has 250 pairs. Initial random samples differ from those of the earlier fixed-iteration experiment, so the two experiments do not isolate time budget as their only difference.

The Set Partitioning comparison reuses the 945-instance locality grid and its fixed initial samples: quota 500, 5K TT draws plus 5K external feasible samples, a 5% elite fraction and TT reconstruction each iteration. All three comparisons use one training sweep per iteration with learning rate 0.05. ADD uses the table sampling backend; EELS uses legacy. Objective caching is enabled for both arms of EELS and Set Partitioning, and disabled for both assignment ADD arms. Analysis-only graph diagnostics are excluded from the timed Set Partitioning runs; selection is unchanged.

Quality and budget. At 200 s, ADD improves mean assignment costs by 3.1% and 3.8% for linear and quadratic objectives; EELS improves them by 2.7% and 3.6% (Figure 8 and Figure 9 and Table 2). At 10 s, ADD improves mean entropic Set Partitioning costs by 1.0%. Zero medians coexist with positive mean gains because many pairs tie.

ComparisonObjectiveSecondsW/T/LMean (%)Median (%)Raw ppHolm pp
ADD: assignmentLinear200179/58/133.12.48.9×10−318.9 \times10^{-31}1.2×10−291.2 \times10^{-29}
ADD: assignmentQuadratic200158/41/513.82.71.6×10−181.6 \times10^{-18}1.7×10−171.7 \times10^{-17}
EELS: assignmentLinear200120/122/82.70.07.5×10−187.5 \times10^{-18}7.5×10−177.5 \times10^{-17}
EELS: assignmentQuadratic200113/112/253.60.09.6×10−169.6 \times10^{-16}7.7×10−157.7 \times10^{-15}
ADD: Set PartitioningEntropic10244/656/451.00.06.0×10−276.0 \times10^{-27}7.7×10−267.7 \times10^{-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 reveals contrasting ADD dynamics. On assignment, the filtering overhead is not repaid at 10 s, but an advantage emerges at 50–200 s. On entropic Set Partitioning, the advantage diminishes as Best Cost catches up. EELS reaches the same recorded incumbents at 50 and 200 s in this experiment.

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)(m,n,W). Checkpoints share runs and are not independent repetitions.

Rank–budget trade-off. At 10 and 50 s the larger-rank Set Partitioning groups exhibit larger mean gains (Figure 13). Even at 200 s a weak upward tendency remains, reaching about 0.2% at the largest locality, but it is not strictly monotone: the pooled gain is only 0.1%. A plausible interpretation is that cost-only selection covers the relevant paths more readily in compact feasible spaces when external samples and sufficient time are available. Diversity filtering can then offer little extra benefit. Harder-to-cover spaces may benefit more from ADD once the budget absorbs filtering and training overhead. The rank comparison in Figure 10 gives context: assignment maximum ranks are approximately 1.7K–24K for n=12n = 12–16, while the Set Partitioning group means span roughly 24–20K. The results suggest a rank–budget–selection trade-off.

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.

Comparison with simulated annealing

For the completed SA experiment we use a separate low-rank Set Partitioning family: connected tiles on a 3×n3 \times n strip, with n=10,12,14n = 10, 12, 14 and m=3nm = 3n. These instances are not the locality grid. Their fixed spatial order and short tiles yield geometric mean maximum exact ranks 27.7, 36.1 and 45.4, respectively. Both quadratic xTQxx^{\mathsf{T}}Qx and the entropic objective are used. The two constructions and their fixed input datasets are distinguished in Supplementary Section S2 and Supplementary Section S3.

We compare two symmetric-TT variants with two simulated annealing (SA) baselines on assignment and the low-rank strip Set Partitioning family. Each family and size n∈{10,12,14}n \in\{10, 12, 14\} contains 40 paired instances with the same 400 initial feasible draws. Separate runs use 10, 50 and 200-second budgets on one CPU core per solver; both quadratic and entropic objectives are evaluated as black boxes. We show n=14n = 14, 200-second trajectories in Figure 14 and Figure 15; the corresponding n=10,12n = 10, 12 curves and complete protocol appear in Supplementary Section S3.

Figure 14. Mean feasible-objective gain versus optimization time at n=14n = 14 (N=196N = 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∣100(C_0-C_{\mathrm{best}})/|C_0| 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 § 9, not persistent-amplitude training.

Figure 15. The same n=14n = 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.

Information and model variants. Data-initialized EELS builds a symmetric TT from the current selected data and expands its graph chain by γ=1\gamma= 1. Full-indicator TT starts from the exact indicator of all feasible solutions. In this experiment EELS rebuilds its model, and full-indicator TT resets its amplitudes, at every outer iteration; this differs from the persistent-amplitude EELS–Best Cost comparison in Section 4.2. Informed SA receives explicit feasibility-preserving moves. Penalty SA receives no such moves: it flips a random bit and minimizes C(x)+α∥Ax−b∥22C(x) + \alpha\lVert Ax - b \rVert_{2}^{2} with a fixed scale-based choice of α\alpha. EELS and penalty SA both use the constraints AA, bb and the initial data, but exploit them differently: EELS enforces feasibility structurally, whereas penalty SA explores infeasible points.

Finite-time quality. EELS outperforms the tested penalty-SA configuration in every 200-second group in mean paired final quality (Supplementary Table S6). Penalty SA does improve its initial feasible best in 630 of 1,440 runs, including improvements in all twelve 200-second groups, but is substantially less effective within these budgets.

The EELS curves typically gain quickly and then plateau, whereas penalty SA continues to make slower gains on the displayed horizon. This is consistent with EELS acting as a rapid intensification step on data-defined support. A flat incumbent curve does not prove a local optimum, and an improving mean does not establish that individual SA chains never stagnate. A possible hybrid would supply feasible solutions from SA to a subsequent EELS stage. Such complementarity is motivated by the SA-seeded TN-GEO booster studied by Alcazar et al. [2], but the proposed SA–EELS hybrid is not tested here.

Rank and informed SA. On assignment, informed SA has better final cost on average in every group, with no individual TT wins (some ties). Its transpositions encode the permutation structure directly, while EELS receives no feasible-move oracle. Full-indicator TT approaches informed SA at n=10n = 10, but loses more at larger sizes. For row-major assignment, the full indicator has maximum TT ranks 461, 1,715 and 6,434 at n=10,12,14n = 10, 12, 14, respectively; construction and training overhead are consistent with reduced search throughput. On low-rank Set Partitioning, the TT endpoints are much closer to informed SA, particularly for the entropic objective, with many paired ties and some TT wins. The observed rank contrast explains a plausible computational mechanism.

Objective-query efficiency. The evaluation-axis curves tell a different story from wall time. On Set Partitioning the TT methods commonly reach comparable mean gains with far fewer objective calls; for example, in the n=14n = 14 entropic 200-second runs, informed SA averages 58.3 million calls versus 0.66 million for EELS and 0.54 million for full-indicator TT. Both TT variants also have higher mean gains than informed SA at the 100,000-call slice on every Set Partitioning group of the 200-second runs. Full-indicator TT has this advantage on assignment at n=10,12n = 10, 12, while EELS does not. These are descriptive slices of time-limited trajectories: SA cooling depends on elapsed time, and every curve is truncated to a query range reached by all 40 tasks. All calls, including repeats and infeasible penalty-SA queries, are counted.

Benchmarking library performance

The implementation of [17] is not open-source. However, the more recent article by the same authors has an accompanying GitHub repository, ConstrainTNet [15]. It implements an exact construction of a U(1)U(1)-symmetric tensor train: no data are needed for initialization, although the construction itself may become intractable for difficult constraint systems. ConstrainTNet also depends on ITensors [9], whereas OhMyU1 uses a specialized Julia back-end for non-degenerate charge sectors.

We compared one right–left training sweep and 400 samples on assignment instances with 4≤n≤104 \le n \le10, using identical full-indicator initial states and training data. Both OhMyU1 sampling backends were measured on one CPU; construction and compilation were excluded. The two libraries use two-site and one-site updates, respectively. The complete input, backend and timing protocol is provided in Supplementary § 10.

The results are shown in Figure 16, and detailed comparison is in Supplementary § 10. OhMyU1 is between 77× and 211× faster with legacy, and between 85× and 448× with table, on the measured grid. The speedup is not a universal comparison of the feature sets of the packages: ConstrainTNet supports inequalities and degenerate charge subspaces, while the present OhMyU1 kernels are specialized for non-degenerate equality-constrained problems. The result instead quantifies the advantage of the specialized back-end for this non-degenerate assignment workload. The two libraries use two-site and one-site updates, respectively, so equal sweep counts do not imply equal learning progress. The benchmark does not isolate the effect of individual implementation choices. All benchmark code and raw measurements are provided with OhMyU1 [10].

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\dim(V^{(c_k)}) = 1 for each link index.

Two PROTES access models. We additionally compare with PROTES [5], separating access to an exact feasible-set indicator from initialization using only feasible observations. These experiments concern binary n×nn \times n assignment, with N=n2N = n^2 variables in row-major order. They are distinct from the preceding trained-kernel comparison with ConstrainTNet. All runs use float64 and one logical CPU on the same local machine; Supplementary Section S5 specifies the construction, timing, training, software versions, and recorded sample and iteration counts.

Exact full indicator: storage and sampling. When all feasible charge states are known, both representations describe the complete set of n!n! assignments. Their minimal total bond dimensions coincide; the advantage of the symmetric representation is its block sparsity, not a smaller total exact TT rank. In Figure 17, dense storage grows substantially faster than storage of the permitted scalar blocks. Actual Julia object sizes include substantial metadata: at n=16n = 16, the full U(1)U(1) object occupies 1.59 GiB, compared with 18.0 MiB of numerical blocks. The corresponding dense variable-rank cores would require approximately 472 GiB; this last number is a storage calculation, not an allocation.

Figure 17. (a) Storage of the full assignment indicator. (b) Sampling from the full uniform feasible distribution.

Image not extracted

Figure 17 (PDF p. 18). 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)U(1) curve counts only allowed coefficients. Markers measure the complete Julia object, including charges and dictionaries, through n=16n = 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≤104 \le n \le10; complete U(1)U(1) models are constructed through n=16n = 16. The distributions and binary variable order are identical. Both OhMyU1 sampling backends are shown.

For sampling we construct the complete indicator in both libraries and use the same uniform distribution over assignments, with no training. All observed samples are feasible. At n=8n = 8 and n=10n = 10, OhMyU1 with the legacy sampler generates approximately 2.0⋅1042.0 \cdot10^{4} and 7.3⋅1037.3 \cdot10^{3} samples per second, respectively, versus 2.3⋅1032.3 \cdot10^{3} and 1.1⋅1021.1 \cdot10^{2} for the more memory-efficient protes_general. The resulting speedups are approximately 8.7×8.7\times and 67×67\times. Small instances do not exhibit universal superiority. The table sampler yields approximately 12K and 1.9K samples per second at these sizes; its per-call preparation is included. Both variants are shown. These measurements compare particular dense and block-sparse implementations, rather than establishing a lower bound on all possible PROTES implementations.

Initialization from feasible observations

We next provide the same 400 feasible observations and objective instance to PROTES and U(1)U(1)-EELS, without providing an indicator or permutation encoding to PROTES. OhMyU1 retains access to A,bA, b, an intentional difference in structural information. EELS uses γ=1\gamma= 1, sector degeneracy one, one training sweep at learning rate 0.05, and up to 10K generated points per outer iteration. All methods run until a common time budget, including initial fitting; the number of iterations is not fixed. Five prespecified PROTES configurations vary rank, learning rate, batch size, Adam steps, and initial-data passes (Supplementary Table S8).

Figure 18 and Supplementary Figure S5 count distinct feasible points absent from the initial dataset, rather than repeated draws. The 50-second, three-seed comparison in Supplementary Figure S5 shows that longer initial fitting improves PROTES. Thus, inability to generate any feasible point is not a robust conclusion; the observed limitation is rare feasible generation under this data-based initialization and update rule. New points need not improve the objective.

Figure 18. New distinct feasible assignments within a 5-second budget, for linear (left) and quadratic (right) objectives, versus assignment size nn. Each point is one matched diagnostic instance/seed; all methods receive the same 400 initial observations. PROTES settings are in Supplementary Table S8; U(1)U(1)-EELS uses the fixed settings above, with both sampling backends shown. Initialization, fitting, sampling, and scoring count toward the budget. At n=4n = 4 the initial data already cover all 24 solutions, so zero novelty is unavoidable. Both panels share the ordinate transformation log⁡10(1+z)\log_{10}(1 + z), with ticks labelled by the original count zz, allowing zeros to be shown. No uncertainty estimate can be obtained from this single-seed screen.

Acknowledgements

We thank Margarita Veshchezerova for providing the initial impetus for this research. We are grateful to Dmitry Gribanov, Elizaveta Iarovikova, Maxim Klimenko, and Ivan Samoylenko for insightful discussions. We appreciate the anonymous reviewers for their helpful feedback.

Declaration of generative AI and AI-assisted technologies

During the preparation of this work, the authors used DeepSeek-V4.1-Flash to assist with code review and debugging, test development, experiment automation, performance exploration, reproducible data visualization, preparation of selected manuscript passages, and language and formatting revisions. The mathematical formulation and core methodological ideas were developed by the human authors. The authors reviewed and edited the AI-assisted outputs and take responsibility for the content of this work.

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

Sergei Iudin; Mikhail Podobrii; Dmitry Zheltkov; Stanislav Moiseev

This document provides the complete strategy screening, benchmark construction, experimental protocols and additional comparisons accompanying the main article. Sections, figures, tables and equations prefixed with S belong to this supplement; references to the main article are identified explicitly.

Complete ADD strategy and weight comparison

Table S1 and Table S2 report every configuration under the protocol of Section 4.3 of the main article, using the same 250 paired objective instances per table. Best Cost was computed once per instance and objective (500 baseline runs); each of the 12 ADD configurations was run on the corresponding 250 instances (6,000 ADD runs). All 6,500 outcomes were checked for completeness, feasibility and consistency of the stored final objective.

StrategyWeightW/T/LWin (%)Mean (%)Median (%)WWppHolm (12)Holm (24)
GDFwfilter=0.4w_{\mathrm{filter}} = 0.4235/14/194.06.95.9279639.5×10−419.5 \times10^{-41}1×10−391 \times10^{-39}2.2×10−392.2 \times10^{-39}
GDFwfilter=0.3w_{\mathrm{filter}} = 0.3239/10/195.66.56.0289082.4×10−412.4 \times10^{-41}2.8×10−402.8 \times10^{-40}5.6×10−405.6 \times10^{-40}
GDFwfilter=0.2w_{\mathrm{filter}} = 0.2232/18/092.85.85.1270284.1×10−404.1 \times10^{-40}4.1×10−394.1 \times10^{-39}9.1×10−399.1 \times10^{-39}
Weighted Rankwrank=0.35w_{\mathrm{rank}} = 0.35222/21/788.85.65.0262076.8×10−396.8 \times10^{-39}5.5×10−385.5 \times10^{-38}1.4×10−371.4 \times10^{-37}
Weighted Rankwrank=0.5w_{\mathrm{rank}} = 0.5227/15/890.85.55.0275311.7×10−391.7 \times10^{-39}1.5×10−381.5 \times10^{-38}3.5×10−383.5 \times10^{-38}
Weighted Rankwrank=0.7w_{\mathrm{rank}} = 0.7225/18/790.04.94.2267461.5×10−381.5 \times10^{-38}1.1×10−371.1 \times10^{-37}2.9×10−372.9 \times10^{-37}
GDFwfilter=0.1w_{\mathrm{filter}} = 0.1214/33/385.64.33.7236301.6×10−371.6 \times10^{-37}9.8×10−379.8 \times10^{-37}2.9×10−362.9 \times10^{-36}
Mixedwmix=0.4w_{\mathrm{mix}} = 0.4189/38/2375.62.82.4207272.4×10−262.4 \times10^{-26}1.2×10−251.2 \times10^{-25}3.4×10−253.4 \times10^{-25}
Mixedwmix=0.3w_{\mathrm{mix}} = 0.3178/36/3671.22.11.7195224.7×10−194.7 \times10^{-19}1.4×10−181.4 \times10^{-18}4.7×10−184.7 \times10^{-18}
Weighted Rankwrank=0.1w_{\mathrm{rank}} = 0.1157/74/1962.82.01.2144573.4×10−233.4 \times10^{-23}1.4×10−221.4 \times10^{-22}4×10−224 \times10^{-22}
Mixedwmix=0.2w_{\mathrm{mix}} = 0.2139/62/4955.61.30.6136568.4×10−118.4 \times10^{-11}1.7×10−101.7 \times10^{-10}4.2×10−104.2 \times10^{-10}
Mixedwmix=0.1w_{\mathrm{mix}} = 0.194/109/4737.60.60.068131×10−41 \times10^{-4}1×10−41 \times10^{-4}3×10−43 \times10^{-4}

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.

StrategyWeightW/T/LWin (%)Mean (%)Median (%)WWppHolm (12)Holm (24)
GDFwfilter=0.4w_{\mathrm{filter}} = 0.4209/26/1583.66.66.2244252×10−342 \times10^{-34}2.5×10−332.5 \times10^{-33}3.5×10−333.5 \times10^{-33}
GDFwfilter=0.3w_{\mathrm{filter}} = 0.3197/33/2078.85.95.4224231.3×10−301.3 \times10^{-30}1.4×10−291.4 \times10^{-29}2×10−292 \times10^{-29}
Weighted Rankwrank=0.35w_{\mathrm{rank}} = 0.35189/28/3375.65.95.4229888.3×10−298.3 \times10^{-29}8.3×10−288.3 \times10^{-28}1.2×10−271.2 \times10^{-27}
Weighted Rankwrank=0.5w_{\mathrm{rank}} = 0.5184/23/4373.65.24.2225102.2×10−222.2 \times10^{-22}1.8×10−211.8 \times10^{-21}2.4×10−212.4 \times10^{-21}
GDFwfilter=0.2w_{\mathrm{filter}} = 0.2179/44/2771.64.63.5196554.3×10−264.3 \times10^{-26}3.9×10−253.9 \times10^{-25}5.7×10−255.7 \times10^{-25}
Weighted Rankwrank=0.7w_{\mathrm{rank}} = 0.7151/28/7160.43.52.0192892.7×10−132.7 \times10^{-13}1.6×10−121.6 \times10^{-12}2.2×10−122.2 \times10^{-12}
Mixedwmix=0.4w_{\mathrm{mix}} = 0.4165/35/5066.02.71.8180311×10−121 \times10^{-12}5.1×10−125.1 \times10^{-12}7.2×10−127.2 \times10^{-12}
GDFwfilter=0.1w_{\mathrm{filter}} = 0.1145/73/3258.02.51.1130192.5×10−142.5 \times10^{-14}1.8×10−131.8 \times10^{-13}2.2×10−132.2 \times10^{-13}
Mixedwmix=0.3w_{\mathrm{mix}} = 0.3140/45/6556.02.11.3150446.6×10−86.6 \times10^{-8}2×10−72 \times10^{-7}2.6×10−72.6 \times10^{-7}
Weighted Rankwrank=0.1w_{\mathrm{rank}} = 0.1137/71/4254.81.90.5125893.3×10−113.3 \times10^{-11}1.3×10−101.3 \times10^{-10}2×10−102 \times10^{-10}
Mixedwmix=0.2w_{\mathrm{mix}} = 0.2122/57/7148.81.40.0121251.9×10−41.9 \times10^{-4}3.8×10−43.8 \times10^{-4}3.8×10−43.8 \times10^{-4}
Mixedwmix=0.1w_{\mathrm{mix}} = 0.198/73/7939.20.50.088100.0860.0860.086

Table S2. Quadratic: 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.

The linear coefficients follow ci∼U[−50,50]c_i \sim U[-50, 50]. For the quadratic family a matrix BB is generated with independent entries from U[−7,7]U[-7, 7] and symmetrized as Q=(B+BT)/2Q = (B + B^T)/2; hence off-diagonal entries of QQ are averages of two uniform draws, rather than uniform themselves. The cost is xTQxx^T Qx, including both off-diagonal directions and the diagonal. The source objective files are fixed across strategies. For objective index o=0o = 0 (linear) or o=1o = 1 (quadratic), instance index ii and size nn, the initial/external source uses a Mersenne Twister seeded by 20261012+100000o+100n+i20261012 + 100000o + 100n + i; the model sampling stream is seeded by this value plus 10710^7. The source stream is independent of MPS sampling. Subsequent source batch sizes can differ because the number of unique MPS samples differs; identical starting data therefore do not imply identical full adaptive trajectories.

We apply the paired Wilcoxon signed-rank test to raw differences CBestCost−CADDC_{\mathrm{BestCost}} - C_{\mathrm{ADD}}, with the right-tailed alternative favoring ADD, as implemented by SignedRankTest in HypothesisTests.jl. Zeros are handled by that implementation; win/tie/loss counts use strict comparisons and exact equality of stored costs. The tables give the positive-rank sum WW, the unadjusted one-sided pp, Holm-adjusted pp over the 12 comparisons in that objective family, and the more conservative adjustment over all 24 baseline comparisons. Mean and median gains use the per-instance relative improvement RR; Rows are ordered by mean relative improvement, matching the weight-selection criterion. Of the 24 baseline comparisons, 23 remain significant at 0.05 after the joint Holm adjustment; Mixed Selection with ωmax⁡=0.1\omega_{\max} = 0.1 on quadratic objectives is the exception (p=0.086p = 0.086).

Set Partitioning construction and ADD transfer protocol

Elements, tiles and binary variables. Start with the ordered set V={1,…,m}V = \{1,\ldots,m\}. A candidate tile SjS_j is a nonempty subset of these elements, not necessarily a contiguous interval. The binary variable xjx_j indicates whether this tile is selected. Defining Aij=1{u∈Sj}A_{ij} = 1\{u \in S_j\} and b=1mb = 1_m, the constraint Ax=bAx = b requires the selected tiles to be disjoint and to cover every element exactly once. There are mm equalities and NN binary variables. We set N=n2N = n^2 only to retain the size labels of the assignment experiments.

Locality and the tile catalogue. Each tile contains at most four elements. Its span is max⁡S−min⁡S+1\max S - \min S + 1, where min⁡S\min S and max⁡S\max S are its smallest and largest element labels. For example, S={3,5,6}S = \{3,5,6\} has size three and span four: it lies inside the interval {3,4,5,6}\{3,4,5,6\}. We admit only tiles with span at most W\mathcal{W}. Increasing W\mathcal{W} allows more distant elements to occur in the same tile, without increasing the maximum tile size.

The tile-size proportions come from the reference case m=18m = 18, n=15n = 15, W=5\mathcal{W} = 5. For a tile of size s≥2s \ge2 and span exactly ℓ\ell, its containing interval has m−ℓ+1m - \ell+ 1 possible positions. Both endpoints belong to the tile, and s−2s - 2 of the ℓ−2\ell- 2 interior elements are chosen. Consequently the number of eligible size-ss tiles is

Ks(m,W)=∑ℓ=sW(m−ℓ+1)(ℓ−2s−2).K_s(m,\mathcal{W}) = \sum_{\ell=s}^{\mathcal{W}} (m-\ell+1) \binom{\ell-2}{s-2}.

At the reference setting, the catalogue contains 18 singletons, 62 pairs, 88 triples and 57 quadruples: exactly 225 = 15215^2 tiles.

Generating one instance. For each (W,m,n)(W,m,n), include all mm singletons, guaranteeing that at least one exact cover exists. Allocate the remaining N−mN-m columns to sizes 2, 3 and 4 in proportions 62 : 88 : 57. Take the floor of each quota and assign the leftover columns to the largest fractional remainders. Include all m−1m-1 adjacent pairs {u,u+1}\{u,u+1\} within the size-two quota. Fill the remaining quotas by uniform sampling without replacement from the eligible, not-yet-selected tiles of each size. Thus columns are distinct; the algorithm checks that each catalogue is large enough. When a quota exhausts its catalogue, that part of the matrix is deterministic. In particular, the reference matrix at (5,18,15)(5,18,15) is deterministic, although its objective arrays and initial draws vary between instances.

Sort columns by the smallest element of their tile. Within each such group, put nonsingletons in lexicographic order and the singleton last. For example, all tiles starting at element 3 precede tiles starting at element 4, and {3}\{3\} is processed last in its group. This spatial ordering is fixed by construction and is not selected by optimization performance. The grid uses W∈{5,6,8,10,12,15,18}W \in\{5,6,8,10,12,15,18\}, m∈{18,19,20}m \in\{18,19,20\} and n∈{13,14,15}n \in\{13,14,15\}, with 15 instances per cell: 945 tasks, or 135 per locality group. Constraints are generated independently of the objective values.

Exact uniform feasible sampling. Let U⊆VU \subseteq V be the elements already covered, and let F(U)F(U) count the ways to complete their cover using available tiles. Set F(V)=1F(V)=1. Otherwise choose the smallest uncovered element uu and compute

F(U)=∑j:u∈Sj,Sj∩U=∅F(U∪Sj).(14)F(U)=\sum_{\substack{j:u\in S_j,\\S_j\cap U=\varnothing}}F(U\cup S_j). \tag*{(14)}

Every completion must contain exactly one tile covering uu. Its other elements must be uncovered, which explains the two restrictions in the sum. Memoization stores these counts as arbitrary-precision integers. To draw a cover, choose each next tile with probability F(U∪Sj)/F(U)F(U\cup S_j)/F(U). Each exact cover has one path under this smallest-uncovered-element rule, and its probability telescopes to 1/F(∅)1/F(\varnothing). The resulting binary vectors are therefore exactly uniform over feasible solutions, with replacement. Integer rejection sampling avoids converting large counts to floating point. The saved inputs contain 500 initial draws, objective arrays and random seeds. The solver verifies input hashes and AX=bAX=b; external batches are also checked for feasibility and identity between the paired arms.

Left-to-right construction of the full indicator and its exact ranks. The task is to determine which virtual charges can occur in a complete feasible solution, before assigning entries to the TT cores. We process the binary decisions x1,…,xNx_1,\ldots,x_N from left to right in the fixed spatial column order. After the first kk decisions, the residual charge is

qk=1−∑j=1kAjxj.q_k=1-\sum_{j=1}^{k}A_jx_j.

An entry equal to one denotes an uncovered element; zero denotes an element already covered. Let QkQ_k be the set of distinct residual charges that are reachable by a prefix (x1,…,xk)(x_1,\ldots,x_k) and admit at least one feasible suffix (xk+1,…,xN)(x_{k+1},\ldots,x_N). Initially Q0={1}Q_0=\{1\}, and at the end QN={0}Q_N=\{0\}. The central issue is how to construct these sets without enumerating complete solutions or solving a separate completion problem for each charge.

State enumeration and the role of singletons. Variables are grouped by the smallest element of their tile. In the group with minimum element uu, all multielement tiles precede the singleton {u}\{u\}. Every singleton is present. From each q∈Qk−1q\in Q_{k-1}, consider the two decisions for tile SkS_k:

  • If xk=0x_k=0, the candidate residual is q′=qq'=q.

  • If xk=1x_k=1, the candidate is q′=q−Akq'=q-A_k. Allow this transition only when qv=1q_v=1 for every v∈Skv\in S_k, so no element is covered twice.

  • At the singleton Sk={u}S_k=\{u\}, also require qu′=0q'_u=0. After this variable no later tile contains uu, so leaving it uncovered cannot lead to a feasible solution.

Merge equal surviving residuals to obtain QkQ_k, retaining the allowed transitions between successive layers. Reachability is automatic because each candidate comes from a retained state of the preceding layer. Completion is also guaranteed: before the singleton {u}\{u\}, every uncovered element still has its singleton among the unprocessed variables; after it, the same is true once uu has been covered. Skip all remaining multielement tiles and select exactly the singletons of uncovered elements.

This gives an explicit feasible suffix for every retained state. Conversely, every feasible solution obeys the transition rules, so none is lost. Thus the forward pass constructs exactly QkQ_k, rather than a superset requiring a later backward feasibility search. This argument depends on the singleton-last order and the presence of all singletons; it does not apply to arbitrary constraint matrices or variable orders.

From states and transitions to the indicator TT. The forward pass determines QkQ_k and its incoming transitions at every binary variable, including those before a singleton. No waiting until the end of a group or backward pruning of earlier layers is required. To form the corresponding core, assign one virtual index to each charge in QkQ_k and set

Gq,x,q′[k]={1,q∈Qk−1, q′∈Qk, q′=q−Akx,0,otherwise.G^{[k]}_{q,x,q'} = \begin{cases} 1, & q \in Q_{k-1},\ q' \in Q_k,\ q' = q - A_kx,\\ 0, & \text{otherwise}. \end{cases}

The boundary indices are fixed to q0=1q_0 = 1 and qN=0q_N = 0. A fixed binary vector determines at most one state path; it has a complete path precisely when it is an exact cover. Contracting the cores therefore gives one for every feasible vector and zero otherwise. For the rank measurements reported here, the implementation only enumerates states, counts transitions and accumulates prefix-path counts; it does not allocate TT cores. Its final path count provides an independent check of the sampler’s F(∅)F(\varnothing).

Why locality bounds the work. While processing the group with minimum element uu, all earlier elements have been covered, and elements beyond u+W−1u + W - 1 have not yet been touched. Only the coverage of at most WW consecutive elements can vary. Store it as a bit mask, with one bit for a covered element (the complement of the residual convention above). After processing {u}\{u\}, drop its coordinate and advance this active window. At any fixed cut, the mask and the window position determine the full residual uniquely. Consequently,

Rk:=∣Qk∣≤2W.R_k := |Q_k| \le2^W.

Each state has at most two outgoing transitions. With machine-word masks and constant-time state lookup, the forward traversal takes O(∑k=1NRk−1)⊆O(NRmax⁡)O\left(\sum_{k=1}^{N} R_{k-1}\right) \subseteq O(NR_{\max}) operations, where Rmax⁡=max⁡0≤k≤NRkR_{\max} = \max_{0 \le k \le N} R_k. The current implementation uses two mask-indexed count arrays of length 2Wactual2^{W_{\mathrm{actual}}}, where Wactual≤WW_{\mathrm{actual}} \le W is the actual maximum tile span, as well as lists of occupied masks. Including initialization of these arrays, its state-enumeration cost is bounded by

O(2W+∑k=1NRk−1),O\left(2^W + \sum_{k=1}^{N} R_{k-1}\right),

with O(2W)O(2^W) working memory.

These bounds concern the state pass after preparing the input and masks; the code uses fixed-width masks and path counts for the benchmark sizes. Retaining the entire transition graph or the sparse cores additionally requires O(∑k=1NRk−1)O\left(\sum_{k=1}^{N} R_{k-1}\right) storage. Dense cores would instead store 2Rk−1Rk2R_{k-1}R_k entries per site. The sparse traversal is therefore linear in the number of visited states, not quadratic in adjacent ranks, but it is not a polynomial-time guarantee in WW: the ranks themselves may grow exponentially.

A complete three-element example. Take V={1,2,3}V = \{1,2,3\} and the ordered tiles

S1={1,2},S2={1},S3={2,3},S4={2},S5={3}.S_1 = \{1,2\}, \quad S_2 = \{1\}, \quad S_3 = \{2,3\}, \quad S_4 = \{2\}, \quad S_5 = \{3\}.

Here the maximum span is two. Start with Q0={(1,1,1)}Q_0 = \{(1,1,1)\}. At the first variable, skipping {1,2}\{1,2\} leaves (1,1,1)(1,1,1), while selecting it gives (0,0,1)(0,0,1). Thus Q1={(1,1,1),(0,0,1)}Q_1 = \{(1,1,1),(0,0,1)\}. Both states have a singleton completion. Next process S2={1}S_2 = \{1\}:

  • From (1,1,1)(1,1,1), skipping leaves element 1 uncovered after its last available tile, so discard that transition. Selecting gives (0,1,1)(0,1,1).

  • From (0,0,1)(0,0,1), selecting would cover element 1 twice, so disallow it. Skipping gives (0,0,1)(0,0,1) and closes the group correctly.

Hence Q2={(0,1,1),(0,0,1)}Q_2 = \{(0,1,1),(0,0,1)\}. The transitions at the first two variables correspond, for example, to the core entries G(1,1,1),1,(0,0,1)[1]=1G^{[1]}_{(1,1,1),1,(0,0,1)} = 1 and G(0,0,1),0,(0,0,1)[2]=1G^{[2]}_{(0,0,1),0,(0,0,1)} = 1.

At S3={2,3}S_3 = \{2,3\}, state (0,1,1)(0,1,1) allows both skipping and selecting, giving (0,1,1)(0,1,1) and (0,0,0)(0,0,0); state (0,0,1)(0,0,1) allows only skipping. Thus Q3={(0,1,1),(0,0,0),(0,0,1)}Q_3 = \{(0,1,1),(0,0,0),(0,0,1)\}. At singleton S4={2}S_4 = \{2\}, state (0,1,1)(0,1,1) must select, whereas (0,0,0)(0,0,0) and (0,0,1)(0, 0, 1) must skip it. Merge the identical resulting residuals to obtain Q4={(0,0,0),(0,0,1)}Q_4 = \{(0, 0, 0), (0, 0, 1)\}. Finally, singleton S5={3}S_5 = \{3\} is skipped from (0,0,0)(0, 0, 0) and selected from (0,0,1)(0, 0, 1), yielding Q5={(0,0,0)}Q_5 = \{(0, 0, 0)\}. The layer sizes are (1,2,2,3,2,1)(1, 2, 2, 3, 2, 1), all at most 22=42^2 = 4. There are exactly three complete paths, with binary vectors (1,0,0,0,1)(1, 0, 0, 0, 1), (0,1,1,0,0)(0, 1, 1, 0, 0) and (0,1,0,1,1)(0, 1, 0, 1, 1). In particular, at cut 2 the charge (0,0,1)(0, 0, 1) has one feasible suffix and (0,1,1)(0, 1, 1) has two: the bond has two states, although the indicator contains three nonzero entries. Multiplying the layer sizes would not count solutions, because only the recorded transitions connect layers.

Why these state counts are the exact TT ranks. At cut kk, unfold the full indicator into a matrix with binary prefixes as rows and binary suffixes as columns. A reachable prefix with residual qq is compatible with a suffix exactly when ∑j=k+1NAjxj=q\sum_{j=k+1}^{N} A_j x_j = q. All prefixes with the same residual therefore have identical compatible suffix sets, and different residuals have disjoint suffix sets. Grouping rows and columns by residual produces one all-ones rectangle per q∈Qkq \in Q_k, with zeros between these rectangles and possibly additional zero rows or columns. Every rectangle is nonempty: reachability supplies a prefix and the singleton completion supplies a suffix. Each rectangle has matrix rank one, and their row and column supports are disjoint. The unfolding rank is consequently exactly ∣Qk∣=Rk|Q_k| = R_k. This is the minimal ordinary TT bond dimension for the specified variable order, not merely an upper bound from a particular construction. The symmetric representation has the same total bond dimension, with charge degeneracy one. Maximum and mean ranks refer to the N−1N - 1 internal cuts. Table S3 pools 135 instances per locality group; its SD includes variation across the nine (m,n)(m, n) combinations, not only within each cell. The bound 2W2^W limits the number of charge states at a cut, not the number of feasible solution paths.

WWMaximum internal rankMean internal rank
524.0±0.224.0 \pm0.217.2±0.817.2 \pm0.8
648±148 \pm131±231 \pm2
8180±10180 \pm10100±10100 \pm10
10660±80660 \pm80300±40300 \pm40
12(2.3±0.4)×103(2.3 \pm0.4) \times10^{3}900±200900 \pm200
15(12±3)×103(12 \pm3) \times10^{3}(3.0±0.8)×103(3.0 \pm0.8) \times10^{3}
18(20±8)×103(20 \pm8) \times10^{3}(5±2)×103(5 \pm2) \times10^{3}

Table S3. Exact-indicator ranks in the fixed locality grid: mean ±\pm sample SD over all 135 instances at each span.

Transfer configuration. We transfer Best Cost + GDF with wfilter=0.4w_{\mathrm{filter}} = 0.4, the shared assignment-selected choice, to the entropic objective in Equation (13) of the main article. Both arms start from the same 500 feasible draws and use 15 outer iterations, one training sweep at learning rate 0.05, charge degeneracy one, 5K TT samples and 5K independent exact-uniform external draws per iteration. Five percent of the initial distinct training size is retained as an elite, with a minimum of one point; no worst-point retention is used. The model is rebuilt from selected data each iteration, without EELS. Boltzmann temperature is the standard deviation of current training costs, with uniform weights when it is zero. The table sampling backend is explicit. External RNG streams are matched by instance and iteration and separate from model sampling; matching seeds do not imply identical TT samples after the distributions diverge. Graph-history diagnostics record the fraction of externally drawn solutions with zero novelty.

There are 945 pairs, or 1,890 solver runs. Four Slurm allocations each execute 32 isolated one-core processes, with one BLAS thread and private per-instance checkpoints. The completed comparison uses equal iteration and requested-sample budgets, not equal runtime or objective-call budgets.

Statistical analysis. We apply one-sided paired Wilcoxon signed-rank tests to raw final-cost differences, excluding exact ties, with Holm adjustment over the seven locality groups. A location-shift interpretation assumes symmetric paired differences. The overall test gives p=2×10−48p = 2 \times10^{-48}; a paired sign test also supports the advantage (p=6.8×10−75p = 6.8 \times10^{-75}). Wins/ties/losses are unchanged by an absolute tolerance of 10−1010^{-10}. The smallest absolute baseline cost is 0.842, so the relative gains do not arise from nearly zero denominators. Mean-gain intervals use 5K paired bootstrap resamples stratified by the 63 design cells; these are pointwise intervals.

The individual-task Spearman correlation between exact maximum rank and relative gain is 0.435. It is positive within all nine (m,n)(m, n) groups, with Holm-adjusted p<0.006p < 0.006 in each. A regression controlling for these nine groups estimates 0.3 percentage points of additional gain per rank doubling (95% HC3 interval 0.3–0.4 percentage points, rounded). The accompanying analysis notebook reports all 63 cell-level A/B summaries, including losses and nonsignificant cells.

WWW/T/LMean95% intervalMedianHolm pp
53/132/00.0[0.0, 0.1]0.00.125
614/121/00.3[0.1, 0.5]0.01.2×10−41.2 \times10^{-4}
827/107/10.6[0.3, 0.9]0.04.1×10−64.1 \times10^{-6}
1044/91/01.7[1.2, 2.2]0.03.4×10−133.4 \times10^{-13}
1263/69/32.5[1.9, 3.2]0.01.1×10−101.1 \times10^{-10}
1575/56/43.1[2.5, 3.8]1.11.5×10−121.5 \times10^{-12}
1879/52/42.9[2.2, 3.6]0.92.5×10−132.5 \times10^{-13}

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.

Separate strip family used for SA. The SA comparison uses a different construction: m=3nm = 3n cells on a 3×n3 \times n rectangular strip, and N=n2N = n^2 binary tile-selection variables. Eligible tiles are connected sets of one to four cells, with connectivity through shared cell edges, spanning at most three strip columns. All singletons are mandatory. We also include the dominoes corresponding to every vertical edge and to the horizontal edges along the top row; together these edges form a spanning tree of the strip.

Select the remaining tiles without replacement using size weights a(S)=exp⁡[−2(∣S∣−2)]a(S) = \exp[-2(|S| - 2)], where ∣S∣|S| is the number of cells in a tile. Among optional tiles, pairs thus have weight 1, triples e−2e^{-2} and quadruples e−4e^{-4}. The coefficient −2-2 is a fixed generator choice favouring small tiles (the code’s light setting), not a Boltzmann temperature, a learned parameter, or a consequence of the objective. The implementation draws independent US∼Uniform⁡(0,1)U_S \sim\operatorname{Uniform}(0,1), forms exponential keys −log⁡US/a(S)-\log U_S/a(S), and selects the required number of tiles with the smallest keys.

The benchmark inputs are generated and saved before optimization, then reused unchanged for all methods. Spatial cell labels are restored and tiles use the singleton-last order described above; the corresponding variable permutation is also applied to the objective arrays. There is no search over variable order. This family is a deliberately low-rank contrast to row-major assignment, not a sample from the adjustable-locality grid. Full-indicator states and ranks are obtained from feasible prefix charges as above, and feasible covers are sampled using Equation (14).

Simulated annealing comparison: full protocol and additional sizes

Instances, objectives and initialization. For each of assignment and strip Set Partitioning, we use 40 previously generated and saved instances at each n=10,12,14n = 10, 12, 14, with N=n2N = n^2 binary variables. Assignment uses its row-major permutation encoding (2n2n equality rows); the strip construction and its 3n3n equalities are specified in § 8. Each instance is evaluated separately with C(x)=xTQxC(x) = x^{T}Qx and the 32-scenario entropic objective. The symmetric quadratic arrays are formed by symmetrizing matrices with independent uniform entries in [−7,7][-7, 7]. Within each (n,i)(n, i), both families use the same saved objective coefficient arrays and entropic scale s=3ns = \sqrt{3n}, although their feasible spaces differ. Initial data are 400 independent uniform feasible draws, with replacement: random permutations for assignment and exact counting for Set Partitioning. All four methods use the same initial draw matrix within a problem, objective and budget. The experiment comprises 5,760 runs: two families, two objectives, three sizes, 40 instances, three budgets and four methods.

Data-initialized EELS and full-indicator TT. Both start by deduplicating and evaluating the initial data. At every outer iteration EELS rebuilds from the current training set and enhances the graph with γ=1\gamma= 1. The full TT constructs the exact complete indicator once inside the timed run, then copies its uniformly normalized amplitudes at each iteration. Both variants train for one sweep, using learning rate 0.05, charge degeneracy one, and normalized Boltzmann weights with temperature equal to the current cost standard deviation (uniform weights at zero spread). After training they draw up to 10K samples, using the legacy backend in batches of 100 for deadline checks. The next training set contains at most 400 distinct lowest-cost points from the previous training set and the new batch; no external feasible samples are injected. The incumbent records all evaluated feasible points, including a partially completed final batch. The number of iterations is time-limited rather than fixed.

Informed SA. Optim.jl’s SimulatedAnnealing runs ten equally timed chains from the ten best distinct initial points. For assignment a proposal swaps the assigned columns of two distinct, uniformly chosen rows. For Set Partitioning a fixed patch is chosen uniformly from the tile supports. If an occupied tile crosses its boundary, the proposal is a self-loop; otherwise the current patch cover is replaced by a uniformly chosen exact cover of that patch. Patch covers are precomputed. These proposals are symmetric and preserve feasibility. Each chain cools geometrically in wall time from the standard deviation of initial costs to 10−310^{-3} times that value, with a machine-epsilon floor. The moves and patch catalogue provide problem-specific information beyond the explicit constraints and initial examples given to data-initialized EELS.

Penalty SA. The same Optim implementation and ten starting points minimize C(x)+α∥Ax−b∥22C(x) + \alpha\lVert Ax-b\rVert_2^2 on the whole binary cube, proposing one uniformly chosen bit flip. There is no repair or feasibility-preserving move catalogue. With RR and σ\sigma the range and sample SD of initial costs, set

sC=max⁡{R,σ,10−8max⁡(1,max⁡x∈T0∣C(x)∣)},α=10sC.(15)s_C = \max\left\{R,\sigma,10^{-8}\max\left(1,\max_{x\in T_0}|C(x)|\right)\right\}, \qquad\alpha=10s_C. \tag*{(15)}
v=median⁡j:∥Aj∥2>0∥Aj∥2,T0=max⁡{σ,αv/log⁡2}.(16)v=\operatorname{median}_{j:\lVert A_j\rVert_2>0}\lVert A_j\rVert^2, \qquad T_0=\max\{\sigma,\alpha v/\log2\}. \tag*{(16)}
Tend=max⁡{10−3σ,10−10sC}.(17)T_{\mathrm{end}}=\max\{10^{-3}\sigma,10^{-10}s_C\}. \tag*{(17)}

Geometric cooling is restarted within each chain. Ignoring the objective change, T0T_0 gives a typical constraint-violating one-bit proposal approximately one-half acceptance probability, rather than freezing every move at a feasible start. The multiplier is fixed across all instances and objectives. Only feasible raw costs update the reported incumbent. Every objective evaluation on an infeasible state nevertheless consumes a call and time. Residual computation, penalty setup, feasible/infeasible counters and best penalized states are recorded. No infeasible evaluated point had a penalized value below the initial feasible best.

Timing, counters and reproducibility. Separate 10, 50 and 200-second runs reuse fixed per-instance seeds. The source seed plus 10610^6 initializes SA’s default RNG, plus 2×1062\times10^6 its proposal RNG, and plus 3×1063\times10^6 the TT RNG. The cluster used Intel Xeon Gold 6226R CPUs at 2.90 GHz, Julia 1.12.5 and Optim.jl 2.3.2. Each solver process has one Julia compute thread and one BLAS thread; 32 independent processes share each exclusive allocation, with four allocations at a time. Timed work includes initial objective calls, TT construction, resets, training, sampling, penalty evaluation and search. Loading, JIT warmup, pre-run validation and informed-SA patch-catalogue construction are excluded; this last exclusion favors informed SA and limits end-to-end runtime interpretation.

Termination is cooperative. Improvements after the requested deadline are excluded, while actual elapsed times are retained. In particular, for quadratic assignment at n=14n=14 with a nominal 10-second budget, full TT averages 22.8 seconds (maximum 27.7) and completes no iteration on any task. At 200 seconds all methods perform search. Exact objective counters include initial calls, duplicates, repeated Optim evaluations, self-loops and penalty-SA infeasible points. The same evaluator is used by all methods: quadratic costs sum the active submatrix of QQ, while the entropic cost uses stable log-mean-exp.

Aggregation and inference. For each panel, average the per-task gain 100(C0−Cbest)/∣C0∣100(C_0-C_{\mathrm{best}})/|C_0| equally over its 40 instances. The curve uses the exact union of improvement events with stepwise interpolation. Pointwise asymmetric 95% percentile-bootstrap intervals resample the 40 tasks 2,000 times (seed 20261014), using the same weights across time and methods. For the objective-call axis, each method stops at the minimum final count over all 40 tasks; endpoints from slower tasks are not extrapolated. The 100,000-call diagnostic is a post hoc slice of the 200-second trajectories, not a separately tuned fixed-query test. Full assignment at n=14n=14 does not reach that slice on all tasks.

Paired tests use one-sided Wilcoxon signed ranks of raw baseline-minus-TT cost differences; differences below 10−9+10−11max⁡(∣Ca∣,∣Cb∣)10^{-9}+10^{-11}\max(|C_a|,|C_b|) are numerical ties. Tests versus penalty SA form a Holm family of 72 comparisons (36 groups times two TT variants). The original informed-SA analysis, extended to include penalty SA as a third candidate, uses 108 comparisons in a separate Holm family. Both are exploratory analyses of this benchmark, with one seed per task.

Table S5. 200-second endpoints. Each cell is mean feasible-objective gain (%) / mean objective calls (millions), over 40 tasks. Means include unsuccessful runs.

FamilyObjectivennInformed SAPenalty SAEELSFull TT
AssignmentQuadratic1073.5 / 368.624.7 / 103.952.4 / 1.671.3 / 1.2
AssignmentQuadratic12102.8 / 303.315.8 / 70.155.5 / 0.9285.1 / 0.34
AssignmentQuadratic14132.9 / 252.59.8 / 48.145.9 / 0.5375.2 / 0.064
AssignmentEntropic1093.3 / 125.227.7 / 62.776.4 / 1.792.7 / 1.2
AssignmentEntropic12115.6 / 108.118.6 / 45.173.9 / 0.98109.5 / 0.35
AssignmentEntropic14141.1 / 95.611.7 / 32.454.6 / 0.57106.2 / 0.067
Set PartitioningQuadratic1087.8 / 86.722.2 / 65.387.1 / 1.787.2 / 1.6
Set PartitioningQuadratic12117.2 / 79.717.3 / 59.8115.9 / 1.0116.7 / 0.88
Set PartitioningQuadratic14139.6 / 67.86.2 / 39.2134.4 / 0.63137.1 / 0.5
Set PartitioningEntropic10200.7 / 69.846.1 / 49.0199.8 / 1.8200.7 / 1.7
Set PartitioningEntropic12201.6 / 64.131.8 / 46.0200.8 / 1.1201.6 / 0.93
Set PartitioningEntropic14210.6 / 58.319.5 / 31.1210.0 / 0.66210.6 / 0.54

Table S5.

Table S6. Paired improvements over penalty SA at 200 seconds: mean 100(Cpenalty−CTT)/∣Cpenalty∣100(C_{\mathrm{penalty}} - C_{\mathrm{TT}})/|C_{\mathrm{penalty}}| (%), wins/ties/losses, and one-sided Wilcoxon pp after Holm correction over all 72 TT–penalty comparisons (including 10 and 50 seconds).

FamilyObjectivennEELS (%)W/T/LHolm ppFull TT (%)W/T/LHolm pp
AssignmentQuadratic1023.340/0/06.5×10−116.5 \times10^{-11}38.540/0/06.5×10−116.5 \times10^{-11}
AssignmentQuadratic1235.039/0/16.5×10−116.5 \times10^{-11}60.740/0/06.5×10−116.5 \times10^{-11}
AssignmentQuadratic1433.540/0/06.5×10−116.5 \times10^{-11}60.040/0/06.5×10−116.5 \times10^{-11}
AssignmentEntropic1038.340/0/06.5×10−116.5 \times10^{-11}51.340/0/06.5×10−116.5 \times10^{-11}
AssignmentEntropic1248.438/1/16.5×10−116.5 \times10^{-11}78.840/0/06.5×10−116.5 \times10^{-11}
AssignmentEntropic1441.239/0/16.5×10−116.5 \times10^{-11}87.940/0/06.5×10−116.5 \times10^{-11}
Set PartitioningQuadratic1053.740/0/06.5×10−116.5 \times10^{-11}53.840/0/06.5×10−116.5 \times10^{-11}
Set PartitioningQuadratic1285.440/0/06.5×10−116.5 \times10^{-11}86.040/0/06.5×10−116.5 \times10^{-11}
Set PartitioningQuadratic14121.840/0/06.5×10−116.5 \times10^{-11}124.340/0/06.5×10−116.5 \times10^{-11}
Set PartitioningEntropic10109.340/0/06.5×10−116.5 \times10^{-11}109.740/0/06.5×10−116.5 \times10^{-11}
Set PartitioningEntropic12125.540/0/06.5×10−116.5 \times10^{-11}126.140/0/06.5×10−116.5 \times10^{-11}
Set PartitioningEntropic14159.140/0/06.5×10−116.5 \times10^{-11}159.640/0/06.5×10−116.5 \times10^{-11}

Table S6.

Figure S1. Additional size n=10n = 10 (N=100N = 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=10n = 10 (N=100N = 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=12n = 12 (N=144N = 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=12n = 12 (N=144N = 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.

Detailed library performance benchmarking

Matched inputs and benchmark protocol

We compared the training and sampling kernels of the two libraries on the binary assignment problem. For an n×nn \times n assignment instance there are n2n^2 binary variables and 2n2n linear equality constraints. We used 4≤n≤104 \le n \le10, one complete right–left training sweep, one batch of ∣T∣=400|T| = 400 samples after training, bond degeneracy one, and learning rate 0.05. A deterministic dense quadratic cost matrix with entries in {−7,…,7}\{-7,\ldots,7\} was generated for every nn. Four hundred random feasible assignments were generated and resampled once according to their Boltzmann weights. The resulting empirical training matrix, including repeated rows, was passed unchanged to both implementations. Thus, both libraries were trained on exactly the same data. OhMyU1 is measured with two sampling backends. The legacy backend follows sampled charge paths using the block dictionaries; table first constructs transition tables for all charge states on each sampling call, then amortizes that preparation over the batch. Both implement the same conditional probabilities. Training is unchanged; the recorded training-time differences between runs reflect timing variation, not a different training algorithm.

The initial tensors represented the same mathematical state: the uniform superposition of all feasible assignments. ConstrainTNet constructed its state exactly from the constraints. For OhMyU1, the complete set of reachable charge sectors at every cut was enumerated exactly by a dynamic construction specific to the assignment variable order; no finite random initialization sample was used. The maximum bond supports were identical in both representations and ranged from 9 at n=4n = 4 to 461 at n=10n = 10.

Tensor construction, initial-state canonicalization and normalization, Julia compilation, and copying of the prepared state were excluded from the reported time. Each kernel was executed once as a warm-up, followed by three measured repetitions; the median wall time is reported. The primary metric is the sum of the median time for one training sweep and the median time for exactly 400 sequential samples from the trained state. All runs used Julia 1.12.5, one default Julia thread, one BLAS thread, and the same Intel Core i5-10210U CPU.

Implementation details and validation

The refreshed benchmark uses OhMyU1 revision e23712d and ConstrainTNet revision 77d8c26 (latest upstream checked on 12 October 2026). ConstrainTNet’s algorithm sources are unmodified; vendored ITensors 0.3.41/NDTensors 0.1.50 are retained. The sole source adjustment increases ITensors’ fixed charge capacity from 20 to 21: at 20 equalities, comparison with an empty charge attempts to insert an inactive component and otherwise fails. The spare slot avoids this boundary error.

The random seed for each problem is 20260923+10000n20260923 + 10000n. The Boltzmann temperature is the sample standard deviation of the 400 candidate costs; 400 draws with replacement form the common empirical training multiset.

One default Julia thread, no interactive thread, and one BLAS thread are used on Windows with an Intel Core i5-10210U processor. The two backends run in separate sequential processes. Each timing starts from a fresh copy, with garbage collection outside the timed region. Compilation, construction, initial-state canonicalization/normalization, and copying are excluded. Each kernel is warmed up and timed three times; the table adds the two kernel medians rather than timing a high-level optimizer wrapper. This avoids the extra pre-training sampling batch in ConstrainTNet.optimizer.

OhMyU1 performs projected two-site updates, whereas ConstrainTNet performs one-site updates. Internal canonicalization, environment construction, and loss evaluation performed by the public ConstrainTNet training routine remain inside its timing. Thus, the measurements compare the cost of the available training and sampling routines for the same inputs and sweep count.

nnTrain LSample LTotal LTrain TSample TTotal TConstrainTNet
40.00250.00330.00580.00240.00040.00281.2
50.00610.00590.0120.00580.00080.00662.2
60.0130.00960.0230.0130.00180.0153.4
70.0280.0130.0410.0280.00420.0325.2
80.0590.0190.0780.0550.00910.0648.5
90.150.0290.180.140.0210.1614
100.30.0440.340.310.0450.3647

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.

PROTES comparison: exact indicators and data-based initialization

OhMyU1 measurements were repeated on 12 October 2026 using revision e23712d, with unchanged inputs, seeds, CPU affinity, batch sizes, and time budgets. The PROTES measurements were retained. The source hashes and separate memory-audit and timing runs are archived. OhMyU1 uses the serial sample_nondeg! routine, with both backend=:legacy and backend=:table reported separately. Full-indicator table timings are the archived repeat after the memory audit; data-initialized table runs were measured separately with identical inputs.

Exact assignment indicator, ranks, and storage

The full structural tensor is I(x)=1{Ax=b}I(x) = 1\{Ax = b\}. For assignment, reshape the N=n2N = n^2 binary variables as xijx_{ij} with exactly one selected entry in every row and column. Process these bits row by row. At a cut after k=rn+sk = rn + s bits, rr rows are complete and ss bits of the next row have been processed, with 0≤s<n0 \le s < n.

A dynamic-programming state records the set SS of columns already used by selected entries and the flag h∈{0,1}h \in\{0, 1\} indicating whether the current, partially processed row already has its selected entry. The completed rows contribute exactly rr selected entries, so h=∣S∣−rh = \lvert S\rvert- r. For example, for n=3n = 3 at k=4k = 4 we have r=1,s=1r = 1, s = 1. State (S={2},h=0)(S = \{2\}, h = 0) means that the first row selected column 2 and the second row skipped column 1. State (S={1,2},h=1)(S = \{1, 2\}, h = 1) means that the second row has already selected column 1. These states have different sets of feasible suffixes.

To process the next bit in column s+1s + 1, choosing zero leaves SS unchanged; choosing one is allowed only if h=0h = 0 and s+1∉Ss + 1 \notin S, and adds that column to SS. At the end of each row require exactly one selected entry and reset the flag for the next row. Merge identical states. Keep only states reachable from the empty prefix and extendable to a complete assignment. For h=0h = 0, an unoccupied column must remain among s+1,…,ns + 1, \ldots, n. For h=1h = 1, at least one occupied column must be among 1,…,s1, \ldots, s, so the current row’s selection can lie in the processed prefix. At the endpoints, S=∅S = \varnothing and S={1,…,n}S = \{1, \ldots, n\}.

Each retained state labels a virtual index. Set a core entry to one for each permitted state transition and to zero otherwise. Every permutation has exactly one binary path, hence unit amplitude; all other binary vectors have zero amplitude. This constructs the full indicator without enumerating n!n! permutations. The symmetric and dense representations encode this same graph; the dense one additionally stores forbidden transitions as zero coefficients. Let RkR_k denote the total virtual dimension at cut kk, equivalently the number of retained charge states, as in the Set Partitioning construction.

With out-of-range binomial coefficients interpreted as zero, the number of states at an internal cut is

Rk=(nr)−(sr−n+s)+(nr+1)−(n−sr+1),R0=RN=1.(18)R_k = \binom{n}{r} - \binom{s}{r-n+s} + \binom{n}{r+1} - \binom{n-s}{r+1}, \qquad R_0 = R_N = 1. \tag*{(18)}

Here rr is the number of completed rows and ss the number of processed bits in the current row. The first pair of terms counts h=0h = 0 states and the second counts h=1h = 1 states. After grouping prefixes and suffixes by residual constraint charge, the indicator unfolding consists of disjoint nonempty all-ones blocks, each of rank one. Consequently RkR_k is the exact minimal ordinary TT rank for this ordering. The maximum is Θ(2n/n)\Theta(2^n / \sqrt{n}) (e.g., 125 at n=8n = 8, 461 at n=10n = 10, and 24309 at $n = 16). The U(1)U(1) representation has the same total link dimension, but every sector has degeneracy one. This exact-rank statement concerns the full indicator; an optimizer’s distribution concentrated on a smaller feasible subset need not have these ranks.

The two dense float64 storage counts in Figure 17 of the main article are

Buniform=8[2(N−2)Rmax⁡2+4Rmax⁡],Bvariable=16∑k=1NRk−1Rk.(19)B_{\mathrm{uniform}} = 8\left[2(N-2)R_{\max}^{2} + 4R_{\max}\right], \qquad B_{\mathrm{variable}} = 16\sum_{k=1}^{N} R_{k-1}R_k. \tag*{(19)}

They describe the fast PROTES core layout and the variable-rank protes_general layout, respectively. For U(1)U(1), the number of allowed scalar transitions at position (r,s)(r,s) is

Er,s=(n−1r)+(nr)−(s+1r−n+s+1)+(nr+1)−(n−sr+1).(20)E_{r,s} = \binom{n-1}{r} + \binom{n}{r} - \binom{s+1}{r-n+s+1} + \binom{n}{r+1} - \binom{n-s}{r+1}. \tag*{(20)}

The first term counts transitions assigning one and the remaining terms count transitions assigning zero. Thus numerical block storage is 8∑r=0n−1∑s=0n−1Er,s8\sum_{r=0}^{n-1}\sum_{s=0}^{n-1}E_{r,s} bytes. These counts were checked against the constructed blocks and dense arrays. MiB and GiB denote 2202^{20} and 2302^{30} bytes. Full U(1)U(1) objects were constructed and measured through n=16n=16 using Base.summarysize, including dictionaries, charge vectors, the constraint matrix, and other reachable fields. The measurement excludes process/runtime memory and temporary buffers; it depends on object sharing in this constructor. Dense curves count coefficient arrays only. Adam states, gradients, and training workspaces are excluded from all storage claims.

Untrained full-indicator sampling protocol

Both models sample uniformly over the same full feasible set. PROTES uses the above zero/one transition cores, padded to a common internal rank for its fast implementation and left at their exact ranks for protes_general. For OhMyU1, backward dynamic programming computes the completion count Ck(q)C_k(q) at every link: kk is the number of processed binary variables and q=b−∑j=1kAjxjq=b-\sum_{j=1}^{k}A_jx_j is the residual constraint vector. Thus Ck(q)C_k(q) counts suffixes (xk+1,…,xN)(x_{k+1},\ldots,x_N) whose contribution equals qq. Starting with CN(0)=1C_N(0)=1, compute backwards

Ck(q)=∑v:q→vq′Ck+1(q′),q′=q−vAk+1,C_k(q) = \sum_{v:q\xrightarrow{v}q'} C_{k+1}(q'), \qquad q'=q-vA_{k+1},

where the sum includes only retained feasible transitions. For example, at a row boundary of assignment, Ck(q)=(n−r)!C_k(q)=(n-r)! after rr completed rows: the remaining rows can be matched bijectively to the unoccupied columns. The scalar on an allowed edge q→q′q\to q' is replaced by Ck+1(q′)/Ck(q)\sqrt{C_{k+1}(q')/C_k(q)}. Products telescope to 1/n!1/\sqrt{n!}, giving an exact right-canonical normalized amplitude. Its squared amplitudes and the PROTES probability indicator therefore induce the same uniform law.

We call the unchanged OhMyU1 serial sample_nondeg! and the upstream PROTES sampling kernels with their usual JAX vectorization. Batches contain 100 samples. Each of three seeds runs until cumulative timed generator calls reach at least one second; a final batch can exceed that duration. Throughput divides the actual generated count by actual timed duration, and counts repetitions. Construction, canonicalization, JIT warm-up, feasibility checks, and unique-point bookkeeping are excluded. PROTES timing includes materializing the output and recomputing right environments per batch, as in its normal sampling loop. The feasible fraction is 100.0% in all recorded batches. Raw per-trial batch counts, times, warm-up/construction times, and distinct-point counts are retained in the accompanying results snapshot. Full dense models are allocated for n=4,…,10n=4,\ldots,10; beyond this grid their storage curves are analytical, not timing measurements. OhMyU1 is measured for n=4,…,16n=4,\ldots,16.

The large U(1)U(1) object traversal initially caused memory pressure at n=15,16n=15,16 on the local machine. Final sampling measurements were repeated without repeating that deep traversal and with garbage collection before warm-up; the initial memory-audit runs are retained separately. The shaded ranges report run-to-run variation, not confidence intervals or an asymptotic complexity result.

Paired, data-initialized optimization protocol

Longer initial fitting improves PROTES: at n=8n=8, fit20 finds 12–25 new points for linear objectives and 17–25 for quadratic objectives in 50 seconds, while EELS with the legacy sampler finds 6.9K–7.3K and 9.3K–10K, respectively. Thus, inability to generate any feasible point is not a robust conclusion; the observed limitation is rare feasible generation under this data-initialization and update rule. New points need not improve the objective. With the table sampler the corresponding EELS ranges are 6.9K–7.3K and 9.4K–10K.

Figure S5. The same data-initialized comparison at n=8n = 8 (N=64N = 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 log⁡10(1+z)\log_{10}(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.

These diagnostic instances are separate from the article’s objective files. For each (n,j,o)(n, j, o), with repetition index jj and objective family oo, NumPy’s generator uses seed 20261008+1000n+10j+1o=quadratic20261008 + 1000n + 10j + 1_{o=\mathrm{quadratic}}. It first draws 400 independent random permutations and converts them to row-major binary assignments. It then draws either independent ci∼U[−50,50]c_i \sim U[-50,50], with cost cTxc^{T}x, or a matrix with independent Bij∼U[−7,7]B_{ij} \sim U[-7,7], sets Q=(B+BT)/2Q = (B + B^{T})/2, and uses cost xTQxx^{T}Qx. Exactly the same arrays are exported to Julia.

Define novelty as the number of distinct generated feasible points outside the set of initial observations. Initial duplicates are not new, repeated generated points count once, and the initial best cost is retained in every method. The 5-second screen uses n=4,…,10n = 4,\ldots,10 and j=0j = 0; the 50-second comparison uses n=8n = 8 and j=0,1,2j = 0,1,2, for both objective families. All five PROTES configurations in Table S8 are included at both budgets. At n=4n = 4 the particular initial datasets cover all 24 solutions.

ConfigurationRankkkktopk_{\mathrm{top}}ggLearning rateeeInitial updates
default51001010.0514
rank20201001010.0514
slow10510010100.01140
batch4001040040100.01110
fit2051001010.052080

Table S8. PROTES settings. kk is the input/generated batch size, ktopk_{\mathrm{top}} the elite count, gg the number of Adam steps per accepted batch, and ee the number of passes through the initial 400 observations. The last column is the number of initial Adam updates, (400/k)eg(400/k)eg.

PROTES starts from its ordinary random dense cores, receives the initial observations through its external-sample interface in deterministically shuffled passes, and applies its normal elite update. Thus only the best 10.0% of each input batch contributes to the likelihood update, not all 400 observations simultaneously. After initialization no more external observations are injected. The external evaluator assigns valid points score (2/π)arctan⁡C(x)(2/\pi)\arctan C(x) and invalid points score 2, preserving the ordering of feasible costs. An entirely infeasible batch uses the upstream pick-update path. If fewer than ktopk_{\mathrm{top}} points are feasible, the unchanged elite rule also includes penalized infeasible points. No mask, repair, indicator, AA, bb, or permutation encoding is given to PROTES.

OhMyU1 receives AA, bb, deduplicates and cost-sorts the same initial data, and rebuilds its TT from the retained data at each outer iteration, applying EELS with γ=1\gamma= 1 and sector degeneracy one before canonicalization. Training uses one right–left sweep, learning rate 0.05, and normalized weights proportional to exp⁡[−(C(x)−Cmin⁡)/T]\exp[-(C(x)-C_{\min})/T], with TT the sample standard deviation of the current costs; weights are uniform if T=0T = 0. The normalized trained TT supplies up to 10K samples, processed in batches of 100 for deadline checks. The next dataset contains up to 400 lowest-cost distinct points from the union of retained and newly generated points. No external feasible generator is called after initialization. The number of iterations is set by the wall-time limit and reported below.

Initial model construction/fitting, subsequent training, sampling, novelty bookkeeping, and objective evaluation all count toward the 5/50-second budgets. Explicit warm-up and file loading do not: PROTES warms its kernels on a synthetic binary objective at the same dimension, while OhMyU1 warms one full outer iteration and discards its model. Residual compilation counts toward the measured budget. Deadlines are cooperative: a current sample or training operation can overrun, and a batch arriving after the deadline is not accepted. All initial fits completed. There is no fixed number of PROTES optimization iterations; generated counts and batch sizes determine the sampling workload, whereas only batches containing feasible points trigger further Adam steps. Total post-initialization Adam-update counts were not separately logged. The result tables give generated counts rather than implying equal iteration counts; actual elapsed times remain available in the archived results.

ConfigurationObjectiveNew pointsGenerated draws (range)
defaultlinear0, 0, 03.3M–3.4M
defaultquadratic0, 0, 03.1M–3.4M
rank20linear0, 0, 01.2M–1.5M
rank20quadratic0, 0, 01.4M–1.6M
slow10linear13, 9, 43M–3.1M
slow10quadratic6, 3, 62.7M–2.9M
batch400linear0, 0, 03.4M–3.6M
batch400quadratic0, 0, 03.5M–3.5M
fit20linear22, 12, 252.9M–3.3M
fit20quadratic17, 18, 253.3M–3.4M

Table S9. Recorded 50-second PROTES runs at n=8n = 8. Triples are new distinct feasible points in seed order j=0,1,2j = 0, 1, 2; ranges cover the three runs. Generated counts include infeasible draws.

nnObjectivejjBudget (s)IterationsDrawsNew points
4linear0538/39380K0
4quadratic0539/40390K0
5linear0525/26260K6
5quadratic0526/27270K3
6linear0516/17170K418
6quadratic0515/16160K406
7linear0510/11110K3K
7quadratic0510/11100K3.5K
8linear057/877K6.6K
8quadratic056/760K7.9K
9linear054/541K8K
9quadratic053/434K11K
10linear053/434K8.4K
10quadratic053/432K11K
8linear05072/73720K6.9K
8linear15059/60590K7.3K
8linear25060/61610K7.2K
8quadratic05055/56560K9.3K
8quadratic15056/57560K9.7K
8quadratic25056/57570K10K

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.

All experiments ran locally on an Intel Core i5-10210U (four physical cores, eight logical processors, approximately 8 GB RAM), Windows 11, with each process pinned to logical CPU 0 and BLAS restricted to one thread. OhMyU1 uses Julia 1.12.5 with one thread; PROTES uses Python 3.12.14, NumPy 1.26.4, JAX 0.4.38 (CPU/x64), and Optax 0.2.4. The upstream revision is 06d447845dd26ffccb8e95c7545fa1d2617940e. The scripts, compact results, hashes, and Julia plotting code accompany the notebook examples/PROTES_assignment_scaling.ipynb.

nnObjectivejjBudget (s)IterationsDrawsNew points
4linear0590/91900K0
4quadratic0574/74740K0
5linear0542/43430K6
5quadratic0543/44440K3
6linear0518/19180K418
6quadratic0520/21210K406
7linear0510/11110K3K
7quadratic059/1091K3.4K
8linear056/765K6.5K
8quadratic055/650K7.7K
9linear053/430K7.9K
9quadratic052/329K11K
10linear051/215K7.7K
10quadratic051/213K8K
8linear05073/74730K6.9K
8linear15066/67660K7.3K
8linear25061/62620K7.2K
8quadratic05058/59580K9.4K
8quadratic15051/52510K9.6K
8quadratic25056/57570K10K

Table S11. 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.

ConfigurationGenerated draws (range)
default34K–390K
rank2054K–140K
slow1028K–260K
batch40078K–470K
fit20120K–340K

Table S12. 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.

References

  1. [1]Affleck, I., Kennedy, T., Lieb, E. H., and Tasaki, H. Rigorous results on valence-bond ground states in antiferromagnets. Physical review letters, 59(7):799, 1987.
  2. [2]Alcazar, J., Ghazi Vakili, M., Kalayci, C. B., and Perdomo-Ortiz, A. Enhancing combinatorial optimization with classical and quantum generative models. Nature Communications, 15(1):2761, 2024.
  3. [3]Antil, H., Dolgov, S., and Onwunta, A. Trisk: Tensor train decomposition algorithm for risk averse optimization. Numerical Linear Algebra with Applications, 30(3):e2481, 2023.arxiv.org/abs/2111.05180
  4. [4]Arenstein, L. and Kastoryano, M. Full grid solution for multi-asset options pricing with tensor networks. arXiv preprint arXiv:2601.00009, 2025.arxiv.org/abs/2601.00009
  5. [5]Batsheva, A., Chertkov, A., Ryzhakov, G., and Oseledets, I. PROTES: probabilistic optimization with tensor sampling. Advances in Neural Information Processing Systems, 36: 808–823, 2023.arxiv.org/abs/2301.12162
  6. [6]Biere, A., van Maaren, H., and Walsh, T. Handbook of satisfiability. SAGE Publications Limited, 2009.
  7. [7]Dolgov, S. and Savostyanov, D. Parallel cross interpolation for high-precision calculation of high-dimensional integrals. Computer Physics Communications, 246:106869, 2020.DOI
  8. [8]Farhi, E., Goldstone, J., and Gutmann, S. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014.arxiv.org/abs/1411.4028
  9. [9]Fishman, M., White, S. R., and Stoudenmire, E. M. The ITensor software library for tensor network calculations. SciPost Phys. Codebases, pp. 4, 2022. doi: 10.21468/SciPostPhysCodeb.4.DOI
  10. [10]Iudin, S. OhMyUI: Repository for the paper "exploration-exploitation generative framework for constrained combinatorial optimization with tensor-trains", 2026. URL https://github.com/antientropic-guy/OhMyUI_public.
  11. [11]Iudin, S., Veshchezerova, M., Tsarova, K., Tadumadze, G., Shete, V., Hao, J.-K., and Perelshtein, M. A parameter-guided two-stage heuristic for liquefied natural gas transportation and trading over long-term horizons. Algorithms, 19(10):822, 2026. doi: 10.3390/a19100822. URL https://www.mdpi.com/1999-4893/19/10/822.DOI
  12. [12]Jones, D. R., Schonlau, M., and Welch, W. J. Efficient global optimization of expensive black-box functions. Journal of Global optimization, 13(4):455–492, 1998.DOI
  13. [13]Kirkpatrick, S., Gelatt Jr, C. D., and Vecchi, M. P. Optimization by simulated annealing. science, 220(4598):671–680, 1983.
  14. [14]Koopmans, T. C. and Beckmann, M. Assignment problems and the location of economic activities. Econometrica: journal of the Econometric Society, pp. 53–76, 1957.DOI
  15. [15]Lopez-Piqueres, J. Constraintnet.jl: Repository for the paper “cons-training tensor networks”, 2024. URL https://github.com/JaviLioPiq/ConstraintNet.jl.
  16. [16]Lopez-Piqueres, J. and Chen, J. Cons-training tensor networks: Embedding and optimization over discrete linear constraints. SciPost Phys., 18:192, 2025.
  17. [17]Lopez-Piqueres, J., Chen, J., and Perdomo-Ortiz, A. Symmetric tensor networks for generative modeling and constrained combinatorial optimization. Machine Learning: Science and Technology, 4(3):035009, 2023.
  18. [18]Mugel, S., Kuchkovsky, C., Sánchez, E., Fernández-Lorenzo, S., Luis-Hita, J., Lizaso, E., and Orús, R. Dynamic portfolio optimization with real datasets using quantum processors and quantum-inspired tensor networks. Physical Review Research, 4(1):013006, 2022.DOI
  19. [19]Nakada, H., Tanahashi, K., and Tanaka, S. Quick design of feasible tensor networks for constrained combinatorial optimization. Quantum, 9:1799, 2025.DOI
  20. [20]Novikov, A., Podoprikhin, D., Osokin, A., and Vetrov, D. Tensorizing neural networks. In Proceedings of the 29th International Conference on Neural Information Processing Systems - Volume 1, pp. 442–450, Cambridge, MA, USA, 2015. MIT Press.arxiv.org/abs/1509.06569
  21. [21]Oseledets, I. V. Tensor-train decomposition. SIAM Journal on Scientific Computing, 33(5):2295–2317, 2011.DOI
  22. [22]Ryzhakov, G. and Oseledets, I. Constructive tt-representation of the tensors given as index interaction functions with applications. In International Conference on Learning Representations (ICLR), 2023. URL https://openreview.net/forum?id=yLzLmF-Esnu.arxiv.org/abs/2206.03832
  23. [23]Sozykin, K., Chertkov, A., Schutski, R., Phan, A.-H., Cichocki, A. S., and Oseledets, I. TTOpt: A maximum volume quantized tensor train-based optimization and its application to reinforcement learning. Advances in neural information processing systems, 35:26052–26065, 2022.arxiv.org/abs/2205.00293
  24. [24]Sozykin, K., Rybin, N., Chertkov, A., Phan, A.-H., Oseledets, I., Shapeev, A., Novikov, I., and Ryzhakov, G. Global optimization of atomic clusters via physically-constrained tensor train decomposition. arXiv preprint arXiv:2601.18592, 2026.arxiv.org/abs/2601.18592
  25. [25]Sulimov, A. V., Zheltkov, D. A., Oferkin, I. V., Kutov, D. C., Katkova, E. V., Tyrtyshnikov, E. E., and Sulimov, V. B. Evaluation of the novel algorithm of flexible ligand docking with moveable target-protein atoms. Computational and Structural Biotechnology Journal, 15:275–285, 2017.DOI
  26. [26]White, S. R. Density matrix formulation for quantum renormalization groups. Physical review letters, 69(19):2863, 1992.pubmed.ncbi.nlm.nih.gov/10046608
  27. [27]Yang, Y., Zhou, J., Wong, N., and Zhang, Z. Loretta: Low-rank economic tensor-train adaptation for ultra-low-parameter fine-tuning of large language models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pp. 3161–3176, 2024.
  28. [28]Zheltkov, D. A. and Osinsky, A. Global optimization algorithms using tensor trains. In International Conference on Large-Scale Scientific Computing, pp. 197–202. Springer, 2019.DOI

Paper details

vlnc:W_nfxmsy6h
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

DeepSeek-V4.1-Flash

View statement
Looking for related papers…
Contents