Celočíselné programování - NOPT016

• Anglický název: Integer Programming
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2024
• Semestr: letní
• E-Kredity: 5
• Rozsah, examinace: letní s.:2/2, 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í
• Další informace: https://kam.mff.cuni.cz/~hladik/CP
• Garant: prof. Mgr. Milan Hladík, Ph.D.
• Vyučující: Mgr. Elif Garajová, Ph.D.; prof. Mgr. Milan Hladík, Ph.D.
• Třída: Informatika Mgr. - Diskrétní modely a algoritmy
• Kategorizace předmětu: Informatika > Optimalizace
• Je neslučitelnost pro: NOPX016
• Je prerekvizitou pro: NOPT020
• Je záměnnost pro: NOPX016

Anotace

čeština

Přednáška se zabývá optimalizačními problémy, kde některé proměnné mohou nabývat jen celočíselných hodnot. Úlohy celočíselného programování se často vyskytují v praktických problémech a mají silnou formulační schopnost. Díky vysoké výpočetní složitosti zároveň představují aktuální a důležitý směr výskumu. Poznámka: Předmět se obvykle koná jednou za dva roky.

Poslední úprava: T_KAM (26.04.2017)

angličtina

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.

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (07.04.2016)

Cíl předmětu

čeština

Seznámení studentů s celočíselným programováním, a to nejen s klasickými výsledky, ale i s novými trendy. Absolventi by měli být schopni aplikovat metodologii v praxi stejně dobře jako navázat na aktuální výzkum v oboru.

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (07.04.2016)

angličtina

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.

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (07.04.2016)

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

čeština

K získání zápočtu je potřeba alespoň 50% bodový zisk z každé série domácích úkolů zadaných v průběhu semestru.

Poslední úprava: Garajová Elif, Mgr., Ph.D. (13.02.2019)

angličtina

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.

Poslední úprava: Garajová Elif, Mgr., Ph.D. (13.02.2019)

Literatura

čeština

Doprovodný text:

https://kam.mff.cuni.cz/~hladik/CP/text_cp.pdf

Další literatura:

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

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (30.09.2021)

angličtina

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

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (07.04.2016)

Požadavky ke zkoušce

čeština

Zkouška je ústní a požadavky odpovídají sylabu předmětu v rozsahu, který byl presentován na přednášce.

Zkouška může mít kontaktní nebo distanční formu.

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (24.09.2020)

angličtina

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

The exam can have the present or the distant form.

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (24.09.2020)

Sylabus

čeština

• Formulace celočíselných úloh

• Celočíselný polyedr, unimodulární matice, NP-úplnost

• Metody sečných nadrovin a branch & bound

• První a druhý Gomoryho algoritmus

• Preprocessing. Heuristiky

• Problém batohu

• Set covering

• Problém obchodního cestujícího

Předpokládají se základní znalosti lineárního programování.

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (14.02.2023)

angličtina

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

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (14.02.2023)