論文の概要: Enhancing Constraint Programming via Supervised Learning for Job Shop Scheduling

• arxiv url: http://arxiv.org/abs/2211.14492v2
• Date: Wed, 12 Apr 2023 07:20:31 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-13 18:27:11.169746
• Title: Enhancing Constraint Programming via Supervised Learning for Job Shop Scheduling
• Title（参考訳）: ジョブショップスケジューリングのための教師付き学習による制約プログラミングの強化
• Authors: Yuan Sun, Su Nguyen, Dhananjay Thiruvady, Xiaodong Li, Andreas T. Ernst and Uwe Aickelin
• Abstract要約: CPソルバにおいて、最初に探索する変数を選択するために使用される変数順序付け戦略は、ソルバの有効性に大きな影響を及ぼす。 本稿では,教師付き学習に基づく新しい変数順序付け手法を提案する。 学習に基づく手法は問題インスタンスの最適解を予測し、予測された解を用いてCPソルバの変数を順序付けする。
• 参考スコア（独自算出の注目度）: 6.4778725014634615
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Constraint programming (CP) is a powerful technique for solving constraint satisfaction and optimization problems. In CP solvers, the variable ordering strategy used to select which variable to explore first in the solving process has a significant impact on solver effectiveness. To address this issue, we propose a novel variable ordering strategy based on supervised learning, which we evaluate in the context of job shop scheduling problems. Our learning-based methods predict the optimal solution of a problem instance and use the predicted solution to order variables for CP solvers. \added[]{Unlike traditional variable ordering methods, our methods can learn from the characteristics of each problem instance and customize the variable ordering strategy accordingly, leading to improved solver performance.} Our experiments demonstrate that training machine learning models is highly efficient and can achieve high accuracy. Furthermore, our learned variable ordering methods perform competitively when compared to four existing methods. Finally, we demonstrate that hybridising the machine learning-based variable ordering methods with traditional domain-based methods is beneficial.
• Abstract（参考訳）: 制約プログラミング(cp)は制約満足度と最適化問題を解決する強力な手法である。 cpソルバにおいて、解法プロセスで最初に探索する変数を選択するために用いられる変数順序付け戦略は、解法の有効性に大きな影響を与える。 そこで本研究では,ジョブショップスケジューリング問題の文脈で評価する教師付き学習に基づく可変順序付け戦略を提案する。 提案手法は,問題インスタンスの最適解を予測し,予測解を用いてcpソルバに対して変数を順序付けする。 従来の変数順序付け手法とは異なり,本手法では各問題インスタンスの特徴から学習し,それに応じて変数順序付け戦略をカスタマイズすることで,解法の性能が向上する。 実験では,機械学習モデルの学習が極めて効率的であり,精度が高いことを示した。 さらに,学習した変数順序付け手法は,既存の4つの手法と比較して競合的に機能する。 最後に,機械学習に基づく変数順序付け手法を従来のドメインベース手法と併用することが有用であることを示す。

関連論文リスト

• Learning Joint Models of Prediction and Optimization [56.04498536842065]
  Predict-Then-Thenフレームワークは、機械学習モデルを使用して、最適化問題の未知のパラメータを、解決前の機能から予測する。 本稿では,共同予測モデルを用いて観測可能特徴から最適解を直接学習する手法を提案する。
  論文  参考訳（メタデータ） (2024-09-07T19:52:14Z)
• Take a Step and Reconsider: Sequence Decoding for Self-Improved Neural Combinatorial Optimization [1.1510009152620668]
  自己改善学習のための単純で問題に依存しないシーケンス復号法を提案する。 以前にサンプリングされたシーケンスを無視するためにポリシーを変更することで、目に見えない代替案のみを検討するように強制する。 本手法は,ジョブショップスケジューリング問題における従来のNCO手法よりも優れていた。
  論文  参考訳（メタデータ） (2024-07-24T12:06:09Z)
• Control in Stochastic Environment with Delays: A Model-based Reinforcement Learning Approach [3.130722489512822]
  遅延フィードバックを伴う環境における制御問題に対する新しい強化学習手法を提案する。 具体的には,決定論的計画を用いた従来の手法に対して,計画を採用する。 この定式化は、決定論的遷移の問題に対する最適ポリシーを回復できることを示す。
  論文  参考訳（メタデータ） (2024-02-01T03:53:56Z)
• Adaptive Robust Learning using Latent Bernoulli Variables [50.223140145910904]
  破損したトレーニングセットから学習するための適応的なアプローチを提案する。 我々は,潜伏したベルヌーイ変数を持つ崩壊した非破壊標本を同定した。 結果の問題は変分推論によって解決される。
  論文  参考訳（メタデータ） (2023-12-01T13:50:15Z)
• Predict-Then-Optimize by Proxy: Learning Joint Models of Prediction and Optimization [59.386153202037086]
  Predict-Then-フレームワークは、機械学習モデルを使用して、最適化問題の未知のパラメータを、解決前の機能から予測する。 このアプローチは非効率であり、最適化ステップを通じてバックプロパゲーションのための手作りの、問題固有のルールを必要とする。 本稿では,予測モデルを用いて観測可能な特徴から最適解を直接学習する手法を提案する。
  論文  参考訳（メタデータ） (2023-11-22T01:32:06Z)
• Reinforcement Learning Methods for Wordle: A POMDP/Adaptive Control Approach [0.3093890460224435]
  我々は、新しい強化学習手法を用いて、人気のあるWordleパズルの解法に対処する。 Wordleパズルでは、比較的控えめな計算コストで最適に近いオンラインソリューション戦略が得られる。
  論文  参考訳（メタデータ） (2022-11-15T03:46:41Z)
• SOLO: Search Online, Learn Offline for Combinatorial Optimization Problems [4.777801093677586]
  我々は,機械スケジューリングやルーティング,割当てといった実世界のアプリケーションで問題を研究する。 RL(Reinforcement Learning)とプランニングを組み合わせた手法を提案する。 この方法は、オフラインでも、オンラインでも、問題のコンポーネントが事前に分かっておらず、むしろ意思決定プロセス中に現れるような、問題の変種にも等しく適用することができる。
  論文  参考訳（メタデータ） (2021-04-04T17:12:24Z)
• Logistic Q-Learning [87.00813469969167]
  MDPにおける最適制御の正規化線形プログラミング定式化から導いた新しい強化学習アルゴリズムを提案する。 提案アルゴリズムの主な特徴は,広範に使用されているベルマン誤差の代わりとして理論的に音声として機能する,政策評価のための凸損失関数である。
  論文  参考訳（メタデータ） (2020-10-21T17:14:31Z)
• Learning with Differentiable Perturbed Optimizers [54.351317101356614]
  本稿では,操作を微分可能で局所的に一定ではない操作に変換する手法を提案する。 提案手法は摂動に依拠し,既存の解法とともに容易に利用することができる。 本稿では,この枠組みが,構造化予測において発達した損失の族とどのように結びつくかを示し,学習課題におけるそれらの使用に関する理論的保証を与える。
  論文  参考訳（メタデータ） (2020-02-20T11:11:32Z)
• Model-based Multi-Agent Reinforcement Learning with Cooperative Prioritized Sweeping [4.5497948012757865]
  本稿では,新しいモデルに基づく強化学習アルゴリズム,Cooperative Prioritized Sweepingを提案する。 このアルゴリズムは、値関数を近似するために因子化を利用することにより、大きな問題に対するサンプル効率の学習を可能にする。 我々の手法は、よく知られたSysAdminベンチマークとランダム化環境の両方において、最先端の協調的なQ-ラーニングアルゴリズムよりも優れている。
  論文  参考訳（メタデータ） (2020-01-15T19:13:44Z)
• Hierarchical Variational Imitation Learning of Control Programs [131.7671843857375]
  パラメータ化された階層的手順(PHP)で表される制御ポリシーの模倣学習のための変分推論手法を提案する。 本手法は, 教師による実演の観察・行動トレースのデータセットにおける階層構造を, 手続き呼び出しや用語の待ち行列に近似した後続分布を学習することによって発見する。 階層的模倣学習(hierarchical mimicion learning)の文脈における変分推論の新たな利点を実証する。
  論文  参考訳（メタデータ） (2019-12-29T08:57:02Z)

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

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