Learning to Perform Local Rewriting for Combinatorial Optimization

2018/09/30 by Chen, Xinyun, Tian, Yuandong · 13 citations
#Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1810.00337

Abstract

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.

Cited by

• HeatACO: A Heatmap-Guided Max--Min Ant System for Large-Scale Travelling Salesman Problems
• Deep Learning--Accelerated Multi-Start Large Neighborhood Search for Real-time Freight Bundling
• A Unified Deep Reinforcement Learning Approach for Close Enough Traveling Salesman Problem
• Multi-Task Vehicle Routing Solver via Mixture of Specialized Experts under State-Decomposable MDP
• Empowering Targeted Neighborhood Search via Hyper Tour for Large-Scale TSP
• LM-GRASP: Instance-Specific Language Models for Combinatorial Construction via Online Imitation Learning
• Iterative In-Context Learning to Enhance LLMs Abstract Reasoning: The Case-Study of Algebraic Tasks
• Edge-Selector Model Applied for Local Search Neighborhood for Solving Vehicle Routing Problems
• POMO+: Leveraging starting nodes in POMO for solving Capacitated Vehicle Routing Problem
• Lifelong Learner: Discovering Versatile Neural Solvers for Vehicle Routing Problems
• Parametrized Multi-Agent Routing via Deep Attention Models
• Efficient Neural Combinatorial Optimization Solver for the Min-max Heterogeneous Capacitated Vehicle Routing Problem
• Learning neuro-symbolic convergent term rewriting systems

Related

• SOLO: Search Online, Learn Offline for Combinatorial Optimization Problems
• Reinforcement Learning for Combinatorial Optimization: A Survey
• Learning with Local Search MCMC Layers
• Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch
• PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimization