Modifications of Branch and Bound algorithm for solving integer linear programming problems
| Thesis title: | Modifikace algoritmu metody větvení a mezí pro řešení úloh celočíselného programování |
|---|---|
| Author: | Vítek, Lukáš |
| Thesis type: | Diplomová práce |
| Supervisor: | Fábry, Jan |
| Opponents: | Pelikán, Jan |
| Thesis language: | Česky |
| Abstract: | Hlavním cílem práce je srovnat výpočetní náročnost vybraných úloh celočíselného programování devíti modifikacemi metody větvení a mezí. Jednotlivé modifikace spočívají v kombinaci volby větvící proměnné a způsobu prohledávání vygenerovaného prohledávacího stromu. V první části práce je představena teorie lineárního programování, celočíselného programování a také typy metod řešení celočíselných úloh, přičemž důraz je kladen zejména na metodu větvení a mezí. Ve druhé části jsou naprogramovány modifikace algoritmů metody větvení a mezí v jazyce Visual Basic for Applications, kdy tento kód je propojen s matematickými modely v MPL for Windows. Prostřednictvím tohoto programu jsou nakonec vyřešeny tři úlohy celočíselného lineárního programování pro více variant vstupních údajů, přičemž je porovnána výpočetní náročnost jednotlivých modifikací a také její robustnost vůči změnám v zadání. Zcela nakonec je na příkladu řezné úlohy demonstrována optimalizace metodou generování sloupců, kdy rychlost této optimalizace je opět srovnána se všemi uvedenými modifikacemi metody větvení a mezí. |
| Keywords: | celočíselné lineární programování; Visual Basic for Applications; MPL for Windows; metoda větvení a mezí |
| Thesis title: | Modifications of Branch and Bound algorithm for solving integer linear programming problems |
|---|---|
| Author: | Vítek, Lukáš |
| Thesis type: | Diploma thesis |
| Supervisor: | Fábry, Jan |
| Opponents: | Pelikán, Jan |
| Thesis language: | Česky |
| Abstract: | The main aim of this diploma thesis is to compare computational difficulty of selected integer linear programming problems by nine alterations of Branch and Bound method. The alterations are based on combination of branching variable selection and generated search tree vertices searching. There are introduced the linear programming theory, the integer linear programming theory and the ways of solving integer linear programming problems in the first part. Especially the Branch and Bound method is described. Secondly, the alterations of Branch and Bound algorithm are programmed in Visual Basic for Applications and they are connected with mathematical models written in MPL for Windows. Three integer linear programming problems with various input data order are solved by this program and their computational difficulty and robustness to input data variations are compared to each other. Finally, by solving the cutting stock problem, the column generation method is demonstrated and compared with other alterations again. |
| Keywords: | Branch and Bound; Integer Linear Programming; Visual Basic for Applications; MPL for Windows |
Information about study
| Study programme: | Kvantitativní metody v ekonomice/Ekonometrie a operační výzkum |
|---|---|
| Type of study programme: | Magisterský studijní program |
| Assigned degree: | Ing. |
| 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: | 7. 11. 2018 |
|---|---|
| Date of submission: | 28. 4. 2019 |
| Date of defense: | 5. 6. 2019 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/67678/podrobnosti |