A K-means Supported Reinforcement Learning Framework to Multi-dimensional Knapsack

Sabah Bushaj, Esra Büyüktahtakın

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

In this paper, we address the difficulty of solving large-scale multi-dimensional knapsack instances (MKP), presenting a novel deep reinforcement learning (DRL) framework. In this DRL framework, we train different agents compatible with a discrete action space for sequential decision-making while still satisfying any resource constraint of the MKP. This novel framework incorporates the decision variable values in the 2D DRL where the agent is responsible for assigning a value of 1 or 0 to each of the variables. To the best of our knowledge, this is the first DRL model of its kind in which a 2D environment is formulated, and an element of the DRL solution matrix represents an item of the MKP. Our framework is configured to solve MKP instances of different dimensions and distributions. We propose a K-means approach to obtain an initial feasible solution that is used to train the DRL agent. We train four different agents in our framework and present the results comparing each of them with the CPLEX commercial solver. The results show that our agents can learn and generalize over instances with different sizes and distributions. Our DRL framework shows that it can solve medium-sized instances at least 45 times faster in CPU solution time and at least 10 times faster for large instances, with a maximum solution gap of 0.28% compared to the performance of CPLEX. Furthermore, at least 95% of the items are predicted in line with the CPLEX solution. Computations with DRL also provide a better optimality gap with respect to state-of-the-art approaches.

Original languageEnglish (US)
Pages (from-to)655-685
Number of pages31
JournalJournal of Global Optimization
Volume89
Issue number3
DOIs
StatePublished - Jul 2024
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Business, Management and Accounting (miscellaneous)
  • Computer Science Applications
  • Control and Optimization
  • Management Science and Operations Research
  • Applied Mathematics

Keywords

  • Combinatorial optimization
  • Deep reinforcement learning
  • Heuristics
  • K-means
  • Mixed integer programming
  • Multi-dimensional Knapsack problem

Fingerprint

Dive into the research topics of 'A K-means Supported Reinforcement Learning Framework to Multi-dimensional Knapsack'. Together they form a unique fingerprint.

Cite this