1143. Computational Analysis of DQN for the Binary Knapsack Problem
Invited abstract in session MC-4: Data science meets strongly NP-Hard CO, stream Data Science meets Optimization.
Monday, 12:30-14:00Room: Rupert Beckett LT
Authors (first author is the speaker)
| 1. | Woo Seok Goh
|
| Industrial Engineering, Seoul National University | |
| 2. | Seyoung Oh
|
| Industrial engineering, Seoul National University | |
| 3. | Kyungsik Lee
|
| Industrial Engineering, Seoul National University |
Abstract
In recent years, deep reinforcement learning (DRL) has been extensively applied to solve NP-hard combinatorial optimization problems (COPs), often achieving high-quality solutions. However, an in-depth investigation into DRL's performance has not been sufficiently addressed. In this work, we focus specifically on an end-to-end Deep Q-Network (DQN) approach tailored for NP-hard COPs. The binary knapsack problem is selected as our test suite for NP-hard COPs, since its true Q-values can be computed in pseudo-polynomial time, allowing a comprehensive performance analysis. We implement the Q-network using two different architectures: a multi-layer perceptron and a graph neural network. We evaluate the solution quality and computational efficiency of DQN. Additionally, we investigate the accuracy of the estimated Q-values from three perspectives: proximity to the true Q-values, consistency in the relative ordering of Q-values, and correctness in optimal action selection. Overall, our research deepens the knowledge of how DQN addresses NP-hard COPs, offering insights into its effectiveness and reliability.
Keywords
- Combinatorial Optimization
- Machine Learning
Status: accepted
Back to the list of papers