Multidimensional Knapsack Problem

Thesis title: Vícerozměrná úloha batohu
Author: Cibulka, Adam
Thesis type: Bakalářská práce
Supervisor: Sekničková, Jana
Opponents: Čížků, Andrea
Thesis language: Česky
Abstract:
Práce se zaměřuje na často používanou aplikaci kombinatorické optimalizace, na úlohu batohu. Cílem úlohy batohu je rozhodnout, jaké položky, případně v jakém počtu a na jaké místo, umístit do omezeného prostoru tak, aby výsledné umístění přineslo co nejvyšší užitek. Z hlediska charakteru spadá tato úloha mezi úlohy celočíselné, a proto může být nalezení výsledku složité, hlavně při aplikaci úlohy na větší rozměry. U úloh jednorozměrných, dvourozměrných i vícerozměrných je matematický model závislý též na maximálním počtu daných předmětů, což úlohy dále rozlišuje a komplikuje. Existuje mnoho způsobů, jak tento typ úloh klasifikovat a následně řešit. Navíc se stále vyvíjejí nové postupy optimalizace. Cílem této práce bude úlohy batohu obecně kategorizovat, popsat včetně jejich reálného použití a formulovat jejich ekonomické a matematické modely. Hlavním cílem je vytvoření aplikace umožňující uživateli snadné zadání problému a nalezení optimálního řešení vícerozměrné úlohy batohu, jedné z typů úloh batohu, která je oproti té klasické rozšířená o další dimenzi.
Keywords: Kombinatorická optimalizace; Dvourozměrná úloha batohu; Lineární programování; Vícerozměrná úloha batohu; Python
Thesis title: Multidimensional Knapsack Problem
Author: Cibulka, Adam
Thesis type: Bachelor thesis
Supervisor: Sekničková, Jana
Opponents: Čížků, Andrea
Thesis language: Česky
Abstract:
This paper focuses on a frequently used application of combinatorial optimization, the knapsack problem. The goal of the knapsack problem is to decide which items, potentially in what number and location, to place in a bounded space so that the resulting placement yields the highest utility. Due to the nature of this problem, it is an integer problem and therefore finding the result can be difficult, especially when applying the problem to larger dimensions. For one-dimensional, two-dimensional and multi-dimensional problems, the mathematical model is also dependent on the maximum number of objects given, which further differentiates and complicates the problem. There are many ways to classify and subsequently solve this type of problems. In addition, new optimization techniques are constantly being developed. The goal of this paper will be to categorize knaspacking problems in general, describe them including their real-world applications, and formulate their economic and mathematical models. The main objective is to create an application that allows the user to easily define the problem and find the optimal solution to a multidimensional knapsack problem, one of the types of knapsack problems that is extended by an additional dimension compared to the traditional one.
Keywords: Combinatorial optimization; Two-dimensional knapsack problem; Multidimensional knapsack problem; Python; Linear programming

Information about study

Study programme: Aplikovaná informatika/Aplikovaná informatika
Type of study programme: Bakalářský studijní program
Assigned degree: Bc.
Institutions assigning academic degree: Vysoká škola ekonomická v Praze
Faculty: Faculty of Informatics and Statistics
Department: Department of Econometrics

Information on submission and defense

Date of assignment: 17. 3. 2022
Date of submission: 8. 5. 2022
Date of defense: 24. 6. 2022
Identifier in the InSIS system: https://insis.vse.cz/zp/80301/podrobnosti

Files for download

    Last update: