# Exploratory Combinatorial Optimization with Reinforcement Learning

@article{Barrett2020ExploratoryCO, title={Exploratory Combinatorial Optimization with Reinforcement Learning}, author={Thomas D. Barrett and William R. Clements and Jakob N. Foerster and A. I. Lvovsky}, journal={ArXiv}, year={2020}, volume={abs/1909.04063} }

Many real-world problems can be reduced to combinatorial optimization on a graph, where the subset or ordering of vertices that maximize some objective function must be found. With such tasks often NP-hard and analytically intractable, reinforcement learning (RL) has shown promise as a framework with which efficient heuristic methods to tackle these problems can be learned. Previous works construct the solution subset incrementally, adding one element at a time, however, the irreversible nature… Expand

#### 28 Citations

Reversible Action Design for Combinatorial Optimization with Reinforcement Learning

- Computer Science
- ArXiv
- 2021

This work utilizes graph neural networks (GNN) to extract latent representations for given problem instances for state-action encoding, and applies deep Q-learning to obtain a policy that gradually refines the solution by flipping or swapping vertex labels. Expand

Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time

- Computer Science, Mathematics
- 2020 19th IEEE International Conference on Machine Learning and Applications (ICMLA)
- 2020

This work develops a new framework to solve any combinatorial optimization problem over graphs that can be formulated as a single player game defined by states, actions, and rewards, including minimum spanning tree, shortest paths, traveling salesman problem, and vehicle routing problem, without expert knowledge. Expand

Solving Combinatorial Problems through Off-Policy Reinforcement Learning Methods

- Computer Science
- 2020 International Conference on Electrical, Communication, and Computer Engineering (ICECCE)
- 2020

This work proves the applicability of RL algorithms to combinatorial puzzles such as river-crossing puzzle and seating arrangement problems and applies quality-networks, deep-quality-nets, and double-deep-nets to environments mentioned above, and concludes that all these methods effectively completed the puzzle tasks with unnoticeable performance differences for the given environments. Expand

Zero Training Overhead Portfolios for Learning to Solve Combinatorial Problems

- Computer Science
- ArXiv
- 2021

ZTopping, i.e., using a ZTop ensemble strategy with a given deep learning approach, can significantly improve the performance of the current state-ofthe-art deep learning approaches on three prototypical CO domains, the hardest unique-solution Sudoku instances, challenging routing problems, and the graph maximum cut problem. Expand

Reinforcement Learning Enhanced Quantum-inspired Algorithm for Combinatorial Optimization

- Computer Science, Mathematics
- Mach. Learn. Sci. Technol.
- 2021

A reinforcement learning agent is used in conjunction with a quantum-inspired algorithm to solve the Ising energy minimization problem, which is equivalent to the Maximum Cut problem and outperforms both baseline heuristics and a black-box hyperparameter optimization approach. Expand

Learning Combinatorial Optimization on Graphs: A Survey With Applications to Networking

- Computer Science, Mathematics
- IEEE Access
- 2020

This work organizes and compares the structures involved with learning to solve combinatorial optimization problems, with a special eye on the telecommunications domain and its continuous development of live and research networks. Expand

Hybrid Heuristic Algorithm Based On Improved Rules & Reinforcement Learning for 2D Strip Packing Problem

- Computer Science
- IEEE Access
- 2020

A hybrid heuristic algorithm based on improved rules and reinforcement learning is proposed to solve the 2D strip packing problem (2DSPP) and it is concluded that the RSRA algorithm would achieve better performance than the other four algorithms on eight datasets, especially on the larger datasets. Expand

An IP Core Mapping Algorithm Based on Neural Networks

- Computer Science
- IEEE Transactions on Very Large Scale Integration (VLSI) Systems
- 2021

Simulation results show that the MPNN-Ptr networks can effectively model the IP core mapping and achieves a 7.90% communication cost reduction on average than the classic mapping algorithm: NMAP. Expand

Quantum-inspired annealers as Boltzmann generators for machine learning and statistical physics

- Computer Science, Physics
- ArXiv
- 2019

This study implements a numerical annealer based on simulating the coherent Ising machine as a tool to sample from a high-dimensional Boltzmann probability distribution with the energy functional defined by the classical Ising Hamiltonian. Expand

Reinforcement Learning for Combinatorial Optimization: A Survey

- Computer Science, Mathematics
- Comput. Oper. Res.
- 2021

This survey explores the synergy between the CO and RL frameworks, which can become a promising direction for solving combinatorial problems. Expand

#### References

SHOWING 1-10 OF 42 REFERENCES

Learning Combinatorial Optimization Algorithms over Graphs

- Computer Science, Mathematics
- NIPS
- 2017

This paper proposes a unique combination of reinforcement learning and graph embedding that behaves like a meta-algorithm that incrementally constructs a solution, and the action is determined by the output of agraph embedding network capturing the current state of the solution. Expand

Neural Combinatorial Optimization with Reinforcement Learning

- Computer Science, Mathematics
- ICLR
- 2017

A framework to tackle combinatorial optimization problems using neural networks and reinforcement learning, and Neural Combinatorial Optimization achieves close to optimal results on 2D Euclidean graphs with up to 100 nodes. Expand

Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search

- Computer Science, Mathematics
- NeurIPS
- 2018

Experimental results demonstrate that the presented approach substantially outperforms recent deep learning work, and performs on par with highly optimized state-of-the-art heuristic solvers for some NP-hard problems. Expand

Learning Heuristics over Large Graphs via Deep Reinforcement Learning

- Computer Science, Mathematics
- ArXiv
- 2019

This paper proposes a deep reinforcement learning framework called GCOMB, which is more than 100 times faster than the state of the art while retaining the same quality of the solution sets, and applies this framework to the popular and challenging data mining problem of Influence Maximization. Expand

Solving NP-Hard Problems on Graphs by Reinforcement Learning without Domain Knowledge

- Computer Science, Mathematics
- ArXiv
- 2019

An algorithm based on reinforcement learning for solving NP-hard problems on graphs that combines Graph Isomorphism Networks and the Monte-Carlo Tree Search for solving combinatorial optimization on graphs is proposed. Expand

A Reinforcement Learning Approach to job-shop Scheduling

- Computer Science
- IJCAI
- 1995

Reinforcement learning methods are applied to learn domain-specific heuristics for job shop scheduling to suggest that reinforcement learning can provide a new method for constructing high-performance scheduling systems. Expand

Reverse quantum annealing approach to portfolio optimization problems

- Physics, Economics
- Quantum Mach. Intell.
- 2019

The best results in terms of expected time-to-solution as a function of number of variables for the hardest instances set are obtained by seeding the quantum annealer with a solution candidate found by a greedy local search and then performing a reverse annealing protocol. Expand

Breakout Local Search for the Max-Cutproblem

- Computer Science
- Eng. Appl. Artif. Intell.
- 2013

Given an undirected graph G=(V,E) where each edge of E is weighted with an integer number, the maximum cut problem (Max-Cut) is to partition the vertices of V into two disjoint subsets so as to… Expand

Breakout Local Search for the Max-Cut Problem

- Mathematics
- 2014

Given an undirected graph G = (V,E) where each edge of E is weighted with an integer number, the maximum cut problem (Max-Cut) is to partition the vertices of V into two disjoint subsets so as to… Expand

The Design of Approximation Algorithms

- Computer Science, Mathematics
- 2011

This book shows how to design approximation algorithms: efficient algorithms that find provably near-optimal solutions to discrete optimization problems. Expand