Reinforcement Learning for the Knapsack Problem

Jacopo Pierotti; Maximilian Kronmueller; Javier Alonso-Mora; J. Theresia van Essen; Wendelin Böhmer

doi:10.1007/978-3-030-86286-2_1

Reinforcement Learning for the Knapsack Problem

Jacopo Pierotti^*, Maximilian Kronmueller, Javier Alonso-Mora, J. Theresia van Essen, Wendelin Böhmer

^*Corresponding author for this work

Research output: Chapter in Book/Conference proceedings/Edited volume › Chapter › Scientific › peer-review

126 Downloads (Pure)

Abstract

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.

Original language	English
Title of host publication	AIRO Springer Series
Publisher	Springer Nature
Pages	3-13
Number of pages	11
DOIs	https://doi.org/10.1007/978-3-030-86286-2_1
Publication status	Published - 2021

Publication series

Name	AIRO Springer Series
Volume	6
ISSN (Print)	2523-7047
ISSN (Electronic)	2523-7055

Bibliographical note

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.

Keywords

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

Access to Document

10.1007/978-3-030-86286-2_1

978-3-030-86286-2_1Final published version, 287 KB

Cite this

@inbook{50c89fbd727049dbbd9c0ef49efb66bc,

title = "Reinforcement Learning for the Knapsack Problem",

abstract = "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.",

keywords = "End-to-end, Knapsack problem, Multi-task DQN, Reinforcement learning, Self-attention, Transformer",

author = "Jacopo Pierotti and Maximilian Kronmueller and Javier Alonso-Mora and {van Essen}, {J. Theresia} and Wendelin B{\"o}hmer",

note = "Green Open Access added to TU Delft Institutional Repository {\textquoteleft}You share, we take care!{\textquoteright} – 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. ",

year = "2021",

doi = "10.1007/978-3-030-86286-2_1",

language = "English",

series = "AIRO Springer Series",

publisher = "Springer Nature",

pages = "3--13",

booktitle = "AIRO Springer Series",

}

TY - CHAP

T1 - Reinforcement Learning for the Knapsack Problem

AU - Pierotti, Jacopo

AU - Kronmueller, Maximilian

AU - Alonso-Mora, Javier

AU - van Essen, J. Theresia

AU - Böhmer, Wendelin

N1 - 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.

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

KW - End-to-end

KW - Knapsack problem

KW - Multi-task DQN

KW - Reinforcement learning

KW - Self-attention

KW - Transformer

UR - http://www.scopus.com/inward/record.url?scp=85122449532&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-86286-2_1

DO - 10.1007/978-3-030-86286-2_1

M3 - Chapter

AN - SCOPUS:85122449532

T3 - AIRO Springer Series

SP - 3

EP - 13

BT - AIRO Springer Series

PB - Springer Nature

ER -

Reinforcement Learning for the Knapsack Problem

Abstract

Publication series

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this