Learning to Perform Local Rewriting for Combinatorial Optimization

By Xinyun Chen, Yuandong Tian. Neural Information Processing Systems, 2018

433 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Software

View Paper: https://www.semanticscholar.org/paper/f2b840c3c14b9f05106589c1be0a2dd4a494c0ba

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Denny Zhou
2. Xinyun Chen
3. Quoc V. Le
4. Yiming Yang
5. Hanxiao Liu
6. Jianfeng Gao
7. Xuezhi Wang
8. Luke S. Zettlemoyer

In Computer Networks and Communications

1. Denny Zhou
2. Yiming Yang
3. Zhiqing Sun
4. Xinyun Chen
5. Quoc V. Le
6. Jie Zhang
7. Wenhu Chen

In Software

1. Yiming Yang
2. Zhiqing Sun
3. Xinyun Chen
4. Quoc V. Le
5. Denny Zhou

Citations in the corpus

• DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization (2023, methodology): “Methods in the third category (improvement heuristics solvers) use a Markov decision process (MDP) to iteratively refines an existing feasible solution with neural network-guided local operations such as 2-opt [71, 2] and node swap [17, 113].”
• Large Language Models as Optimizers (2023, background): “…including heuristic algorithms and solvers (Rosenkrantz et al., 1977; Golden et al., 1980; Optimization et al., 2020; Applegate et al., 2006; Helsgaun, 2017), and approaches based on training deep neural networks (Kool et al., 2019; Deudon et al., 2018; Chen & Tian, 2019; Nazari et al., 2018).”
• POMO: Policy Optimization with Multiple Optima for Reinforcement Learning (2020, background): “[12] for TSP and Chen & Tian [13], Hottung & Tierney [14],”
• Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning (2020, methodology): “First, unlike previous works [23, 24, 25], it is not hard bounded by the instance size (|J | and |M|), since all parameters are shared across all nodes in the graph.”