CTU FEE Moodle
Optimization in Intelligent Systems
B232 - Summer 23/24
Optimization in Intelligent Systems - A7B35OIS
| Credits | 6 |
| Semesters | Summer |
| Completion | Assessment + Examination |
| Language of teaching | Czech |
| Extent of teaching | 2+2c |
Annotation
The goal is to show the algorithms for several combinatorial optimization problems. Following the subject on algorithms, we show optimisation techniques based on graphs, integer linear programming, heuristics, approximation algorithms and state space search methods. We focus on application of optimization in stores, ground transport, flight transport, logistics, planning of human resources, scheduling in production lines, message routing, scheduling in parallel computers.
Study targets
No data.
Course outlines
1. Example Applications and Formulation of Problems.
2. Basic Terms of Graph Theory.
3. Spanning Trees.
4. Network Flows.
5. Linear Programming.
6. Algorithms for Linear Programming. Test I.
7. Time Complexity of Algorithms.
8. Branch and Bound Technique and its Applications
9. Metaheuristics and Approximation Algorithms.
10. Scheduling on Monoprocessor
11. Scheduling on Parallel Processors
12. The Job Shop Problem
13. Reserve.
2. Basic Terms of Graph Theory.
3. Spanning Trees.
4. Network Flows.
5. Linear Programming.
6. Algorithms for Linear Programming. Test I.
7. Time Complexity of Algorithms.
8. Branch and Bound Technique and its Applications
9. Metaheuristics and Approximation Algorithms.
10. Scheduling on Monoprocessor
11. Scheduling on Parallel Processors
12. The Job Shop Problem
13. Reserve.
Exercises outlines
1. Introduction to the Scheduling Toolbox.
2. Properties of Graphs.
3. Spanning Tree and Clustering.
4. Individual Projects - Topics.
5. Applications of Network Flows
6. Linear Programming
7. Scheduling and Branch and Bound Technique
8. Approximation Algorithms and the SAT Problem
9. Individual Projects - Defense of the Programs
10. Test II.
11. Individual Projects - Defense.
12. Assessment.
13. Reserve.
2. Properties of Graphs.
3. Spanning Tree and Clustering.
4. Individual Projects - Topics.
5. Applications of Network Flows
6. Linear Programming
7. Scheduling and Branch and Bound Technique
8. Approximation Algorithms and the SAT Problem
9. Individual Projects - Defense of the Programs
10. Test II.
11. Individual Projects - Defense.
12. Assessment.
13. Reserve.
Literature
Main textbook
[1] B. H. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms. Springer, third ed., 2006.
Some parts of:
[2] J. Demel, Grafy a jejich aplikace. Academia, second ed., 2002.
[3] J. Blazevicz, Scheduling Computer and Manufacturing Processes. Springer, second ed., 2001.
[1] B. H. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms. Springer, third ed., 2006.
Some parts of:
[2] J. Demel, Grafy a jejich aplikace. Academia, second ed., 2002.
[3] J. Blazevicz, Scheduling Computer and Manufacturing Processes. Springer, second ed., 2001.
Requirements
Linear algebra
Agorithmisation
Agorithmisation