Přístupnostní navigace
E-application
Search Search Close
Publication detail
ŠEDA, M. ŠEDA, P.
Original Title
Stochastic Heuristics for Knapsack Problems
Type
journal article in Scopus
Language
English
Original Abstract
In this paper, we introduce knapsack problem formulations, discuss their time complexity and propose their representation and solution based on the instance size. First, deterministic methods are briefly summarized. They can be applied to small-size tasks with a single constraint. However, because of NP-completeness of the problem, more complex problem instances must be solved by means of heuristic techniques to achieve an approximation of the exact solution in a reasonable amount of time. The problem representations and parameter settings for a genetic algorithm and simulated annealing frameworks are shown.
Keywords
knapsack problem, dynamic programming, branch and bound method, heuristic, genetic algorithm, simulated annealing
Authors
ŠEDA, M.; ŠEDA, P.
Released
5. 8. 2018
Publisher
Springer-Verlag
Location
Berlin
ISBN
2194-5357
Periodical
Advances in Intelligent Systems and Computing
Year of study
837
Number
1
State
Swiss Confederation
Pages from
157
Pages to
166
Pages count
10
BibTex
@article{BUT149171, author="Miloš {Šeda} and Pavel {Šeda}", title="Stochastic Heuristics for Knapsack Problems", journal="Advances in Intelligent Systems and Computing", year="2018", volume="837", number="1", pages="157--166", doi="10.1007/978-3-319-97888-8\{_}1", issn="2194-5357" }