Detail publikačního výsledku

Stochastic Heuristics for Knapsack Problems

ŠEDA, M.; ŠEDA, P.

Originální název

Stochastic Heuristics for Knapsack Problems

Anglický název

Stochastic Heuristics for Knapsack Problems

Druh

Článek Scopus

Originální abstrakt

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.

Anglický abstrakt

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.

Klíčová slova

knapsack problem, dynamic programming, branch and bound method, heuristic, genetic algorithm, simulated annealing

Klíčová slova v angličtině

knapsack problem, dynamic programming, branch and bound method, heuristic, genetic algorithm, simulated annealing

Autoři

ŠEDA, M.; ŠEDA, P.

Rok RIV

2019

Vydáno

05.08.2018

Nakladatel

Springer-Verlag

Místo

Berlin

ISSN

2194-5357

Periodikum

Advances in Intelligent Systems and Computing

Svazek

837

Číslo

1

Stát

Švýcarská konfederace

Strany od

157

Strany do

166

Strany počet

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