IA102 Linear and Integer Optimization Tasks and their Solutions

Fakulta informatiky
jaro 2011
Rozsah
2/1. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: z.
Vyučující
prof. RNDr. Petr Hliněný, Ph.D. (přednášející)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Petr Hliněný, Ph.D.
Rozvrh
St 9:00–11:50 G123
Předpoklady
Matematické znalosti na úrovni základních kurzů lineární algebry (vektory, matice, lineární rovnice) a diskrétní matematiky (relace, grafy). Vítány jsou i úvodní znalosti topologie.
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Předmět si smí zapsat nejvýše 50 stud.
Momentální stav registrace a zápisu: zapsáno: 0/50, pouze zareg.: 0/50, pouze zareg. s předností (mateřské obory): 0/50
Mateřské obory/plány
předmět má 18 mateřských oborů, zobrazit
Cíle předmětu
This subject presents students with basic types of optimization tasks (e.g., combinatorial, linear, and integer optimization), and teaches the most common solution methods. The main focus is on explaining and understanding (not memorizing!) the presented solution methods, including their thorough mathematical background, so that the students would be able to combine these methods with other approaches in solving nonstandard optimization problems. At the end of the course students should be able to: understand and explain the network-flow algorithm, the simplex method, and the branch-and-bound algorithm; formulate suitable and sound mathematical models of practical optimization problems; and use available tools to solve these problems.
Osnova
  • Kombinatorická optimalizace: hladový algoritmus a jeho použití v příkladech.
  • Toky v sítích: formulace a použití. Dualita toků a řezů.
  • Úloha lineární optimalizace: formulace a aplikace.
  • Konvexita a mnohostěny v lineární optimalizaci.
  • Dualita úloh v lineární optimalizaci.
  • Vysvětlení principů simplexové metody pro řešení lineární optimalizace.
  • Implementace simplexové metody, umělé proměnné.
  • Degenerované úlohy, prevence zacyklení a délka výpočtu.
  • Úlohy celočíselné optimalizace: formulace a příklady.
  • Obecné vysvětlení metody větvení a mezí, relaxace úlohy.
  • Kombinatorické optimalizační problémy.
  • Umění formulace úloh celočíselné optimalizace.
  • Pokročilá diskrétní optimalizace.
Literatura
  • P. Hliněný, Optimalizační úlohy, http://www.fi.muni.cz/~hlineny/Teaching/OU/OU-text07.pdf.
  • NEMHAUSER, George L. a Laurence A. WOLSEY. Integer and combinatorial oprimization. New York: John Wiley & Sons, 1988, 763 s. ISBN 0-471-82819-X. info
  • JANÁČEK, Jaroslav. Matematické Programování. Žilina, SK: EDIS Žilinská Univerzita, 2003. info
Výukové metody
This is an advanced course, taught mostly in English (with also Czech materials), and conducted quite informally (a seminar-type lecturing). Students are expected to actively participate in all the lectures and tutorials.
Metody hodnocení
Evaluation is based on a mandatory written individual homework assignment (one essay), and on a subsequent oral exam.
Vyučovací jazyk
Angličtina
Informace učitele
http://is.muni.cz/el/1433/jaro2011/IA102/index.qwarp
Online course materials - main: P. Hliněný, Optimalizační úlohy, "http://www.fi.muni.cz/~hlineny/Teaching/OU/OU-text07.pdf" (in czech). Supplementary: R.J. Vanderbei, Linear Programming: Foundations and Extensions, "http://www.princeton.edu/~rvdb/LPbook/". A. Schrijver, A Course in Combinatorial Optimization. "http://homepages.cwi.nl/~lex/files/dict.pdf", CWI, Amsterdam. Sven O. Krumke, Course Materials, "http://optimierung.mathematik.uni-kl.de/~krumke/lecturenotes.html".
Další komentáře
Studijní materiály
Předmět je vyučován jednou za dva roky.
Předmět je zařazen také v obdobích podzim 2005, jaro 2007, jaro 2009.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/fi/jaro2011/IA102