%0 Journal Article %1 chen2018learning %A Chen, Xinyun %A Tian, Yuandong %D 2018 %K combinatorics optimization %T Learning to Perform Local Rewriting for Combinatorial Optimization %U http://arxiv.org/abs/1810.00337 %X 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.

@article{chen2018learning, 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.}, added-at = {2019-09-04T16:03:57.000+0200}, author = {Chen, Xinyun and Tian, Yuandong}, biburl = {https://www.bibsonomy.org/bibtex/21e359bbbe8e94098a48261c0335511a1/kirk86}, description = {[1810.00337] Learning to Perform Local Rewriting for Combinatorial Optimization}, interhash = {6f48d6d11cde7030216799061bf909de}, intrahash = {1e359bbbe8e94098a48261c0335511a1}, keywords = {combinatorics optimization}, note = {cite arxiv:1810.00337}, timestamp = {2019-09-04T16:03:57.000+0200}, title = {Learning to Perform Local Rewriting for Combinatorial Optimization}, url = {http://arxiv.org/abs/1810.00337}, year = 2018 }