Optimalizační metody - NOPT048

LS 2012, Jiří Sgall, pátek 10:40, S9

Kontakt a konzultace

Konzultace nejlépe po předběžné domluvě mailem. Nejčastěji mě zastihnete v úterý 13-15 hod.

E-mail: last name at iuuk.mff.cuni.cz
Telefon: 221 914 293
http://iuuk.mff.cuni.cz/~sgall/
Pracovna: 3. patro, místnost 326, Malostranské nám. 25

Cvičení mají vlastní stránku.

Zkoušky

Termíny

Průběh zkoušky

Součastí zkoušky jsou příklady (napsat duální program, napsat lineární program pro daný problém, spočítat vrchol mnohostěnu apod.). Tato část zkoušky je prominuta studentům, kteří získali z úkolů alespoň 70 bodů.

Hlavní částí zkoušky je ústní zkouška z probírané teorie. Po zadání otázek budete mít čas na přípravu. Studijní materiály (skripta, učebnice a zápisky z přednášek) ani notebooky, kalkulačky, PDA, atd., nejsou u zkoušky dovoleny. Společenský oblek není nutný.

Literatura a další pomůcky

• Představu o přednášce si můžete udělat podle stránek prvního běhu z r. 2010.
  
• Poznámky k přednáškám z roku 2010
  
• Úvod, úloha lineárního a celočíselného programování, příklady
  
• Kombinatorická geometrie, mnohostěny
  
• Dualita lineárního programování, simplexová metoda
  
• Unimodularita, Königovo lemma, toky
• Párování v obecných grafech
• Polytop párování
• Celočíselné programování, metoda řezů
• Aproximační algoritmy, matroidy
  
• Knihy a skripta:
• skripta J. Matouška Lineární programování a lineární algebra pro informatiky, vyšla v ITI Series 2006-311 a jsou k zapůjčení v informatické knihovně MFF UK
• skripta J. Matouška Introduction to Discrete Geometry vyšla v ITI Series 2003-150 a jsou k zapůjčení v informatické knihovně MFF UK
• William J. Cook, William H. Cunningham, William R. Pulleyblank, and Alexander Schrijver: Combinatorial Optimization
  
• Laurence A. Wolsey and George L. Nemhauser: Integer and Combinatorial Optimization
• Laurence A. Wolsey: Integer Programming
• Howard Karloff: Linear Programming
  
• Zdroje na internetu:
• K. Fukuda: Frequently Asked Questions in Polyhedral Computation

Poznámky z přednášky

Postupně vznikající poznámky z teto přednášky budou k dispozici zde. Pro jejich psaní používejte prosím soubor s makry a jako pro text použijte buď vzor nebo dřívější přednášku. Vše je v kódování ISO-8859-2 a překládá se v pdfcslatex. (Pokud použijete jiné kódování nebo babel, je to také v pořádku.)

Větší opravy poznámek jsou v tabulce označeny tučným datem aktualizace. Kromě toho byly poznámky aktualizovány především o drobné opravy, které provedli kolegové Pavel Taufer, Jakub Hajič, Michal Koutný.

Probraná témata - aktuální

• 24. 2.
• úloha lineárního programování
• převedení rovnic na nerovnice atd.
  
• úloha celočíselného programování
• příklady: dopravní problém, hledání nejkratší cesty
• 2. 3.
• příklady: vrcholové pokrytí, nezávislá množina
  
• příklad: perfektní párování maximální váhy, optimum LP relaxace je rovno celočíselnému optimu
• opakování: afinní prostory, obal, kombinace, nezávislost
• definice: dimenze, konvexní množina, konvexní obal, konvexní kombinace
• konvexní obal X je množina všech konvexních kombinací bodů z X
• věta (Caratheodory): bod konvexního obalu X je konvexní kombinací kombinací nejvýše d+1 bodů z X, kde d je dimenze X
• 9. 3.
  
• definice: nadrovina, poloprostor
  
• definice: konvexní mnohostěn jako průnik poloprostorů
• terminologie: omezený konvexní mnohostěn
• věta o oddělování konvexních množin nadrovinou
  
• věta Minkowski-Weyl: X je omezený konvexní mnohostěn právě když X je konvexní obal konečné množiny bodů
• definice: kužel, polyedrální kužel
• věta (bez důkazu): kužel je generovaný jako nezáporné kombinace konečně mnoha vektorů
• věta (bez důkazu): konvexní mnohostěn je součet omezeného konvexního mnohostěnu a polyedrálního kuželu
  
• 16. 3.
  
• definice: stěna mnohostěnu, vrchol, faseta
• věta: omezený mnohostěn je konvexní obal vrcholů, vrcholy jsou právě extremální body
• věta: stěna stěny je stěna
• minimální popis mnohostěnu
• věta: dimenze polytopu je dána hodností systému rovnic v minimálním popisu
  
• věta: v minimálním popisu polytopu nerovnosti vzájemně jednoznačně odpovídají fasetám
• 23. 3.
  
• dokončení minimálního popisu polytopu
  
• stěna jako průnik faset
  
• svaz stěn mnohostěnu
• simplexová metoda
  
• příklad
  
• bázické řešení
  
• pivotovací krok
  
• 30. 3.
  
• simplexová metoda
  
• bázické řešení
• pivotovací krok obecně
• ukončení (optimum, neomezenost)
• nalezení počátečního řešení dvoufázovou metodou
  
• degenerovanost
• pivotovací pravidla
• efektivnost, zacyklení
• 6. 4.
• simplexová metoda
  
• nalezení počátečního řešení dvoufázovou metodou
• výpočetní složitost
  
• elipsoidová metoda, separační orákulum
• metody vnitřního bodu
• totálně unimodulární matice
• definice, důsledky pro LP
  
• totálně unimodulární matice se dvěma nenulovými prvky ve sloupci
• 13. 4.
• dualita: příklad, znění pro různé tvary LP, rovnicový tvar apod.
• Farkasovo lemma pro nerovnice pomocí Fourier-Motzkinovy eliminace
• Farkasovo lemma pro rovnice
  
• 20. 4.
  
• věta o odvozování libovolné platné nerovnosti, která je důsledkem soustavy nerovností
• dualita: důkaz z Farkasova lemmatu
• totálně unimodulární matice, dokončení, příklady
• 27. 4.
• toky a řezy: dualita a její důsledky
• Königova věta:  maximálního párování a minimálního vrcholové pokrytí v bipartitním grafu
• perfektní párování minimální ceny v bipartitním grafu pomocí primárně duálního algoritmu
• 4. 5.
• párování v obecných grafech
• párování maximální velikosti
• perfektní párování minimální ceny (Edmonsův kvítkový/blossom algoritmus)
• 11. 5.
• Edmondsův algoritmus, dokončení
  
• polytop párování, jeho vlastnosti, vrcholy, fasety
• aproximační algoritmy
• 2-aproximační algoritmus pro vrcholové pokrytí
• 18. 5.
• matroidy
• definice, charakterizace množiny bází
• příklady: vektorové prostory, lesy, Fano
• řádová funkce (rank) - definice a vlastnosti
  
• hladový algoritmus
• 25. 5.
• matroidy
• hladový algoritmus, dokončení
  
• polytop matroidu, jeho celočíselnost
• metoda řezů (sečných nadrovin, cutting plane methods)
• platný řez, příklady
  
• věta o univerzalitě: lze odvodit každou nerovnost platnou pro všechna celočíselná řešení
  
• přehled metod celočíselného programování