Matematické programování a polyedrální kombinatorika - NOPT034

• Anglický název: Mathematical Programming and Polyhedral Combinatorics
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2021
• Semestr: letní
• E-Kredity: 4
• Rozsah, examinace: letní s.:2/1, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština, angličtina
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Další informace: https://kam.mff.cuni.cz/~kolman/matprog.html
• Garant: prof. RNDr. Martin Loebl, CSc.; doc. Mgr. Petr Kolman, Ph.D.; doc. Hans Raj Tiwary, M.Sc., Ph.D.
• Třída: Informatika Mgr. - Diskrétní modely a algoritmy
• Kategorizace předmětu: Informatika > Diskrétní matematika, Optimalizace
• Je neslučitelnost pro: NOPX034
• Je záměnnost pro: NOPX034

Anotace

čeština

Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (08.05.2019)

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

angličtina

Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (08.05.2019)

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

Podmínky zakončení předmětu

čeština

Poslední úprava: doc. Mgr. Petr Kolman, Ph.D. (30.09.2020)

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ě.

angličtina

Poslední úprava: doc. Mgr. Petr Kolman, Ph.D. (30.09.2020)

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.

Literatura

Poslední úprava: doc. Mgr. Jan Hubička, Ph.D. (06.09.2021)

• 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.

Požadavky ke zkoušce

čeština

Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (24.05.2019)

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

angličtina

Poslední úprava: doc. Mgr. Petr Kolman, Ph.D. (30.09.2020)

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

Sylabus

čeština

Poslední úprava: doc. Mgr. Jan Hubička, Ph.D. (06.09.2021)

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.

angličtina

Poslední úprava: doc. Mgr. Jan Hubička, Ph.D. (06.09.2021)

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

Ellipsoid algorithm

Interior point

Extended formulations