🤖 machine learning

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

This paper proposes a reservoir computing approach that automatically discovers and reuses intermediate dynamic programming results across multiple combinatorial optimization problems to improve approximation accuracy and reduce computation time, validated on the traveling salesman and subset sum problems.

Original authors: Sora Todaka, Akihiro Yamamoto, Nozomi Akashi

Published 2026-07-28

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Sora Todaka, Akihiro Yamamoto, Nozomi Akashi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a master chef trying to cook three different meals for a dinner party: a spicy curry, a delicate soufflé, and a hearty stew. In the old way of doing things, you would start the first recipe from scratch, wash your hands, start the second recipe from scratch, and then do the same for the third. You'd be chopping onions, measuring spices, and heating pans over and over again, even though the first three steps of every recipe are almost identical. This is how computers often work today: they solve one math problem, throw away all the notes they made while solving it, and then start completely fresh for the next problem, even if the two problems are related.

But what if you could keep those notes? What if, while cooking the curry, you realized the way you chopped the onions was actually perfect for the stew, too? This idea of "recycling" work is a classic trick in computer science called Dynamic Programming. It's like writing down the answer to a small math puzzle in a notebook so you don't have to solve it again later. Another concept, Reservoir Computing, is a bit like a chaotic, bubbling pot of soup. You throw ingredients (data) into the pot, and the way they swirl and mix creates a complex pattern. You don't control the swirls, but you can learn to read the pattern to guess what the soup tastes like. The big question scientists are asking is: Can we take the "notes" from solving one hard puzzle and use them as ingredients to solve a different hard puzzle, saving time and energy?

This is exactly what the researchers in this paper set out to explore. They propose a new way to solve tricky math puzzles called combinatorial optimization problems—think of these as games where you have to find the absolute best arrangement of things, like the shortest route for a traveling salesman or the perfect combination of numbers to reach a target sum. Usually, if you want to solve two different versions of these games, you run two separate, heavy-duty computer programs. The authors suggest a smarter approach: run the heavy program for just one of the games, keep the massive list of intermediate results it generates (the "notes"), and then use a simple, lightweight math trick called linear regression to guess the answers for the other games based on those notes.

In their experiments, the team tested this idea on two famous puzzles: the Traveling Salesman Problem (finding the shortest path to visit a list of cities) and the Subset Sum Problem (finding a group of numbers that add up to a specific target). They found that by "recycling" the computational process of solving the "hardest" version of the Traveling Salesman Problem (finding the longest route), they could predict the solution to the "easiest" version (finding the shortest route) with surprising accuracy. It's as if they cooked the spicy curry, looked at the bubbling pot, and instantly knew exactly how to make the soufflé without ever turning on the oven for the second dish.

The results suggest that this method is not just a theoretical curiosity. When they tried to find the shortest route for 14 cities, their "recycled" method was about nine times faster than solving it from scratch, and it was actually more accurate than several standard, well-known shortcuts used by experts. Similarly, for the number-summing puzzle, sharing the work allowed them to solve two different goals at once much faster than doing them separately. The authors suggest that this points to a new way of thinking about computing: instead of treating every problem as a brand-new task that requires a fresh start, we could design systems where different problems "share a brain," organically recycling the intermediate steps of one to help solve the other. It's a bit like how our brains might use the same neural pathways for walking and dancing, repurposing old skills for new moves. While this doesn't mean we can solve every impossible math problem instantly, it suggests a future where computers are less like isolated workers and more like a collaborative team, constantly reusing their best ideas to get the job done faster.

Technical Summary: Recycling Computational Processes of Dynamic Programming for Combinatorial Optimization Problems

Problem Statement

The paper addresses the inefficiency inherent in current computational paradigms where distinct optimization problems are solved independently, even when they share the same input. While the principle of reusing intermediate results (e.g., dynamic programming, memoization) is well-established within a single problem, the authors investigate whether computational processes can be shared across multiple simultaneously solved problems. The core challenge is that manually designing algorithms to exploit nontrivial cross-task relationships is difficult. The authors propose a machine learning approach to automatically discover and leverage these relationships, specifically aiming to solve a target combinatorial optimization problem (Problem B) by recycling the computation results of a different, related problem (Problem A).

Methodology

The authors propose a framework based on reservoir computing, adapted for combinatorial optimization. Instead of using a physical or abstract dynamical system as the reservoir, they utilize the Dynamic Programming (DP) table generated while solving a source problem (Problem A) as the computational resource.

Framework Overview

Reservoir Definition: A DP algorithm is run for Problem A (the source problem) on a given input $u$ . The resulting DP table, which records intermediate states and values, is treated as a fixed, high-dimensional feature vector $\phi(u)$ .
Readout Mechanism: A linear regression model (with $L_2$ regularization/ridge regression) is trained to map these DP features to the solution of Problem B (the target problem).
Training: The weights of the linear regression are learned in a supervised manner using input-target pairs. The DP process itself is fixed and not retrained; only the linear readout is optimized.
Solution Construction: For problems requiring decision variables (e.g., specific tours or subsets) rather than just optimal values, the method approximates the value function defined by the target problem's DP recurrence. A greedy construction algorithm then uses these approximated values to sequentially build the solution.

Experimental Setup

The study validates this approach on two fundamental NP-hard problems:

Traveling Salesman Problem (TSP):
- Source (Reservoir): Maximum-cost TSP (MAXTSP) solved via DP.
- Target: Minimum-cost TSP (MINTSP).
- Tasks: Predicting the optimal tour cost and constructing the tour.
- Baselines: Linear regression on raw inputs, Extreme Learning Machines (ELM), Next Generation Reservoir Computing (NG-RC), and heuristics like Nearest Neighbor and Christofides.
Subset Sum Problem (SSP):
- Source (Reservoir): Decision version (DECSSP) solved via DP.
- Targets: Maximum subset size (MAXSSP) and Minimum subset size (MINSSP) for a given sum.
- Tasks: Predicting the optimal subset size and constructing the subset.
- Baselines: Similar generic feature sets and independent DP solutions.

Key Results

Traveling Salesman Problem (TSP)

Optimal Value Prediction: Using the MAXTSP DP table as features, the proposed method achieved a Mean Absolute Percentage Error (MAPE) of 1.61% for MINTSP. This outperformed generic baselines (ELM, NG-RC) and specialized heuristics. Notably, to achieve similar performance with NG-RC-DIST, approximately 10 times more features were required, suggesting the MAXTSP table contains highly relevant information for MINTSP.
Solution Construction: The proposed method achieved a tour length gap of 1.03% compared to the optimal solution, outperforming standard approximation algorithms like Christofides (18.8% gap) and Nearest Neighbor (14.3% gap).
Efficiency: The method was approximately 9 times faster than solving MINTSP independently via exact DP.
Generalization: The model, trained on synthetic data, successfully generalized to the real-world TSPLIB instance burma14, constructing the optimal solution with zero error.

Subset Sum Problem (SSP)

Optimal Value Prediction: The proposed method using the DECSSP DP table achieved the highest Cohen's Kappa scores for both MAXSSP and MINSSP tasks. It outperformed generic baselines even when those baselines used more than 10 times the number of features.
Solution Construction: The method correctly constructed solutions with 91.8% accuracy for MAXSSP and 99.5% accuracy for MINSSP.
Efficiency: By sharing the DP computation for the simpler DECSSP subproblem, the total time to solve both MAXSSP and MINSSP was significantly reduced compared to running independent DP algorithms for each.

Key Contributions

Recycling Computational Processes: The paper introduces a novel paradigm where the intermediate states of a DP algorithm for one problem serve as a "reservoir" to solve a different problem on the same input.
Automatic Discovery of Cross-Task Relationships: By using machine learning (linear regression) to map DP tables to target solutions, the method automatically uncovers nontrivial relationships between problems (e.g., between MAXTSP and MINTSP) that are difficult to design manually.
Efficiency Gains: The approach demonstrates that solving multiple problems simultaneously via shared computation can yield higher approximation accuracy and reduced computation time compared to independent solutions or generic machine learning features.
Extension of Reservoir Computing: The work extends the concept of reservoir computing from physical or abstract dynamical systems to algorithmic computation processes (specifically DP tables).

Significance and Claims

The authors claim that this work suggests a new form of computation distinct from conventional design, where multiple processes organically share and recycle intermediate results.

Complementarity: The approach is presented as complementary to existing machine learning for optimization. Rather than trying to improve a single algorithm's performance in isolation, it focuses on extracting additional information from an existing algorithm's computation to solve related problems at a low marginal cost.
Scalability: As computational resources become more constrained (slowing Moore's Law), the ability to share processes across problems offers a pathway to greater efficiency.
Scientific Implication: The research lays the groundwork for studying the relationship between problems and algorithms as an object of study itself, potentially revealing hidden structural connections between seemingly distinct optimization problems.
Limitations: The authors modestly note that the method relies on the target problem being substantively related to the source problem's computation, as the readout is kept lightweight (linear). It is not a universal solution for arbitrary algorithm-problem combinations.