The quadratic assignment problem and its solution
| Thesis title: | Kavdratický přiřazovací problém a jeho řešení |
|---|---|
| Author: | Nováčková, Monika |
| Thesis type: | Bakalářská práce |
| Supervisor: | Jablonský, Josef |
| Opponents: | Fábry, Jan |
| Thesis language: | Česky |
| Abstract: | Kvadratický přiřazovací problém je jednou z nejsložitějších úloh kombinatorické optimalizace. Jedná se o velmi rozsáhlou rozhodovací úlohu třídy NP-complete. Poprvé tento problém představili v roce 1957 Koopmans a Beckman. Od té doby byly zkoumány různé metody řešení tohoto problému. Jedná se o nejrůznější exaktní ale i heuristické algoritmy. V této práci je podrobněji popsán jeden z exaktních algoritmů tzv. metoda větví a mezí (branch and bound algorithm) založená na Gilmore Lawlerově způsobu výpočtu dolních mezí. Dále jsou zde popsány některé aplikační oblasti kvadratického přiřazovacího problému. Jedná se například o úlohu, jak nejlépe rozmístit jednotlivé kliniky a zařízení v areálu nemocnice tak, aby pacienti celkově během svého pobytu v nemocnici museli překonat, co nejmenší vzdálenost mezi jednotlivými klinikami, nebo jak uspořádat jednotlivé komponenty v počítači na desce motherboard tak, aby celkový součin množství signálů a vzdálenosti, kterou musí data překonat, byl co nejmenší. |
| Keywords: | Gilmore-Lawlerovi dolní meze; kvadratický přiřazovací problém; metoda větví a mezí; kombinatorická optimalizace |
| Thesis title: | The quadratic assignment problem and its solution |
|---|---|
| Author: | Nováčková, Monika |
| Thesis type: | Bachelor thesis |
| Supervisor: | Jablonský, Josef |
| Opponents: | Fábry, Jan |
| Thesis language: | Česky |
| Abstract: | The QAP (quadratic assignment problem) is one of the most involved combinatorial optimization problems. This formidable decision problem is included in the complexity class called NP-complete. The QAP has been first time introduced by Koopmans and Beckman in year 1957. Since then the various methods for solving this problem have been investigated. The studied methods include both: exact algorithms and heuristic methods. Some of them will be shortly described in this paper. One of them, the branch and bound algorithm based on Gilmore Lawler bounds will be analyzed in detail. View applications of this problem will be also discussed. Described applications include the problem of localization of the departments or clinics in a hospital in order to minimize the total traveling distance among clinics by patients. Another described example of application of this problem is the task how to place the components on a computer motherboard optimally. |
| Keywords: | quadratic assignment problem; Gilmore-Lawler bound; branch and bound algorithm; combinatorial optimization |
Information about study
| Study programme: | Kvantitativní metody v ekonomice/Matematické metody v ekonomii |
|---|---|
| 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: | 4. 11. 2009 |
|---|---|
| Date of submission: | 15. 5. 2010 |
| Date of defense: | 7. 9. 2010 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/22677/podrobnosti |