# Subject description - BE4M35KO

Summary of Study | Summary of Branches | All Subject Groups | All Subjects | List of Roles | Explanatory Notes               Instructions
BE4M35KO Combinatorial Optimization
Roles:PV, P Extent of teaching:3P+2C
Department:13135 Language of teaching:EN
Guarantors:  Completion:Z,ZK
Lecturers:Hanzálek Z. Credits:6
Tutors:Benedikt O., Minaeva A., Módos I., Novák A., Vlk M. Semester:L

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. 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.
Springer, sixth ed., 2018. http://dx.doi.org/10.1007/978-3-662-56039-6
 J. Blazevicz, Scheduling Computer and Manufacturing Processes. Springer,
second ed., 2001.
 J. Demel, Grafy a jejich aplikace. Academia, second ed., 2015.
https://kix.fsv.cvut.cz/~demel/grafy/gr.pdf

Requirements:

Optimisation, Discrete mathematics, Logics and graphs

Webpage:

https://cw.fel.cvut.cz/wiki/courses/a4m35ko/start

Subject is included into these academic programs:

 Program Branch Role Recommended semester MEOI7_2018 Artificial Intelligence P 2 MEOI9_2018 Data Science P 2 MEOI8_2018 Bioinformatics P 2 MEOI4_2018 Computer Engineering P 2 MEOI3_2018 Computer Graphics P 2 MEOI2_2018 Cyber Security P 2 MEOI1_2018 Human-Computer Interaction P 2 MEOI6_2018 Software Engineering P 2 MEOI5_2018 Computer Vision and Image Processing P 2 MEBIO3_2018 Image Processing PV 2 MEBIO2_2018 Medical Instrumentation PV 2 MEBIO_2018 Common courses PV 2 MEBIO1_2018 Bioinformatics PV 2 MEOI7_2016 Artificial Intelligence P 2 MEOI9_2016 Data Science P 2 MEOI8_2016 Bioinformatics P 2 MEOI4_2016 Computer Engineering P 2 MEOI3_2016 Computer Graphics P 2 MEOI2_2016 Cyber Security P 2 MEOI1_2016 Human-Computer Interaction P 2 MEOI6_2016 Software Engineering P 2 MEOI5_2016 Computer Vision and Image Processing P 2 MEBIO_2018 Common courses PV 2 MEBIO4_2018 Signal Processing PV 2

 Page updated 25.6.2021 05:53:03, semester: L/2021-2, L/2020-1, Z,L/2022-3, Z/2021-2, Send comments about the content to the Administrators of the Academic Programs Proposal and Realization: I. Halaška (K336), J. Novák (K336)