456-0340/01 – Optimization Problems (OU)
Gurantor department | Department of Computer Science | Credits | 4 |
Subject guarantor | doc. RNDr. Petr Hliněný, Ph.D. | Subject version guarantor | doc. RNDr. Petr Hliněný, Ph.D. |
Study level | undergraduate or graduate | Requirement | Choice-compulsory |
Year | 3 | Semester | summer |
| | Study language | Czech |
Year of introduction | 2003/2004 | Year of cancellation | 2005/2006 |
Intended for the faculties | FEI | Intended for study types | Master |
Subject aims expressed by acquired skills and competences
Teaching methods
Summary
This subject presents students with basic types of optimization tasks, and teaches some basic solution methods.
The main focus is on linear optimization and the simplex method.
Other types mentioned are network flows and branch-and-bound methods.
Compulsory literature:
Vašek Chvátal: Linear Programming,
W H Freeman & Co. 1983.
Laurence A. Wolsey, George L. Nemhauser:
Integer and Combinatorial Optimization,
Wiley-Interscience 1999.
A. Schrijver, A Course in Combinatorial Optimization. http://homepages.cwi.nl/~lex/files/dict.pdf, CWI, Amsterdam.
Recommended literature:
Way of continuous check of knowledge in the course of semester
E-learning
Other requirements
Prerequisities
Subject has no prerequisities.
Co-requisities
Subject has no co-requisities.
Subject syllabus:
Lectures:
The greedy algorithm and its applications.
Network flows with applications, duality to cuts.
Linear optimization (linear programming) problem.
Convexity and duality
The simplex method for linear programming.
Implementing the simplex method.
Degenerated steps, complexity.
Applications: flows, transportation, games.
Integer or discrete optimization problem.
The branch-and-bound method in a shortcut.
Implementing branch-and-bound.
Specific variants: scheduling and TSP.
Exercises:
Tutorials are devoted to practical solving of optimization problems.
Conditions for subject completion
Occurrence in study plans
Occurrence in special blocks
Assessment of instruction
Předmět neobsahuje žádné hodnocení.