Nonuniform Neighborhood Sampling Based Simulated Annealing for the Directed Feedback Vertex Set Problem

Abstract

The feedback vertex set problem (FVSP), a combinatorial optimization problem, finds a set of vertices that intersect all cycles of the directed graph. One of the cutting-edge heuristics for this problem is a simulated annealing (SA)-based algorithm named the SA-FVSP. In this paper, we propose an improved variant of the SA-FVSP by applying the nonuniform neighborhood sampling (NNS), namely, the SA-FVSP-NNS. The NNS is a general strategy for improving the SA-based algorithm. Its basic idea is to prioritize the neighbors which are closer to the global optimum by assigning them with higher sampling probabilities. By doing this, these neighbors are more likely to be selected in the sampling process. To apply this general strategy to the SA-FVSP, we propose the concepts of the priority function and the sampling function, respectively. The priority function utilizes the known heuristic rules of the FVSP to estimate and score the quality of neighbors, while the sampling function converts the scores computed by the priority function to sampling probabilities, which can directly guide the NNS process. Experiments indicate that the SA-FVSP-NNS algorithm outperforms the SA-FVSP.

Keywords

• Feedback vertex set
• simulated annealing
• nonuniform neighborhood sampling