Improving local search for the weighted sum coloring problem using the branch-and-bound algorithm

作者：

Highlights：

• Novel branching heuristics and lower bound based on weighted clique partitioning for weighted sum coloring problem.

• An efficient branch-and-bound algorithm BABWSCP for weighted sum coloring problem.

• A paradigm of improving local search using branch-and-bound for weighted sum coloring problem.

• An algorithm BABLS by improving the local search algorithm CCLSWSC using the branch-and-bound algorithm BABWSCP.

摘要

•Novel branching heuristics and lower bound based on weighted clique partitioning for weighted sum coloring problem.•An efficient branch-and-bound algorithm BABWSCP for weighted sum coloring problem.•A paradigm of improving local search using branch-and-bound for weighted sum coloring problem.•An algorithm BABLS by improving the local search algorithm CCLSWSC using the branch-and-bound algorithm BABWSCP.

论文关键词：Combinatorial optimization,Weighted sum coloring,Branch-and-bound,Heuristics,Local search

论文评审过程：Received 30 December 2021, Revised 13 March 2022, Accepted 28 March 2022, Available online 1 April 2022, Version of Record 23 April 2022.

论文官网地址：https://doi.org/10.1016/j.knosys.2022.108703