Probability learning based tabu search for the budgeted maximum coverage problem

作者：

Highlights：

• We are the first to address the NP-hard Budgeted Maximum Coverage Problem.

• We propose an algorithm that combines reinforcement learning with local search.

• We introduce the first set of benchmark instances for the problem.

• The proposed algorithm outperforms the comparison algorithms and the CPLEX solver.

摘要

•We are the first to address the NP-hard Budgeted Maximum Coverage Problem.•We propose an algorithm that combines reinforcement learning with local search.•We introduce the first set of benchmark instances for the problem.•The proposed algorithm outperforms the comparison algorithms and the CPLEX solver.

论文关键词：Budgeted maximum coverage problem,Learning-based optimization,Tabu search,Combinatorial optimization

论文评审过程：Received 18 November 2020, Revised 29 May 2021, Accepted 30 May 2021, Available online 13 June 2021, Version of Record 25 June 2021.

论文官网地址：https://doi.org/10.1016/j.eswa.2021.115310