Source-linked AI summary
Learning to Perform Local Rewriting for Combinatorial Optimization
Xinyun Chen, Yuandong Tian
TL;DR
Hard combinatorial optimization often depends on heuristics whose tuning is time-consuming. NeuRewriter learns reinforcement-learning policies for local region and rule selection, iteratively rewriting solutions. It outperforms heuristic-based software and neural baselines across the evaluated domains.
Problem
Many NP-hard combinatorial problems rely on manually designed heuristics, whose application and prioritization are time-consuming to determine.
Method
NeuRewriter learns separate region-picking and rule-picking policies to iteratively rewrite local parts of a current solution using reinforcement learning.
Results
NeuRewriter outperforms heuristic-based algorithms and baseline neural networks that generate complete solutions across multiple evaluated domains.
Takeaways & Limitations
The evaluation demonstrates the effectiveness of neural rewriting across expression simplification, online job scheduling, and vehicle routing.
Takeaways & Limitations
Local rewriting can become time-consuming when each iteration requires large changes, making starting from scratch preferable when global restructuring is needed.
Abstract
from arXiv · showhide
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.
1 Introduction
NeuRewriter addresses the time-consuming design and tuning of heuristics by learning to iteratively rewrite local parts of solutions. It is evaluated across expression simplification, online job scheduling, and vehicle routing.
- Manual heuristic design requires deciding when, where, and how to prioritize routines, a process that can take commercial solvers decades to tune.
- Directly predicting complete solutions can become difficult as the number of variables grows, while gradient-guided iterative improvement does not apply directly to discrete spaces.
- NeuRewriter learns a reinforcement-learning policy that selects regions and rewriting rules to improve local solution components until convergence.
- The approach is tested on expression simplification, online job scheduling, and vehicle routing problems.
- NeuRewriter outperforms the expression simplification component in Z3; the supplied passage does not include the remaining online-scheduling comparison.
2 Related Work
Related work contrasts direct solution generation and gradient-based optimization with NeuRewriter’s reinforcement-learned local rewriting. The framework connects learned policies with local search and addresses limitations of supervised expression rewriting.
- Neural combinatorial-optimization methods often construct complete solutions directly, but complex configurations can make this difficult.
- Gradient-based trajectory optimization is effective for continuous spaces, whereas discrete problems create difficulties because local rewriting is not differentiable.
- NeuRewriter uses a learned reinforcement-learning policy to guide which neighboring solution local search should visit.
- For expression simplification, supervised rewriting requires ground-truth rewriting paths and may not discover novel routines; reinforcement learning is used to mitigate these limitations.
- The paper evaluates neural approaches in job scheduling and vehicle routing alongside prior work on those tasks.
3 Problem Setup
The paper formulates optimization as sequential local rewriting from an initial feasible solution, with separate policies selecting regions and applicable rules. It motivates this formulation by limitations of manually designed routines.
- The rewriting formulation starts from a feasible solution and incrementally improves it by applying local rules until convergence.
- It is especially suited to problems where feasible solutions are easy to find and local structures support incremental improvement.
- Each solution is a state, while a local region together with its rewriting rule forms an action.
- At each iteration, separate policies select a state-dependent region and an applicable rule, producing the next state and ultimately minimizing final cost.
- Manually designed routines can be incomplete, inefficient to search, cumbersome to maintain, and inflexible.
- Reinforcement learning is proposed to train the neural rewriter and explore rewriting paths beyond manually designed routines.
4 Neural Rewriter Model
NeuRewriter treats optimization as iterative local rewriting: it selects a state-dependent region, chooses an applicable rule, and updates the solution. Region and rule policies are trained jointly with reinforcement learning to reward cumulative cost improvement.
- Model Overview: The score predictor evaluates every candidate region, while the rule selector predicts a distribution over the complete ruleset.Candidate regions are problem-dependent and can include expression subtrees, scheduling jobs, or route nodes.
- Training: Each rewriting step receives reward c(st) − c(st+1), so positive reward corresponds to reducing the task-specific cost.The cost function is defined separately for each application domain.
- Training: The region-picking policy is parameterized from Q(st, ωt), which is learned from cumulative rewards sampled under the current policies.The episode length is T and γ is the reward decay factor.
- Training: The rule-picking policy uses Advantage Actor-Critic with the learned Q function as critic, and the joint loss is Lu(φ)+αLω(θ).The formulation avoids bootstrapping for the rule selector and trains both policies simultaneously.
5 Applications
The paper applies the rewriting framework to expression simplification, online job scheduling, and vehicle routing, adapting the state representation and ruleset to each domain. These applications use structured neural encoders and domain-specific local moves to improve complete solutions.
- Expression Simplification: Expression simplification minimizes Halide expression length using semantics-preserving rewriting templates over expression parse trees.The rule-based baseline contains hundreds of manually designed templates checked in a predefined order.
- Expression Simplification: Uphill rewriting rules can lengthen expressions before shortening them, helping escape local optima but requiring hard-to-generalize manual preconditions.The paper motivates neural decision-making as a way to learn these application conditions.
- Expression Simplification: The expression ruleset contains 19 categories, including simple rules and uphill rules with manually designed preconditions removed.The neural policy learns when to apply these core rules.
- Online Job Scheduling: Online job scheduling assumes fixed resource requirements, continuous non-preemptive execution, and a pending queue with capacity W.New jobs are either allocated immediately or added to the queue, with full queues requiring immediate scheduling of a queued job.
- Online Job Scheduling: Scheduling rewrites reschedule a job after another job finishes or at its arrival time, yielding a ruleset of size 2W.Each job can switch order with at most W preceding and W following jobs.
- Online Job Scheduling: Schedules are represented as DAGs whose nodes are jobs plus a machine node, with edges encoding job-start dependencies.A job starting at arrival time links from the machine node; otherwise, dependencies link from jobs finishing at its start time.
- Vehicle Routing: For CVRP, the method minimizes total route length while serving customer demands through depot-starting and depot-ending routes under vehicle capacity.Routes are embedded with a bidirectional LSTM, and local rules swap nodes in the route.
6 Experiments
Experiments evaluate NeuRewriter on expression simplification, online job scheduling, and vehicle routing, showing strong quality, efficiency, scalability, and generalization across varied settings.
- Expression Simplification: NeuRewriter reduces expression length and parse-tree size by around 52% and 59% on average, respectively.It further reduces average expression length and tree size by around 20% and 15% compared with rule-based rewriters.
- Expression Simplification: NeuRewriter outperforms Z3-ctx-solver-simplify in both result quality and time efficiency.This comparison holds despite Z3’s optimized C++ implementation and broader rewriting capabilities.
- Expression Simplification: Even when trained on short expressions, NeuRewriter remains comparable with Z3 on longer expressions and generalizes across data distributions.The evaluation trains on expressions capped at lengths 20, 30, 50, or 100, then tests on expressions longer than 100.
- Online Job Scheduling: NeuRewriter outperforms heuristic algorithms and DeepRM as resource-type complexity increases, while remaining much more time-efficient than OR-tools.Its runtime is comparable to DeepRM while achieving much better results, and it can outperform offline algorithms with full job-sequence knowledge.
- Online Job Scheduling: NeuRewriter excels across almost all job distributions, except uniform short or long job lengths where existing methods are sufficient.It also generalizes to distributions different from those used in training without substantial performance drop.
- Vehicle Routing: NeuRewriter balances vehicle-routing solution quality and runtime, especially on larger problems, and can generalize beyond training distributions.On different distributions, it exceeds classic heuristics and is sometimes comparable or better than OR-tools.
7 Conclusion
The paper formulates combinatorial optimization as iterative local rewriting and evaluates a neural rewriter across multiple domains. Its main limitation is that local rewriting can be slow when each step must make large structural changes.
- Conclusion: NeuRewriter formulates optimization as iterative rewriting of an existing solution toward the optimum.Deep reinforcement learning trains the neural rewriter to improve complete solutions across multiple domains.
- Conclusion: Across multiple domains, NeuRewriter outperforms heuristic algorithms and neural baselines that generate complete solutions directly.This evaluation supports the effectiveness of the neural-rewriter formulation.
- Conclusion: Local rewriting can become time-consuming when large changes are required at each iteration.If every rewriting step must change the global structure, starting from scratch may be preferable.
A More Details of the Dataset
NeuRewriter uses task-specific representations and neural components to select local regions and rewriting rules across expression simplification, job scheduling, and vehicle routing.
- Examples: The paper illustrates rewriting with Halide expressions, job schedules, and vehicle routes.The figures show expression reduction, job-graph schedule representations, and route-rewriting examples.
- Expression simplification: Expression simplification uses tree structure and whole-expression context to score sub-trees and select rewriting rules.Sub-tree inputs concatenate local and root embeddings, while the rule selector outputs probabilities over rewriting rules.
- Online job scheduling: Job embeddings encode resource requirements, machine usage during execution, and current-job slowdown.Each job is represented in a vector whose dimensions include resources, execution-time machine usage, zero padding, and slowdown.
- Online job scheduling: Job scheduling rewrites move a job under another job or the machine node, and the rule selector scores feasible parent choices.Graph nodes use parent states, and the selector predicts probabilities over possible moves.
- Vehicle routing: Vehicle-routing node embeddings combine location, normalized demand, previous-node information, distance, and remaining vehicle resources.The embedding has seven dimensions and includes both route context and capacity-related state.
D More Details on Training
During evaluation, NeuRewriter greedily selects the highest-probability region and rule, stopping when the predicted value is below a threshold or no rule applies.
- Inference: Evaluation selects the region and rewriting rule with maximum policy probability at each step.The forward pass uses arg max selection for both policy components.
- Inference: Inference terminates when Q(st, ωt; θ) < ϵ or the selected rule does not apply.This stopping criterion is specified for evaluation rather than training.
- Hyper-parameters: The iteration budget is 50 steps for expression simplification and job scheduling, and 200 for vehicle routing.The larger vehicle-routing budget addresses cases where 50 rewrites are insufficient for competitive solutions.
E More Results for Job Scheduling Problem
Job-scheduling evaluations examine solver behavior across job-frequency and resource distributions, as well as sensitivity to the quality of initial schedules.
- Baseline comparison: OR-tools is less effective than heuristic scheduling algorithms and neural approaches in this job-scheduling setting, especially with more resource types.The authors attribute observed schedules to OR-tools often prioritizing long jobs over short jobs.
- Ablations: The evaluation varies job-frequency and resource distributions in separate ablation studies.Tables 3 and 4 report these distribution-focused experiments.
- Initial schedules: Initial schedules are generated with different average slowdowns by randomly allocating jobs one at a time.This supplements earliest-job-first initialization.
- Initial schedules: With D = 20 resource types, final performance remains consistently better than other baselines despite differences in initial-schedule quality.The results indicate substantial improvement of initial solutions across the tested starting conditions.
F More Discussion of the Evaluation on Vehicle Routing Problem
Vehicle-routing experiments initialize routes with a nearest-feasible-node heuristic and evaluate rewriting across problem sizes and a cross-size generalization setting.
- Initialization: Initial routes visit the nearest feasible customer or return to the depot when capacity conditions require it.Average initial tour lengths are 7.74 for VRP20, 13.47 for VRP50, and 20.36 for VRP100.
- Evaluation: The vehicle-routing evaluation reports results for multiple problem sizes and includes an example of NeuRewriter’s rewriting steps.Table 6 contains routing results, while Figure 10 visualizes the rewriting process.
- Generalization: 17.33 average tour length on VRP100 follows training on VRP50, compared with 18.00 reported in [35].The authors present this as evidence that the approach could adapt to different problem distributions.
- Rewriting example: The VRP20 example reduces tour length from 7.31 initially to 5.98 after rewriting.Red edges mark the region selected for the next rewrite, and green edges mark already rewritten edges.
G More Results for Expression Simplification
Figures 11 and 12 show successful expression rewrites that simplify cases beyond both the Halide rule-based rewriter and the Z3 solver.
- The first example rewrites a complex inequality to 34 ≤ (v0 − v1 + 13)%35.
- The second example rewrites a nested minimum inequality to 136 ≤ (v0 − v1 + 12)%137.