Linear programming and combinatorial optimization - NOPX048
Title: Lineární programování a kombinatorická optimalizace
Guaranteed by: Student Affairs Department (32-STUD)
Faculty: Faculty of Mathematics and Physics
Actual: from 2020
Semester: summer
E-Credits: 6
Hours per week, examination: summer s.:2/2, C+Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: taught
Language: Czech
Teaching methods: full-time
Teaching methods: full-time
Is provided by: NOPT048
Guarantor: prof. RNDr. Martin Loebl, CSc.
prof. RNDr. Jiří Sgall, DrSc.
Class: Informatika Bc.
Classification: Informatics > Optimalization
Pre-requisite : {NXXX015, NXXX018, NXXX022, NXXX023, NXXX024, NXXX025, NXXX030, NXXX031, NXXX033}
Incompatibility : NOPT048
Interchangeability : NOPT048
Is incompatible with: NOPT048
Is interchangeable with: NOPT048
Opinion survey results   Examination dates   SS schedule   Noticeboard   
Annotation -
An introduction to mainly discrete optimisation is given. The lecture is centered around the theory of linear programming.
Last update: LOEBL/MFF.CUNI.CZ (09.11.2010)
Aim of the course - Czech

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.

Last update: LOEBL/MFF.CUNI.CZ (09.11.2010)
Course completion requirements -

Hans Raj Tiwary:

Students need to pass 50% of the homeworks and 50% of the quizzes to pass the tutorial. Due to the requirements, additional attempts to pass the tutorial are excluded.

Passing the tutorials is required before taking the exam.

Last update: Tiwary Hans Raj, doc., M.Sc., Ph.D. (16.02.2022)
Literature -

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

Last update: Hladík Milan, prof. Mgr., Ph.D. (22.11.2012)
Requirements to the exam -

Hans Raj Tiwary:

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

Last update: Kynčl Jan, doc. Mgr., Ph.D. (23.05.2019)
Syllabus -

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

Matroids

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