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

Co se jinam nevejde

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

Příspěvekod mathemage » 11. 1. 2013 22:15

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]
Carpe Diem!
mathemage
Matfyz(ák|ačka) level III
 
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Login do SIS: had

Zpět na Ostatní

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník

cron