Subject description - B4M35KO
Summary of Study |
Summary of Branches |
All Subject Groups |
All Subjects |
List of Roles |
Explanatory Notes
Instructions
Springer, sixth ed., 2018.
http://dx.doi.org/10.1007/978-3-662-56039-6
second ed., 2001.
https://kix.fsv.cvut.cz/~demel/grafy/gr.pdf
| B4M35KO | Combinatorial Optimization | ||
|---|---|---|---|
| Roles: | PS, PV, P | Extent of teaching: | 3P+2C |
| Department: | 13135 | Language of teaching: | CS |
| Guarantors: | Hanzálek Z. | Completion: | Z,ZK |
| Lecturers: | Hanzálek Z. | Credits: | 6 |
| Tutors: | Too many persons | Semester: | L |
Web page:
https://cw.fel.cvut.cz/wiki/courses/ko/startAnotation:
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. We focus on application of optimization in stores, ground transportation, flight transportation, logistics, planning of human resources, scheduling in production lines, message routing, scheduling in parallel computers.Course outlines:
| 1. | Introduction to Basic Terms of Combinatorial Optimization, Example Applications and a Test of Preliminary Knowledge | |
| 2. | Integer Linear Programming - Algorithms | |
| 3. | Problem Formulation by Integer Linear Programming | |
| 4. | The Shortest Paths. Problem Formulation by Shortest Paths. | |
| 5. | Problem Formulation by Shortest Paths. | |
| 6. | Flows and Cuts - Algorithms and Problem Formulation. Test I. | |
| 7. | Multicommodity network flows | |
| 8. | Knapsack Problem and Pseudo-polynomial Algorithms | |
| 9. | Traveling Salesman Problem and Approximation Algorithms | |
| 10. | Monoprocessor Scheduling | |
| 11. | Scheduling on Parallel Processors. Test II. | |
| 12. | Project Scheduling with Time Windows. | |
| 13. | Constraint Programming. | |
| 14. | Reserved |
Exercises outline:
| 1. | Policy and Individual Project Market | |
| 2. | Introduction to the Experimental Environment and Optimization Library | |
| 3. | Integer Linear Programming | |
| 4. | Individual Project I - Assignment and Problem Classification | |
| 5. | Traveling Salesman Problem | |
| 6. | Individual Project II - Related Work and Solution | |
| 7. | Applications of Network Flows and Cuts | |
| 8. | Individual Project III - Consultation | |
| 9. | Test III | |
| 10. | Scheduling | |
| 11. | Advanced Methods for Solving Combinatorial Problems | |
| 12. | Individual Project IV - evaluation and written report | |
| 13. | Ungraded Assessment | |
| 14. | Reserved |
Literature:
| B. | H. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms. |
| J. | Blazevicz, Scheduling Computer and Manufacturing Processes. Springer, |
| J. | Demel, Grafy a jejich aplikace. Academia, second ed., 2015. |
Requirements:
Optimisation, Discrete mathematics, Logics and graphs Subject is included into these academic programs:| Program | Branch | Role | Recommended semester |
| MPBIO1_2018 | Bioinformatics | PS | 2 |
| MPBIO3_2018 | Image processing | PS | 2 |
| MPBIO2_2018 | Medical Instrumentation | PV | 2 |
| MPOI1_2018 | Human-Computer Interaction | P | 2 |
| MPOI9_2018 | Data Science | P | 2 |
| MPOI8_2018 | Bioinformatics | P | 2 |
| MPOI7_2018 | Artificial Intelligence | P | 2 |
| MPOI6_2018 | Software Engineering | P | 2 |
| MPOI5_2018 | Computer Vision and Image Processing | P | 2 |
| MPOI4_2018 | Computer Engineering | P | 2 |
| MPOI3_2018 | Computer Graphics | P | 2 |
| MPOI2_2018 | Cyber Security | P | 2 |
| MPBIO4_2018 | Signal processing | PV | 2 |
| Page updated 6.10.2024 17:51:16, semester: Z,L/2024-5, Z/2025-6, L/2023-4, Send comments about the content to the Administrators of the Academic Programs | Proposal and Realization: I. Halaška (K336), J. Novák (K336) |