論文の概要: Neural Networked Assisted Tree Search for the Personnel Rostering
Problem
- arxiv url: http://arxiv.org/abs/2010.14252v1
- Date: Sat, 24 Oct 2020 22:23:20 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-03 13:21:19.693645
- Title: Neural Networked Assisted Tree Search for the Personnel Rostering
Problem
- Title（参考訳）: 人事ロスタリング問題に対するニューラルネットワークを用いた木探索
- Authors: Ziyi Chen and Patrick De Causmaecker and Yajie Dou
- Abstract要約: 本稿では,Deep Neural NetworkとTree Searchを組み合わせた新しい手法を提案する。
スケジュールを行列として扱うことで、ニューラルネットワークは現在の解と最適な解の間の距離を予測することができる。
既存の(最適に近い)ソリューションを分析して、問題インスタンスをロースターする人事に対するソリューション戦略を選択することができる。
- 参考スコア（独自算出の注目度）: 6.052423212814052
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The personnel rostering problem is the problem of finding an optimal way to
assign employees to shifts, subject to a set of hard constraints which all
valid solutions must follow, and a set of soft constraints which define the
relative quality of valid solutions. The problem has received significant
attention in the literature and is addressed by a large number of exact and
metaheuristic methods. In order to make the complex and costly design of
heuristics for the personnel rostering problem automatic, we propose a new
method combined Deep Neural Network and Tree Search. By treating schedules as
matrices, the neural network can predict the distance between the current
solution and the optimal solution. It can select solution strategies by
analyzing existing (near-)optimal solutions to personnel rostering problem
instances. Combined with branch and bound, the network can give every node a
probability which indicates the distance between it and the optimal one, so
that a well-informed choice can be made on which branch to choose next and to
prune the search tree.
- Abstract（参考訳）: 人事ロスタリング問題は、すべての有効なソリューションが従わなければならない一連の厳しい制約と、有効なソリューションの相対的品質を定義する一連の軟弱な制約の下で、従業員をシフトに割り当てる最適な方法を見つけるための問題である。
この問題は文献で大きな注目を集めており、多くの正確でメタヒューリスティックな方法によって解決されている。
人事ロスタリング問題に対するヒューリスティックの複雑かつコストのかかる設計を自動化するために,深層ニューラルネットワークと木探索を組み合わせた新しい手法を提案する。
スケジュールを行列として扱うことで、ニューラルネットワークは現在の解と最適な解の間の距離を予測することができる。
既存の(ほぼ)最適解を分析して、問題解決戦略を選択することができる。
分岐とバウンドを組み合わせることで、ネットワークは各ノードに、そのノードと最適なノードの距離を示す確率を与えることができるので、次にどのブランチを選択し、探索木を刈り取るかを適切に選択することができる。
関連論文リスト
- An Unsupervised Learning Framework Combined with Heuristics for the Maximum Minimal Cut Problem [5.092968949752308]
本研究は,MMCPの最大値と非教師なし学習フレームワークを提案する。
重要な観察は、それぞれの溶液が少なくとも1本の枝木に対応することである。
フレームワークを評価し、特定のアプリケーションを提供するために、広範な実験を行います。
論文 参考訳（メタデータ） (2024-08-16T02:07:34Z) - BalMCTS: Balancing Objective Function and Search Nodes in MCTS for
Constraint Optimization Problems [7.196057722218442]
制約問題最適化(COP)は、通常ブランチ・アンド・バウンド(B&B)法によって解決される問題において、複雑な課題を提起する。
COPを解くための深度優先探索アルゴリズムに基づく新しいニューラルネットワークアルゴリズムを提案する。
提案手法は,最初の5つの実現可能な解のうち17.63%未満のギャップを有する実現可能な解を同定する。
論文 参考訳（メタデータ） (2023-12-26T03:09:08Z) - Reinforcement Learning for Node Selection in Branch-and-Bound [52.2648997215667]
現在の最先端セレクタは手作りのアンサンブルを使用して、ナイーブなサブノードセレクタと、個々のノードデータに依存する学習ノードセレクタを自動的に切り替える。
孤立ノードではなく木の状態全体を考慮しながら強化学習(RL)を用いる新しいシミュレーション手法を提案する。
論文 参考訳（メタデータ） (2023-09-29T19:55:56Z) - Interpretable Decision Tree Search as a Markov Decision Process [8.530182510074983]
教師付き学習タスクに最適な決定木を見つけることは、大規模に解決する上で難しい問題である。
近年、マルコフ決定問題 (MDP) としてこの問題の枠組みを定め、深層強化学習を用いてスケーリングに取り組むことが提案されている。
そこで我々は,全ての状態に対して生成する情報理論テスト生成関数を用いて,MDPの分解能を拡大する手法を提案する。
論文 参考訳（メタデータ） (2023-09-22T08:18:08Z) - TreeDQN: Learning to minimize Branch-and-Bound tree [78.52895577861327]
Branch-and-Boundは、Mixed Linear Programsという形で最適化タスクを解決するための便利なアプローチである。
解法の効率は、分割する変数を選択するのに使用される分岐に依存する。
分岐を効率的に学習できる強化学習法を提案する。
論文 参考訳（メタデータ） (2023-06-09T14:01:26Z) - Let the Flows Tell: Solving Graph Combinatorial Optimization Problems
with GFlowNets [86.43523688236077]
組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。
GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。
本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
論文 参考訳（メタデータ） (2023-05-26T15:13:09Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。
本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。
ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
論文 参考訳（メタデータ） (2021-12-03T14:23:05Z) - Learning Robust Scheduling with Search and Attention [6.217548079545464]
物理層リソースをチャネル品質、バッファサイズ、要求および制約に基づいてユーザに割り当てることは、無線リソースの管理における中心的な最適化問題の1つである。
MU-MIMOスケジューリングでは、スケジューラが複数のユーザを同じ時間周波数の物理リソースに割り当てることができる。
本稿では,MU-MIMOスケジューリング問題を木構造問題として扱うとともに,AlphaGo Zeroの最近の成功から借用して,最高の実行ソリューションを探す可能性について検討する。
論文 参考訳（メタデータ） (2021-11-15T20:46:26Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Neural Learning of One-of-Many Solutions for Combinatorial Problems in
Structured Output Spaces [20.101005623256626]
複数のソリューションの存在に消極的であることは、トレーニング能力を著しく損なう可能性がある、と私たちは主張する。
本稿では、既存の予測ネットワークをRL問題に適用し、解乗法を扱う汎用学習フレームワークを提案する。
論文 参考訳（メタデータ） (2020-08-27T08:37:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。