Hard Integer Programs
| Thesis title: | Těžké celočíselné programy |
|---|---|
| Author: | Sokol, Ondřej |
| Thesis type: | Bakalářská práce |
| Supervisor: | Černý, Michal |
| Opponents: | Jablonský, Josef |
| Thesis language: | Česky |
| Abstract: | Práce se zabývá těžkými celočíselnými programy. V první části jsou vysvětleny základní principy funkce presolve a řezů. V další části jsou pak analyzovány dvě vybrané celočíselné úlohy z hlediska výpočetní náročnosti. První úloha je jednoduchý program bez přípustného řešení, druhá úloha je pak variací problému batohu. Tyto úlohy jsou řešeny pomocí řešitelů Gurobi, CPLEX, LPSolve a CoinMP v prostředí programu MPL, přičemž je zkoumán vliv funkce presolve a řezů na náročnost úlohy. Výsledky prokázaly, že u první z analyzovaných úloh použití funkce presolve nebo řezů výrazně urychlilo nalezení řešení. U druhé úlohy presolve i řezy zrychlují vyřešení pouze u úloh s malou dimenzí. S rostoucí dimenzí obě metody svůj význam ztrácejí, někdy dokonce čas k nalezení řešení prodlužují. |
| Keywords: | funkce presolve; řezy; binární proměnné; celočíselné programy |
| Thesis title: | Hard Integer Programs |
|---|---|
| Author: | Sokol, Ondřej |
| Thesis type: | Bachelor thesis |
| Supervisor: | Černý, Michal |
| Opponents: | Jablonský, Josef |
| Thesis language: | Česky |
| Abstract: | This work deals with hard integer programming problems. The first section explains the basic principles of presolve and cutting functions. The next section analyses two selected integer programming problems. First problem is simple task with no feasible solution. Second problem is variation of knapsack problem. These problems are solved by using Gurobi, CPLEX, and LPSolve CoinMP solvers in MPL environment and their computational complexity, including the impact of presolve and cuts functions on the complexity of the task, is evaluated and compared. The results showed that for the first problem presolve and cuts methods significantly accelerated the solution. For the second problem presolve and cuts methods accelerate finding solution only for tasks with a small dimension. Surprisingly, it turns out that both methods sometimes increase the time needed to find the optimal solution with the increasing dimension of the problem. |
| Keywords: | cuts; presolve; binary variables; integer programs |
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: | 6. 3. 2013 |
|---|---|
| Date of submission: | 7. 6. 2013 |
| Date of defense: | 25. 6. 2013 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/42020/podrobnosti |