Název: Použití programování s omezujícími podmínkami při řešení diskrétních úloh
Překlad názvu: Constraint Programming as Means for Solving Discrete Problems
Autoři: Janečková, Jitka ; Fábry, Jan (vedoucí práce) ; Černý, Michal (oponent)
Typ dokumentu: Diplomové práce
Rok: 2010
Jazyk: cze
Nakladatel: Vysoká škola ekonomická v Praze
Abstrakt: [cze] [eng]
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. 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: (binární) problém splňování podmínek; globální podmínka; konzistenční technika; optimalizace; redukce domény; (Binary) Constraint Satisfaction Problem; Consistency Algorithm; Domain Reduction; Global Constraint; Optimization

Instituce: Vysoká škola ekonomická v Praze (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři VŠE.
Původní záznam: http://www.vse.cz/vskp/eid/29605

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-81927


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Vysoká škola ekonomická v Praze
Vysokoškolské kvalifikační práce > Diplomové práce