Original title: Použití programování s omezujícími podmínkami při řešení diskrétních úloh
Translated title: Constraint Programming as Means for Solving Discrete Problems
Authors: Janečková, Jitka ; Fábry, Jan (advisor) ; Černý, Michal (referee)
Document type: Master’s theses
Year: 2010
Language: cze
Publisher: Vysoká škola ekonomická v Praze
Abstract: [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.
Keywords: (Binary) Constraint Satisfaction Problem; Consistency Algorithm; Domain Reduction; Global Constraint; Optimization; (binární) problém splňování podmínek; globální podmínka; konzistenční technika; optimalizace; redukce domény

Institution: University of Economics, Prague (web)
Document availability information: Available in the digital repository of the University of Economics, Prague.
Original record: http://www.vse.cz/vskp/eid/29605

Permalink: http://www.nusl.cz/ntk/nusl-81927


The record appears in these collections:
Universities and colleges > Public universities > University of Economics, Prague
Academic theses (ETDs) > Master’s theses