456-0340/01 – Optimization Problems (OU)

Gurantor departmentDepartment of Computer ScienceCredits4
Subject guarantordoc. RNDr. Petr Hliněný, Ph.D.Subject version guarantordoc. RNDr. Petr Hliněný, Ph.D.
Study levelundergraduate or graduateRequirementChoice-compulsory
Year3Semestersummer
Study languageCzech
Year of introduction2003/2004Year of cancellation2005/2006
Intended for the facultiesFEIIntended for study typesMaster
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Credit and Examination 2+2
Combined Credit and Examination 2+2

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

Další požadavky na studenta

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

Combined form (validity from: 1960/1961 Summer semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of points
Exercises evaluation and Examination Credit and Examination 100 (145) 51
        Examination Examination 100  0
        Exercises evaluation Credit 45  0
Mandatory attendence parzicipation:

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.FormStudy language Tut. centreYearWSType of duty
2004/2005 (N2646) Information Technology (2612T025) Computer Science and Technology P Czech Ostrava 3 Choice-compulsory study plan
2004/2005 (N2646) Information Technology (2612T025) Computer Science and Technology K Czech Ostrava 3 Choice-compulsory study plan
2003/2004 (N2646) Information Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Choice-compulsory study plan
2003/2004 (N2646) Information Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Choice-compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner