Subject description - AE4M77KO
Summary of Study |
Summary of Branches |
All Subject Groups |
All Subjects |
List of Roles |
Explanatory Notes
Instructions
| AE4M77KO |
Combinatorial Optimization |
| Roles: | |
Extent of teaching: | 3P+2C |
| Department: | 13135 |
Language of teaching: | EN |
| Guarantors: | |
Completion: | Z,ZK |
| Lecturers: | |
Credits: | 6 |
| Tutors: | |
Semester: | L |
Web page:
https://cw.fel.cvut.cz/wiki/courses/a4m35ko/start
Anotation:
The goal is to show the problems and algorithms of combinatorial optimization (often called discrete optimization; there is a strong overlap with the term operations research).
Following the courses on linear algebra, graph theory, and basics of optimization, we show optimization techniques based on graphs, integer linear programming, heuristics, approximation algorithms and state space search methods.
Course outlines:
| 1. | | Introduction of Basic Terms of Combinatorial Optimization, Example Applications and Test on Preliminary Knowledge |
| 2. | | Integer Linear Programming - Algorithms |
| 3. | | Problem Formulation by Integer Linear Programming |
| 4. | | Heuristics, Test |
| 5. | | Shortest Paths |
| 6. | | Network Flows and Cuts |
| 7. | | Multicommodity network flows |
| 8. | | Dynamic Programming, Test |
| 9. | | Knapsack Problem and Pseudo-polynomial Algorithms |
| 10. | | Traveling Salesman Problem and Approximation Algorithms |
| 11. | | Monoprocessor Scheduling |
| 12. | | Scheduling on Parallel Processors |
| 13. | | Project Scheduling with Time Windows |
| 14. | | Constraint Programming |
Exercises outline:
| 1. | | Introduction to the Experimental Environment and Optimisation library |
| 2. | | Integer Linear Programming |
| 3. | | Applications of Integer Linear Programming |
| 4. | | Assignment of Term Projects |
| 5. | | Branch and Bound Technique |
| 6. | | Shortest Paths |
| 7. | | Applications of Network Flows and Cuts |
| 8. | | Presentation of Term Projects |
| 9. | | Monoprocessor Scheduling - Earliest Deadline First |
| 10. | | Approximation Algorithms - List Scheduling |
| 11. | | Reserved |
| 12. | | Test |
| 13. | | Giving over Term Projects |
| 14. | | Credits |
Literature:
| B. | | H. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms. |
Springer, third ed., 2006.
| J. | | Blazevicz, Scheduling Computer and Manufacturing Processes. Springer, |
second ed., 2001.
| J. | | Demel, Grafy a jejich aplikace. Academia, second ed., 2002. |
Requirements:
Subject is included into these academic programs:
| Program |
Branch |
Role |
Recommended semester |
| Page updated 25.4.2025 17:53:37, semester: Z/2026-7, L/2025-6, Z/2024-5, L/2026-7, L/2024-5, Z/2025-6, Send comments about the content to the Administrators of the Academic Programs |
Proposal and Realization: I. Halaška (K336), J. Novák (K336) |