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

[mathemage]

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]