Combinatorial Reinforcement Learning of Linear Assignment Problems
| Autor: | Klaus Bogenberger, Bernd Kaltenhäuser, P. Franeck, Sascha Hamzehi |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Theoretical computer science
Matching (graph theory) Linear programming Computer science 02 engineering and technology 010501 environmental sciences Decision problem 01 natural sciences k-nearest neighbors algorithm Cardinality 0202 electrical engineering electronic engineering information engineering Bipartite graph Reinforcement learning 020201 artificial intelligence & image processing Pairwise comparison 0105 earth and related environmental sciences |
| Zdroj: | ITSC |
| DOI: | 10.1109/itsc.2019.8916920 |
| Popis: | Recent growing interest in Artificial Intelligence (AI) and platform-based autonomous fleet management systems support the algorithmic research of new means for dynamic and large-scale fleet management. At the same time, recent advancements in deep and reinforcement learning confirm promising results by solving large-scale and complex decision problems and might provide new context sensitive benefits for optimization. In this paper, we solve a residing combinatorial optimization problem commonly known as graph-based pairwise assignment, maximum bipartite cardinality matching, min-cut, or max-sum problem by the application of reinforcement learning in comparison with traditional linear programming algorithms. We provide simulative quantitative and qualitative results regarding by solving symmetric and asymmetric bipartite graphs with multiple algorithms. Particularly, the comparison includes solutions of Cplex, Hungarian-Munkres-Kuhn, Jonker Volgenant and Nearest Neighbor algorithm to reinforcement learning-based algorithms such as Q-learning and Sarsa algorithms. Finally, we show that reinforcement learning can solve small symmetric bipartite maximum matching problems close to linear programming quality, depending on the available processing time and graph size, but on the other hand is outperformed for large-scale asymmetric problems by linear programming-based and nearest neighbor-based algorithms subject to the constraint of achieving conflict-free solutions. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|