SubjectsSubjects(version: 941)
Course, academic year 2023/2024
   Login via CAS
Integer Programming - NOPX016
Title: Celočíselné programování
Guaranteed by: Student Affairs Department (32-STUD)
Faculty: Faculty of Mathematics and Physics
Actual: from 2022
Semester: summer
E-Credits: 6
Hours per week, examination: summer s.:2/2, C+Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
Virtual mobility / capacity: no
State of the course: taught
Language: Czech
Teaching methods: full-time
Teaching methods: full-time
Is provided by: NOPT016
Guarantor: prof. Mgr. Milan Hladík, Ph.D.
Class: Informatika Mgr. - Diskrétní modely a algoritmy
Classification: Informatics > Optimalization
Pre-requisite : {NXXX007, NXXX008, NXXX009}
Incompatibility : NOPT016
Interchangeability : NOPT016
Annotation -
Last update: prof. Mgr. Milan Hladík, Ph.D. (07.04.2016)
The lecture studies optimization problems with discrete (integer) variables. Integer programming problems often arise in practical problems and many problems can be formulated in terms of integer programming. Due to high computational complexity, it is still a challenge and in focus of current research. Remark: The course can be tought once in two years.
Aim of the course -
Last update: prof. Mgr. Milan Hladík, Ph.D. (07.04.2016)

Students will learn not only the classical results in integer programming, but also the current trends. Absolvents should be able to apply their knowledge in practice and also do the reserach in this field.

Course completion requirements -
Last update: Mgr. Elif Garajová (13.02.2019)

To pass the tutorial, the student has to obtain at least 50 % of the points in each set of homework problems assigned during the semester.

Literature -
Last update: prof. Mgr. Milan Hladík, Ph.D. (07.04.2016)

[1] G.L. Nemhauser, L.A. Wolsey. Integer and combinatorial optimization. Wiley, New York, 1999.

[2] A. Schrijver. Theory of linear and integer programming. Repr. Wiley, Chichester, 1998.

[3] L.A. Wolsey. Integer programming. Wiley, Chichester, 1998.

Requirements to the exam -
Last update: prof. Mgr. Milan Hladík, Ph.D. (24.09.2020)

The exam is oral and consists of questions on subjects covered by the lectures.

The exam can have the present or the distant form.

Syllabus -
Last update: prof. Mgr. Milan Hladík, Ph.D. (14.02.2023)
  • Formulation of integer problems
  • Integer polyhedron, unimodular matrices, NP-completeness
  • Cutting planes and branch & bound methods
  • The first and second Gomory algorithms
  • Preprocessing. Heuristics
  • Knapsack problem
  • Set covering
  • Travelling salesman problem

It is assumed that the students have a basic knowledge of linear programming.

Charles University | Information system of Charles University |