Mathematical Programming and Polyhedral Combinatorics - NOPT034

• Title: Matematické programování a polyedrální kombinatorika
• Guaranteed by: Department of Applied Mathematics (32-KAM)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2021
• Semester: summer
• E-Credits: 4
• Hours per week, examination: summer s.:2/1, C+Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: Czech, English
• Teaching methods: full-time
• Additional information: https://kam.mff.cuni.cz/~kolman/matprog.html
• Guarantor: prof. RNDr. Martin Loebl, CSc.; doc. Mgr. Petr Kolman, Ph.D.; doc. Hans Raj Tiwary, M.Sc., Ph.D.
• Teacher(s): doc. Mgr. Petr Kolman, Ph.D.; doc. Hans Raj Tiwary, M.Sc., Ph.D.
• Class: Informatika Mgr. - Diskrétní modely a algoritmy
• Classification: Informatics > Discrete Mathematics, Optimalization
• Is incompatible with: NOPX034
• Is interchangeable with: NOPX034

Annotation

English

A follow-up to the lecture Linear programming and combinatorial optimization NOPT048.

Last update: Kynčl Jan, doc. Mgr., Ph.D. (08.05.2019)

Czech

Volné pokračování přednášky Lineární programování a kombinatorická optimalizace - NOPT048. Specializovanější témata.

Last update: Kynčl Jan, doc. Mgr., Ph.D. (08.05.2019)

Course completion requirements

English

The exam is oral. The requirements correspond to the syllabus as covered by the lectures. If university attendance is limited, the exam may be held online.

Last update: Kolman Petr, doc. Mgr., Ph.D. (30.09.2020)

Czech

Pro získání zápočtu je nutné získat polovinu z celkového počtu bodů za domácí úkoly zadané během semestru. Povaha kontroly studia neumožňuje opakování zápočtu.

V případě omezení přítomnosti studentů na univerzitě je možné zkoušku konat distančně.

Last update: Kolman Petr, doc. Mgr., Ph.D. (30.09.2020)

Literature

• M. Grotschel, L. Lovasz, A. Schrijver: Geometric Algorithms and Combinatorial Optimization

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

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

• B. Korte, J. Vygen: Combinatorial Optimization, Springer, 2000

• A. Schrijver: Combinatorial Optimization (3 volume, A,B, & C)

• Guenter M. Ziegler: Lectures on Polytopes

• Various research articles.

Last update: Hubička Jan, doc. Mgr., Ph.D. (06.09.2021)

Requirements to the exam

English

The exam is oral. The requirements correspond to the syllabus as covered by the lectures.

Last update: Kolman Petr, doc. Mgr., Ph.D. (30.09.2020)

Czech

Zkouška je ústní. Požadavky odpovídají sylabu v míře pokryté přednáškami.

Last update: Kynčl Jan, doc. Mgr., Ph.D. (24.05.2019)

Syllabus

English

Polyhedra/Polytopes: basic notions, face lattice, polar duality

Ellipsoid algorithm

Interior point

Extended formulations

Last update: Hubička Jan, doc. Mgr., Ph.D. (06.09.2021)

Czech

Mnohostěny a polytopy: základní pojmy, struktura množiny stěn, polární dualita

Elipsoidový algoritmus.

Metody vnitřního bodu.

Rozšířené formulace.

Last update: Hubička Jan, doc. Mgr., Ph.D. (06.09.2021)