Learning to Perform Local Rewriting for Combinatorial Optimization

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.

arXiv commentPublished in NeurIPS 2019

References in corpus (14)

• Playing Atari with Deep Reinforcement Learning
• Learning Combinatorial Optimization Algorithms over Graphs
• Reinforcement Learning with Deep Energy-Based Policies
• Learning to Optimize Tensor Programs
• Attention, Learn to Solve Routing Problems!
• Learning a SAT Solver from Single-Bit Supervision
• Sentence Compression as Tree Transduction
• GamePad: A Learning Environment for Theorem Proving
• Learning Continuous Semantic Representations of Symbolic Expressions
• Learning to Discover Efficient Mathematical Identities
• Adaptive Neural Compilation
• Deep Reinforcement Learning for Multi-Resource Multi-Machine Job Scheduling
• Learning Heuristics for Quantified Boolean Formulas through Deep Reinforcement Learning
• Approximating meta-heuristics with homotopic recurrent neural networks

Cited by in corpus (14)

• Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problem
• Heterogeneous Attentions for Solving Pickup and Delivery Problem via Deep Reinforcement Learning
• Location-routing Optimisation for Urban Logistics Using Mobile Parcel Locker Based on Hybrid Q-Learning Algorithm
• Route Planning for Last-Mile Deliveries Using Mobile Parcel Lockers: A Hybrid Q-Learning Network Approach
• Deep reinforcement learning for machine scheduling: Methodology, the state-of-the-art, and future directions
• Neural Airport Ground Handling
• Efficient Neural Neighborhood Search for Pickup and Delivery Problems
• One model Packs Thousands of Items with Recurrent Conditional Query Learning
• Learning for routing: A guided review of recent developments and future directions
• Optimizing Nurse Scheduling: A Supply Chain Approach for Healthcare Institutions
• Reinforcement Learning Enhanced Quantum-inspired Algorithm for Combinatorial Optimization
• Neural Heterogeneous Scheduler
• Learning Heuristics for Transit Network Design and Improvement with Deep Reinforcement Learning
• Learning Markov Random Fields for Combinatorial Structures via Sampling through Lovász Local Lemma