論文の概要: Reinforcement Learning for Search Tree Size Minimization in Constraint Programming: New Results on Scheduling Benchmarks
- arxiv url: http://arxiv.org/abs/2508.20056v1
- Date: Wed, 27 Aug 2025 17:13:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-28 19:07:41.717349
- Title: Reinforcement Learning for Search Tree Size Minimization in Constraint Programming: New Results on Scheduling Benchmarks
- Title（参考訳）: 制約プログラミングにおける探索木サイズ最小化のための強化学習:スケジューリングベンチマークの新しい結果
- Authors: Vilém Heinz, Petr Vilím, Zdeněk Hanzálek,
- Abstract要約: 本稿では,分類分岐決定によって導かれる探索木の大きさを最小化することは,マルチアーム・バンディット(MAB)問題と密接に関連していることを示す。
この知見に基づいて、MAB強化学習アルゴリズムをFDSに適用し、問題固有の改良とパラメータチューニングにより拡張し、2つの最も基本的なスケジューリング問題について評価する。
その結果、最高の拡張MABアルゴリズムと構成を使用した拡張FDSは、JSSPでは1.7倍、RCPSPベンチマークでは2.1倍高速となる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Failure-Directed Search (FDS) is a significant complete generic search algorithm used in Constraint Programming (CP) to efficiently explore the search space, proven particularly effective on scheduling problems. This paper analyzes FDS's properties, showing that minimizing the size of its search tree guided by ranked branching decisions is closely related to the Multi-armed bandit (MAB) problem. Building on this insight, MAB reinforcement learning algorithms are applied to FDS, extended with problem-specific refinements and parameter tuning, and evaluated on the two most fundamental scheduling problems, the Job Shop Scheduling Problem (JSSP) and Resource-Constrained Project Scheduling Problem (RCPSP). The resulting enhanced FDS, using the best extended MAB algorithm and configuration, performs 1.7 times faster on the JSSP and 2.1 times faster on the RCPSP benchmarks compared to the original implementation in a new solver called OptalCP, while also being 3.5 times faster on the JSSP and 2.1 times faster on the RCPSP benchmarks than the current state-of-the-art FDS algorithm in IBM CP Optimizer 22.1. Furthermore, using only a 900-second time limit per instance, the enhanced FDS improved the existing state-of-the-art lower bounds of 78 of 84 JSSP and 226 of 393 RCPSP standard open benchmark instances while also completely closing a few of them.
- Abstract（参考訳）: FDS(Failure-Directed Search)は、CP(Constraint Programming)において、探索空間を効率的に探索するために使われる有意義な完全汎用探索アルゴリズムである。
本稿では, FDSの特性を解析し, 分岐決定によって導かれる探索木の大きさを最小化することは, マルチアームバンディット(MAB)問題と密接に関連していることを示す。
この知見に基づいて、MAB強化学習アルゴリズムをFDSに適用し、問題固有の改善とパラメータチューニングを拡張し、ジョブショップスケジューリング問題(JSSP)とリソース制約計画問題(RCPSP)の2つの最も基本的なスケジューリング問題について評価する。
その結果、拡張されたFDSは、最高の拡張MABアルゴリズムと構成を使用して、JSSPで1.7倍、RSPSPベンチマークで2.1倍、JSSPで3.5倍、JSSPベンチマークで2.1倍、IBM CP Optimizer 22.1で現在の最先端FDSアルゴリズムよりも高速になった。
さらに、インスタンスあたり900秒の時間制限のみを使用して、拡張されたFDSは、既存の最先端のJSSPの78と393 RCPSP標準のオープンベンチマークインスタンスの226の低いバウンダリを改善し、そのいくつかを完全にクローズした。
関連論文リスト
- Knowledge-Guided Memetic Algorithm for Capacitated Arc Routing Problems with Time-Dependent Service Costs [18.734871315760717]
本稿では,ゴールデンセクション探索と負相関探索を用いた知識誘導メメティックアルゴリズムを提案する。
最先端の手法よりも高い探索効率を実現する。
論文 参考訳（メタデータ） (2025-07-29T12:17:25Z) - A*-Decoding: Token-Efficient Inference Scaling [0.0]
推論時間スケーリングは、言語モデルのパフォーマンスを改善するためのパラメータスケーリングの強力な代替手段として登場した。
A*-decoding(A*-decoding)は、A*検索アルゴリズムに基づいて、固定された計算予算を最適に活用する検索ベースの推論時戦略である。
我々の研究は、より効率的でスケーラブルな言語モデルのデプロイメントにおける将来的な進歩を指して、思慮深い推論時戦略がSLMの推論をいかに向上させるかを実証している。
論文 参考訳（メタデータ） (2025-05-19T19:19:48Z) - PlanGEN: A Multi-Agent Framework for Generating Planning and Reasoning Trajectories for Complex Problem Solving [89.60370366013142]
制約,検証,選択という3つの重要な要素を持つモデルに依存しない,スケーラブルなエージェントフレームワークであるPlanGENを提案する。
具体的には、推論時間アルゴリズムの性能を向上させるために、制約誘導反復検証を提案する。
論文 参考訳（メタデータ） (2025-02-22T06:21:56Z) - APB: Accelerating Distributed Long-Context Inference by Passing Compressed Context Blocks across GPUs [81.5049387116454]
我々は、効率的な長文推論フレームワークであるAPBを紹介する。
APBはプリフィル速度を高めるためにマルチホスト近似アテンションを使用する。
APBはFlashAttn、RingAttn、StarAttnと比較して最大9.2x、4.2x、1.6xの速度を実現している。
論文 参考訳（メタデータ） (2025-02-17T17:59:56Z) - FastDiagP: An Algorithm for Parallelized Direct Diagnosis [64.65251961564606]
FastDiagは、競合を事前に決定せずに診断計算をサポートする典型的な直接診断アルゴリズムである。
本稿では,投機的プログラミングのアイデアに基づく新しいアルゴリズムであるFastDiagPを提案する。
このメカニズムは、高速な回答で一貫性チェックを提供し、アルゴリズムのランタイムパフォーマンスを高めるのに役立つ。
論文 参考訳（メタデータ） (2023-05-11T16:26:23Z) - DeciLS-PBO: an Effective Local Search Method for Pseudo-Boolean
Optimization [10.513103815142731]
PBO(Pseudo-Boolean Optimization)の解法における局所探索アルゴリズムの改良法について検討する。
我々のアルゴリズムであるDeciLS-PBOは最先端のアルゴリズムと比較して有望な性能を持つ。
論文 参考訳（メタデータ） (2023-01-28T17:03:56Z) - HUSP-SP: Faster Utility Mining on Sequence Data [48.0426095077918]
高実用性シーケンシャルパターンマイニング (HUSPM) が重要視されている。
シークエンスプロジェクション(seqPro)と呼ばれるコンパクトな構造を設計し、シークエンスプロ構造(HUSP-SP)を用いた効率的なアルゴリズムを提案する。
HUSP-SPは, 実行時間, メモリ使用量, 検索空間のプルーニング効率, スケーラビリティにおいて, 最先端のアルゴリズムを著しく上回っている。
論文 参考訳（メタデータ） (2022-12-29T10:56:17Z) - Empirical Evaluation of Project Scheduling Algorithms for Maximization
of the Net Present Value [0.0]
本稿では,3つのプロジェクトスケジューリングアルゴリズムの実証的性能解析について述べる。
選択されたアルゴリズムは、Recursive Search (RS)、Steepest Ascent Approach (SAA)、Hybrid Search (HS)である。
論文 参考訳（メタデータ） (2022-07-05T03:01:33Z) - Revisiting State Augmentation methods for Reinforcement Learning with
Stochastic Delays [10.484851004093919]
本稿では,遅延を伴うマルコフ決定過程(MDP)の概念を正式に述べる。
遅延MDPは、コスト構造が大幅に単純化された(遅延なしで)等価な標準MDPに変換可能であることを示す。
この等価性を利用して、モデルフリーな遅延分解RLフレームワークを導出し、このフレームワーク上に構築された単純なRLアルゴリズムでさえ、動作や観測の遅延を伴う環境におけるほぼ最適報酬を達成することを示す。
論文 参考訳（メタデータ） (2021-08-17T10:45:55Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。