SubjectsSubjects(version: 962)
Course, academic year 2024/2025
   Login via CAS
Mathematical Programming and Polyhedral Combinatorics - NOPX034
Title: Matematické programování a polyedrální kombinatorika
Guaranteed by: Student Affairs Department (32-STUD)
Faculty: Faculty of Mathematics and Physics
Actual: from 2022
Semester: winter
E-Credits: 5
Hours per week, examination: winter 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
Teaching methods: full-time
Teaching methods: full-time
Is provided by: NOPT034
Guarantor: prof. RNDr. Martin Loebl, CSc.
doc. Mgr. Petr Kolman, Ph.D.
Class: Informatika Mgr. - Diskrétní modely a algoritmy
Classification: Informatics > Discrete Mathematics, Optimalization
Pre-requisite : {NXXX007, NXXX008, NXXX009, NXXX036, NXXX037}
Incompatibility : NOPT034
Interchangeability : NOPT034
Annotation -
A follow-up to the lecture Linear programming and combinatorial optimization NOPT048.
Last update: Kynčl Jan, doc. Mgr., Ph.D. (08.05.2019)
Course completion requirements -

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)
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 -

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)
Syllabus -

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)
 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html