“Learning to Perform Local Rewriting for Combinatorial Optimization”, 2018-09-30 (; backlinks; similar):
Search-based methods for hard combinatorial optimization are often guided by heuristics. Tuning heuristics in various conditions and situations is often time-consuming.
In this paper, we propose NeuRewriter that learns a policy to pick heuristics and rewrite the local components of the current solution to iteratively improve it until convergence. The policy factorizes into a region-picking and a rule-picking component, each parameterized by a neural network trained with actor-critic methods in reinforcement learning.
NeuRewriter captures the general structure of combinatorial problems and shows strong performance in 3 versatile tasks: expression simplification, online job scheduling, and vehicle routing problems.
NeuRewriter outperforms the expression simplification component in Z3; outperforms DeepRM and Google OR-tools in online job scheduling; and outperforms recent neural baselines and Google OR-tools in vehicle routing problems.