Celočíselné programování

Cvičení k přednášce M. Hladíka, které se koná ve čtvrtek od 9:00. Případné dotazy a připomínky můžete směřovat na adresu elif@kam.mff.cuni.cz.


V případě distanční výuky se bude cvičení konat přes Zoom. Odkaz na příslušný Zoom meeting bude všem přihlášeným studentům zaslán před prvním cvičením. Pokud máte zájem získat odkaz na online cvičení dodatečně, napište mi.

Požadavky na zápočet

  • K získání zápočtu je potřeba alespoň 50% bodový zisk (= 10 bodů) z každé série domácích úkolů. Dodatečné body je možno získat řešením bonusových domácích úkolů zadáných koncem semestru.
  • Řešení domácích úkolů zasílejte v rozumně čitelné podobě e-mailem na adresu elif@kam.mff.cuni.cz (ideálně jeden pdf soubor).

Stav získaných bodů

Přehled získaných bodů za domácí úkoly: ✔ = alespoň 50%, ✘ = méně než 50%.
Pokud máte zájem o přidání do tabulky, napište mi svoji zvolenou přezdívku.

Přezdívka S1 S2 S3 S4 S5 Σ
Maximalistický student 20 20 20 20 20 100
Eudaimonia
50713
PP

Náplň cvičení

11.03.2021

Formulace úloh celočíselného programování.

01.04.2021

Celočíselné polyedry. (Totálně) unimodulární matice. Složitost celočíselného programování.

22.04.2021 (plán)

Metody pro řešení celočíselných úloh: sečné nadroviny a branch-and-bound.

06.05.2021 (plán)

Heuristiky, dekompozice, column generation. Software pro řešení celočíselných úloh.

20.05.2021 (plán)

Speciální případy: Problém batohu, TSP a další.

Odkazy a studijní materiály

  • Doprovodný text k přednášce (M. Hladík)
  • Modelovací kuchařky: MOSEK, FICO
  • Solvery pro řešení optimalizačních úloh: NEOS (online), CPLEX, GAMS, GLPK, Gurobi, SCIP
  • The Cutting Plane Game (G. Muñoz)
  • Další literatura: Integer Programming (L. Wolsey), Theory of Linear and Integer Programming (A. Schrijver), Applied Integer Programming (D. Chen et al.), Integer Programming (M. Conforti et al.)