論文の概要: Recycling computational processes of dynamic programming for combinatorial optimization problems: a reservoir computing approach

• arxiv url: http://arxiv.org/abs/2607.23009v1
• Date: Sat, 25 Jul 2026 02:54:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-28 22:34:14.965937
• Title: Recycling computational processes of dynamic programming for combinatorial optimization problems: a reservoir computing approach
• Title（参考訳）: 組合せ最適化問題に対する動的プログラミングのリサイクル計算過程:貯水池計算アプローチ
• Abstract要約: 計算結果の再利用は、計算コストを削減するための長年の原則である。 機械学習を使って、非自明なクロスタスク関係を利用するアルゴリズムを発見します。 これらの結果から,従来の計算設計とは異なる新たな計算形式が示唆された。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 従来の計算結果の再利用は、計算コストを削減するための長年の原則であるが、そのような再利用は、主に1つの問題の計算に限られている。 複数の同時解問題にまたがる計算過程の共有は原則として可能であるが、非自明なクロスタスク関係を利用するアルゴリズムを設計することは困難である。 ここでは、機械学習を用いて、そのようなアルゴリズムを自動的に発見する。 具体的には、貯水池計算に基づいて、動的プログラミングによって記録された計算結果を線形回帰問題として、線形回帰問題として利用し、それらを利用して他の組合せ最適化計算を支援する手法を提案する。 旅行セールスマンとサブセットの総和問題に対するアプローチを検証する。 動的プログラミングプロセスの多重化により、一般的な特徴よりも近似精度が向上し、独立した解に比べて計算時間を短縮する。 これらの結果は、複数のプロセスが効率よく中間結果と状態を共有・リサイクルする従来の計算設計とは異なる、新しい計算形式を示唆している。

関連論文リスト

• Batched First-Order Methods for Parallel LP Solving in MIP [5.672808839120628]
  本研究では, 線形プログラミング問題のバッチを, 強い分岐や束縛といった混合整数型プログラミング手法で効率的に解くために, 原始双対ハイブリッドアルゴリズムを拡張した。 提案手法の有効性を様々なケーススタディで検証し,計算環境に応じて一階法が従来の単純な解法より優れている問題の大きさを同定する。
  論文  参考訳（メタデータ） (2026-01-29T17:02:46Z)
• Predicting Probabilities of Error to Combine Quantization and Early Exiting: QuEE [68.6018458996143]
  本稿では,量子化と早期出口動的ネットワークを組み合わせたより一般的な動的ネットワークQuEEを提案する。 我々のアルゴリズムは、ソフトアーリーエグジットや入力依存圧縮の一形態と見なすことができる。 提案手法の重要な要素は、さらなる計算によって実現可能な潜在的な精度向上の正確な予測である。
  論文  参考訳（メタデータ） (2024-06-20T15:25:13Z)
• Task Scheduling Optimization with Direct Constraints from a Tensor Network Perspective [41.94295877935867]
  本研究では,量子インスパイアされたテンソルネットワーク技術を用いた産業プラントにおけるタスク最適化手法を提案する。 計算のための3つのアルゴリズムが提示される: 主アルゴリズム、必要最小限の制約のみを加算する反復アルゴリズム、および、反復アルゴリズムと基本的な遺伝的アルゴリズムを組み合わせる遺伝的アルゴリズム。
  論文  参考訳（メタデータ） (2023-11-17T10:10:46Z)
• Scalable computation of prediction intervals for neural networks via matrix sketching [79.44177623781043]
  既存の不確実性推定アルゴリズムでは、モデルアーキテクチャとトレーニング手順を変更する必要がある。 本研究では、与えられたトレーニングされたニューラルネットワークに適用し、近似予測間隔を生成できる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-06T13:18:31Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。 スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。 その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
  論文  参考訳（メタデータ） (2021-03-10T03:16:12Z)
• Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
  予測+最適化問題は、予測係数を使用する最適化プロブレムと、確率係数の機械学習を組み合わせる。 本稿では, 予測係数を1次線形関数として, 最適化問題の損失を直接表現する方法を示す。 本稿では,この制約を伴わずに最適化問題に対処し,最適化損失を用いてその係数を予測する新しい分割アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-04T00:26:56Z)
• Parallel Scheduling Self-attention Mechanism: Generalization and Optimization [0.76146285961466]
  本稿では,SAT(Satisfiability check)ソルバによって解決された小インスタンスの最適スケジューリングから導いた一般スケジューリングアルゴリズムを提案する。 余剰計算をスキップする際のさらなる最適化戦略も推進され、元の計算の約25%と50%の削減が達成される。 提案アルゴリズムは、入力ベクトルの数がアーキテクチャで利用可能な演算ユニットの数に割り切れる限り、問題のサイズにかかわらず適用可能である。
  論文  参考訳（メタデータ） (2020-12-02T12:04:16Z)
• Coded Distributed Computing with Partial Recovery [56.08535873173518]
  部分回復型符号化計算(CCPR)と呼ばれる新しい符号化行列ベクトル乗法を導入する。 CCPRは計算時間と復号化の複雑さを減らし、精度と計算速度のトレードオフを可能にする。 次に、この手法をより一般的な計算タスクの分散実装に拡張し、部分的回復を伴う符号化通信方式を提案する。
  論文  参考訳（メタデータ） (2020-07-04T21:34:49Z)
• Simple and Scalable Parallelized Bayesian Optimization [2.512827436728378]
  本稿では,非同期並列設定のためのシンプルでスケーラブルなBO法を提案する。 マルチ層パーセプトロンのベンチマーク関数とハイパーパラメータ最適化を用いて実験を行った。
  論文  参考訳（メタデータ） (2020-06-24T10:25:27Z)
• Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving [106.63673243937492]
  ニューラルネットワークの評価や自己回帰モデルからのサンプリングなどのフィードフォワード計算は、機械学習においてユビキタスである。 本稿では,非線形方程式の解法としてフィードフォワード計算の課題を定式化し,ジャコビ・ガウス・シーデル固定点法とハイブリッド法を用いて解を求める。 提案手法は, 並列化可能な繰り返し回数の削減(あるいは等値化)により, 元のフィードフォワード計算と全く同じ値が与えられることを保証し, 十分な並列化計算能力を付与する。
  論文  参考訳（メタデータ） (2020-02-10T10:11:31Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。