# Mat. prog. a polyedr. kombinatorika Kolman 10. 1. 2013

<{ForumPost(poster="mathemage", timestamp=2013-01-11 22:15:37)}>
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 $\mathcal{O}(n^{3.5}L)$, 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é $x^Ts$, 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 $v^Ts = 0$ - viz skriptíčka doc. Kolmana]
<{/ForumPost}>