SubjectsSubjects(version: 916)
Course, academic year 2022/2023
   Login via CAS
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
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.
Class: Informatika Mgr. - Diskrétní modely a algoritmy
Classification: Informatics > Discrete Mathematics, Optimalization
Is incompatible with: NOPX034
Is interchangeable with: NOPX034
Annotation -
Last update: Mgr. Jan Kynčl, Ph.D. (08.05.2019)
A follow-up to the lecture Linear programming and combinatorial optimization NOPT048.
Course completion requirements -
Last update: 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.

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

Requirements to the exam -
Last update: doc. Mgr. Petr Kolman, Ph.D. (30.09.2020)

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

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

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

Ellipsoid algorithm

Interior point

Extended formulations

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