Publication detail

Stochastic Heuristics for Knapsack Problems

Š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"
}