1)
Porovnání elipsoidové metody vs. metody vnitřního bodu [výhody/nevýhody, podobnosti/odlišnosti...]
Na přednášce sice nebylo, ale je zajímavé se nad tím zamyslet:
Jaké jsou výhody EM oproti IPM?
Některé kombinatorické úlohy by vytvořily příliš velké vstupní matice. IPM by běželo v čase
, kde samotné L by už mohlo být exponenciálně velké (např. všechny cesty ze zdroje do spotřebiče v nějakém grafu/síti). EM není závislé na representaci vstupu, potřebuje jen znát, kdy je nějaká z omezujících podmínek/nerovností porušena. Pokud bychom měli k disposici orákulum/oracle/vědmu, které dokáže rychle ukázat na takový porušený řádek (třeba v polynomiálním čase), elipsoidová metoda vyřeší úlohu v polynomiálním čase i přes exponenciální počet podmínek.
Kupř.
úloha min řezu: proměnné = indikátory přítomnosti hrany v řezu; podmínky = součet řezových hran roven aspoň 1 (ale cest může být až exponenciálně, třeba v úplňáku); mininmalizuje samozřejmě součet řezových hran
To je celočíselná LP úloha. Zrelaxujeme a dostaneme LP. Jako oracle použijeme Dijkstrův algoritmus s hranami ohodnocenými nalezeným řešením. Je-li součet v nejkratší cestě menší než 1, je to neporušená cesta, nejde tedy o řez a nalezli jsme porušenou podmínku. Je-li aspoň 1, pak všechny cesty jsou aspoň 1 a tedy jde o řez. Nevím, jak se to pořeší s neceločíselnými proměnnými, ale to už je problém relaxace ILP.
2)
Skok ze skorooptimálního řešení do optimálního řešení v metodě vnitřního bodu [Dostatečný pokles potenciálu dá malé
, ten bude mít malé složky, dále Lemma 37 a 38, u těch chtěl i důkazy, je dobré to pochopit, nakonec garance, že dotyčný vrchol je optimální. Lze nahlédnout z
- viz skriptíčka doc. Kolmana]
1) [b]Porovnání elipsoidové metody vs. metody vnitřního bodu[/b] [výhody/nevýhody, podobnosti/odlišnosti...]
Na přednášce sice nebylo, ale je zajímavé se nad tím zamyslet: [i]Jaké jsou výhody EM oproti IPM?[/i]
Některé kombinatorické úlohy by vytvořily příliš velké vstupní matice. IPM by běželo v čase [latex]\mathcal{O}(n^{3.5}L)[/latex], kde samotné L by už mohlo být exponenciálně velké (např. všechny cesty ze zdroje do spotřebiče v nějakém grafu/síti). EM není závislé na representaci vstupu, potřebuje jen znát, kdy je nějaká z omezujících podmínek/nerovností porušena. Pokud bychom měli k disposici orákulum/oracle/vědmu, které dokáže rychle ukázat na takový porušený řádek (třeba v polynomiálním čase), elipsoidová metoda vyřeší úlohu v polynomiálním čase i přes exponenciální počet podmínek.
Kupř. [i]úloha min řezu[/i]: proměnné = indikátory přítomnosti hrany v řezu; podmínky = součet řezových hran roven aspoň 1 (ale cest může být až exponenciálně, třeba v úplňáku); mininmalizuje samozřejmě součet řezových hran
To je celočíselná LP úloha. Zrelaxujeme a dostaneme LP. Jako oracle použijeme Dijkstrův algoritmus s hranami ohodnocenými nalezeným řešením. Je-li součet v nejkratší cestě menší než 1, je to neporušená cesta, nejde tedy o řez a nalezli jsme porušenou podmínku. Je-li aspoň 1, pak všechny cesty jsou aspoň 1 a tedy jde o řez. Nevím, jak se to pořeší s neceločíselnými proměnnými, ale to už je problém relaxace ILP.
2) [b]Skok ze skorooptimálního řešení do optimálního řešení v metodě vnitřního bodu[/b] [Dostatečný pokles potenciálu dá malé [latex]x^Ts[/latex], ten bude mít malé složky, dále Lemma 37 a 38, u těch chtěl i důkazy, je dobré to pochopit, nakonec garance, že dotyčný vrchol je optimální. Lze nahlédnout z [latex]v^Ts = 0[/latex] - viz skriptíčka doc. Kolmana]