Subject description - A4M35KO

Summary of Study | Summary of Branches | All Subject Groups | All Subjects | List of Roles | Explanatory Notes               Instructions
A4M35KO Combinatorial Optimization Extent of teaching:3+2c
Guarantors:  Roles:P,V Language of
teaching:
CS
Teachers:  Completion:Z,ZK
Responsible Department:13135 Credits:6 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. Modeling Languages for Solving Combinatorial Problems
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 - hand in a code and a written report
13. Ungraded Assessment
14. Reserved

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.
TORSCHE http://rtime.felk.cvut.cz/scheduling-toolbox/

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
MPIB Common courses V
MPOI1 Artificial Intelligence P 2
MPOI5NEW Software Engineering P 2
MPOI4NEW Computer Graphics and Interaction P 2
MPOI5 Software Engineering P 2
MPOI4 Computer Graphics and Interaction P 2
MPOI3 Computer Vision and Image Processing P 2
MPOI2 Computer Engineering P 2
MPKME1 Wireless Communication V 2
MPKME5 Systems of Communication V 2
MPKME4 Networks of Electronic Communication V 2
MPKME3 Electronics V 2
MPKME2 Multimedia Technology V 2
MPEEM1 Technological Systems V 2
MPEEM5 Economy and Management of Electrical Engineering V 2
MPEEM4 Economy and Management of Power Engineering V 2
MPEEM3 Electrical Power Engineering V 2
MPEEM2 Electrical Machines, Apparatus and Drives V 2
MPKYR4 Aerospace Systems V 2
MPKYR1 Robotics V 2
MPKYR3 Systems and Control V 2
MPKYR2 Sensors and Instrumentation V 2


Page updated 20.6.2019 17:52:57, semester: Z,L/2020-1, L/2018-9, Z,L/2019-20, Send comments about the content to the Administrators of the Academic Programs Proposal and Realization: I. Halaška (K336), J. Novák (K336)