Reinforcement Learning for the Knapsack Problem

Reinforcement Learning for the Knapsack Problem

Pierotti, J. (TU Delft Discrete Mathematics and Optimization)
Kronmueller, Maximilian
Alonso-Mora, J. (TU Delft Learning & Autonomous Control)
van Essen, J.T. (TU Delft Discrete Mathematics and Optimization)
Böhmer, J.W. (TU Delft Algorithmics)

2021

Combinatorial optimization (CO) problems are at the heart of both practical and theoretical research. Due to their complexity, many problems cannot be solved via exact methods in reasonable time; hence, we resort to heuristic solution methods. In recent years, machine learning (ML) has brought immense benefits in many research areas, including heuristic solution methods for CO problems. Among ML methods, reinforcement learning (RL) seems to be the most promising method to find good solutions for CO problems. In this work, we investigate an RL framework, whose agent is based on self-attention, to achieve solutions for the knapsack problem, which is a CO problem. Our algorithm finds close to optimal solutions for instances up to one hundred items, which leads to conjecture that RL and self-attention may be major building blocks for future state-of-the-art heuristics for other CO problems.

End-to-end
Knapsack problem
Multi-task DQN
Reinforcement learning
Self-attention
Transformer

http://resolver.tudelft.nl/uuid:50c89fbd-7270-49db-bd9c-0ef49efb66bc

https://doi.org/10.1007/978-3-030-86286-2_1

Springer Nature

2023-07-01

AIRO Springer Series

AIRO Springer Series, 2523-7047, 6

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Institutional Repository

book chapter

© 2021 J. Pierotti, Maximilian Kronmueller, J. Alonso-Mora, J.T. van Essen, J.W. Böhmer