Recycling computational processes of dynamic programming for combinatorial optimization problems: a reservoir computing approach

# Recycling computational processes of dynamic programming for combinatorial optimization problems: a reservoir computing approach
Source: [https://arxiv.org/html/2607.23009](https://arxiv.org/html/2607.23009)
\[1\]\\fnmSora\\surTodaka

\[1\]\\orgdivGraduate School of Informatics,\\orgnameKyoto University,\\orgaddress\\citySakyo\-ku, Kyoto,\\countryJapan

2\]\\orgdivInstitute for Liberal Arts and Sciences,\\orgnameKyoto University,\\orgaddress\\citySakyo\-ku, Kyoto,\\countryJapan

###### Abstract

Reusing previously computed results is a long\-standing principle for reducing computational cost, but such reuse has largely been confined to a single problem’s computation\. Sharing computational processes across multiple simultaneously solved problems remains possible in principle, yet designing algorithms that exploit nontrivial cross\-task relationships is difficult to do manually\. Here, we use machine learning to discover such algorithms automatically\. Specifically, based on reservoir computing, we propose a method that uses computation results recorded by dynamic programming for combinatorial optimization problems as features for linear regression, leveraging them to assist other combinatorial optimization computations\. We validate the approach on the traveling salesman and subset sum problems\. Multiplexing the dynamic programming process improves approximation accuracy over generic features and reduces computation time compared with independent solutions\. These results suggest a new form of computation, distinct from conventional computational design, in which multiple processes efficiently share and recycle intermediate results and states\.

###### keywords:

combinatorial optimization, reservoir computing, linear regression, dynamic programming, traveling salesman problem, subset sum problem

## 1Introduction

Saving computed results and reusing them efficiently has long been an important design principle for reducing computational cost\. Before the advent of computers, when computational resources were limited to human calculation, this principle was practiced rigorously\. For example, tables of trigonometric functions, logarithms, and probability density functions were indispensable for computing essential functions in daily life and engineering\. In particular, Napier’s logarithm tables, completed after 20 years of computation, made it possible to reduce costly multiplication to table lookup and simple addition\.

The idea of efficient reuse of computation persists in modern computer science in the form of lookup tables and memorization, and it underlies many approaches to computational efficiency\. For instance, dynamic programming \(DP\) records and reuses solutions to subproblems that appear repeatedly in inductive solution processes, and it is widely used in optimization problems as an algorithm design technique to eliminate redundant computation\. Another concrete example of the sharing intermediate results also appears in matrix multiplication\. While the naive algorithm for multiplying two2×22\\times 2matrices requires eight multiplications, Strassen reduced this to seven by constructing seven shared intermediate terms for the entries\. More recently, AlphaTensor discovered new algorithms that reduce the number of multiplications for4×44\\times 4matrix multiplication through reinforcement learning\[[1](https://arxiv.org/html/2607.23009#bib.bib1)\]\. This is a striking example of machine learning autonomously uncovering complex sharing of intermediate results that would be difficult to design by hand\. It suggests that machine learning can enable more advanced and efficient sharing of computational resources\.

Most of the efficiency gains discussed thus far concern reusing intermediate results within a single problem\. However, if we broaden the scope to computing multiple problems simultaneously, could we share their computation processes and further improve efficiency? In fact, even for basic functions, simultaneous computation may be more efficient\. A standard example is simultaneously finding the maximum and minimum of a sequence\. Computing these independently requiresNNcomparisons each, for a total of2​N2Ncomparisons\. Interestingly, computing them together can be done with only1\.5​N1\.5Ncomparisons\[[2](https://arxiv.org/html/2607.23009#bib.bib2)\]\. This algorithm achieves this savings by performing0\.5​N0\.5Ncomparisons that contribute to both computations\. Such recycling of computational processes, which shares computation across multiple problems in this way, is considered to have a broader range of applications than the reuse of computation within a single problem\.

In more complex settings, it is difficult to discover nontrivial relationships between problems and design how their computation processes can be shared\. There is a reservoir computing\[[3](https://arxiv.org/html/2607.23009#bib.bib3),[4](https://arxiv.org/html/2607.23009#bib.bib4),[5](https://arxiv.org/html/2607.23009#bib.bib5)\]approach that exploit dynamics as a computational resource in a nontrivial way\. Reservoir computing uses a fixed dynamics called a “reservoir”, driven by inputs that exploits the resulting complex dynamics as high\-dimensional nonlinear features for computation\. A wide variety of dynamical systems can be used as computational resources, from physical phenomena\[[6](https://arxiv.org/html/2607.23009#bib.bib6)\]such as liquid\[[7](https://arxiv.org/html/2607.23009#bib.bib7),[8](https://arxiv.org/html/2607.23009#bib.bib8),[9](https://arxiv.org/html/2607.23009#bib.bib9)\], quantum\[[10](https://arxiv.org/html/2607.23009#bib.bib10),[11](https://arxiv.org/html/2607.23009#bib.bib11),[12](https://arxiv.org/html/2607.23009#bib.bib12),[13](https://arxiv.org/html/2607.23009#bib.bib13)\], and robotic systems\[[14](https://arxiv.org/html/2607.23009#bib.bib14),[15](https://arxiv.org/html/2607.23009#bib.bib15),[16](https://arxiv.org/html/2607.23009#bib.bib16),[17](https://arxiv.org/html/2607.23009#bib.bib17),[18](https://arxiv.org/html/2607.23009#bib.bib18),[19](https://arxiv.org/html/2607.23009#bib.bib19)\]to discrete dynamical systems such as cellular automata\[[20](https://arxiv.org/html/2607.23009#bib.bib20),[21](https://arxiv.org/html/2607.23009#bib.bib21),[22](https://arxiv.org/html/2607.23009#bib.bib22),[23](https://arxiv.org/html/2607.23009#bib.bib23),[24](https://arxiv.org/html/2607.23009#bib.bib24),[25](https://arxiv.org/html/2607.23009#bib.bib25)\]\. These systems merely follow their inherent physical laws or rules, yet their evolution can be viewed as a nonlinear mapping of inputs into a high\-dimensional feature space and leveraged for other computational purposes\. In other words, nontrivial relationships between the dynamics and the target computation are discovered and exploited through training of the output layer\. Cellular automata also have a computational model aspect; one\-dimensional cellular automata are known to be Turing complete\[[26](https://arxiv.org/html/2607.23009#bib.bib26)\]\. This suggests that the computation process itself can be multiplexed and repurposed for other objectives\.

In this study, we explore the idea of recycling computational processes through reservoir computing in the context of combinatorial optimization algorithms\. The field of combinatorial optimization has been deeply studied alongside computational theory, and it provides guidance for analyzing shared computation processes\. As a new approach to reservoir computing, we propose a method that uses the DP process for solving one combinatorial optimization problem as a reservoir to solve another combinatorial optimization problem with the same input\. DP is a key algorithm design technique for optimization problems, and it explicitly stores intermediate values in a table for recycle\. Therefore, we can define the computation process as the DP table and design the reservoir accordingly\. The proposed method computes a combinatorial optimization problem used for the reservoir \(Problem A\) and a target combinatorial optimization problem \(Problem B\) simultaneously: Problem A is solved by DP, and Problem B is solved by recycling the DP table for Problem A as features in linear regression\.

We conducted numerical experiments using the traveling salesman problem \(TSP\) and subset sum problem \(SSP\), another representative combinatorial optimization problem, to evaluate the effectiveness of the approach\. As a result, we achieved higher accuracy in approximating those problems than with generic linear regression features and basic heuristics by multiplexing the dynamic programming computation process, and we reduced computation time compared with solving the problems independently\.

As Moore’s law slows and the problems addressed in mathematical optimization continue to grow in scale, the finiteness of computational resources is again coming to the forefront\. In current computing practice, each time a problem is solved, a separate process is launched; once the computation ends, its process is discarded, and no sharing or recycle occurs\. Our approach suggests a different computational paradigm, in which multiple computational processes organically share and recycle intermediate results and states to make more efficient use of computational resources\.

## 2Results

### 2\.1Proposed framework

The method proposed in this study uses DP to solve a combinatorial optimization problem as a reservoir and restricts the trainable output layer to linear regression\. Figure[1](https://arxiv.org/html/2607.23009#S2.F1)shows conceptual comparison between the conventional and proposed frameworks\.

Figure 1:Conceptual comparison between the conventional and proposed frameworks\.a, In the conventional framework, Problem A and Problem B are each solved independently by a dedicated algorithm for the same input𝐮\\mathbf\{u\}\.b, In the proposed framework, Problem A is solved by DP, and the resulting tabledp1​\(𝐮\),…,dpM​\(𝐮\)\\mathrm\{dp\}\_\{1\}\(\\mathbf\{u\}\),\\dots,\\mathrm\{dp\}\_\{M\}\(\\mathbf\{u\}\)is recycled as a reservoir: its entries serve as input features to a linear regression readout that approximates the solution of Problem B, eliminating the need to run a separate algorithm for Problem B\.##### Problem setting

Let the input vector be𝐮=\(u1,…,uD\)∈ℝD\\mathbf\{u\}=\(u\_\{1\},\\dots,u\_\{D\}\)\\in\\mathbb\{R\}^\{D\}, whereDDis the dimension of the input\. We aim to solve multiple combinatorial optimization problems A, B, C, … for the same input simultaneously\. Conventionally, separate algorithms are designed for each problem and are solved independently\. In the proposed method, Problem A is solved by DP, and the other problems recycle the DP table, which records computation process for solving Problem A—as features to approximate the solutions by linear regression\. This eliminates the need to run individual algorithms for problems B, C, … and replaces them with a lightweight linear transformation\.

Suppose that running the DP for Problem A yields a table of sizeMM\. As each table element is a function of the input𝐮\\mathbf\{u\}, we write

𝐃𝐏​\(𝐮\)=\(dp1​\(𝐮\),…,dpM​\(𝐮\)\)⊤∈ℝM\.\\mathbf\{DP\}\(\\mathbf\{u\}\)=\(\\mathrm\{dp\}\_\{1\}\(\\mathbf\{u\}\),\\dots,\\mathrm\{dp\}\_\{M\}\(\\mathbf\{u\}\)\)^\{\\top\}\\in\\mathbb\{R\}^\{M\}\.

##### Linear readout

In this method,𝐃𝐏​\(𝐮\)\\mathbf\{DP\}\(\\mathbf\{u\}\)is shared as the feature vector for linear regression to solve another Problem B\. Let the bias term beb∈ℝb\\in\\mathbb\{R\}, and define the weight vector as𝐖=\(w1,…,wM,b\)⊤∈ℝM\+1\\mathbf\{W\}=\(w\_\{1\},\\dots,w\_\{M\},b\)^\{\\top\}\\in\\mathbb\{R\}^\{M\+1\}\. We also define the augmented feature vector by appending a constant 1,ϕ​\(𝐮\)=\(dp1​\(𝐮\),…,dpM​\(𝐮\),1\)⊤∈ℝM\+1\\boldsymbol\{\\phi\}\(\\mathbf\{u\}\)=\(\\mathrm\{dp\}\_\{1\}\(\\mathbf\{u\}\),\\dots,\\mathrm\{dp\}\_\{M\}\(\\mathbf\{u\}\),1\)^\{\\top\}\\in\\mathbb\{R\}^\{M\+1\}\. The model outputy^\\hat\{y\}is computed by the following linear combination:

y^=𝐖⊤​ϕ​\(𝐮\)=∑j=1Mwj​dpj​\(𝐮\)\+b\.\\hat\{y\}=\\mathbf\{W\}^\{\\top\}\\boldsymbol\{\\phi\}\(\\mathbf\{u\}\)=\\sum\_\{j=1\}^\{M\}w\_\{j\}\\mathrm\{dp\}\_\{j\}\(\\mathbf\{u\}\)\+b\.Here𝐃𝐏​\(𝐮\)\\mathbf\{DP\}\(\\mathbf\{u\}\)is a function determined by the DP algorithm for solving Problem A and is fixed, rather than learned for Problem B\. The only learnable parameters are the weights𝐖\\mathbf\{W\}\.

##### Training

Training is performed in a supervised manner\. Given training data consisting ofTtrainT\_\{\\mathrm\{train\}\}input\-target pairs\(𝐮\(t\)∈ℝD,y\(t\)∈ℝ\)\(t=1,…,Ttrain\)\(\\mathbf\{u\}^\{\(t\)\}\\in\\mathbb\{R\}^\{D\},y^\{\(t\)\}\\in\\mathbb\{R\}\)\\quad\(t=1,\\dots,T\_\{\\mathrm\{train\}\}\), we learn the weights𝐖\\mathbf\{W\}so that the model outputy^\\hat\{y\}approximates the desired outputyy\. The error is minimized using least squares with L2 regularization \(ridge regression\):

𝐖=argmin𝐖​\(∑t=1Ttrain\(y\(t\)−y^\(t\)\)2\+λ​‖𝐖‖22\)\.\\mathbf\{W\}=\\underset\{\\mathbf\{W\}\}\{\\mathrm\{argmin\}\}\\left\(\\sum\_\{t=1\}^\{T\_\{\\mathrm\{train\}\}\}\(y^\{\(t\)\}\-\\hat\{y\}^\{\(t\)\}\)^\{2\}\+\\lambda\\\|\\mathbf\{W\}\\\|^\{2\}\_\{2\}\\right\)\.Hereλ\>0\\lambda\>0is the regularization parameter\.

##### Solution construction

The proposed method is a model that approximates a real\-valued function of the input\. However, in optimization problems, in addition to estimating the optimal value of the objective function, one must construct decision variables that achieve that optimum \(e\.g\., subsets or permutations in combinatorial optimization\)\. In this study, to construct solutions for combinatorial optimization problems using a real\-valued function\-approximation model, we adopt a DP\-based framework\. Specifically, we formulate the target problem as a DP and approximate the value function defined by the DP function with the learning model\. Using the approximate values as guidance, we construct the solution sequentially\.

In other words, solution construction can be reduced to multiple function\-approximation problems\. If the target problem can be reduced toLLfunctionsg1​\(𝐮\),…,gL​\(𝐮\)g\_\{1\}\(\\mathbf\{u\}\),\\dots,g\_\{L\}\(\\mathbf\{u\}\), then eachgℓg\_\{\\ell\}is learned independently, and at the timing required for solution construction, its estimate is produced to construct the solution\.

### 2\.2Experimental setting

The main purpose of this experiment is to examine how well a different problem can be solved by recycling, as features for linear regression, the DP computation process that solves a certain combinatorial optimization problem\. Followiing this objective, we conducted numerical experiments on the TSP and the SSP\. Both are fundamental problems in combinatorial optimization and have been studied extensively because of their broad applications\[[27](https://arxiv.org/html/2607.23009#bib.bib27),[28](https://arxiv.org/html/2607.23009#bib.bib28)\]\. Moreover, since exact algorithms faster than brute\-force search based on DP are known, these problems are suitable for the experimental setting in this study\.

#### 2\.2\.1Traveling salesman problem

In the TSP, given a set of cities and travel costs between every pair of cities, the task is to find a tour that visits every city exactly once and returns to the starting city, with the minimum total travel cost\. The most naive algorithm enumerates all visit orders and requiresO​\(n\!\)O\(n\!\)time\. The TSP is NP\-hard, and it is believed that no polynomial\-time algorithm exists for finding an exact solution\. The well\-known exact algorithm for the TSP is DP, which runs inO​\(2n​n2\)O\(2^\{n\}n^\{2\}\)time\. In addition, we also consider the problem of finding, among all tours that visit each city exactly once, the tour with the maximum travel cost\. This problem is also NP\-hard and can also be solved by DP\. We call the problem of finding the maximum\-cost tour MAXTSP, and the minimum\-cost tour MINTSP\.

##### Task setting

The input isnncities on the two\-dimensional plane\[0,1\)×\[0,1\)\[0,1\)\\times\[0,1\),𝐮=\(x1,y1,…,xn,yn\)∈\[0,1\)2​n\\mathbf\{u\}=\(x\_\{1\},y\_\{1\},\\ldots,x\_\{n\},y\_\{n\}\)\\in\[0,1\)^\{2n\}, and we use the Euclidean distanced​\(i,j\)=\(xi−xj\)2\+\(yi−yj\)2d\(i,j\)=\\sqrt\{\(x\_\{i\}\-x\_\{j\}\)^\{2\}\+\(y\_\{i\}\-y\_\{j\}\)^\{2\}\}as the travel cost between two cities\. For this input, we aim to solve both MAXTSP and MINTSP simultaneously\. Specifically, we solve the DP for MAXTSP and use it as a computational resource to approximate MINTSP with the proposed method\. While, in principle, both would be solved independently by DP, in this study, we run DP only for MAXTSP \(Problem A\) and approximate MINTSP \(Problem B\) by linear regression to improve efficiency\.

##### DP of MAXTSP as a reservoir

Without loss of generality, we start the tour from city11\. LetS∈2VS\\in 2^\{V\}be a subset of the city setV=\{1,2,…,n\}V=\\\{1,2,\\ldots,n\\\}that contains city11, and letv∈Sv\\in S\. We define a state as the pair\(S,v\)\(S,v\)\. Letmaxtsp\(S,v\)​\(𝐮\)∈ℝ\\mathrm\{maxtsp\}\_\{\(S,v\)\}\(\\mathbf\{u\}\)\\in\\mathbb\{R\}be the maximum path length when starting from city11, having visited the setSSand currently being at cityvv\. The optimal value of MAXTSP ismaxtsp\(V,1\)​\(𝐮\)\\mathrm\{maxtsp\}\_\{\(V,1\)\}\(\\mathbf\{u\}\)\. The recurrence ismaxtsp\(S,v\)​\(𝐮\)=maxw∈S,w≠v⁡d​\(w,v\)\+maxtsp\(S∖\{v\},w\)​\(𝐮\)\\mathrm\{maxtsp\}\_\{\(S,v\)\}\(\\mathbf\{u\}\)=\\max\_\{w\\in S,\\ w\\neq v\}d\(w,v\)\+\\mathrm\{maxtsp\}\_\{\(S\\setminus\\\{v\\\},w\)\}\(\\mathbf\{u\}\)\. We use theO​\(2n​n\)O\(2^\{n\}n\)dimensional tablemaxtsp\(S,v\)​\(𝐮\)\\mathrm\{maxtsp\}\_\{\(S,v\)\}\(\\mathbf\{u\}\)as features for linear regression\.

##### Data generation

The input is generated by sampling each city coordinate\(xi,yi\)∈\[0,1\)×\[0,1\)\(x\_\{i\},y\_\{i\}\)\\in\[0,1\)\\times\[0,1\)independently from the uniform distribution\. Since the input is originally a set ofnnpoints, we sort the points in lexicographic order≺\\prec\(first byxx, and then byyyifxxis equal\) to make the representation unique\. Thus,\(x1,y1\)≺\(x2,y2\)≺⋯≺\(xn,yn\)\(x\_\{1\},y\_\{1\}\)\\prec\(x\_\{2\},y\_\{2\}\)\\prec\\cdots\\prec\(x\_\{n\},y\_\{n\}\)holds\. Among the generated instances,TtrainT\_\{\\mathrm\{train\}\}are used for training andTevalT\_\{\\mathrm\{eval\}\}for evaluation\.

In the experiments, we perform two tasks: \(i\) prediction of the optimal value of MINTSP and \(ii\) construction of a tour\.

##### \(i\) Prediction of the optimal value

The objective function is the optimal value of MINTSP\. Evaluation is performed by the mean absolute percentage error \(MAPE\) between the predicted and true values on the evaluation data\. We setn=10,λ=0\.01,Ttrain=105,n=10,\\lambda=0\.01,\\;T\_\{\\mathrm\{train\}\}=10^\{5\},andTeval=104T\_\{\\mathrm\{eval\}\}=10^\{4\}\. In this experiment, we use the DP table for MAXTSP as features for linear regression to predict the optimal value of MINTSP\. To compare the feature performance, we also evaluate linear regression with generic features as baselines: linear regression on the raw input \(INPUT\), extreme learning machine \(ELM\)\[[29](https://arxiv.org/html/2607.23009#bib.bib29)\], and next generation reservoir computing \(NG\-RC\)\[[30](https://arxiv.org/html/2607.23009#bib.bib30)\], the last of which we examine in two variants, NG\-RC\-INPUT and NG\-RC\-DIST\. In addition, we compare the model with three further methods that use features specifically related to MINTSP:N​A\\sqrt\{NA\}\[[31](https://arxiv.org/html/2607.23009#bib.bib31)\],stdRT\\mathrm\{std\_\{RT\}\}\[[32](https://arxiv.org/html/2607.23009#bib.bib32)\], and minimum\-weight matching \(MATCHING\)\. Details of all comparison methods are given in Methods\.

##### \(ii\) Solution construction

Beyond predicting the optimal value, we also construct a tour \(solution\)\. We evaluate the average percentage by which the tour length produced by the model exceeds the optimal solution over all evaluation data\. We setn=14,λ=0\.01,Ttrain=5×105n=14,\\lambda=0\.01,\\;T\_\{\\mathrm\{train\}\}=5\\times 10^\{5\}, andTeval=104T\_\{\\mathrm\{eval\}\}=10^\{4\}\.

To reduce the computation time in this experiment, we performed feature selection during training and used only 2,000 features instead of the full MAXTSP table with size 53,500 features\. For feature selection, we used recursive feature elimination\[[33](https://arxiv.org/html/2607.23009#bib.bib33)\]and reduced the number of features by10%10\\%at each step\. We provide detail analysis of feature selection in Appendix\.

In this experiment, the model outputs an approximate solution given an input\. To assess solution quality, we compare the model with three representative TSP approximation algorithms: nearest neighbor \(NN\), Christofides algorithm \(CHRIS\)\[[34](https://arxiv.org/html/2607.23009#bib.bib34)\], and farthest insertion \(INSERT\); details are given in Methods\.

##### Out\-of\-distribution evaluation \(TSPLIB\)

To examine generalization performance outside the training data distribution, we also performed evaluations on instances from TSPLIB\[[35](https://arxiv.org/html/2607.23009#bib.bib35)\], which is a standard benchmark for TSP\. This dataset is constructed from real cities\. We performed the evaluation on burma14, the smallest TSPLIB instance with 14 cities\.

#### 2\.2\.2Subset sum problem

The SSP involves, given a set of numbersSSand a target valuenn, finding a subset ofSSwhose sum equalsnn\. In this study, we distinguish the following three tasks:

- •DECSSPn: Decide whether thereexistsa subset whose sum equalsnn\.
- •MAXSSPn: If such a subset exists, find themaximumnumber of elements among those subsets\.
- •MINSSPn: If such a subset exists, find theminimumnumber of elements among those subsets\.

DECSSP is easier than MAXSSP and MINSSP because it requires only an existence check\. For example, forS=\(2,5,8,4,2\)S=\(2,5,8,4,2\)andn=13n=13, a subset summing to1313exists; the one with the maximum number of elements is\(2,5,4,2\)\(2,5,4,2\), and the one with the minimum number of elements is\(5,8\)\(5,8\)\. Therefore MAXSSP\(S\)13\{\}\_\{13\}\(S\)is44and MINSSP\(S\)13\{\}\_\{13\}\(S\)is22\. On the other hand, whenn=18n=18, no such subset exists\. SSP is NP\-hard, and a pseudo\-polynomial\-time DP algorithm is known to be an exact method that is faster than brute\-force search\.

##### Task setting

The input is𝐮=\(u1,…,uD\)∈\{1,…,U\}D\\mathbf\{u\}=\(u\_\{1\},\\ldots,u\_\{D\}\)\\in\\\{1,\\ldots,U\\\}^\{D\}, whereUUis the maximum input value andDDis the input dimension\. For this input, we aim to solve MAXSSP and MINSSP simultaneously\. Rather than solving them independently, we first solve the simpler common subproblem DECSSP by DP and use its table as a computational resource to solve MINSSP and MAXSSP with the proposed method\. Compared with computing each independently, this approach shares the computation process of the common DECSSP subproblem and improves efficiency\.

##### DP of DECSSP as a reservoir

Letdecsspi,j​\(𝐮\)\\mathrm\{decssp\}\_\{i,j\}\(\\mathbf\{u\}\)denote whether there exists a subset of\(u1,u2,⋯,ui\)\(u\_\{1\},u\_\{2\},\\cdots,u\_\{i\}\)whose sum isjj\. We fill the table in increasing order ofiiandjjfor1≤i≤D1\\leq i\\leq Dand0≤j≤U​D0\\leq j\\leq UDusing the following recurrence:decsspi,j​\(𝐮\)=decsspi−1,j​\(𝐮\)∨decsspi−1,j−ui​\(𝐮\)\\mathrm\{decssp\}\_\{i,j\}\(\\mathbf\{u\}\)=\\mathrm\{decssp\}\_\{i\-1,j\}\(\\mathbf\{u\}\)\\lor\\mathrm\{decssp\}\_\{i\-1,j\-u\_\{i\}\}\(\\mathbf\{u\}\)\. This recurrence considers two cases depending on whether theii\-th element is used: if we excludeuiu\_\{i\}, we reduce todecsspi−1,j​\(𝐮\)\\mathrm\{decssp\}\_\{i\-1,j\}\(\\mathbf\{u\}\); if we include it, we reduce todecsspi−1,j−ui​\(𝐮\)\\mathrm\{decssp\}\_\{i\-1,j\-u\_\{i\}\}\(\\mathbf\{u\}\)\. We use thisU​D2UD^\{2\}\-sized tabledecsspi,j​\(𝐮\)\\mathrm\{decssp\}\_\{i,j\}\(\\mathbf\{u\}\)as features for linear regression\.

##### Data generation

We generateDDintegers independently and uniformly at random between11andUU, and sort the values in descending order to form one instance\. Thusu1≥u2≥⋯≥uDu\_\{1\}\\geq u\_\{2\}\\geq\\cdots\\geq u\_\{D\}holds\. Among the generated instances,TtrainT\_\{\\mathrm\{train\}\}are used for training andTevalT\_\{\\mathrm\{eval\}\}for evaluation\.

We again conduct two experiments: \(i\) prediction of the optimal value and \(ii\) solution construction\.

##### \(i\) Optimal value prediction

The objective is the number of elements of MAXSSPnand MINSSPnwhen the sumnnis specified between11andU​DUD\. For evaluation, we round the model output to an integer and compute the accuracy—that is, whether it matches the integer answer\. We report Cohen’s Kappa normalized to\[0,1\]\[0,1\], where0corresponds to the most naive model that always outputs the single value with the highest frequency in the training data\. Herepep\_\{e\}is the accuracy of that naive model\.Kappa:=1−1−accuracy1−pe\\mathrm\{Kappa\}:=1\-\\frac\{1\-\\mathrm\{accuracy\}\}\{1\-p\_\{e\}\}\. In this experiment, when predicting MAXSSPnand MINSSPn, we first predict whether a subset summing tonnexists; if we predict it exists, we then predict the number of elements\. We setU=10,D=10,λ=0\.01U=10,D=10,\\lambda=0\.01, andTeval=2,000T\_\{\\mathrm\{eval\}\}=2,000, withTtrainT\_\{\\mathrm\{train\}\}set to1010times the number of features for each method, and vary the remaining three parameters\. To compare the DP table of DECSSP as features, we also use the generic features INPUT, ELM, and NG\-RC as baselines, as in the TSP experiments\.

##### \(ii\) Solution construction

We also construct solutions rather than merely predicting optimal values\. Evaluation is the accuracy of correctly constructing a subset with the maximum \(minimum\) number of elements\. We perform experiments for allnnbetween11andU​DUD\. We set the same parameters as \(i\)\. In this experiment, we compare the computation time with the case where MAXSSP and MINSSP are solved independently by DP\. In the proposed method, we first construct the DP table for solving DECSSP and then use this DP table as features to construct solutions for MAXSSP and MINSSP\.

### 2\.3Experimental results

#### 2\.3\.1Traveling salesman problem

Figure 2:The performances of MINTSP optimal value prediction and examples of solutions\.a, the mean absolute percentage error \(MAPE\) of the predicted MINTSP optimal value as a function of the number of features, for the proposed method \(MAXTSP\) and baseline features \(INPUT, ELM,N​A\\sqrt\{NA\},stdRT\\mathrm\{std\_\{RT\}\}, NG\-RC\-INPUT, NG\-RC\-DIST, MATCHING\)\.b–e, Examples, for the same instance, of the solutions computed by each method for use in optimal value prediction\.b, The target MINTSP tour\.c, The MAXTSP tour computed by the DP used as the reservoir in the proposed method\.d, The convex hull used to compute theN​A\\sqrt\{NA\}feature\.e, The minimum\-weight matching computed by DP for the MATCHING baseline\.##### \(i\) Optimal value prediction

The results of the optimal value prediction experiment are shown in Fig\.[2](https://arxiv.org/html/2607.23009#S2.F2)\. A larger number of features \(i\.e\., further to the right in the plot\) corresponds to higher expressive power and better performance\. Indeed, for ELM and NG\-RC, increasing the number of features reduces the error\. The proposed method using the MAXTSP DP table as features achieves an average error of 1\.61%, which is the highest performance in other methods\. In particular, reaching similar performance with NG\-RC\-DIST, which we consider the most suitable baseline for approximating TSP, requires approximately 10 times more features, indicating that the MAXTSP table contains many features that are useful for approximating MINTSP\. Looking at MATCHING, where a different algorithm is used as the reservoir, the error is lower than NG\-RC\-INPUT and ELM at a comparable feature count, but it is still worse than MAXTSP\. This suggests that for approximating MINTSP, the DP for MAXTSP carries information processing more closely aligned than the DP for MATCHING\.

Table 1:Results of constructing approximate MINTSP tours\.For each method, the average percentage by which the constructed tour is longer than the optimal solution \(Gap\) and the average time required to construct the solution \(Time\) are reported per test instance\.
##### \(ii\) Solution construction

The results of tour construction are shown in Table[1](https://arxiv.org/html/2607.23009#S2.T1)\. For the evaluation data, we report the average percentage by which each method’s constructed tour is longer than the optimal solution and the average computation time per instance\. The proposed MAXTSP method achieved the best performance among the compared approximation algorithms, with an error of 1\.03%\. It was also about nine times faster than independently computing MINTSP by DP\. An important point is that the compared algorithms are designed to solve MINTSP, whereas in the proposed method, the features come from a DP designed for MAXTSP, and only the linear regression component is designed for MINTSP\. This indicates that the DP designed for MAXTSP contains enough information processing capacity to yield approximations that outperform heuristic algorithms dedicated to MINTSP\.

Figure 3:Results for the burma14 instance\.Tours constructed for the TSPLIB instance burma14 by the proposed method \(a, MAXTSP\) and the baseline heuristics \(b, INSERT;c, CHRIS;d, NN\), with the percentage gap from the optimal tour length shown above each panel\.Fig[3](https://arxiv.org/html/2607.23009#S2.F3)shows the actual tours constructed by each method for the TSPLIB instance burma14\. The proposed MAXTSP achieved zero error and constructed the optimal solution\. This indicates that the model trained on synthetic data generalizes well to out\-of\-distribution real data\.

#### 2\.3\.2Subset sum problem

Figure 4:The performances of SSP optimal value prediction\.a,b, Kappa of the predicted optimal value fora, MAXSSP andb, MINSSP on the evaluation data, as a function of the number of features, for the proposed method using the DECSSP DP table \(DECSSP\) and baseline features \(INPUT, ELM, NG\-RC\)\.Table 2:Results of SSP solution construction\.For each component of the conventional approach \(independent DP for MAXSSP and MINSSP\) and the proposed approach \(a shared DP for DECSSP followed by readout layers for MAXSSP and MINSSP\), the accuracy of the constructed solution and the average time required per instance are reported; DP for DECSSP alone does not yield a solution and therefore has no associated accuracy\. The rightmost Accuracy and Time columns report, respectively, the accuracy averaged over the solved tasks and the total time summed over all components, giving the overall cost of obtaining both the MAXSSP and MINSSP solutions\.ComponentAccuracyTimeAccuracyTimeConventionalDP for MAXSSP1000\.2951000\.579DP for MINSSP1000\.284ProposedDP for DECSSP0\.02695\.70\.065Readout for MAXSSP91\.80\.019Readout for MINSSP99\.50\.021##### \(i\) Optimal value prediction

The results of the optimal value prediction experiment are shown in Fig\.[4](https://arxiv.org/html/2607.23009#S2.F4)\. While more features generally imply higher expressive power and better performance, ELM and NG\-RC indeed improved in accuracy as the number of features increases\. The proposed method using the DECSSP DP table as features achieved the best Kappa for both the MAXSSP and MINSSP tasks, showing excellent performance per feature count\. For both tasks, it outperformed generic\-feature baselines even when those used more than 10 times as many features\. This indicates that the DECSSP DP table is a good feature set for both MAXSSP and MINSSP\. We provide the results of how performance changed when the parameter U and D were varied in Appendix\.

##### \(ii\) Solution construction

The results of solution construction are shown in Table 2\. The proposed method correctly constructed solutions with an accuracy of 91\.8% for MAXSSP and an accuracy of 99\.5% for MINSSP\. In the conventional approach, MAXSSP and MINSSP are solved independently by DP\. In the proposed method, we compute the lighter DP for DECSSP and share its table as linear regression features for MAXSSP and MINSSP\. Thus the computations required to solve the two tasks are the DP for DECSSP and the output layers for MAXSSP and MINSSP\. Since each of these three computations is lightweight, we can obtain approximate solutions faster than the conventional exact DP approach\. We provide the detail results of the solution construction in Appendix\.

## 3Discussion

Inspired by reservoir computing, this study proposed a method that treats algorithms as more general computational resources and recycles computation processes in combinatorial optimization problems in a multiplexed manner\. To verify its effectiveness, we conducted experiments on the TSP and the SSP\. For the TSP, we showed that the DP process for one problem \(MAXTSP\) provides features that are useful for solving a different problem \(MINTSP\), even though the two objectives are, superficially, opposites of each other\. For the SSP, we showed that sharing the computation process of a simpler common subproblem \(DECSSP\) makes it possible to solve two related problems \(MAXSSP and MINSSP\) at a substantially lower additional cost than solving each of them independently\. Together, these results indicate that the DP table computed for one problem is not merely a byproduct of solving that problem but a reusable computational resource that can be repurposed, through a lightweight linear readout, to solve other problems that share the same input\.

Within the same framework, the proposed method can be extended in two directions\. First, the reservoir is not restricted to DP: any algorithm that exposes an intermediate computation process, such as a table, a set of internal variables, or a sequence of states, can in principle serve as the reservoir\. Second, the readout is not restricted to linear regression: replacing it with a more expressive output model, such as a nonlinear or hierarchical readout, may make it possible to recycle computational resources whose relation to the target problem is more complex than what a linear map can capture\.

##### Relation to machine learning for combinatorial optimization

Solving combinatorial optimization problems with machine learning has already been studied extensively\[[36](https://arxiv.org/html/2607.23009#bib.bib36)\]\. Such approaches offer several advantages beyond simply improving performance: a single trained model can be applied to a variety of problems, and learning can automatically capture the distribution of instances and problem\-specific characteristics that would be difficult to build into a hand\-designed algorithm\. However, this line of work is, almost without exception, aimed at improving the performance of the solution algorithm for an individual problem considered in isolation\. The present study takes a different stance: rather than designing an independent solution algorithm for each problem, we aim to share computational processes across multiple problems solved for a common input\. In other words, our focus is on how much additional information can be extracted from an existing algorithm’s computation, and at how little additional cost, rather than on how much a single algorithm’s own performance can be improved\.

For this reason, our approach is complementary to, rather than competing with, research on improving individual algorithms: whenever a new, higher\-performing algorithm for some problem is developed, our framework offers a way to ask how much additional information about*other*problems can be extracted from that algorithm’s computation process\. This is also why, throughout our experiments, we compared the proposed method against baselines that solve each problem independently or that use generic features, rather than against the best\-known specialized algorithm for each target problem; our aim was to evaluate the value of recycled computation, not to outperform the state of the art on any single problem\.

##### Engineering and scientific implications

On completion, this line of research is expected to yield, from an engineering standpoint, a technique for obtaining information about several related problems from a single optimization computation at low additional cost, providing a basis for accelerating computation through the sharing of computational processes\. Of course, the proposed method does not work well for an arbitrary combination of algorithm and problem: because the readout is kept lightweight, most of the computation needed to solve the target problem must be carried by the computational process of the original algorithm, so the algorithm and the target problem must be substantively related\. This raises the question of which combinations of algorithm and problem allow the method to succeed\.

Addressing this question, from a scientific standpoint, this line of research is expected to lay the foundation for a new framework that treats the relationship between a problem and an algorithm as an object of study in its own right, potentially leading to the discovery of nontrivial relationships between problems that are not apparent from their definitions alone, such as the relationship we observed between MAXTSP and MINTSP\.

More broadly, the pursuit of extensive sharing of computational processes suggests a computational paradigm distinct from current practice, in which a separate process is launched each time a problem is solved and is discarded once the computation ends, with no sharing or recycle across processes\. Instead, our results point toward a mode of computation in which multiple computational processes organically share and recycle intermediate results and states, analogous to how the biological brain flexibly repurposes shared neural resources across different cognitive tasks, thereby making more efficient use of computational resources\.

## Methods

The execution environment consisted of Intel Xeon Gold 6230 CPU for TSP and Intel Xeon w3\-2535 CPU with an NVIDIA RTX 2000 Ada Generation GPU for SSP\.

### Comparison methods

Here we describe in detail the baseline and comparison methods used in the experiments\.

##### Generic regression features

For the optimal value prediction experiment, we compare the proposed DP features against the following generic features\.

- •Linear regression on the raw input \(INPUT\):Use𝐮=\(u1,…,uD\)\\mathbf\{u\}=\(u\_\{1\},\\ldots,u\_\{D\}\)as features\. The number of features isDD\.
- •Extreme learning machine \(ELM\)\[[29](https://arxiv.org/html/2607.23009#bib.bib29)\]:A single\-hidden\-layer feedforward neural network where only the output layer is trained and the other parameters are randomly initialized\. It can be regarded as linear regression on random nonlinear features\. The number of featuresMMcan be set freely, and, in general, a largerMMyields higher expressive power\[[37](https://arxiv.org/html/2607.23009#bib.bib37)\]\.
- •Next generation reservoir computing \(NG\-RC\)\[[30](https://arxiv.org/html/2607.23009#bib.bib30)\]:Multivariate polynomial regression that uses all terms up to the degreeppof the input variables as features\. We examine two variants: polynomials of the input variables \(NG\-RC\-INPUT\) and polynomials of the distance matrix between cities \(NG\-RC\-DIST\)\. The number of features is\(D\+pp\)\\binom\{D\+p\}\{p\}whereDDis the number of variables, and the maximum degreeppcan be chosen freely\. Largerppyields higher expressive power\.

##### TSP\-specific comparison features

In addition, we compare the model with the following three methods as features related to MINTSP\.

- •𝐍𝐀\\mathbf\{\\sqrt\{NA\}\}: A classical and well\-known method to approximate the optimal value of MINTSP by linear regression\. LetNNbe the number of vertices andAAthe area of the convex hull of the point set, and useN​A\\sqrt\{NA\}as the feature\[[31](https://arxiv.org/html/2607.23009#bib.bib31)\]\. The number of features is one\.
- •𝐬𝐭𝐝𝐑𝐓\\mathbf\{std\_\{RT\}\}: To predicting the MINTSP optimal value in settings not limited to the Euclidean plane, a method was proposed that uses the standard deviation of random tour lengths as a feature\[[32](https://arxiv.org/html/2607.23009#bib.bib32)\]\. Theoretically, this value is linearly dependent onN​A\\sqrt\{NA\}under certain conditions\. In this experiment, we use two features: the standard deviationstdRT\\mathrm\{std\_\{RT\}\}and the meanmeanRT\\mathrm\{mean\_\{RT\}\}of random tour lengths\.
- •Minimum\-weight matching \(MATCHING\):Whennnis even, consider formingn/2n/2pairs of points without using any vertex twice, minimizing the sum of distances within each pair\. We solve this problem by DP and use its table as features\. This is a variant of the proposed method, intended to examine the case where the DP solves a problem other than MAXTSP\.

##### TSP approximation algorithms

For the solution construction experiment, we compare the model with the following representative TSP approximation algorithms\.

- •Nearest neighbor \(NN\):A greedy method that repeatedly visits the nearest vertex\. The time complexity isO​\(N2\)\\mathrm\{O\}\(N^\{2\}\)\.
- •Christofides algorithm \(CHRIS\):An algorithm with a 1\.5\-approximation guarantee when distances satisfy the triangle inequality\. It had the best known guarantee until 2021\[[34](https://arxiv.org/html/2607.23009#bib.bib34)\]\. The time complexity isO​\(N3\)\\mathrm\{O\}\(N^\{3\}\)\.
- •Farthest insertion \(INSERT\):An algorithm that starts with the tour of the two farthest vertices and inserts the farthest remaining vertex into the best position in the tour\. The time complexity isO​\(N2\)\\mathrm\{O\}\(N^\{2\}\)\.

### Training details of SSP

In the SSP experiments, the objective function MAXSSPntakes values in\{1,…,D,false\}\\\{1,\\ldots,D,\\mathrm\{false\}\\\}\. If no subset with sumnncan be formed, the value isfalse\\mathrm\{false\}; otherwise, it is the maximum subset size in\{1,…,D\}\\\{1,\\ldots,D\\\}\. To learn these two types of values,false\\mathrm\{false\}and size, by linear regression, we train two types of weights and predict the value of MAXSSPn\. The first weight learns whether the output isfalse\\mathrm\{false\}, and the second weight learns the size using only training data whose labels are notfalse\\mathrm\{false\}\. At prediction time, we first use the first weight to predict whether the output isfalse\\mathrm\{false\}\. If it is predicted not to befalse\\mathrm\{false\}, we then use the second weight to predict the size\. The prediction of MINSSPnis performed in the same way\.

### Solution construction

We describe in detail what the model learns in each experiment and how it constructs a solution\.

##### Solution construction for MINTSP

The objective function learned by the model isg\(n,v\)​\(𝐮\)g\_\{\(n,v\)\}\(\\mathbf\{u\}\), which is the minimum length of a path that starts from vertex11in annn\-vertex input𝐮\\mathbf\{u\}, visits every vertex exactly once, and ends at vertexvv\. To approximate this function, the model uses the DP table for solving MAXTSP as features\. Letℐ=\{\(S,v\)∣S∈2V,1∈S,v∈S\}\\mathcal\{I\}=\\\{\(S,v\)\\mid S\\in 2^\{V\},\\ 1\\in S,\\ v\\in S\\\}be the set of valid states; that is,SSranges over the2n−12^\{n\-1\}subsets ofVVthat contain city11, and for each suchSS,vvranges over its\|S\|\|S\|elements\. Fixing an arbitrary enumeration\(S1,v1\),\(S2,v2\),…,\(S\|ℐ\|,v\|ℐ\|\)\(S\_\{1\},v\_\{1\}\),\(S\_\{2\},v\_\{2\}\),\\ldots,\(S\_\{\|\\mathcal\{I\}\|\},v\_\{\|\\mathcal\{I\}\|\}\)ofℐ\\mathcal\{I\}, we define the vector𝐌𝐀𝐗𝐓𝐒𝐏​\(𝐮\):=\(maxtsp\(S1,v1\)​\(𝐮\),maxtsp\(S2,v2\)​\(𝐮\),…,maxtsp\(S\|ℐ\|,v\|ℐ\|\)​\(𝐮\)\)∈ℝ\|ℐ\|\\mathbf\{MAXTSP\}\(\\mathbf\{u\}\):=\\big\(\\mathrm\{maxtsp\}\_\{\(S\_\{1\},v\_\{1\}\)\}\(\\mathbf\{u\}\),\\mathrm\{maxtsp\}\_\{\(S\_\{2\},v\_\{2\}\)\}\(\\mathbf\{u\}\),\\ldots,\\mathrm\{maxtsp\}\_\{\(S\_\{\|\\mathcal\{I\}\|\},v\_\{\|\\mathcal\{I\}\|\}\)\}\(\\mathbf\{u\}\)\\big\)\\in\\mathbb\{R\}^\{\|\\mathcal\{I\}\|\}\. Using this vector as features, the model learns the weight𝐖\(n,v\)\\mathbf\{W\}\_\{\(n,v\)\}and approximates𝐖\(n,v\)​𝐌𝐀𝐗𝐓𝐒𝐏​\(𝐮\)≈g\(n,v\)​\(𝐮\)\\mathbf\{W\}\_\{\(n,v\)\}\\mathbf\{MAXTSP\}\(\\mathbf\{u\}\)\\approx g\_\{\(n,v\)\}\(\\mathbf\{u\}\)\.

The algorithm for constructing a solution is greedy\. Starting from vertex11, it greedily determines the next vertex to visit in sequence\. Suppose that the set of already visited vertices isS∈2VS\\in 2^\{V\}and the current vertex isvv\. LetT=V∖ST=V\\setminus Sandk=\|T\|k=\|T\|\. For a subsetR=\{i1<i2<⋯<im\}⊆VR=\\\{i\_\{1\}<i\_\{2\}<\\cdots<i\_\{m\}\\\}\\subseteq V, with indices listed in increasing order, we also write𝐮​\[R\]=\(xi1,yi1,xi2,yi2,…,xim,yim\)\\mathbf\{u\}\[R\]=\(x\_\{i\_\{1\}\},y\_\{i\_\{1\}\},x\_\{i\_\{2\}\},y\_\{i\_\{2\}\},\\ldots,x\_\{i\_\{m\}\},y\_\{i\_\{m\}\}\)\. Since11is the smallest element ofVV, whenever1∈R1\\in Rit is always mapped to the first coordinate pair, sog\(m,⋅\)​\(𝐮​\[R\]\)g\_\{\(m,\\cdot\)\}\(\\mathbf\{u\}\[R\]\)is consistent with the convention that the path starts from vertex11\. The next vertex to visit is determined byarg​minw∈Td​\(v,w\)\+g\(k\+1,w\)​\(𝐮​\[T∪\{1\}\]\)\\mathop\{\\rm arg~min\}\\limits\_\{w\\in T\}d\(v,w\)\+g\_\{\(k\+1,w\)\}\(\\mathbf\{u\}\[T\\cup\\\{1\\\}\]\)\. This represents the length of the remaining path when vertexwwis visited next in the tour\. In practice,g\(k\+1,w\)​\(𝐮​\[T∪\{1\}\]\)g\_\{\(k\+1,w\)\}\(\\mathbf\{u\}\[T\\cup\\\{1\\\}\]\)is replaced by the value predicted by linear regression using𝐌𝐀𝐗𝐓𝐒𝐏​\(𝐮\)\\mathbf\{MAXTSP\}\(\\mathbf\{u\}\)as features\. Specifically, we use𝐖\(k\+1,w\)​𝐌𝐀𝐗𝐓𝐒𝐏​\(𝐮​\[T∪\{1\}\]\)\\mathbf\{W\}\_\{\(k\+1,w\)\}\\mathbf\{MAXTSP\}\(\\mathbf\{u\}\[T\\cup\\\{1\\\}\]\)in place ofg\(k\+1,w\)​\(𝐮​\[T∪\{1\}\]\)g\_\{\(k\+1,w\)\}\(\\mathbf\{u\}\[T\\cup\\\{1\\\}\]\)\. If these predictions are correct, the optimal solution is obtained\. The table𝐌𝐀𝐗𝐓𝐒𝐏​\(𝐮​\[T∪\{1\}\]\)\\mathbf\{MAXTSP\}\(\\mathbf\{u\}\[T\\cup\\\{1\\\}\]\)is a subset of𝐌𝐀𝐗𝐓𝐒𝐏​\(𝐮\)\\mathbf\{MAXTSP\}\(\\mathbf\{u\}\), and the corresponding portion is extracted from𝐌𝐀𝐗𝐓𝐒𝐏​\(𝐮\)\\mathbf\{MAXTSP\}\(\\mathbf\{u\}\)and used as features\.

##### Solution construction for SSP

In the solution construction experiment for MAXSSP, the model learns the objective functionmaxsspi,j​\(𝐮\)=MAXSSPj​\(𝐮​\[\{1,…,i\}\]\)∈\{1,…,i,false\}\\mathrm\{maxssp\}\_\{i,j\}\(\\mathbf\{u\}\)=\\mathrm\{MAXSSP\}\_\{j\}\(\\mathbf\{u\}\[\\\{1,\\ldots,i\\\}\]\)\\in\\\{1,\\ldots,i,\\mathrm\{false\}\\\}for1≤i≤D1\\leq i\\leq Dand0≤j≤U​D0\\leq j\\leq UD\. As described in “Training details of SSP” above, two types of weights are learned and used during training and prediction\. The solution is constructed by the following greedy method, which decides in order from theDD\-th element whether each element is included in the subset\. Suppose that we have decided whether to include elements up to the\(i\+1\)\(i\+1\)\-th element and that the sum of the selected subset isjj\. Then, whether to include theii\-th element is determined by comparingmaxsspi−1,n−j​\(𝐮\)\\mathrm\{maxssp\}\_\{i\-1,n\-j\}\(\\mathbf\{u\}\)andmaxsspi−1,n−j−ui​\(𝐮\)\+1\\mathrm\{maxssp\}\_\{i\-1,n\-j\-u\_\{i\}\}\(\\mathbf\{u\}\)\+1\. If the former is larger, the element is not included in the subset; if the latter is larger, the element is included\. MINSSP is handled in the same way\.

\\bmhead

Acknowledgements This work supported by JSPS KAKENHI Grant No\. 25K00011\.

## Appendix Appendix ATraining size

To examine the required number of training samples, we conducted experiments in which the prediction performance was evaluated while varying the number of training samples\. The basic settings were the same as those of the experiments for predicting the optimal value of MINTSP and the optimal values of MAXSSP and MINSSP\. In addition to the proposed method, we evaluated various baseline methods; for methods whose number of features could be changed, we also varied the number of features\. For each method and each feature count, we plotted the performance, as the number of training samples was varied\. The results are shown in Fig\.[5](https://arxiv.org/html/2607.23009#A1.F5)\. The horizontal axis is the number of training samples divided by the number of features\. Based on these results, we judged that using at least1010times as many training samples as features would be sufficient throughout this study\.

Figure 5:Training\-size dependence of the optimal value prediction performance\.a, MAPE of the predicted MINTSP optimal value for the proposed method \(MAXTSP\) and baseline features \(ELM, NG\-RC\-INPUT, NG\-RC\-DIST, MATCHING\), as a function of the number of training samples divided by the number of features; the number of features used for each method is given in parentheses in the legend\.b,c, Kappa of the predicted optimal value forb, MAXSSP andc, MINSSP, for the proposed method \(DECSSP\) and baseline features \(INPUT, ELM, NGRC\), as a function of the number of training samples divided by the number of features\.
## Appendix Appendix BFeature selection for MINTSP solution construction

In the MINTSP solution construction experiment, we varied the number of features selected from the MAXTSP DP table\. All other settings were kept the same\. The results, shown in Fig\.[6](https://arxiv.org/html/2607.23009#A2.F6), reveal that that performance deteriorated as the number of features was reduced\. However, we found that the performance remained almost unchanged down to 2,000 features\. Because using fewer features shortens the computation time required to construct a solution, we selected 2,000 features in the main experiment, which was the smallest feature count among those that maintained performance\.

Figure 6:Effect of the number of selected MAXTSP\-DP features on MINTSP solution construction performance\.The average percentage by which the tour constructed by the proposed method exceeds the optimal MINTSP tour length \(MAPE\) is shown as a function of the number of features selected from the MAXTSP DP table by recursive feature elimination\.
## Appendix Appendix CSystematic analysis for the SSP experiments\.

We present detailed experimental results for SSP\.

##### Optimal value prediction

We examined how performance changed when the parametersUUandDDwere varied\. We variedUUandDDfrom22to2020in increments of22and created colormaps using the normalized accuracy\. For each method,TtrainT\_\{\\mathrm\{train\}\}was set to1010times its number of features, andTeval=2,000T\_\{\\mathrm\{eval\}\}=2,000was used throughout\. The number of features isDDfor INPUT andU​D​\(D\+1\)/2UD\(D\+1\)/2for the proposed DECSSP method; for ELM, the number of features was matched to that of DECSSP, and for NG\-RC, the polynomial degree was chosen so that its number of features was closest to that of DECSSP\. The results, shown in Fig\.[7](https://arxiv.org/html/2607.23009#A3.F7), indicate that prediction becomes more difficult asUUincreases\. However, the proposed method using DECSSP as features consistently achieved high performance\.

Figure 7:Optimal value prediction performance for SSP as the parametersUUandDDare varied\.a,b, Kappa of the predicted optimal value fora, MAXSSP andb, MINSSP, for the baseline features \(INPUT, ELM, NGRC\) and the proposed method \(DECSSP\), shown as a colormap as a function of the maximum input valueUUand the input dimensionDD\.
##### Solution construction

We also compared the proposed method with the generic features used as baselines in the optimal value prediction experiments\. In addition, we examined how accurately the objective functionsmaxsspi,j​\(𝐮\)\\mathrm\{maxssp\}\_\{i,j\}\(\\mathbf\{u\}\), predicted during solution construction, could be approximated\. For each objective function with1≤i≤D1\\leq i\\leq Dand0≤j≤U​D0\\leq j\\leq UD, the accuracy was visualized as a two\-dimensional colormap\. The same analysis was conducted for MINSSP\. The results are shown in Fig\.[8](https://arxiv.org/html/2607.23009#A3.F8)\. The proposed method using DECSSP as features approximated the objective functions more accurately than the other methods\. We also confirmed that the prediction accuracy of the objective functions was consistent with the accuracy of solution construction\. Fig[9](https://arxiv.org/html/2607.23009#A3.F9)shows bar plots of the accuracy for each target sumnnin the solution construction experiment\. For largenn, in most cases, the target sumnnexceeded the sum of all input elements, so no subset could be formed; this made the result trivial and yielded high accuracy for all methods\. Even in nontrivial cases, the proposed method constructed correct solutions with higher accuracy than the other methods\.

Figure 8:Accuracy of the objective functions predicted during SSP solution construction\.a,b, Accuracy of the predicted objective functionmaxsspi,j​\(𝐮\)\\mathrm\{maxssp\}\_\{i,j\}\(\\mathbf\{u\}\)fora, MAXSSP and the corresponding objective function forb, MINSSP, for the baseline features \(INPUT, ELM, NGRC\) and the proposed method \(DECSSP\), shown as a colormap as a function ofiiandjj\.Figure 9:Solution construction accuracy for each target sumnnin SSP\.a,b, Accuracy of the constructed solutions for each target sumnn, fora, MAXSSP andb, MINSSP, for the baseline features \(INPUT, ELM, NGRC\) and the proposed method \(DECSSP\)\.

## References

- \\bibcommenthead
- Fawzi et al\. \[2022\]Fawzi, A\., Balog, M\., Huang, A\., Hubert, T\., Romera\-Paredes, B\., Barekatain, M\., Novikov, A\., R\. Ruiz, F\.J\., Schrittwieser, J\., Swirszcz, G\.: Discovering faster matrix multiplication algorithms with reinforcement learning\. Nature610\(7930\), 47–53 \(2022\)
- Pohl \[1972\]Pohl, I\.: A sorting problem and its complexity\. Communications of the ACM15\(6\), 462–464 \(1972\)
- Jaeger \[2001\]Jaeger, H\.: The “echo state” approach to analysing and training recurrent neural networks\-with an erratum note\. Bonn, Germany: German national research center for information technology gmd technical report148\(34\), 13 \(2001\)
- Maass et al\. \[2002\]Maass, W\., Natschläger, T\., Markram, H\.: Real\-time computing without stable states: A new framework for neural computation based on perturbations\. Neural computation14\(11\), 2531–2560 \(2002\)
- Nakajima and Fischer \[2021\]Nakajima, K\., Fischer, I\. \(eds\.\): Reservoir Computing: Theory, Physical Implementations, And Applications\. Natural Computing Series\. Springer, Singapore \(2021\)
- Nakajima \[2020\]Nakajima, K\.: Physical reservoir computing—an introductory perspective\. Japanese Journal of Applied Physics59\(6\), 060501 \(2020\)
- Natschläger et al\. \[2002\]Natschläger, T\., Maass, W\., Markram, H\.: The “liquid computer”: A novel strategy for real\-time computing on time series\. Special Issue on Foundations of Information Processing of TELEMATIK8\(1\), 39–43 \(2002\)
- Fernando and Sojakka \[2003\]Fernando, C\., Sojakka, S\.: Pattern recognition in a bucket\. In: European Conference on Artificial Life, pp\. 588–597 \(2003\)\. Springer
- Goto et al\. \[2021\]Goto, K\., Nakajima, K\., Notsu, H\.: Twin vortex computer in fluid flow\. New Journal of Physics23\(6\), 063051 \(2021\)
- Fujii and Nakajima \[2017\]Fujii, K\., Nakajima, K\.: Harnessing disordered\-ensemble quantum dynamics for machine learning\. Physical Review Applied8\(2\), 024030 \(2017\)
- Nakajima et al\. \[2019\]Nakajima, K\., Fujii, K\., Negoro, M\., Mitarai, K\., Kitagawa, M\.: Boosting computational power through spatial multiplexing in quantum reservoir computing\. Physical Review Applied11\(3\), 034021 \(2019\)
- Ghosh et al\. \[2019a\]Ghosh, S\., Opala, A\., Matuszewski, M\., Paterek, T\., Liew, T\.C\.: Quantum reservoir processing\. npj Quantum Information5\(1\), 35 \(2019\)
- Ghosh et al\. \[2019b\]Ghosh, S\., Paterek, T\., Liew, T\.C\.: Quantum neuromorphic platform for quantum state preparation\. Physical review letters123\(26\), 260404 \(2019\)
- Hauser et al\. \[2011\]Hauser, H\., Ijspeert, A\.J\., Füchslin, R\.M\., Pfeifer, R\., Maass, W\.: Towards a theoretical foundation for morphological computation with compliant bodies\. Biological cybernetics105\(5\), 355–370 \(2011\)
- Caluwaerts et al\. \[2013\]Caluwaerts, K\., D’Haene, M\., Verstraeten, D\., Schrauwen, B\.: Locomotion without a brain: physical reservoir computing in tensegrity structures\. Artificial life19\(1\), 35–66 \(2013\)
- Nakajima et al\. \[2013\]Nakajima, K\., Hauser, H\., Kang, R\., Guglielmino, E\., Caldwell, D\.G\., Pfeifer, R\.: A soft body as a reservoir: case studies in a dynamic model of octopus\-inspired soft robotic arm\. Frontiers in computational neuroscience7, 91 \(2013\)
- Zhao et al\. \[2013\]Zhao, Q\., Nakajima, K\., Sumioka, H\., Hauser, H\., Pfeifer, R\.: Spine dynamics as a computational resource in spine\-driven quadruped locomotion\. In: 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp\. 1445–1451 \(2013\)\. IEEE
- Nakajima et al\. \[2015\]Nakajima, K\., Hauser, H\., Li, T\., Pfeifer, R\.: Information processing via physical soft body\. Scientific reports5\(1\), 10487 \(2015\)
- Akashi et al\. \[2024\]Akashi, N\., Kuniyoshi, Y\., Jo, T\., Nishida, M\., Sakurai, R\., Wakao, Y\., Nakajima, K\.: Embedding bifurcations into pneumatic artificial muscle\. Advanced Science11\(25\), 2304402 \(2024\)
- Yilmaz \[2015a\]Yilmaz, O\.: Symbolic computation using cellular automata\-based hyperdimensional computing\. Neural computation27\(12\), 2661–2692 \(2015\)
- Yilmaz \[2015b\]Yilmaz, O\.: Machine learning using cellular automata based feature expansion and reservoir computing\. Journal of Cellular Automata10\(2015\)
- Nichele and Molund \[2017\]Nichele, S\., Molund, A\.: Deep learning with cellular automaton\-based reservoir computing\. Complex Systems26\(4\) \(2017\)
- Nichele and Gundersen \[2017\]Nichele, S\., Gundersen, M\.S\.: Reservoir computing using nonuniform binary cellular automata\. Complex Systems26\(3\), 225–246 \(2017\)
- McDonald \[2017\]McDonald, N\.: Reservoir computing & extreme learning machines using pairs of cellular automata rules\. In: 2017 International Joint Conference on Neural Networks \(ijcnn\), pp\. 2429–2436 \(2017\)\. IEEE
- Moran et al\. \[2019\]Moran, A\., Frasser, C\.F\., Roca, M\., Rossello, J\.L\.: Energy\-efficient pattern recognition hardware with elementary cellular automata\. IEEE Transactions on Computers69\(3\), 392–401 \(2019\)
- Cook \[2004\]Cook, M\.: Universality in elementary cellular automata\. Complex systems15\(1\), 1–40 \(2004\)
- Matai et al\. \[2010\]Matai, R\., Singh, S\.P\., Mittal, M\.L\.: Traveling salesman problem: an overview of applications, formulations, and solution approaches\. Traveling salesman problem, theory and applications1\(1\), 1–25 \(2010\)
- Hans et al\. \[2004\]Hans, K\., Ulrich, P\., David, P\.: Knapsack problems\. Springer \(2004\)
- Huang et al\. \[2004\]Huang, G\.\-B\., Zhu, Q\.\-Y\., Siew, C\.\-K\.: Extreme learning machine: a new learning scheme of feedforward neural networks\. In: 2004 IEEE International Joint Conference on Neural Networks \(IEEE Cat\. No\. 04CH37541\), vol\. 2, pp\. 985–990 \(2004\)\. Ieee
- Gauthier et al\. \[2021\]Gauthier, D\.J\., Bollt, E\., Griffith, A\., Barbosa, W\.A\.: Next generation reservoir computing\. Nature Communications12\(1\), 5564 \(2021\)
- Beardwood et al\. \[1959\]Beardwood, J\., Halton, J\.H\., Hammersley, J\.M\.: The shortest path through many points\. In: Mathematical Proceedings of the Cambridge Philosophical Society, vol\. 55, pp\. 299–327 \(1959\)\. Cambridge University Press
- Kou et al\. \[2022\]Kou, S\., Golden, B\., Poikonen, S\.: Optimal TSP tour length estimation using standard deviation as a predictor\. Computers & Operations Research148, 105993 \(2022\)
- Guyon et al\. \[2002\]Guyon, I\., Weston, J\., Barnhill, S\., Vapnik, V\.: Gene selection for cancer classification using support vector machines\. Machine learning46\(1\), 389–422 \(2002\)
- Karlin et al\. \[2021\]Karlin, A\.R\., Klein, N\., Gharan, S\.O\.: A \(slightly\) improved approximation algorithm for metric TSP\. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp\. 32–45\. ACM, Virtual Italy \(2021\)
- Reinelt \[1991\]Reinelt, G\.: TSPLIB—A Traveling Salesman Problem Library\. ORSA Journal on Computing3\(4\), 376–384 \(1991\)
- Bengio et al\. \[2021\]Bengio, Y\., Lodi, A\., Prouvost, A\.: Machine learning for combinatorial optimization: a methodological tour d’horizon\. European Journal of Operational Research290\(2\), 405–421 \(2021\)
- Huang et al\. \[2006\]Huang, G\.\-B\., Zhu, Q\.\-Y\., Siew, C\.\-K\.: Extreme learning machine: theory and applications\. Neurocomputing70\(1\-3\), 489–501 \(2006\)