Combining Reinforcement Learning and Configuration Checking for Maximum
  k-plex Problem
  The Maximum k-plex Problem is an important combinatorial optimization problem
with increasingly wide applications. Due to its exponential time complexity,
many heuristic methods have been proposed which can return a good-quality
solution in a reasonable time. However, most of the heuristic algorithms are
memoryless and unable to utilize the experience during the search. Inspired by
the multi-armed bandit (MAB) problem in reinforcement learning (RL), we propose
a novel perturbation mechanism named BLP, which can learn online to select a
good vertex for perturbation when getting stuck in local optima. To our best of
knowledge, this is the first attempt to combine local search with RL for the
maximum $ k $-plex problem.
  Besides, we also propose a novel strategy, named Dynamic-threshold
Configuration Checking (DTCC), which extends the original Configuration
Checking (CC) strategy from two aspects.
  Based on the BLP and DTCC, we develop a local search algorithm named BDCC and
improve it by a hyperheuristic strategy. The experimental result shows that our
algorithms dominate on the standard DIMACS and BHOSLIB benchmarks and achieve
state-of-the-art performance on massive graphs.
