Těžké celočíselné programy
| Název práce: | Těžké celočíselné programy |
|---|---|
| Autor(ka) práce: | Sokol, Ondřej |
| Typ práce: | Bakalářská práce |
| Vedoucí práce: | Černý, Michal |
| Oponenti práce: | Jablonský, Josef |
| Jazyk práce: | Česky |
| Abstrakt: | 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í. |
| Klíčová slova: | funkce presolve; řezy; binární proměnné; celočíselné programy |
| Název práce: | Hard Integer Programs |
|---|---|
| Autor(ka) práce: | Sokol, Ondřej |
| Typ práce: | Bachelor thesis |
| Vedoucí práce: | Černý, Michal |
| Oponenti práce: | Jablonský, Josef |
| Jazyk práce: | Česky |
| Abstrakt: | 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. |
| Klíčová slova: | cuts; presolve; binary variables; integer programs |
Informace o studiu
| Studijní program / obor: | Kvantitativní metody v ekonomice/Matematické metody v ekonomii |
|---|---|
| Typ studijního programu: | Bakalářský studijní program |
| Přidělovaná hodnost: | Bc. |
| Instituce přidělující hodnost: | Vysoká škola ekonomická v Praze |
| Fakulta: | Fakulta informatiky a statistiky |
| Katedra: | Katedra ekonometrie |
Informace o odevzdání a obhajobě
| Datum zadání práce: | 6. 3. 2013 |
|---|---|
| Datum podání práce: | 7. 6. 2013 |
| Datum obhajoby: | 25. 6. 2013 |
| Identifikátor v systému InSIS: | https://insis.vse.cz/zp/42020/podrobnosti |