Home     Teaching     Research     Misc

Milan Hladík Celočíselné programování (NOPT016), letní semestr 2014/2015

Přednáska se cvičením se koná v úterý od 12:20 v S221 (chodba KAM, 2. patro) a od 14:00 v S9.

Aktuální: Začínáme dne 3.3. od 12:20. Ve dnech 24.2. a 17.3. přednáška a cvičení odpadá!

Podmínky pro zápočet: dostatečná aktivní účast na cvičeních a vypracování alespoň jednoho úkolu. Ilustrativní příklady v GAMSu jsou zde, ale můžete použít i jiný software.

Zajímavé úložky na promyšlení (PDF). Jejich vyřešení či dobře míněný pokus se počítají k dobru při zkoušce.

Probraná a plánovaná témata

3.3.	Formulace celočíselných úloh. Celočíselný polyedr a Meyerova věta. (Totálně) unimodulární matice: vztah k celočíselnému programování (Hoffman-Kruskalova věta), matici incidence orientovaného a neorientovaného grafu, dopravnímu problému a tokům v sítích.
10.3.	Formulace celočíselných úloh. NP-úplnost celočíselného programování. Velikost zápisu čísel a řešení soustav rovnic a nerovnic. Diskuse omezenosti úlohy, převod mezi optimalizační a rozhodovací úlohou.
24.3.	Metody sečných nadrovin - lexikografie, l-metoda a příklad. První Gomoryho algoritmus - formulace a základní vlastnosti.
31.3.	První Gomoryho algoritmus - příklad a důkaz konečnosti. Druhý Gomoryho algoritmus - odvození řezu.
7.4.	Druhý Gomoryho algoritmus - příklad. Letmo Chvátal-Gomoryho řezy. Metoda branch & bound a branch & cut - procházení stromu, volba proměnné na dělení.
14.4.	Preprocessing. Heuristiky. Problém batohu: složitost a relaxace.
21.4.	Problém batohu: úvod, relaxace, sečné nadroviny, branch & bound, preprocessing, použití. Set covering: úvod, branch & bound, preprocessing, set partitioning, hladový algoritmus.
21.4.	Set covering: aproximační faktor hladového algoritmu. Problém obchodního cestujícího: .

Software

V počítačové laborce K10 v Karlíně jsou dostupné následující programy:
• MATLAB: umí řešit pouze binární (0-1) úlohy lineárního celočíselného programování (funkce bintprog)
• GAMS (General Algebraic Modeling System). Používá různé řešiče (solvery) pro různé typy úloh - lineární a nelineární programování, lineární a nelineární celočíselné programování,... Pro lineární celočíselné programování je jedním z nejlepších CPLEX.
On-line optimalizace:
• NEOS, (zatím zdarma).
Další volně šiřitelný software:
• SCIP (Solving Constraint Integer Programs)
• GLPK (GNU Linear Programming Kit)
Komerční software:
• CPLEX od ILOG-u
• Gurobi
Články o software:
• A. Atamturk, M.W.P. Savelsbergh: Integer Programming Software Systems, 2007 (pěkný přehled).
• J.T. Linderoth, T.K. Ralphs: Noncommercial Software for Mixed-Integer Linear Programming, 2004.

Odkazy

Problém batohu:
• D. Pisinger: Algorithms for Knapsack Problems, 1995, disertační práce.
Problém obchodního cestujícího:
• TSP, mnoho informací, applety, zdarma ke stažení solver
• TSP, applet (anglicky)