Constraint Programming as Means for Solving Discrete Problems
| Thesis title: | Použití programování s omezujícími podmínkami při řešení diskrétních úloh |
|---|---|
| Author: | Janečková, Jitka |
| Thesis type: | Diplomová práce |
| Supervisor: | Fábry, Jan |
| Opponents: | Černý, Michal |
| Thesis language: | Česky |
| Abstract: | 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. |
| Keywords: | optimalizace; redukce domény; (binární) problém splňování podmínek; globální podmínka; konzistenční technika |
| Thesis title: | Constraint Programming as Means for Solving Discrete Problems |
|---|---|
| Author: | Janečková, Jitka |
| Thesis type: | Diploma thesis |
| Supervisor: | Fábry, Jan |
| Opponents: | Černý, Michal |
| Thesis language: | Česky |
| Abstract: | 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: | Optimization; Global Constraint; Domain Reduction; Consistency Algorithm; (Binary) Constraint Satisfaction Problem |
Information about study
| Study programme: | Kvantitativní metody v ekonomice/Matematické metody v ekonomii |
|---|---|
| Type of study programme: | Magisterský studijní program |
| Assigned degree: | Ing. |
| 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: | 13. 4. 2010 |
|---|---|
| Date of submission: | 31. 7. 2010 |
| Date of defense: | 25. 1. 2012 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/26168/podrobnosti |