\select@language {czech}
\contentsline {chapter}{\numberline {}{Seznam obr\IeC {\'a}zk\IeC {\r u}}}{xiii}{chapter*.5}
\contentsline {chapter}{\numberline {}{Seznam tabulek}}{xv}{chapter*.6}
\contentsline {chapter}{\numberline {1}\IeC {\'U}vod}{1}{chapter.1}
\contentsline {section}{\numberline {1.1}Obecn\IeC {\'y} \IeC {\'u}vod}{1}{section.1.1}
\contentsline {section}{\numberline {1.2}C\IeC {\'\i }l pr\IeC {\'a}ce}{2}{section.1.2}
\contentsline {section}{\numberline {1.3}\IeC {\v C}len\IeC {\v e}n\IeC {\'\i } pr\IeC {\'a}ce}{2}{section.1.3}
\contentsline {chapter}{\numberline {2}Probl\IeC {\'e}m pokryt\IeC {\'\i }}{3}{chapter.2}
\contentsline {section}{\numberline {2.1}Dominance}{3}{section.2.1}
\contentsline {subsection}{\numberline {2.1.1}Dominance \IeC {\v r}\IeC {\'a}dk\IeC {\r u}}{4}{subsection.2.1.1}
\contentsline {subsection}{\numberline {2.1.2}Dominance sloupc\IeC {\r u}}{4}{subsection.2.1.2}
\contentsline {subsection}{\numberline {2.1.3}Nezbytn\IeC {\'e} sloupce}{4}{subsection.2.1.3}
\contentsline {chapter}{\numberline {3}\IeC {\v R}e\IeC {\v s}en\IeC {\'\i } probl\IeC {\'e}mu pokryt\IeC {\'\i }}{5}{chapter.3}
\contentsline {section}{\numberline {3.1}Metoda v\IeC {\v e}tv\IeC {\'\i } a hranic}{5}{section.3.1}
\contentsline {subsection}{\numberline {3.1.1}Vylep\IeC {\v s}en\IeC {\'\i }}{6}{subsection.3.1.1}
\contentsline {subsection}{\numberline {3.1.2}Sn\IeC {\'\i }\IeC {\v z}en\IeC {\'\i } horn\IeC {\'\i } meze\IeC {\'\i }}{6}{subsection.3.1.2}
\contentsline {subsection}{\numberline {3.1.3}Spodn\IeC {\'\i } mez}{6}{subsection.3.1.3}
\contentsline {subsection}{\numberline {3.1.4}MSIR}{7}{subsection.3.1.4}
\contentsline {section}{\numberline {3.2}AURA II}{8}{section.3.2}
\contentsline {subsection}{\numberline {3.2.1}Heuristika MSIR}{8}{subsection.3.2.1}
\contentsline {section}{\numberline {3.3}Heuristick\IeC {\'e} metody}{9}{section.3.3}
\contentsline {subsection}{\numberline {3.3.1}Heuristika podle Serv\IeC {\'\i }ta}{10}{subsection.3.3.1}
\contentsline {subsection}{\numberline {3.3.2}Heuristika ContribAdd}{10}{subsection.3.3.2}
\contentsline {section}{\numberline {3.4}Lagrangeovsk\IeC {\'a} relaxace}{11}{section.3.4}
\contentsline {subsection}{\numberline {3.4.1}Principy Lagrangeovsk\IeC {\'e} relaxace}{11}{subsection.3.4.1}
\contentsline {subsection}{\numberline {3.4.2}Relaxace probl\IeC {\'e}mu pokryt\IeC {\'\i }}{11}{subsection.3.4.2}
\contentsline {subsection}{\numberline {3.4.3}Subgradientem \IeC {\v r}\IeC {\'\i }zen\IeC {\'y} postup}{12}{subsection.3.4.3}
\contentsline {subsection}{\numberline {3.4.4}Nastaven\IeC {\'\i } horn\IeC {\'\i } meze}{13}{subsection.3.4.4}
\contentsline {subsection}{\numberline {3.4.5}\IeC {\'U}prava \IeC {\v r}e\IeC {\v s}en\IeC {\'\i } probl\IeC {\'e}mu Lagrangeovsk\IeC {\'e} relaxace}{13}{subsection.3.4.5}
\contentsline {subsection}{\numberline {3.4.6}V\IeC {\'y}stupy Lagrangeovsk\IeC {\'e} relaxace}{15}{subsection.3.4.6}
\contentsline {section}{\numberline {3.5}Du\IeC {\'a}ln\IeC {\'\i } probl\IeC {\'e}m}{15}{section.3.5}
\contentsline {subsection}{\numberline {3.5.1}Du\IeC {\'a}ln\IeC {\'\i } probl\IeC {\'e}m probl\IeC {\'e}mu pokryt\IeC {\'\i }}{16}{subsection.3.5.1}
\contentsline {chapter}{\numberline {4}Implementace }{19}{chapter.4}
\contentsline {section}{\numberline {4.1}Z\IeC {\'a}kladn\IeC {\'\i } algoritmus}{19}{section.4.1}
\contentsline {subsection}{\numberline {4.1.1}Reprezentace matice}{20}{subsection.4.1.1}
\contentsline {subsection}{\numberline {4.1.2}Odstran\IeC {\v e}n\IeC {\'\i } dominanc\IeC {\'\i }}{20}{subsection.4.1.2}
\contentsline {subsection}{\numberline {4.1.3}T\IeC {\v r}\IeC {\'\i }d\IeC {\v e}n\IeC {\'\i } matice}{21}{subsection.4.1.3}
\contentsline {section}{\numberline {4.2}Lagrangeovsk\IeC {\'a} relaxace}{22}{section.4.2}
\contentsline {subsection}{\numberline {4.2.1}Algoritmus Lagrangeovsk\IeC {\'e} relaxace}{22}{subsection.4.2.1}
\contentsline {subsubsection}{\numberline {4.2.1.1}Parametry Lagrangeovsk\IeC {\'e} relaxace}{23}{subsubsection.4.2.1.1}
\contentsline {subsection}{\numberline {4.2.2}Algoritmus Du\IeC {\'a}ln\IeC {\'\i } Lagrangeovsk\IeC {\'e} relaxace}{23}{subsection.4.2.2}
\contentsline {subsubsection}{\numberline {4.2.2.1}Parametry Du\IeC {\'a}ln\IeC {\'\i } Lagrangeovsk\IeC {\'e} relaxace}{25}{subsubsection.4.2.2.1}
\contentsline {subsubsection}{\numberline {4.2.2.2}Optimalizace implementace}{25}{subsubsection.4.2.2.2}
\contentsline {subsection}{\numberline {4.2.3}Reprezentace matice}{25}{subsection.4.2.3}
\contentsline {subsection}{\numberline {4.2.4}Jazyk implemetace}{25}{subsection.4.2.4}
\contentsline {chapter}{\numberline {5}Experiment\IeC {\'a}ln\IeC {\'\i } v\IeC {\'y}sledky}{27}{chapter.5}
\contentsline {section}{\numberline {5.1}Testovac\IeC {\'\i } data a prost\IeC {\v r}ed\IeC {\'\i }}{27}{section.5.1}
\contentsline {section}{\numberline {5.2}Chov\IeC {\'a}n\IeC {\'\i } Lagrangeovsk\IeC {\'e} relaxace}{27}{section.5.2}
\contentsline {subsection}{\numberline {5.2.1}V\IeC {\'y}voj horn\IeC {\'\i } a spodn\IeC {\'\i } meze}{28}{subsection.5.2.1}
\contentsline {subsection}{\numberline {5.2.2}Konvergence multiplik\IeC {\'a}tor\IeC {\r u}}{29}{subsection.5.2.2}
\contentsline {subsection}{\numberline {5.2.3}Multiplik\IeC {\'a}tory kroku a iterace}{30}{subsection.5.2.3}
\contentsline {subsection}{\numberline {5.2.4}V\IeC {\'y}b\IeC {\v e}r heuristiky}{31}{subsection.5.2.4}
\contentsline {subsection}{\numberline {5.2.5}\IeC {\v C}etnost spou\IeC {\v s}t\IeC {\v e}n\IeC {\'\i } kompletuj\IeC {\'\i }c\IeC {\'\i } heuristiky}{31}{subsection.5.2.5}
\contentsline {subsection}{\numberline {5.2.6}Z\IeC {\'a}vislost b\IeC {\v e}hu relaxace na hustot\IeC {\v e} matice}{32}{subsection.5.2.6}
\contentsline {subsection}{\numberline {5.2.7}Z\IeC {\'a}vislost b\IeC {\v e}hu relaxace na velikosti matice}{32}{subsection.5.2.7}
\contentsline {section}{\numberline {5.3}Du\IeC {\'a}ln\IeC {\'\i } relaxace}{33}{section.5.3}
\contentsline {subsection}{\numberline {5.3.1}V\IeC {\'y}voj spodn\IeC {\'\i } a horn\IeC {\'\i } meze}{34}{subsection.5.3.1}
\contentsline {subsection}{\numberline {5.3.2}Srovn\IeC {\'a}n\IeC {\'\i } jednoduch\IeC {\'e} a du\IeC {\'a}ln\IeC {\'\i } relaxace}{35}{subsection.5.3.2}
\contentsline {section}{\numberline {5.4}Chov\IeC {\'a}n\IeC {\'\i } \IeC {\v r}e\IeC {\v s}i\IeC {\v c}e}{35}{section.5.4}
\contentsline {subsection}{\numberline {5.4.1}Z\IeC {\'a}vislost b\IeC {\v e}hu \IeC {\v r}e\IeC {\v s}i\IeC {\v c}e na hustot\IeC {\v e} matice}{36}{subsection.5.4.1}
\contentsline {subsection}{\numberline {5.4.2}Z\IeC {\'a}vislost b\IeC {\v e}hu \IeC {\v r}e\IeC {\v s}i\IeC {\v c}e na velikosti matice}{37}{subsection.5.4.2}
\contentsline {subsection}{\numberline {5.4.3}Z\IeC {\'a}vislost b\IeC {\v e}hu \IeC {\v r}e\IeC {\v s}i\IeC {\v c}e na nastaven\IeC {\'\i } Lagrangeovsk\IeC {\'e} relaxace}{38}{subsection.5.4.3}
\contentsline {section}{\numberline {5.5}Srovn\IeC {\'a}n\IeC {\'\i } \IeC {\v r}e\IeC {\v s}i\IeC {\v c}\IeC {\r u} probl\IeC {\'e}mu prokryt\IeC {\'\i }}{38}{section.5.5}
\contentsline {subsection}{\numberline {5.5.1}Porovn\IeC {\'a}n\IeC {\'\i } B\&B Lagrange s AURA II}{39}{subsection.5.5.1}
\contentsline {subsection}{\numberline {5.5.2}Porovn\IeC {\'a}n\IeC {\'\i } Lagrangeovsk\IeC {\'e} relaxace s heuristikami}{40}{subsection.5.5.2}
\contentsline {subsection}{\numberline {5.5.3}Porovn\IeC {\'a}n\IeC {\'\i } \IeC {\v r}e\IeC {\v s}i\IeC {\v c}\IeC {\r u} na re\IeC {\'a}ln\IeC {\'y}ch matic\IeC {\'\i }ch}{44}{subsection.5.5.3}
\contentsline {chapter}{\numberline {6}Za\IeC {\v c}len\IeC {\v e}n\IeC {\'\i } do programu BOOM}{47}{chapter.6}
\contentsline {chapter}{\numberline {7}Z\IeC {\'a}v\IeC {\v e}r}{49}{chapter.7}
\contentsline {chapter}{Literatura}{51}{chapter*.7}
\contentsline {chapter}{\numberline {A}Seznam pou\IeC {\v z}it\IeC {\'y}ch zkratek}{53}{appendix.A}
\contentsline {chapter}{\numberline {B}Obsah p\IeC {\v r}ilo\IeC {\v z}en\IeC {\'e}ho CD}{55}{appendix.B}
\contentsline {chapter}{\numberline {C}Ovl\IeC {\'a}d\IeC {\'a}n\IeC {\'\i } programu BOOM}{57}{appendix.C}
