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

• URL: http://arxiv.org/abs/2607.23009v1
• Date: Sat, 25 Jul 2026 02:54:32 GMT
• Title: Recycling computational processes of dynamic programming for combinatorial optimization problems: a reservoir computing approach
• Abstract summary: Reusing previously computed results is a long-standing principle for reducing computational cost.<n>We use machine learning to discover algorithms that exploit nontrivial cross-task relationships.<n>These results suggest a new form of computation distinct from conventional computational design.
• Score: 0.45880283710344055
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Batched First-Order Methods for Parallel LP Solving in MIP [5.672808839120628]
  We extend the primal-dual hybrid algorithm to efficiently solve batches of related linear programming problems that arise in mixed-integer programming techniques such as strong branching and bound tightening.<n>We demonstrate the effectiveness of our approach on various case studies and identify the problem sizes where first-order methods outperform traditional simplex-based solvers depending on the computational environment one can use.
  arXiv  Detail & Related papers  (2026-01-29T17:02:46Z)
• Predicting Probabilities of Error to Combine Quantization and Early Exiting: QuEE [68.6018458996143]
  We propose a more general dynamic network that can combine both quantization and early exit dynamic network: QuEE. Our algorithm can be seen as a form of soft early exiting or input-dependent compression. The crucial factor of our approach is accurate prediction of the potential accuracy improvement achievable through further computation.
  arXiv  Detail & Related papers  (2024-06-20T15:25:13Z)
• Task Scheduling Optimization with Direct Constraints from a Tensor Network Perspective [41.94295877935867]
  This work presents a novel method for task optimization in industrial plants using quantum-inspired tensor network technology.<n>Three algorithms for computation are presented: the main algorithm, the iterative algorithm which adds only the minimal amount of necessary constraints, and the genetic algorithm which combines the iterative algorithm with basic genetic algorithms.
  arXiv  Detail & Related papers  (2023-11-17T10:10:46Z)
• Scalable computation of prediction intervals for neural networks via matrix sketching [79.44177623781043]
  Existing algorithms for uncertainty estimation require modifying the model architecture and training procedure. This work proposes a new algorithm that can be applied to a given trained neural network and produces approximate prediction intervals.
  arXiv  Detail & Related papers  (2022-05-06T13:18:31Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  We develop a two-stage framework, in which reinforcement learning (RL) and traditional operations research (OR) algorithms are combined together. The scheduling problem is solved in two stages, including a finite Markov decision process (MDP) and a mixed-integer programming process, respectively. Results show that the proposed algorithms could stably and efficiently obtain satisfactory scheduling schemes for agile Earth observation satellite scheduling problems.
  arXiv  Detail & Related papers  (2021-03-10T03:16:12Z)
• Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
  The predict+optimize problem combines machine learning ofproblem coefficients with a optimization prob-lem that uses the predicted coefficients. We show how to directlyexpress the loss of the optimization problem in terms of thepredicted coefficients as a piece-wise linear function. We propose a novel divide and algorithm to tackle optimization problems without this restriction and predict itscoefficients using the optimization loss.
  arXiv  Detail & Related papers  (2020-12-04T00:26:56Z)
• Parallel Scheduling Self-attention Mechanism: Generalization and Optimization [0.76146285961466]
  We propose a general scheduling algorithm, which is derived from the optimum scheduling for small instances solved by a satisfiability checking(SAT) solver. Strategies for further optimization on skipping redundant computations are put forward as well, with which reductions of almost 25% and 50% of the original computations are respectively achieved. The proposed algorithms are applicable regardless of problem sizes, as long as the number of input vectors is divisible to the number of computing units available in the architecture.
  arXiv  Detail & Related papers  (2020-12-02T12:04:16Z)
• Coded Distributed Computing with Partial Recovery [56.08535873173518]
  We introduce a novel coded matrix-vector multiplication scheme, called coded computation with partial recovery (CCPR) CCPR reduces both the computation time and the decoding complexity by allowing a trade-off between the accuracy and the speed of computation. We then extend this approach to distributed implementation of more general computation tasks by proposing a coded communication scheme with partial recovery.
  arXiv  Detail & Related papers  (2020-07-04T21:34:49Z)
• Simple and Scalable Parallelized Bayesian Optimization [2.512827436728378]
  We propose a simple and scalable BO method for asynchronous parallel settings. Experiments are carried out with a benchmark function and hyperparameter optimization of multi-layer perceptrons.
  arXiv  Detail & Related papers  (2020-06-24T10:25:27Z)
• Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving [106.63673243937492]
  Feedforward computation, such as evaluating a neural network or sampling from an autoregressive model, is ubiquitous in machine learning. We frame the task of feedforward computation as solving a system of nonlinear equations. We then propose to find the solution using a Jacobi or Gauss-Seidel fixed-point method, as well as hybrid methods of both. Our method is guaranteed to give exactly the same values as the original feedforward computation with a reduced (or equal) number of parallelizable iterations, and hence reduced time given sufficient parallel computing power.
  arXiv  Detail & Related papers  (2020-02-10T10:11:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.