Combinatorial Optimization and Schedule Generation Using Deep Bipartite Assignment

Thumbnail Image
Salgo, Alexander
AI , Machine Learning , Combinatorial Optimization , Operations Research , Scheduling , WTA , NSP , Nurse Scheduling Problem , Deep Reinforcement Learning , Deep Learning , Attention , Bipartite Assignment , Assignment Problems , Neural Networks
Recent advances in deep reinforcement learning (DRL) have allowed it to contribute to areas which were previously the domain of traditional algorithms. Operations research (OR), however, has lagged behind in this respect. OR problems often involve data with properties that are difficult for deep learning techniques to handle, and there is a concomitant lack of background research to draw from when designing new DRL approaches in this area. A 2019 paper introduced Deep Bipartite Assignment (DBA), a neural network architecture which allows DRL to be applied to simple bipartite assignment problems such as the Weapon-Target Assignment problem (WTA). In this work, we accomplish two objectives. First, we demonstrate that DBA can be extended to address more complex scheduling problems, including the Nurse Scheduling Problem and the Spatio-Temporal WTA. Second, we use DBA as a starting point to research the effects of various design choices on performance when solving scheduling and assignment problems using DRL. We identify patterns in hyperparameter choice, network structure, and training algorithm choice which can be used by future researchers to design better performing DRL agents for OR problems.
External DOI