Determining Destroy Sets in Large Neighborhood Search by Generative Flow Networks

Abstract

Large Neighborhood Search (LNS) is an often applied metaheuristic for solving challenging combinatorial optimization problems. Typically, it relies on the scheme of iteratively removing parts of a solution by one or more destroy operators and cleverly augmenting the solution again by repair operators. Destroy operators are usually handcrafted and often a mixture of uniform random selection and problem-specific heuristics, and their choice can dramatically impact the performance. Inspired by the recent success of Generative Flow Networks (GFlowNets), we propose their usage to compile promising destroy sets. These generative deep learning models stand out in that their goal is not to learn a single high-reward structure but to produce diverse structures according to a complex probability density function. As considering many different but promising destroy sets is fundamental in LNS, we believe GFlowNets to be well suited for this purpose. We study an intentionally generic and simple LNS framework and apply it to three hard graph problems. The only problem-specific part is the repair operator that is realized by basic iterated random construction heuristics. When applying the best GFlowNet model, the effectiveness of the LNS is on average increased by 6.52% in terms of online performance compared to a corresponding baseline LNS. Moreover, a comparison to integer linear programming models solved by Gurobi shows that they are clearly dominated by our GFlowNet-guided LNS on the considered hard benchmark instances with a mean relative improvement of 20.73% in terms of final solution quality.