Timezone: »

Learning to Perform Local Rewriting for Combinatorial Optimization
Xinyun Chen · Yuandong Tian

Tue Dec 10 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #178

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 three 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.

Author Information

Xinyun Chen (UC Berkeley)
Yuandong Tian (Facebook AI Research)

More from the Same Authors