SubjectsSubjects(version: 849)
Course, academic year 2019/2020
   Login via CAS
Linear programming and combinatorial optimization - NOPT048
Title in English: Lineární programování a kombinatorická optimalizace
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2018 to 2019
Semester: summer
E-Credits: 6
Hours per week, examination: summer s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Guarantor: prof. RNDr. Jiří Sgall, DrSc.
prof. RNDr. Martin Loebl, CSc.
Class: Informatika Bc.
Classification: Informatics > Optimalization
Annotation -
Last update: LOEBL/MFF.CUNI.CZ (09.11.2010)
An introduction to mainly discrete optimisation is given. The lecture is centered around the theory of linear programming.
Aim of the course - Czech
Last update: LOEBL/MFF.CUNI.CZ (09.11.2010)

Cílem přednášky je, aby se studenti seznámili se základními metodami diskrétní optimalizace a naučili se v optimalizaci orientovat tak, aby byli schopni sami rozpoznat nové trendy.

Course completion requirements -
Last update: Mgr. Jan Kynčl, Ph.D. (23.05.2019)

Hans Raj Tiwary:

To pass the tutorials it is required to get at least a half of total points for homework assigned during the semester and weekly quizzes. Due to the requirements, additional attempts to pass the tutorial are excluded.

Passing the tutorials is required before taking the exam.

Literature -
Last update: doc. Mgr. Milan Hladík, Ph.D. (22.11.2012)

A. Schrijver, Theory of linear and integer programming, John Wiley, 1986

W.J.Cook, W.H. Cunningham W.R.Pulleyblank, A. Schrijver, Combinatorial Optimization, John Wiley, 1997

J. Matoušek, B. Gärtner, Understanding and using linear programming, Springer, 2006.

J. Matoušek Introduction to Discrete Geometry. ITI Series 2003-150, MFF UK, 2003

Requirements to the exam -
Last update: Mgr. Jan Kynčl, Ph.D. (23.05.2019)

Hans Raj Tiwary:

For the main exam, the requirements correspond to the syllabus as covered by the lectures.

Syllabus -
Last update: LOEBL/MFF.CUNI.CZ (09.11.2010)

Linear and integer programming problem, examples

Combinatorial geometry, polytopes and their minimal description, Minkowski-Weyl's theorem

Duality of linear programming, Farkas' lemma

Simplex method, pivoting rules

Polynomial algorithms for linear programming (overview)

Unimodularity, König's lemma, network flows

Weighted matchings in general graphs, Edmonds' algorithm

Matching polytope

Integer programming

Approximation algorithms


Charles University | Information system of Charles University |