Bandit-based Variable Fixing for Binary Optimization on GPU Parallel Computing
抄録
This paper explores whether reinforcement learning is capable of enhancing metaheuristics for the quadratic unconstrained binary optimization (QUBO), which have recently attracted attention as a solver for a wide range of combinatorial optimization problems. In particular, we introduce a novel approach called the bandit-based variable fixing (BVF). The key idea behind BVF is to regard an execution of an arbitrary metaheuristic with a variable fixed as a play of a slot machine. Thus, BVF explores variables to fix with the maximum expected reward, and executes a metaheuristic at the same time. The bandit-based approach is then extended to fix multiple variables. To accelerate solving multi-armed bandit problem, we implement a parallel algorithm for BVF on a GPU. Our results suggest that our proposed BVF enhances original metaheuristics.
31st Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP), 01-03 March 2023, Naples, Italy.
収録刊行物
-
- 2023 31st Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP)
-
2023 31st Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP) 2023-03
IEEE
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1050015333085580416
-
- HANDLE
- 2433/284024
-
- 本文言語コード
- en
-
- 資料種別
- conference paper
-
- データソース種別
-
- IRDB