Použití programování s omezujícími podmínkami při řešení diskrétních úloh
Název práce: | Použití programování s omezujícími podmínkami při řešení diskrétních úloh |
---|---|
Autor(ka) práce: | Janečková, Jitka |
Typ práce: | Diplomová práce |
Vedoucí práce: | Fábry, Jan |
Oponenti práce: | Černý, Michal |
Jazyk práce: | Česky |
Abstrakt: | Použití programování s omezujícími podmínkami (CP) je jedním z možných způsobů řešení diskrétních úloh. Lze ho použít jak k hledání přípustného řešení, tak k optimalizaci. CP nabízí celou řadu metod určených buď k samotnému nalezení řešení nebo ke zrychlení procesu jeho hledání -- od prohledávacích algoritmů přes konzistenční techniky po propagační techniky, které jsou vlastně jen kombinací předchozích dvou. K optimalizaci se nejčastěji používá metoda větvení a mezí, která se v některých aspektech odlišuje od stejnojmenné metody matematického programování (MP). Porovnání CP s MP je zajímavé i v dalších ohledech. CP například vyniká ve flexibilnější formulaci úloh, která umožňuje vytvořit často jednodušší a menší model. Naopak jeho nevýhodou je omezené použití: Problém (optimálního) splňování podmínek, jak úlohu programování s omezujícími podmínkami nazýváme, nesmí obsahovat spojité proměnné. Vhodné je pak především pro úlohy obsahující hodně omezení, které mají málo proměnných, nejlépe pouze dvě. Práce seznámí čtenáře se základními pojmy programování s omezujícími podmínkami, především se ale zabývá popisem algoritmů a technik používaných k řešení diskrétních úloh a porovnáním CP s matematickým programováním. |
Klíčová slova: | optimalizace; redukce domény; (binární) problém splňování podmínek; globální podmínka; konzistenční technika |
Název práce: | Constraint Programming as Means for Solving Discrete Problems |
---|---|
Autor(ka) práce: | Janečková, Jitka |
Typ práce: | Diploma thesis |
Vedoucí práce: | Fábry, Jan |
Oponenti práce: | Černý, Michal |
Jazyk práce: | Česky |
Abstrakt: | Application of constraint programming (CP) is one of the possible ways of solving discrete problems. It can be used for both search for feasible solution and optimization. CP offers a whole range of approaches for either a solution search or for acceleration of the process of its search -- from search algorithms or consistency techniques to propagation algorithms, which are basically only a combination of the two preceding methods. For optimization we most often use branch and bound approach, which differs in some aspects from a method of the same name used in mathematical programming (MP). Comparison of CP and MP is interesting in many other aspects. With CP the formulation of problems is more flexible, which allows for creation of often simpler and smaller models. On the other hand, its disadvantage is a limited use: Constraint satisfaction (optimisation) problem, as we call the constraint programming problem, cannot contain any discrete variables. CP is suitable especially for problems with a lot of constraints and only few variables, ideally only two. In the beginning, the paper introduces the basic terms of constraint programming, then it describes algorithms and techniques used for solving discrete problems and compares CP with mathematical programming. |
Klíčová slova: | Optimization; Global Constraint; Domain Reduction; Consistency Algorithm; (Binary) Constraint Satisfaction Problem |
Informace o studiu
Studijní program / obor: | Kvantitativní metody v ekonomice/Matematické metody v ekonomii |
---|---|
Typ studijního programu: | Magisterský studijní program |
Přidělovaná hodnost: | Ing. |
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: | 13. 4. 2010 |
---|---|
Datum podání práce: | 31. 7. 2010 |
Datum obhajoby: | 25. 1. 2012 |
Identifikátor v systému InSIS: | https://insis.vse.cz/zp/26168/podrobnosti |