Learning to Perform Local Rewriting for Combinatorial Optimization

2018/09/30 by Xinyun Chen, Yuandong Tian, Chen, Xinyun +1 · 156 citations
Computer Science · Mathematics · #Artificial Intelligence (cs.AI) #Artificial intelligence #Computer science #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #Logic, programming, and type systems #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Mathematics #Model-Driven Software Engineering Techniques #Programming language #Rewriting #Theoretical computer science #cs.AI #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.1810.00337

published in arXiv (Cornell University) (Cornell University) · Published in NeurIPS 2019

openalex publication_date 2018/09/30 · arxiv created 2019/10/30 · arxiv updated 2019/10/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Playing Atari with Deep Reinforcement Learning
• Learning to Discover Efficient Mathematical Identities
• Reinforcement Learning with Deep Energy-Based Policies
• Learning Combinatorial Optimization Algorithms over Graphs
• Approximating meta-heuristics with homotopic recurrent neural networks
• Learning a SAT Solver from Single-Bit Supervision
• Attention, Learn to Solve Routing Problems!
• Learning Heuristics for Quantified Boolean Formulas through Deep Reinforcement Learning

Cited by

• Learning-Optimized Qubit Mapping and Reuse to Minimize Inter-Core Communication in Modular Quantum Architectures
• 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
• Synergizing Reinforcement Learning and Genetic Algorithms for Neural Combinatorial Optimization
• 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
• Preference-Driven Multi-Objective Combinatorial Optimization with Conditional Computation
• Learning for routing: A guided review of recent developments and future directions
• Beyond Simple Graphs: Neural Multi-Objective Routing on Multigraphs
• EFormer: An Effective Edge-based Transformer for Vehicle Routing Problems
• Latent Guided Sampling for Combinatorial Optimization
• Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning
• DOPPLER: Dual-Policy Learning for Device Assignment in Asynchronous Dataflow Graphs
• Learning to Insert for Constructive Neural Vehicle Routing Solver
• Beyond Solving: Prescriptive Probing for Neural Routing Solvers
• Algorithm Discovery With LLMs: Evolutionary Search Meets Reinforcement Learning
• Heterogeneous Attentions for Solving Pickup and Delivery Problem via Deep Reinforcement Learning

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