|
|
Workforce Optimisation
Pacinda, Štefan ; Barták, Roman (advisor) ; Klusáček, Dalibor (referee)
Title: Workforce Optimisation Author: Štefan Pacinda Department / Institute: Department of Theoretical Computer Science and Mathematical Logic (KTIML) Supervisor of the master thesis: doc. RNDr. Roman Barták Ph.D., KTIML Abstract: Workforce management deals with the problem of maintaining productive workforce for example in call centers, hospitals, transportation companies etc. It includes the problem of deciding which skills are necessarily at each given time and how many personnel with given skills is required. These decisions are followed by solving the problem of allocating particular employees to shifts while satisfying the skill demands but also other constraints derived for example from law regulations, trade unions agreements, and individual preferences. This thesis deals with workforce optimization, that is with the optimal assignment of personnel to shifts in order to cover the demand for resources that vary over time. In this paper the solved problem is described in all detail and modeled as mixed integer program. Implementation details are presented and exhaustive analysis and experiments on a real life problem instance are performed to assure that the aims of the work have been met. Keywords: Rostering, Workforce Management, Shift Scheduling
|
|
|
Incomplete Search Techniques
Lehotský, Jakub ; Barták, Roman (advisor) ; Surynek, Pavel (referee)
Title:Incomplete Search Techniques Author: Jakub Lehotský Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor: Doc. RNDr. Roman Barták, Ph.D. Supervisor's email address: bartak@ktiml.mff.cuni.cz Abstract:The constraint satisfaction problems is set of discrete combinatorial problems which address to solve many of the real life problems. They are commonly solved by inference and search algorithms. In most cases the complete search algorithm can find a solution to a problem, but in many cases, search space is too large to be explored completely. In these case the limitation of search space is necessary in a way which gives us some way to still find a solution without having to search whole search space. Discrepancy-based search algorithms limit the search space by limiting the number where search decisions go against the heuristic in given search. Incomplete algorithms don't guarantee finding a solution. Many incomplete algorithms have any-time property useful in optimization problems, where algorithm provides some solution at any time even if it is not an optimal one. Keywords: CSP, incomplete search, discrepancy search 1
|
|
|
Constraint satisfaction for inductive logic programming
Chovanec, Andrej ; Barták, Roman (advisor) ; Železný, Filip (referee)
Inductive logic programming is a discipline investigating invention of clausal theories from observed examples such that for given evidence and background knowledge we are finding a hypothesis covering all positive examples and excluding all negative ones. In this thesis we extend an existing work on template consistency to general consistency. We present a three-phase algorithm DeMeR decomposing the original problem into smaller subtasks, merging all subsolutions together yielding a complete solution and finally refining the result in order to get a compact final hypothesis. Furthermore, we focus on a method how each individual subtask is solved and we introduce a generate-and-test method based on the probabilistic history-driven approach for this purpose. We analyze each stage of the proposed algorithms and demonstrate its impact on a runtime and a hypothesis structure. In particular, we show that the first phase of the algorithm concentrates on solving the problem quickly at the cost of longer solutions whereas the other phases refine these solutions into an admissible form. Finally, we prove that our technique outperforms other algorithms by comparing its results for identifying common structures in random graphs to existing systems.
|
|
|
Global Constraints
Mlejnek, Jaroslav ; Surynek, Pavel (referee) ; Barták, Roman (advisor)
Global constraints play a crucial role in solving real-life combinatorial problems thanks to encapsulation of dedicated solving techniques for particular sub-problems and integration of these techniques via general constraint satisfaction technology. There exist many global constraints developed for particular problems as well as derived from existing solving techniques. This work focuses on providing an easy-to-use survey of existing global constraints with particular emphasis on practical applicability.
|
|
|
Portfolio Optimisation
Huml, Tomáš ; Surynek, Pavel (referee) ; Barták, Roman (advisor)
The goal of this work is to propose an algorithm selecting an optimal portfolio from input projects, which are assessed by costs, profits and potential risk. Any interdependencies can be defined among these input projects. Summary of alternative approaches concerning this topic is part of this work too. Program implementing proposed algorithm is attached to this work. Output of program computation is a portfolio achieving the highest possible profit as well as satisfying all of input constraints and defined interdependencies among the projects. The program allows graph comparison of resulted portfolios and provides detail information about each portfolio.
|
|
|
Constraint satisfaction for HW/SW verification
Cigler, Luděk ; Vomlelová, Marta (referee) ; Barták, Roman (advisor)
Constraint satisfaction techniques (CSP) are a powerful framework for modeling and solving various problems in artificial intelligence and operations research. Verification of HW and SW can profit from employing constraint satisfaction for test generation. The essential property of a CSP algorithm (wrt. test generation) is the uniform generation of solution samples. We present several algorithms for sampling solutions of a CSP and extend them so that they can be used for sampling solutions of CSP with preferences. We test the performance of our algorithms on various benchmark problems.
|
|
|
Global Constraints with Cost
Hejna, Martin ; Čepek, Ondřej (referee) ; Barták, Roman (advisor)
Planning problems are a very important application area for constraint satisfactory problems. Temporal networks are a common way of planning problems representation. In temporal network nodes represent time points and arcs represent time relations. A solution of temporal network means finding such parameters of nodes, that all constraints hold. A nested temporal network, as presented in this thesis, is a special case of the temporal network, which has a restricted structure to be still powerfull for practical use and simultaneously allows using of more effective solving methods. In this thesis nested temporal networks are defined and explored. A polynomial time method for global consistency of alternatives is presented and a proof of NP-completeness for global consistency is demonstrated. If more than one solution exist, it is suitable to have a method for comparing solutions. A common way to accomplish this is price. Usual task is to find solution with minimal price. In the thesis we use the Branch and Bound method with a new filtering algorithm, which exploites the special structure of nested temporal network.
|
|
|
Constraint modelling
Haničinec, Tomáš ; Surynek, Pavel (referee) ; Barták, Roman (advisor)
Constraint programming is one of the possible ways how to solve complicated combinatorial (and other) problems. We model a problem using variables representing real world objects and constraints representing various relations between the objects. However, there are often many possible ways how to model a problem. And what's more, the choice of a modeling strategy can a®ect the resulting efficiency dramatically. Unfortunately, there is no general recipe how to model problems e±ciently. Nevertheless there are still several modeling techniques, heuristics or advices that could improve the e±ciency of models. Some of these techniques are problem dependent, some can be applied only to a certain classes of problems but they still often help. This thesis is trying to give more or less complete list of the most important modeling techniques along with an explanation of why, how and for which classes of problems they work best and also with empirical results underlying the presented facts.
|
|
|
Global Constraints in Scheduling
Vilím, Petr ; Barták, Roman (advisor) ; Rudová, Hana (referee) ; Wolf, Armin (referee)
In this place, I would like to say my best thanks to everyone who supported me in my work and helped me along my whole Ph.D. study. First of all I owe a major debt to my supervisor Doc. RNDr. Roman Barták, Ph.D. for his patient leading, collaboration, support and help; especially for guidingmy research to this topic, providing important information from CP field, helping me publish my papers and reviewing them (most of them several times). Next I want to thank to Doc. RNDr. Ondřej Čepek, Ph.D. I wrote with him and Roman Barták a paper to CP 2004 which was very successful. They both contributed to this success. I also wish to express my gratitude to the whole CP community. To anonymous reviewers for providing me valuable feedback, for pointing out flaws in my papers and helping me to fix them. To my mentors on CP conferences who gave me a lot of helpful advices concerning my research and this a Ph.D. Thesis. I'm also very thankful to all the people with whom I could discuss during several conferences - they often asked very good questions; and good questions are often one half of whole research. My special thanks belongs to Philippe Baptiste, Mats Carlsson, Narendra Jussien, Philippe Laborie, Francois Laburthe, Narendra Jussien, Claude Le Pape, Jean-Charles Régin, Jerome Rôgerie, Francesca Rossi and...
|
|
|
Compiling Planning Problems
Toropila, Daniel ; Chrpa, Lukáš (referee) ; Barták, Roman (advisor)
Constraint satisfaction techniques are used frequently for solving scheduling problems, but they are still seldom in AI planning. There exist several attempts to apply constraint satisfaction for solving AI planning problems, however, these techniques never became prevailing in planning and did not reach the success of, for example, SATbased planners. In this work we argue that the existing constraint models for classical AI planning are indeed not exploiting fully the power of constraint satisfaction and we propose their reformulation which significantly improves efficiency.
|
guest ::
