SubjectsSubjects(version: 901)
Course, academic year 2021/2022
  
Linear Programming and Combinatorial Optimization - NOPT048
Title: Lineární programování a kombinatorická optimalizace
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2020
Semester: summer
E-Credits: 5
Hours per week, examination: summer s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
Virtual mobility / capacity: no
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Additional information: https://iuuk.mff.cuni.cz/~sgall/vyuka/LP/
Guarantor: prof. RNDr. Martin Loebl, CSc.
prof. RNDr. Jiří Sgall, DrSc.
Class: Informatika Bc.
Classification: Informatics > Optimalization
Incompatibility : NOPX048
Interchangeability : NOPX048
Is incompatible with: NOPX048
Is interchangeable with: NOPX048
Files Comments Added by
download 01-uvod.mp4 úvod, úloha LP prof. RNDr. Jiří Sgall, DrSc.
download 01-uvod.pdf úvod, úloha LP prof. RNDr. Jiří Sgall, DrSc.
download 02-konvexni-mnoziny.mp4 nejkratší cesty, konvexní množiny prof. RNDr. Jiří Sgall, DrSc.
download 02-konvexni-mnoziny.pdf nejkratší cesty, konvexní množiny prof. RNDr. Jiří Sgall, DrSc.
download 03-konvexni-mnohosteny.mp4 konvexní mnohostěny prof. RNDr. Jiří Sgall, DrSc.
download 03-konvexni-mnohosteny.pdf konvexní mnohostěny prof. RNDr. Jiří Sgall, DrSc.
download 04-steny-mnohostenu.mp4 stény mnohostěnů prof. RNDr. Jiří Sgall, DrSc.
download 04-steny-mnohostenu.pdf stény mnohostěnů prof. RNDr. Jiří Sgall, DrSc.
download 05-minimalni-popis-mnohostenu.mp4 minimální popis mnohostěnu prof. RNDr. Jiří Sgall, DrSc.
download 05-minimalni-popis-mnohostenu.pdf minimální popis mnohostěnu prof. RNDr. Jiří Sgall, DrSc.
download 06-simplexova-metoda.mp4 simlplexová metoda prof. RNDr. Jiří Sgall, DrSc.
download 06-simplexova-metoda.pdf simlplexová metoda prof. RNDr. Jiří Sgall, DrSc.
download 07-algoritmy-pro-LP.mp4 algoritmy pro lineární programování prof. RNDr. Jiří Sgall, DrSc.
download 07-algoritmy-pro-LP.pdf algoritmy pro lineární programování prof. RNDr. Jiří Sgall, DrSc.
download 08-dualita-LP.mp4 dualita lineárního programování prof. RNDr. Jiří Sgall, DrSc.
download 08-dualita-LP.pdf dualita lineárního programování prof. RNDr. Jiří Sgall, DrSc.
download 09-dualita-parovani.mp4 dualita, podmínky komplementarity, párování v bipartitních grafech prof. RNDr. Jiří Sgall, DrSc.
download 09-dualita-parovani.pdf dualita, podmínky komplementarity, párování v bipartitních grafech prof. RNDr. Jiří Sgall, DrSc.
download 10-parovani-obecne-grafy.mp4 párování v obecných grafech prof. RNDr. Jiří Sgall, DrSc.
download 10-parovani-obecne-grafy.pdf párování v obecných grafech prof. RNDr. Jiří Sgall, DrSc.
download 11-totalni-unimodularita.mp4 totální unimodularita prof. RNDr. Jiří Sgall, DrSc.
download 11-totalni-unimodularita.pdf totální unimodularita prof. RNDr. Jiří Sgall, DrSc.
download 12-matroidy.mp4 matroidy a hladový algoritmus prof. RNDr. Jiří Sgall, DrSc.
download 12-matroidy.pdf matroidy a hladový algoritmus prof. RNDr. Jiří Sgall, DrSc.
download 13-celociselne-programovani.mp4 celočíselné programování, metoda řezů, mnohostěn párování, aproximační algoritmy prof. RNDr. Jiří Sgall, DrSc.
download 13-celociselne-programovani.pdf celočíselné programování, metoda řezů, mnohostěn párování, aproximační algoritmy prof. RNDr. Jiří Sgall, DrSc.
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: doc. Hans Raj Tiwary, M.Sc., Ph.D. (16.02.2022)

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.

Literature -
Last update: prof. 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

Matroids

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html