\documentclass[twoside,a4paper,12pt]{report}
\usepackage[czech]{babel}
\usepackage[utf8]{inputenc}
\usepackage{indentfirst}
\usepackage{graphicx}
\usepackage{k336_thesis_macros}
\usepackage{algorithmic}
\usepackage[subsection]{algorithm}
\usepackage{alltt}
\usepackage{float}
\usepackage{multirow}
\usepackage[
bookmarks=true,
colorlinks=true,
breaklinks=true,
urlcolor=red,
citecolor=blue,
linkcolor=blue,
unicode=true,
]
{hyperref} 
\newtheorem{definition}{Definice}[section]
\newtheorem{sentence}{Věta}[section]
\addtolength{\evensidemargin}{-20pt}
\addtolength{\oddsidemargin}{-10pt}
\begin{document}
\pagenumbering{roman} \thispagestyle{empty}



\vfill
\pagebreak
zde je zadani
\cleardoublepage

\begin{center}

České vysoké učení technické v Praze\\
Fakulta elektrotechnická\\
\vglue 10mm
\includegraphics[width=50mm]{logocvut}
\vglue 30mm
{\large Diplomová práce}\\
\bigskip
{\Large\bf Řešení problému pokrytí}\\
\bigskip
\bigskip
{\Large\it Bc. Filip Cakl}\\
\vfill
\item[Vedoucí práce:]\ Ing. Petr Fišer\\
\vglue 15mm
{Studijní program: Elektrotechnika a informatika, strukturovaný, Navazující magisterský}\\
\bigskip
{Obor: Výpočetní technika}\\
\bigskip
květen\ 2010
\end{center}
\newpage
\cleardoublepage
\vfill
\chapter*{Poděkování}
Mé poděkování patří ing. Petru Fišerovi za odborné vedení, trpělivou pomoc a veškerý čas, který mi věnoval při zpracovávání této diplomové práce. Dále bych rád poděkoval rodině za podporu, bez které by pro mne psaní této práce bylo mnohem obtížnější.
\pagebreak
\cleardoublepage

\vfill
\chapter*{Prohlášení}
Prohlašuji, že jsem svou diplomovou práci vypracoval samostatně a použil jsem pouze podklady uvedené v přiloženém seznamu.
Nemám závažný důvod proti užití tohoto školního díla ve smyslu \S 60 Zákona č. 121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o změně některých zákonů (autorský zákon).
\\[15mm]
V Praze dne 1.12.2009   \hfill \hbox to 70mm{\tiny\dotfill}
\pagebreak

\cleardoublepage

\abstractpage

\noindent
This thesis is focused on method of solving covering problem which uses Lagrangean re\-la\-xa\-ti\-on. Covering problem occurs in several fields of computer science, logic synthesis and reliability analysis. This thesis contains design and implementation of algorithm, that solves covering problem by exploring the problem space with using branch and bound method. Heuristic used for branching is based on Lagrangean relaxation. Behavior of algorithm is studied and algorithm’s efficiency is compared to AURAII. I have been given materials mentioned in the References. Final implementation of algorithm is integrated into program BOOM.

% Prace v cestine musi krome abstraktu v anglictine obsahovat i
% abstrakt v cestine.
\vglue60mm

\noindent{\Huge \textbf{Abstrakt}}
\vskip 2.75\baselineskip

\noindent
Tato práce se zabývá řešením problému pokrytí pomocí Lagrangeovské relaxace. Problém pokrytí se objevuje v mnoha oblastech počítačového výzkumu, syntéze logických obvodů  a analýze spolehlivosti. Tato práce obsahuje návrh a implementaci algoritmu, který řeší problém pokrytí prohledáváním stavového prostoru problému metodou větví a hranic. Pro ořezávání větví je využita heuristika založená na Lagrangeovské relaxaci. Studováno je chování této relaxace a rozdíly ve výkonnosti navrženého algoritmu proti algoritmu AURA II. Výsledný algoritmus je začleněn do programu BOOM. 

\cleardoublepage
\tableofcontents

\cleardoublepage
\listoffigures
\addcontentsline{toc}{chapter}{\protect\numberline{}{Seznam obrázků}}

\cleardoublepage
\listoftables
\addcontentsline{toc}{chapter}{\protect\numberline{}{Seznam tabulek}}

\cleardoublepage

\pagenumbering{arabic}

% kapitola 1
\chapter{Úvod}
\section{Obecný úvod}

Problém pokrytí má použití v mnoha oblastech počítačového výzkumu. Je nutné jej řešit při syntéze logických obvodů,  dvouúrovňové minimalizaci logických obvodů a plánování rozvržení zdrojů.

Řešení tohoto problému bývá obecně časově náročné – jedná se o NPO úplný problém. Byly navrženy mnohé algoritmy, které se liší v časových složitostech a kvalitě nalezených řešení.  

Jedním ze způsobů, jak najít řešení, může být využití rekurzivního algoritmu, který zkouší smysluplné kombinace prvků řešení, dokud není nalezeno minimální pokrytí. Tento způsob řešení je ale časově velmi náročný. Snížení  výpočetního času může být dosaženo například zamezením prohledávání prostoru v místech, kde se řešení nenachází \cite{1}.

Dále je možné využít genetických algoritmů nebo algoritmů simulovaného ochlazování. I tyto algoritmy jsou ale časově náročné \cite{3}.

Existují však i jiné možnosti - jednou z nich je použití heuristik, které dokážou najít řešení pokrytí v přípustném čase. Tento způsob je ovšem bývá vykoupen neoptimálností takto nalezeného řešení. Pro rozsáhlé problémy je to obvykle jediná možná varianta z důvodu časové náročnosti \cite{6} \cite{7}.
	
Tato práce vychází z diplomové práce „Moderní metody řešení problému pokrytí z roku 2008 od Lukáš Krejčíka, v které byl zpracován algoritmus pro nalezení optimálního řešení AURA II  \cite{2}. 

Lagrangeovská relaxace spočívá v transformaci problému pokrytí na problém Lagran\-geovský, kdy se  omezující podmínky problému přemění do tvaru tzv. trestných koeficientů (multiplikátorů). Při hledání optimálního řešení se tyto multiplikátory projevují v závislosti na plnění nebo neplnění omezujících podmínek původního problému. Optimální řešení La\-gran\-geovského problému tvoří spodní mez původního problému, což je vlastnost, kterou algoritmus popsaný v této práci využívá.

\newpage

\section{Cíl práce}

Cílem této práce je popsat Lagrangeovskou relaxaci a použít jí v algoritmu, který řeší problém pokrytí.
Chování Lagrangeovské relaxace by mělo být prostudováno a popsáno.

Druhým cílem je zakomponování vytvořeného algoritmu do exaktního algoritmu založeném na metodě vetví a hranic, tak, aby sloužil pro určování spodní meze ceny řešení. Takto vytvořený řešič bude porovnán se stávajícími algoritmy řešící problém pokrytí (AURA II, heuristické metody).

Vytvořený řešič má být zakomponován do minimalizátoru BOOM.

\section{Členění práce}

V předchozích odstavcích byly představeny některé algoritmy pro řešení problému pokrytí a byly specifikovány cíle této práce. 

V následující kapitole je přesně definován problém pokrytí a některé základní pojmy. 

Třetí kapitola se zabývá existujícími způsoby řešení problému pokrytí - základní rekurzivní algoritmus s využitím horních a spodním mezí, heuristiky pro řešení problému pokrytí a nakonec principy Lagrangeovské relaxace. 

V čtvrté kapitole jsou popsány vytvořené algoritmy. Nejdříve celkový řešič problému pokrytí. Poté samotný algoritmus založený na Lagrangeovské relaxaci. 

Pátá kapitola obsahuje popis prováděného měření a jejich výsledky. 

Šestá kapitola se zabývá začleněním vytvořených algoritmů do programu BOOM. 

V poslední kapitole jsou shrnuty výsledky práce a nástin možností dalšího rozšíření této práce.

\cleardoublepage
%kapitola 2

\chapter{Problém pokrytí}

V této kapitole jsou shrnuty základní pojmy, definice problému pokrytí a možnosti jeho řešení.

\begin{definition}
\label{problem}
Nechť $X=\{x_{1}, x_{2}, ..., x_{m}\}$ je množina řádků a $Y=\{y_{1}, y_{2}, ..., y_{n}\}$ je mno\-žina sloupců v matici $A$ o rozměrech $m \times n$ a $CENA$ je funkce definovaná na $Y \mid cena(y)\rightarrow R$, která každému $y\in Y$ přiřadí kladné reálné číslo. Prvek $y_{j} \in Y$ pokrývá prvek $x_{i}\in X$ pokud $A[i,j]=1$, jinak  $A[i,j]=0$. Problém pokrytí $\langle X,Y,CENA\rangle$ spočívá v nalezení podmnožiny $S$ množiny $Y$ takové, že pro každý prvek $x$ množiny $X$ existuje prvek $y$ množiny $Y$ tak, že $xRy$, přičemž součet $CENA(S)$ je minimální.
\end{definition}

Jinými slovy: je dána matice $A$, jejíž všechny prvky jsou  rovny $1$ nebo $0$. Řádek $x_{i}$ je pokrytý sloupcem $y_{j}$ pokud $A_{i,j} = 1$. Sloupce jsou ohodnoceny kladným reálným číslem, zvaným cena sloupce.  Řešení problému pokrytí spočívá v nalezení podmnožiny sloupců matice $A$ tak, že každý řádek matice $A$ je pokrytý alespoň jedním sloupcem podmnožiny, přičemž souhrnná cena sloupců v dané podmnožině je minimální. Tuto souhrnná cena bude dále označována jako cena řešení.

\section{Dominance}

Při hledání řešení je možné pracovat pouze s \emph{cyklickým jádrem}  matice $A$, které se získá tzv. \emph{odstraněním dominancí}. Tyto pojmy jsou objasněny na následujícím příkladu.

\begin{table*}[htb]
	\centering
		\begin{tabular}{|c|c|c|c|c|}
			\hline
			$x_{1}$ &  &  & 1 & \\
			\hline
			$x_{2}$ &1  &1  &  &1 \\
			\hline
			$x_{3}$ &  &1  &  &1 \\
			\hline
			$x_{4}$ &  & 1 & 1 &1 \\
			\hline
			& $y_{1}$  & $y_{2}$  & $y_{3}$ & $y_{4}$ \\
			\hline			
		\end{tabular}
	\caption{Příklad na dominance}
	\label{tab:dominance}
\end{table*}

\subsection{Dominance řádků}

\begin{definition}
Nechť $\langle X,Y,CENA \rangle$ je problém pokrytí. Řádek $x'$ množiny $X$ všech řádků dominuje $x$ právě tehdy, když všechny prvky množiny sloupců $Y$ které pokrývají $x'$ pokrývají také $x$.
\end{definition}

Jinými slovy: pokud nějaký řádek $x'$ obsahuje ve sloupcích jedničky a jiný řádek $x$ obsahuje jedničky ve stejných sloupcích, ($x$ může obsahovat jedničky i na dalších sloupcích), tak $x'$ dominuje $x$. Vždy, kdy je pokryt řádek $x'$, bude pokryt i řádek $x$. Řádek $x$ tedy může být vyřazen z matice. 

V tabulce ~\ref{tab:dominance} je vidět, že řádek $x_{3}$ dominuje řádku $x_{4}$, protože řádek $x_{3}$ je pokryt sloupci $y_{2}$ a $y_{4}$ a oba tyto sloupce také pokrývají řádek $x_{4}$. Totéž platí i pro řádek $x_{2}$. To, že řádek $x_{3}$ dominuje řádkům $x_{2}$ a $x_{4}$, znamená, že výběrem sloupce pokrývající řádek $x_{3}$ dojde vždy k pokrytí řádků $x_{2}$ a $x_{4}$. Proto lze řádky $x_{2}$ a $x_{4}$ vyloučit z matice. 


\subsection{Dominance sloupců}

\begin{definition}
Nechť $\langle X,Y, CENA \rangle$ je problém pokrytí. Sloupec $y'$ množiny všech sloupců $Y$  dominuje sloupci $y$ právě tehdy, když všechny prvky množiny řádků $X$, které jsou pokryty $y$ jsou také pokryté $y'$.
\end{definition}

To znamená, že pokud nějaký sloupec $y'$ obsahuje jedničky ve všech řádcích, ve kterých je obsahuje sloupec $y$ ( $y'$ může obsahovat jedničky i na jiných řádcích ), tak $y'$ dominuje $y$. 

V tabulce ~\ref{tab:dominance} je vidět, že sloupec $y_{4}$ dominuje sloupcům $y_{2}$ a $y_{1}$ a zároveň sloupec $y_{2}$ dominuje sloupcům $y_{4}$ a $y_{1}$. Nabízí se tedy možnost vyloučit z matice sloupce $y_{4}$ nebo $y_{2}$. Při vylučování sloupců se však musí dát pozor na to, aby se nepřišlo o minimální řešení. Vyloučení je možné jen tehdy, pokud cena dominujícího sloupce menší než cena sloupce, kterému sloupec dominuje. Nelze tedy vyloučit sloupec $y_{2}$, kterému dominuje sloupec $y_{4}$, protože jeho cena je menší než cena sloupce $y_{4}$.


\subsection{Nezbytné sloupce}

Sloupec $y$ množiny sloupců $Y$ je nezbytný, pokud je jediný, který pokrývá řádek $x$ z množiny řádků $X$. Tyto sloupce musí vždy patřit do řešení, můžou být proto z matice vyřazeny a problém tak může být redukován. Minimální řešení původního problému lze získat přidáním těchto sloupců do minimálního řešení redukovaného problému. 

Při řešení dominancí sloupců však v matici mohou vzniknout nové dominance řádků a naopak. Algoritmus řešící problém pokrytí tedy musí opakované řešit dominance, dokud se v matici nějaké vyskytují. Při nalezení nezbytných sloupců musí tyto zahrnout do řešení. Algoritmus na matici aplikujeme algoritmy popsané výše tak dlouho, dokud je matice re\-du\-ko\-vá\-na odstraňováním dominancí.


\cleardoublepage
% kapitola 3
\chapter{Řešení problému pokrytí}
\label{RPP}

Pokud jsou na matici aplikovány výše uvedené techniky, matice se dostane do stavu, kdy ji tyto procesy již více nezmenší. Zbylá matice se nazývá \emph{cyklické jádro matice}, $\langle X,Y, CENA \rangle$. Pokud je prázdné, množina všech nezbytných prvků byla nalezena během procesů popsaných výše. 

\section{Metoda větví a hranic}

\begin{algorithm}
\caption{Branch and Bound}
\label{alg:alg1}


Branch\_and\_bound($A$,$Path$) \{
\vspace{1 mm}

\hspace{4 mm}/* odstraní dominantní řádky a sloupce, 

\hspace{4 mm}vybere do řešení nezbytné sloupce */

\hspace{4 mm}$A$ = solve\_dominance($A$);
\vspace{2 mm}

\hspace{4 mm}if ( $A$ == $\emptyset$ ) \{

\hspace{8 mm}if ( cost($Path$) $<$ $UB$ ) $UB$ = cost($Path$)

\hspace{8 mm}$bestSolution = Path$

\hspace{4 mm}\} else \{

\hspace{8 mm}$j$ = select\_column($A$);

\hspace{8 mm}$Path1$= $Path+j$;

\hspace{8 mm}$A'$ = $A$ - \{ $j$ + rows\_covered\_ by($j$) \}

\hspace{8 mm}$Solution1$ = Branch\_And\_Bound($A'$,$Path1$)

\hspace{8 mm}$A''$ = $A$ – \{$j$\}

\hspace{8 mm}$Solution2$ = Branch\_And\_Bound($A''$,$Path2$)

\hspace{8 mm}$bestSolution$ = min( $Solution1$ , $Solution2$ )

\hspace{4 mm}\}

\hspace{4 mm}return $bestSolution$

\}

\vspace{4 mm}

\end{algorithm}

Pokud je nalezeno cyklické jádro, je třeba v něm najít minimální řešení. Nalezení přesného řešení problému pokrytí lze dosáhnout pomocí rekurzivního algoritmu - metodou větví a hranic popsané v \cite{1} spočívajícím ve výběru sloupců do řešení a hledáním smysluplné kombinace sloupců tak, aby byly pokryty všechny řádky a zároveň cena řešení byla co nejmenší. Al\-go\-rit\-mus je schopen vyloučit z řešení takové kombinace sloupců, jejichž cena je vyšší než cena zatím nejlepšího nalezeného řešení (cenu dosud nejlepšího nalezeného řešení označujeme jako horní mez – $UB$).

Stavový prostor algoritmu je reprezentován binárním stromem. Kořen stromu představuje počáteční problém, hrany znamenají rekurzivní volání algoritmu, cesty do jednotlivých uzlů reprezentují částečné nalezené řešení ($Path$). List je dosažen tehdy, když je nalezeno řešení, nebo cena nalezeného řešení překročila horní mez. Vstupem algoritmu je cyklické jádro problému ($A$), výstupem je minimální řešení pokrytí ($bestSolution$).

\subsection{Vylepšení}

Tento algoritmus lze vylepšit dvěma způsoby:
\begin{enumerate}
\item Snížením horní meze $UB$
\item Zavedením spodní meze $LB$
\end{enumerate}

\subsection{Snížení horní mezeí}
\label{lowerUB}

Čím nižší bude horní mez, tím více bude algoritmus ořezávat větve které nevedou na optimální řešení a tím rychlejší prohledávání prostoru ve výsledku bude. Snížení horní meze lze docílit dvěma způsoby:
\begin{enumerate}
\item Použitím heuristiky. Tento krok je vhodný provést především před samotným spuštěním algoritmu větví a hranic. Docílí se tím to, že algoritmus omezí prohledávání stavového prostoru hlavně pro počáteční fáze prohledávání.
\item Vhodným výběrem sloupců. Pokud algoritmus již od počátku běhu vybírá sloupce tak, že první nalezené řešení bude mít nízkou (pokud možno optimální) cenu, omezí se tím prohledávaný prostor.
\end{enumerate}

\subsection{Spodní mez}

Předpokládejme, že známe hodnotu $LB(A_{N})$ reprezentující minimální cenu řešení po\-třeb\-nou pro pokrytí matice $A$ v daném stavu $N$. Tato hodnota poskytuje spodní mez řešení matice $A$. V takovém případě, pokud :

\begin{equation}
UB \leq LB(A_{N}) + cena(Path)
\end{equation}

hledání lze zastavit a algoritmus se ve stavovém prostoru může vrátit zpět. 
Následuje popis algoritmu využívající znalost spodní meze (LB).

\newpage

\begin{algorithm}
\caption{Branch and Bound s využitím spodní meze}
\label{alg:alg2}

Branch\_and\_bound\_LB($A$,$Path$) \{
\vspace{1 mm}

\hspace{4 mm}/* odstraní dominantní řádky a sloupce, 

\hspace{4 mm}vybere do řešení nezbytné sloupce */

\hspace{4 mm}$A$ = solve\_dominance($A$);
\vspace{2 mm}

\hspace{4 mm}/*Nalezne spodní mez pro aktuální problém*/

\hspace{4 mm}$LB$  = find\_lower\_bound($A$);

\hspace{4 mm}$lBoundNew$ = cost($Path$) + $LB$ 
\vspace{2 mm}

\hspace{4 mm}if ( $lBoundNew \ge UB$ ) \{

\hspace{8 mm}/*pokud jsme již dosáhli spodní meze, nebudeme větvit dále*/

\hspace{8 mm}$bestSolution = \emptyset$

\hspace{8 mm}return $bestSolution$

\hspace{4 mm}\}
\vspace{2 mm}

\hspace{4 mm}if ( $A$ == $\emptyset$ ) \{

\hspace{8 mm}if ( cost($Path$) $<$ $UB$ ) $UB$ = cost($Path$)

\hspace{8 mm}$bestSolution = Path$

\hspace{4 mm}\} else \{

\hspace{8 mm}$j$ = select\_column($A$);

\hspace{8 mm}$Path1$= $Path+j$;

\hspace{8 mm}$A'$ = $A$ - \{ $j$ + rows\_covered\_ by($j$) \}

\hspace{8 mm}$Solution1$ = Branch\_And\_Bound($A'$,$Path1$)

\hspace{8 mm}$A''$ = $A$ – \{$j$\}

\hspace{8 mm}$Solution2$ = Branch\_And\_Bound($A''$,$Path2$)

\hspace{8 mm}$bestSolution$ = min( $Solution1$ , $Solution2$ )

\hspace{4 mm}\}

\hspace{4 mm}return $bestSolution$

\}
\vspace{4 mm}

\end{algorithm}

Způsob, jak zjistit hodnotu $LB(A_{N})$, může být např. zjištěním množiny nezávislých řádků - MSIR (\emph{maximum set of independent rows}).

\subsection{MSIR}
\begin{table*}[h]
	\centering
		\begin{tabular}{|c|c|c|c|c|}
			\hline
			$x_{1}$ & 1 &1  & & \\
			\hline
			$x_{2}$ &  &  &1  &1 \\
			\hline
			$x_{3}$ &  & &1  &1 \\
			\hline
			$x_{4}$ &  &  & 1 &1 \\
			\hline
			& $y_{1}$  & $y_{2}$  & $y_{3}$ & $y_{4}$ \\
			\hline			
		\end{tabular}
	\caption{Příklad na MSIR}
	\label{tab:msir}
\end{table*}

\begin{definition}
Nechť $\langle X,Y, CENA \rangle$ je problém pokrytí a $Y'$ je podmnožina $Y$ taková, že pro dva různé libovolné prvky $y_{1}$ a $y_{2}$ z množiny $Y'$, všechny prvky $x$, které pokrývají $y_{1}$ nepokrývají $y_{2}$ a naopak. Množina $Y'$ je pak nezávislou podmnožinou $Y$ a její cena poskytuje spodní mez řešení.
\end{definition}

Jinak řečeno: v matici $A$ se nachází množiny řádků takové, že žádný sloupec pokrývající řádek z jedné množiny nepokrývá ani jeden řádek z jiné množiny. V tabulce~\ref{tab:msir} je nezávislou podmnožinou řádků podmnožina $X=\{x_{1}, x_{2}\}$, neboť $x_{1}$ je pokryt právě sloupci $y_{1}$ a  $y_{2}$ a  $x_{2}$ je pokryt právě sloupci  $y_{3}$ a  $y_{4}$. Z toho lze vyvodit, že pro pokrytí bude třeba vybrat jeden sloupec z podmnožiny $\{ y_{1},  y_{2}\}$ a jeden sloupec z podmnožiny $\{ y_{3},  y_{4}\}$. Vybereme-li sloupce s nižší cenou, dostaneme minimální cenu pokrytí $2+2=4$.

Hledání množiny MSIR však znamená hledání řešení dalšího NP-úplného problému, a čas pro hledání MSIR by jistě převýšil čas uspořený nalezením přesné spodní meze. Proto je pro nalezení MSIR zvolena rychlá heuristická funkce. Její použití vede k nižší hodnotě než MSIR a tedy větší části stavového prostoru, který je třeba prohledat. Řešení zůstává řešením exaktním.

\section{AURA II}

Algoritmus AURA II je blíže popsán v \cite{3}. Jde o algoritmus, který pro určení spodní meze využívá heuristiku hledající MSIR. Při splnění určitých podmínek používá tzv. negativní přístup, kdy se při splnění určitých podmínek snaží tuto spodní mez zvýšit bližším zkoumáním množin MSIR.

\subsection{Heuristika MSIR}

V předešlé části je řečeno, že hledání $MSIR$ je časově náročné. Proto se v AURA II k jejímu nalezení používá následující heuristika:

\begin{algorithm}[H]
\caption{Find MSIR}
\label{alg:alg3}

FindMSIR($A$) \{
\vspace{1 mm}

\hspace{4 mm}$bestRow$ = first\_row($A$)

\hspace{4 mm}for each row $\in A$ \{

\hspace{8 mm}$r$ = find\_row\_with\_minimum\_1($A$)

\hspace{8 mm}if ( RP($r$) $<$ RP($bestRow$) ) $bestRow = r$

\hspace{4 mm}\}

\hspace{4 mm}for each row r $\in A$ \{

\hspace{8 mm}if ( rows\_are\_dependent($r$,$bestRow$,$A$))  

\hspace{12 mm}$A'$ = remover\_row\_from\_matrix($r$,$A$)

\hspace{4 mm}\}

\hspace{4 mm}$MSIR$ = minimal\_cost\_column\_covering($bestRow$)

\hspace{4 mm}$MSIR$ = $MSIR$ + FindMSIR($A'$)

\hspace{4 mm}return $MSIR$

\}
\vspace{4 mm}

\end{algorithm}

\newpage


\noindent kde $RP$ znamená řádkový příspěvek:
$$RP(x_{i})=\sum_{j=1}^{n}A_{i,j} \cdot SP(y_{j})$$
kde $SP$ znamená sloupcový příspěvek:

$$SP(y_{j}) = \sum_{i=1}^{m}A_{i,j} $$

Čím nižší bude $RP(x_{i})$, tím vyšší bude šance na nezávislost řádků. Jinými slovy, al\-go\-rit\-mus vybírá řádky, které jsou minimálně pokryty a toto pokrytí je tvořeno sloupci, které pokrývají nejméně řádků. 
\\

Nechť:
$$
K(A_{N})= UB - LB(A_{N}) + cena(path)
$$
Pokud je $K(A_{N})<0$, je třeba zastavit další volání algoritmu. V opačném případě je cena částečného nalezeného řešení menší než cena nejlepšího nalezeného řešení a je možné dále prohledávat stavový prostor. Tehdy má algoritmus dvě možnosti jak pokračovat. První z nich je označena jako \emph{"pozitivní"} - algoritmus bude pokračovat ve větvení, aby se přesvědčil, že jím doposud nalezené řešení je nejlepší. 
Druhý přístup se nazývá\emph{"negativní"} - algoritmus se snaží dokázat, že lepší řešení již neexistuje. Pokud je nalezená hodnota $K(A_{N})$ nízká, je přirozenější pro algoritmus být „skeptický“ ohledně nalezení lepšího řešení.

Algoritmus AURA II se při řešení problému pokrytí snaží zahrnout obě techniky. Pra\-cu\-je s upraveným rekurzivní algoritmem - zpočátku řeší problém v režimu pozitivního přístupu. Později, když počet vzniklých podproblémů je dostatečně veliký, je každý podproblém řešen v režimu negativního přístupu. Čím menší je hodnota $K(A_{N})$, tím přirozenější je řešení podproblému v režimu negativního přístupu.

Negativní přístup AURA II spočívá ve zvyšování spodní meze postupným přidáváním řádků do MSIR a zkoumáním možných řešení. Algoritmus je přesně popsán v \cite{1}.

\section{Heuristické metody}

Nalezení exaktního řešení pro větší matice trvá velmi dlouhou dobu. V některých pří\-pa\-dech (především pro rozsáhlé problémy) je použití heuristické funkce pro nalezení řešení UCP jediná možnost, jak zjistit alespoň přijatelné řešení. V této kapitole jsou stručně popsány dvě hladové heuristiky.

\newpage
\subsection{Heuristika podle Servíta}
\label{Servit}

Tato heuristika je popsána v \cite{6}. Heuristika se snaží vybírat sloupce, které jsou pokryty řádky, které jsou pokryty co nejméně sloupci, přičemž se berou v úvahy ceny sloupců pokrývající řádky. Velikost pokrytí sloupců je udávána jako síla pokrytí SPS.

$$SPS(y_{j}) = \frac{\sum_{i=1}^{m}A_{i,j} \cdot SPR(x_i)}{cost(j)} $$
kde $SPR$ značí sílu pokrytí řádku:

$$SPR(x_{i}) = \left( \sum_{j=1}^{n}  \frac{A_{i,j}}{c_j} \right)^{-1} $$

Při každém přidání sloupce se redukuje původní problém (matice). Heuristika tak musí zkoušet, jestli v matici nevznikly nové nezbytné sloupce.

\begin{algorithm}
\caption{Servít}
\label{alg:alg4}

Servít($A$) \{
\vspace{1 mm}

\hspace{4 mm}while ($A$ is not covered) \{

\hspace{8 mm}$c$ = find\_column\_with\_maximum\_SPS($A$)

\hspace{8 mm}add\_to\_solution($c$,$solution$)

\hspace{8 mm}remove\_from\_problem($c$,$A$)

\hspace{8 mm}e = find\_essential\_columns($A$)

\hspace{8 mm}add\_to\_solution($e$,$solution$)

\hspace{8 mm}remove\_from\_problem($e$,$A$)

\hspace{4 mm}\}

\hspace{4 mm}return $solution$

\}
\vspace{4 mm}

\end{algorithm}

\subsection{Heuristika ContribAdd}
\label{ContrAdd}

Jedná se o heuritstiku, která se v algoritmu AURA II používá k výběru sloupce při větvení. Lze ji ovšem použít samostatně za předpokladu, že se v každé iteraci kontroluje, jestli v matici nevznikly nezbytné sloupce. Heuristika se snaží vybírat sloupce, které jsou pokryty řádky, které jsou pokryty co nejméně sloupci. Síla pokrytí sloupců se vypočítá takto:

$$SPS(y_{j}) = \frac{\sum_{i=1}^{m}A_{i,j} \cdot SPR(x_i)}{cost(j)} $$

kde $SPR$ značí sílu pokrytí řádku:

$$SPR(x_{i}) = \left( \sum_{j=1}^{n}A_{i,j} \right)^{-1} $$

\begin{algorithm}
\caption{ContribAdd}
\label{alg:alg5}

ContribAdd($A$) \{
\vspace{1 mm}

\hspace{4 mm}while ($A$ is not covered) \{

\hspace{8 mm}$c$ = find\_column\_with\_maximum\_SPS($A$)

\hspace{8 mm}add\_to\_solution($c$,$solution$)

\hspace{8 mm}e = find\_essential\_columns($A$)

\hspace{8 mm}add\_to\_solution($e$,$solution$)

\hspace{8 mm}remove\_from\_problem($e$,$A$)

\hspace{4 mm}\}

\hspace{4 mm}return $solution$

\}
\vspace{4 mm}

\end{algorithm}

\section{Lagrangeovská relaxace}

\subsection{Principy Lagrangeovské relaxace}
\label{LRP}

Lagrangeovská relaxace optimalizačních problémů s omezujícími podmínkami je vel\-mi často používanou technikou pro jejich řešení. Lagrangeovská relaxace se tvoří takto \cite[3]:
\begin{enumerate}
\item Odstraní se množiny omezujících podmínek problému
\item Tyto podmínky se promítnou do optimalizační funkce ve formě tzv. trestných ko\-e\-fi\-ci\-ent\-ů, které se nazývají \emph{Lagrangeovské multiplikátory}.
\end{enumerate}

\subsection{Relaxace problému pokrytí}
\label{LP}

Mějme jiný zápis pro problém pokrytí $P$ definovaném v \ref{problem}:

$$min z = cx$$
$$podm.: \ Ax > e \ , \ x \in  \{ 0,1 \} ^n $$

{\settowidth{\parindent}
{Kde:\ }
\makebox[0pt][r]
{Kde:\ }$c$ je vektor cen.

$x$ je binární vektor sloupců. Prvek tohoto vektoru je jedna, pokud daný sloupec pat\-ří do řešení, jinak je roven nule.

$e$ je vhodný jednotkový vektor $(e_{i}=1;i=1,2,….m)$. Nerovnice $Ax>e$ tedy reprezentuje podmínku říkající, že každý řádek musí být pokryt alespoň jedním sloupcem.}

Tento problém může být relaxován na problém lineárního programování $LP$ změnou omezující podmínky:

$$min z = cx$$
$$podm.: \ Ax > e \ ,\  0 \le x \le 0 $$

Pokud je optimální řešení tohoto problému celočíselné, je potom také optimální řešení původního problému $P$. Tomu však většinou není a optimální výsledek tak slouží jako spodní mez původního problému $(z_{P}^* \le z_{LP}^*)$.

Jelikož i tento lineární problém není snadné řešit, lze jej převést na problém Lagrangeovské relaxace $LRP$. To se provede postupem popsaným v \ref{LRP}. Výsledkem je:

$$min z = \tilde{c}x+\lambda e$$
$$podm.: \ 0 \le x \le 0 $$

{\settowidth{\parindent}
{Kde:\ }
\makebox[0pt][r]
{Kde:\ }$\tilde{c} = c - A \lambda$ je vektor \emph{redukovaných cen} sloupců  (nebo také vektor Lagrangeovských cen).

$\lambda$ jsou Lagrangeovské multiplikátory definované pro každý řádek matice $A$. Tyto mul\-ti\-pli\-kátory charakterizují \emph{míru neplnění původních omezujících podmínek} aktuálního řešení $x$ pro jednotlivé řádky.}

Ze vzorce pro redukovanou cenu sloupce vyplývá to, že bude-li sloupec pokrývat řádky s větší mírou neplnění omezujících podmínek, jeho redukovaná cena bude nižší a jeho zařazení do řešení je tudíž žádoucí. Optimálního řešení $LRP$ lze dosáhnout vhodnou volbou sloupců. Očividně se vyplatí vybírat do řešení ty sloupce, jejichž redukovaná cena je záporná $( \tilde{c}_{j}^*  \le 0)$ - tak se pokryjí právě ty řádky, které mají velkou míru neplnění omezujících podmínek. Sloupec se do řešení zahrne tak, že se nastaví jemu  příslušná proměnná ve vektoru $x$  $(x_{j}=1)$.

Řešení LRP nemusí být přípustným řešením problému pokrytí P (některé řádky zůstanou nepokryty), avšak modifikace řešení LRP přidáváním nebo odebíráním sloupců může vést k dobrým řešením. 

Cena řešení $LRP$ pro všechny $\lambda \ge 0$ tvoří spodní mez lineární relaxace $(z_P^* \le z_{LP}^* \le z_{LRP}^*)$. Cílem Lagrangeovské relaxace je tedy určit takové hodnoty multiplikátorů $\lambda$, pro něž je cena řešení $LRP$ $z_{LRP}^* (\lambda)$ nejvyšší. Technika zde označovaná jako subgradientem řízený postup, která umožňuje vyjít z jakýchkoliv hodnot $\lambda_0$  a postupně je vylepšovat – potenciálně až na hodnoty, kdy $z_{LRP}^* (\lambda)=z_P^*$.

\subsection{Subgradientem řízený postup}
\label{Supgrpostup}

Hlavním cílem je iterativně vylepšovat hodnoty $\lambda_k$ na základě ceny posledního řešení $z_{LRP} (\lambda_{k-1})$. Optimální řešení problému $x_k^*=x_{LRP}^* (\lambda_k )$ porušuje omezení na pokrytí o hodnotu $s_{\lambda_k }=e-Ax_k^*$ (rezerva) a cena tohoto řešení je $z_{\lambda_k }=z_{LRP}^* (\lambda_k )$. Tyto vztahy vedou k úpravě $\lambda_k$ podle vztahu:

$$\lambda_{k+1} = max \left( \lambda_k + s_{\lambda_k} \frac {  \arrowvert z_{P}^* - z_{\lambda_k}  \arrowvert }{ \Arrowvert s_{\lambda_k} \Arrowvert^2} , 0\right)$$

V dalším kroku budou porušená omezení (reprezentované kladnými hodnotami $ s_{\lambda_k}$ pe\-na\-li\-zo\-vá\-na tak, že bude navýšen příslušný multiplikátor, zatímco při splněných podmínkách budou multiplikátory sníženy (nikdy pod 0).

Subgradient $\Arrowvert s_{\lambda_k} \Arrowvert^2$  je vektor, který udává směr dalšího postupu při řešení. Jak vyplývá ze vtahu $s_{\lambda_k}=e-Ax_k^*$, složky subgradientu pro dosud nepokryté řádky jsou jednotkové, pro ostatní jsou nulové nebo záporné. 
Rozdíl $ \arrowvert z_{P}^* - z_{\lambda_k}  \arrowvert$ určuje, jak moc se cena optimalizační funkce blíží k optimální hodnotě. Čím je dále, tím je větší rozdíl a tím více se budou multiplikátory měnit. Tímto procesem se nastavují multiplikátory $\lambda_k$  a hodnota $z_{\lambda_k}$ postupně osciluje. Její nejlepší známá hodnota $LB$ postupně roste a blíží se k $z_{P}^*$. Zároveň s tím $\lambda_k$ obsahuje více informací o problému.

Teoreticky je zajištěna konvergence tohoto procesu. Většinou je ale hodnota $z_P^*$ neznámá a je nahrazena horní mezí $UB$. Použití horní meze ale může zamezit konvergenci, protože rozdíl $UB-z_{\lambda_k}$ může být větší jak 0. Proto se používá zmenšující se koeficient kroku $t_k$. Tento je zmenšen (např. půlen) vždy po určitém počtu iterací $N_t$, během kterých se nezmění hodnota $LB$. Pokud se totiž tato hodnota nemění, je velice pravděpodobné, že je to způsobeno příliš velkými změnami v multiplikátorech. Výsledkem je mírně upravený vztah:

$$\lambda_{k+1} = max \left( \lambda_k + t_k s_{\lambda_k} \frac {  \arrowvert UB - z_{\lambda_k}  \arrowvert }{ \Arrowvert s_{\lambda_k} \Arrowvert^2} , 0\right)$$

\bigskip

Proces končí ve chvíli, kdy je $z_{\lambda_k}$ velmi blízko $UB$ (může být zadaná určitá mez) nebo $t_k$ je natolik malé, že neumožňuje další změny v $LB$ $(t_k<t_{min})$. Třetí podmínka může nastat, pokud předpokládáme, že vektor cen $c$ je celočíselný. V tom případě je $z_P^*$ také celočíselné. Pokud známé celočíselné řešení má cenu $\lceil z_{\lambda_k} \rceil$, je optimální, protože žádné jiné nemůže být lepší.

První hodnoty $\lambda_0$, kdy nejsou známy žádné informace o problému, můžou být jakékoliv (pokud nejsou negativní). K jejich nastavení je ale také možné použít heuristiku. 

\bigskip

Určování hodnot $\lambda_0$ , $t_{min}$ , $t_0$ a $N_t$ se věnují další kapitoly. Pro jejich určení bylo provedeno několik experimentálních měření.

\subsection{Nastavení horní meze}

Hodnotu $UB$ je možné získat dvěma způsoby:

\begin{enumerate}
\item Heuristikou. Tato může být jakákoliv (např. Contrib Add - v \ref{ContrAdd}). V heuristice je ale možné použít řešení $LRP$ – taková heuristika se potom nazývá \emph{Lagrangeovská heuristika}.
\item Pomocí duálního problému. Ten je popsán v kapitole 3.6.
\end{enumerate}

Lagrangeovské heuristiky pro problém pokrytí pracují tak, že začnou s řešením $LRP$, přidají do řešení sloupce tak, aby upravené řešení bylo přípustným řešením problému pokrytí a případně odeberou z řešení sloupce nadbytečné. Pravidla pro přidávání či odebírání sloupců mohou být určena různě, vznikne tak několik variant Lagrangeovské heuristiky. Pravidla jsou převzata z \cite{2}.

Řešení $LRP$ sice není přijatelné jako řešení $P$, ale jako výchozí řešení může poslouží dobře \cite{4}. Pokud jsou hodnoty Lagrangeovských multiplikátorů téměř optimální, je prav\-dě\-po\-dob\-né, že příslušné řešení $LRP$ je blízko optimálního a Lagrangeovské ceny mohou poskytnout dobré informace o tom, jak upravovat řešení tak, aby bylo přijatelné pro problém $P$.

\subsection{Úprava řešení problému Lagrangeovské relaxace}

\label{varianty}

V této části je popsáno pět heuristik, které v této práci byly použity pro vytvoření přípustného řešení problému P z řešení LRP. Všechny tyto heuristiky mají společné to, že se skládají ze dvou fází:

\begin{enumerate}
\item V první fázi jsou do řešení $LRP$ přidávány sloupce tak, aby byly pokryty všechny řádky. Přidávání sloupců probíhá tak, že se vždy pro jeden řádek vybírá mezi sloupci, který daný řádek pokrývají. Řádky se vybírají podle počtu sloupců, které pro daný řádek obsahují jedničku (řádky s více jedničkami se vybírají pro pokrytí jako první).
\item V druhé části jsou naopak sloupce odebírány, nikdy však tak, aby došlo k porušení pokrytí.
\end{enumerate}

Heuristiky se liší v kritériích, podle kterých jsou sloupce přidávány a odebírány:

\medskip

\textbf{Varianta 1}

\begin{itemize}\itemsep1pt
\item Přidávány jsou sloupce s nejnižší cenou. \item Odebírány jsou sloupce s nejvyšší cenou.
\end{itemize}

Tato varianta představuje původní řešení navržené Beasleym \cite{2} a nevyužívá informace z vypočtených Lagrangeovských multiplikátorů. Ostatní varianty tyto informace různým způsobem využívají.

\medskip
\textbf{Varianta 2}
\begin{itemize}
\item Přidávány jsou sloupce s nejnižší redukovanou cenou.
\item Odebírány jsou sloupce s nejvyšší cenou.
\end{itemize}

\medskip
\textbf{Varianta 3}
\begin{itemize}
\item Přidávány jsou sloupce s nejnižší modifikovanou redukovanou cenou.
\item Odebírány jsou sloupce s nejvyšší cenou.
\end{itemize}

\medskip
\textbf{Varianta 4}

\begin{itemize}
\item Přidávány jsou sloupce s nejnižší redukovanou cenou.
\item Odebírány jsou sloupce s nejvyšší redukovanou cenou.
\end{itemize}

\medskip
\textbf{Varianta 5}

\begin{itemize}
\item Přidávány jsou sloupce s nejnižší modifikovanou redukovanou cenou.
\item Odebírány jsou sloupce s nejvyšší modifikovanou redukovanou cenou.
\end{itemize}

Pro varianty 3 až 5 se používá modifikovaná redukovaná cena. Její výpočet probíhá tak, že pro již pokryté řádky se Lagrangeovské multiplikátory vynulují.

\subsection{Výstupy Lagrangeovské relaxace}
\label{sloupec}

Lagrangeovská relaxace poskytuje tři výstupy:

\begin{enumerate}
\item $LB$ - Dolní mez řešení problému. 
\item Řešení (ne nutně optimální) problému pokrytí. 
\item Sloupec, který by se měl v algoritmu B\&B přidat do řešení. Jedná se o sloupec, který je součástí heuristického řešení a jeho redukovaná cena je nejnižší.
\end{enumerate}

\section{Duální problém}

V lineárním programování lze ke každému problému najít sdružený – tzv. \emph{duální} problém \cite[9]. Tvoří se takto:

\begin{enumerate}
\item Pokud je původní (\emph{primární}) problém maximalizační, duální bude minimalizační (a naopak).
\item Proměnné v primárním problému slouží jako omezení v duálním.
\item Omezení v primárním problému slouží jako proměnné v duálním problému.
\end{enumerate}

Mějme např. problém:

$$max  \sum_{j=1}^{n}c_jx_j \ , \ podm.:  \sum_{n=1}^{n}a_{i,j}x_j \leq b_i \ , \ x_j \geq 0$$
$$ i = 1,2,3,.....,m \ , \ j = 1,2,3,.....,n $$
$$ x = (x_1,x_2,x_3,.....,x_n) \ , \ y = (y_1,y_2,y_3,.....,y_m) $$

Potom duální problém vypadá takto:

$$min  \sum_{i=1}^{m}b_iy_i \ , \ podm.:  \sum_{i=1}^{m}y_ia_{i,j} \geq c_j \ , \ y_i \geq 0$$
$$ i = 1,2,3,.....,m \ , \ j = 1,2,3,.....,n $$
$$ x = (x_1,x_2,x_3,.....,x_n) \ , \ y = (y_1,y_2,y_3,.....,y_m) $$

Duální problém k duálnímu problému je primární problém.\\

\emph{Slabá věta} o dualitě říká, že pokud jsou řešení primárního \emph{x} i duálního \emph{y} problému přijatelná, potom platí:

$$ \sum_{j}c_jx_j \leq \sum_{i}b_iy_i$$

\newpage

důkaz:

$$ \sum_{j}c_jx_j \leq $$
$$ \leq  \sum_{j} \left( \sum_{i}y_ia_{ij}  \right) x_j =  \sum_{ij}y_ia_{i,j}x_j = \sum_{i} \left( \sum_{j}a_{ij}x_i  \right) y_i \leq $$
$$  \leq \sum_{i}b_iy_i $$

\emph{Silná věta} o dualitě říká, že optimální řešení primárního $x^*$ i duálního $y^*$ problému jsou přijatelná pouze pokud platí:

$$ \sum_{j}c_jx^*_j = \sum_{i}b_iy^*_i$$

důkaz je konstruktivní za pomoci simplexové metody \cite{10}.

\subsection{Duální problém problému pokrytí}

K problému $LP$ uvedeném v \ref{LP} existuje následující duální problém $LD$:

$$max w = ey$$
$$podm.: \ Ay < c \ ,\ 0 \le y \le \bar{c} $$

{\settowidth{\parindent}
{Kde:\ }
\makebox[0pt][r]
{Kde:\ }$y$ je vektor je vektor duálních proměnných.

$\bar{c} = min_{j:A_{ij}=1}c_j$ je nejmenší možná cena sloupce, který pokrývá daný řádek. }

$LD$ je úzce spjat s $LRP$: pokud je duální přípustné řešení y použit jako vektor La\-gran\-ge\-ov\-ských multiplikátorů $\lambda$, příslušné řešení $LRP$ s cenou $z_{LRP}^* (m)$ je rovné ceně řešení duálního problému $w(m)$.

$$c-Ay= \tilde{c}(m)>0 \to x_{LRP}^*(m)=0 \to $$
$$ \to z_{LRP}^*(m) = ye = ey = w_{LD}(m)$$


Tedy každé dobré duální řešení je dobrý vektor Lagrangeovských multiplikátorů. Především každé optimální řešení duálního problému je optimální vektor multiplikátorů, protože \\ $z_{LRP}^* (m^* ) = w_{LD} (m^*)$. Podle silné věty o dualitě \cite{4} navíc platí, že $w_{LD}^*=z_{LP}^*$.

Řešení duálního problému je stejně složité jako řešení primárního. Lze jej ale podobně jako primární problém relaxovat na Lagrangeovský duální lineární problém $LDP$:

$$max w = \tilde{e}y + \mu c$$
$$podm.: \ 0 \le y \le \bar{c} $$

{\settowidth{\parindent}
{Kde:\ }
\makebox[0pt][r]
{Kde:\ }$\tilde{e}=e-A\mu$ je vektor \emph{duálních redukovaných cen sloupců}.

$\mu$ jsou \emph{Duální Lagrangeovské multiplikátory}.}

\medskip
Cena optimálního řešení $LD$ představuje horní mez problému $LP$ $w_{LDP} (\mu^* ) \ge w_{LD}^*=z_{LP}^*$. Tato mez může vylepšit hodnotu $UB$ použitou ve vztahu pro úpravu Lagrangeovských multiplikátorů $\lambda$ v části \ref{LP}. 

Obdobně jako pro řešení $LRP$ i pro řešení $LDP$ platí, že žádoucí je do řešení zahrnout pouze řádky, jejichž duální redukovaná cena je nezáporná $(\tilde{e}_i^* \ge 0)$ \cite[5]. Stejně tak platí, že cílem duální Lagrangeovské relaxace je najít takové hodnoty multiplikátorů $\mu$, pro něž je cena řešení problému $LDP$ $w_{LDP}^* (\mu)$ nejnižší. Řádek se do řešení zahrne tak, že se nastaví jemu  příslušná proměnná $y_i=\bar{c}_i$ , jinak $y_i=0$.

Vztah pro úpravu $\mu$ je následující:

$$\mu_{k+1} = max \left( \mu_k + t_{Dk} s_{D \lambda_k} \frac {  \arrowvert w_{LDP \lambda_k} - LB   \arrowvert }{ \Arrowvert s_{D \lambda_k} \Arrowvert^2} , 0\right)$$

{\settowidth{\parindent}
{Kde:\ }
\makebox[0pt][r]
{Kde:\ }$s_{D \lambda_k} = Ay_k^* - c_{jk}$ (duální rezerva) představuje velikost porušení omezení $A_y \le c$ problému $D$.}

\medskip
\emph{Duální koeficient kroku} $t_{Dk}$ se obdobě jako ve vztahu v \ref{LP} požívá proto, aby bylo zajištěno vylepšování hodnoty $UB$. Tento koeficient je zmenšen (např. půlen) vždy po určitém počtu iterací $N_t$, během kterých se nezmění hodnota $UB$.

Počáteční hodnoty multiplikátorů $\mu_0$ mohou být určeny náhodně (pokud nejsou negativní) nebo mohou být určeny heuristikou.

Metoda subgradientem řízeného postupu je aplikována na primární i duální Lagrangeovský problém. Nejlepší známá řešení jsou použita jako meze problémů, což vede k přesnějšímu výpočtu multiplikátorů, které se tak nastaví v menším počtu kroků.


\cleardoublepage
%kapitola 4

\chapter{Implementace }

V této části je popsán celkový algoritmus, který využívá postupy popsané v kapitole \ref{RPP}. Základem je poupravený Branch and Bound algoritmus, který pro určení spodní meze využívá Lagrangeovskou relaxaci. Tato relaxace také může vracet řešení (ne nutně op\-ti\-mál\-ní), které může být použito k nastavení horní meze a nejlepšího známého řešení. Relaxace také vrací sloupec, který se zahrne do řešení při větvení.

\section{Základní algoritmus}

\begin{algorithm}
\caption{Branch and Bound s využitím Lagrangeovské relaxace}
\label{alg:alg6}

Branch\_and\_bound\_Lagrange($A$,$Path$) \{
\vspace{1 mm}

\hspace{4 mm}/* odstraní dominantní řádky a sloupce, 

\hspace{4 mm}vybere do řešení nezbytné sloupce */

\hspace{4 mm}$A$ = solve\_dominance($A$);
\vspace{2 mm}

\hspace{4 mm}$tempSolution$ = $bestSolution$
\vspace{2 mm}

\hspace{4 mm}if ( $A$ == $\emptyset$ ) \{

\hspace{8 mm}if ( cost($Path$) $<$ $UB$ ) $UB$ = cost($Path$)

\hspace{8 mm}$bestSolution = Path$

\hspace{4 mm}\} else \{

\hspace{8 mm}$A$ = sort\_matrix($A$)

\hspace{8 mm}/*Nalezne spodní mez pro aktuální problém*/

\hspace{8 mm}$Lagrange\_solution$, $LB\_Lagrange$, 

\hspace{8 mm}$Lagrange\_column$  = Solve\_Lagrange\_($A$,$Params$);

\hspace{8 mm}$lBoundNew$ = cost($Path$) + $LB\_Lagrange$ 
\vspace{2 mm}


\hspace{8 mm}if ( $lBoundNew \ge UB$ ) \{

\hspace{12mm}/*pokud jsme již dosáhli spodní meze, nebudeme větvit dále*/

\hspace{12 mm}$bestSolution = \emptyset$

\hspace{12 mm}return $bestSolution$

\hspace{8 mm}\} else \{

\hspace{12 mm}/*Horní mez nebyla dosažena*/

\vspace{4 mm}
\end{algorithm}
\newpage
\begin{algorithm}[H]

\vspace{4 mm}

\hspace{12 mm}if (  $LB\_Lagrange$ == $Lagrange\_soluton\_cost$ ) \{

\hspace{16 mm}/*Bylo nalazeno heuristické řešení, které již nemůže být lepší*/

\hspace{16 mm}$bestSolution = Lagrange\_soluton$

\hspace{16 mm}$uBound = cost(Path) + Lagrange\_soluton\_cost$

\hspace{16 mm}return bestSolution


\hspace{12 mm}  \} else \{

\hspace{16 mm}/*Bylo nalazeno heuristické řešení, může ale existovat lepší řešení*/
        
\hspace{16 mm}$tempSolution = Lagrange\_soluton$

\hspace{16 mm}$uBound =cost(Path) + Lagrange\_soluton\_cost$

\hspace{12 mm}  \}

\hspace{8 mm}\} 
        
\hspace{8 mm}$Path1$= $Path+Lagrange\_column$;

\hspace{8 mm}$A'$ = $A$ - \{ $j$ + rows\_covered\_ by($Lagrange\_column$) \}

\hspace{8 mm}$Solution1$ = Branch\_And\_Bound($A'$,$Path1$)

\hspace{8 mm}$A''$ = $A$ – \{$Lagrange\_column$\}

\hspace{8 mm}$Solution2$ = Branch\_And\_Bound($A''$,$Path2$)

\hspace{8 mm}$bestSolution$ = min( $tempSolution$ , $Solution1$ , $Solution2$ )

\hspace{4 mm}\}

\hspace{4 mm}return $bestSolution$

\}
\vspace{4 mm}

\end{algorithm}

Parametry předávané metodě Solve\_Lagrange jsou popsané v části věnující se dané metodě.

\subsection{Reprezentace matice}
\label{reprezentace}
Data matice jsou uložena v dvourozměrném poli obsahujícím jedničky a nuly. Dále je uložen vektor obsahující ceny sloupců. Nakonec se k  reprezentaci matice používají dva spojové seznamy - jeden pro řádky a druhý pro sloupce. V každém prvku seznamu se vede informace o tom, kterému řádku(resp. sloupci) prvek odpovídá a dále počet jedniček obsažených v daném řádku(sloupci). Tento údaj se s výhodou používá při odstraňování dominancí a třídění matice. Navíc se v takovéto reprezentaci dají velmi snadno odebírat řádky(sloupce) jednoduchým odebíráním prvků ze seznamů.

\subsection{Odstranění dominancí}

Odstraňování dominancí v algoritmu probíhá ve dvou fázích:

\begin{enumerate}
\item řádková fáze: Algoritmus prochází všechny řádky. Vždy vezme jeden řádek $x'$ z matice a porovná ho s ostatními řádky. Pokud nalezne řádek $x$ obsahující stejný nebo vyšší počet jedniček jako řádek $x'$, je šance, že řádek $x'$ dominuje řádku $x$. Dále algoritmus zjistí, jestli $x$ obsahuje jedničky ve stejných sloupcích jako $x'$. Pokud ano, řádek $x$ je odstraněn z matice. Jelikož se porovnává každý řádek s každým, operační složitost algoritmu v nejhorším případě je $O(n \times m^2)$, kde $m$ je počet řádků a $n$ počet sloupců matice. V této části také algoritmus při procházení porovnávaného řádku $x'$ zjišťuje, jestli daný řádek není pokryt pouze jedním sloupcem. Pokud ano, je sloupec pokrývající daný řádek zařazen do řešení jakožto nezbytný.
\item sloupcová fáze: Algoritmus vezme sloupec $y'$ z matice a porovná ho s ostatními sloupci. Pokud sloupec $y$ obsahuje stejný nebo menší počet jedniček jako sloupec $y'$, je možnost, že $y'$ dominuje $y$. Algoritmus zjistí, zda $y$ obsahuje jedničky ve všech řádcích, ve kterých je obsahuje $y'$, a je splněna podmínka $cena(y') \le cena(y)$. Pokud ano, sloupec $y$ je vyjmut z matice. Pokud podmínka splněna není, sloupec se neodstraňuje – algoritmus by se tak mohl připravit o minimální řešení. Opět se porovnává každý sloupec s každým, takže operační složitost v nejhorším případě, kdy se nevyškrtne žádný sloupec, je $O(m \times n^2)$,kde $m$ je počet řádků a $n$ počet sloupců matice.
\end{enumerate}

\subsection{Třídění matice}
\label{sorteni}

Pro potřeby Lagrangeovské relaxace je nutné mít matici v odpovídajícím tvaru. Algoritmus matici setřídí následovně:

\begin{itemize}
\item Řádky podle počtu sloupců, které daný řádek pokrývají
\item Sloupce podle ceny. Pokud nějaké sloupce mají stejnou cenu, jsou seřazeny podle počtu řádků, které sloupce pokrývají.
\end{itemize}

Třídění matice je fyzicky provedeno tak, že se mění pořadí referencí sloupců a řádků ve spojových seznamech (viz \ref{reprezentace}).

\newpage
\section{Lagrangeovská relaxace}

Tato metoda může a nemusí brát v úvahu duální problém. Porovnání jejich výkonnosti a účinnosti se nachází v části \ref{varianty}. Zde následuje popis obou metod.



\subsection{Algoritmus Lagrangeovské relaxace}

\begin{algorithm}[H]
\caption{Lagrangeovská relaxace}
\label{alg:alg7}

Solve\_Lagrange ($A$,$t_init$,$t_min$,$N$,$N_t$,$N_h$) \{
\vspace{1 mm}

\hspace{4 mm}$t$=$t_{init}$
%\vspace{2 mm}

\hspace{4 mm}for ( $i_t$ = 1 to $N$ ) \{
%\vspace{2 mm}

\hspace{8 mm}/*Řešení $LRP$:*/ 

\hspace{8 mm}/*výpočet redukovaných cen a přidání sloupce do řešení $LRP$*/ 

\hspace{8 mm}$z_{LRP}$ = 0 

\hspace{8 mm}for ( $j$ = 1 to $n$ ) \{

\hspace{8 mm}$\tilde{c}_j=c_j-\sum_{i=1}^{m}A_{i,j}\lambda_j$ 

\hspace{12 mm}if ($\tilde{c}_j < 0$) then \{

\hspace{16 mm}$x_j = 0$ 

\hspace{16 mm}$z_{LRP} = z_{LRP} + c_j$

\hspace{12mm}\} else $x_j = 1$ 

\hspace{8 mm}\}

\hspace{8 mm}/*dopočítání ceny řešení $LRP$*/

\hspace{8 mm}for ( $i$ = 1 to $m$ ) $z_{LRP} = z_{LRP} + \lambda_i$
%\vspace{2 mm}

\hspace{8 mm}/*zjištění $UB_{heur}$*/

\hspace{8 mm}if ( $i_t$ mod $N_h$ == $0$ ) then $UB_{heur} = $ complete\_solution($x$)
%\vspace{2 mm}

\hspace{8 mm}/*=uprava mezí*/

\hspace{8 mm}$LB = max(LB,z_{DUAL})$

\hspace{8 mm}$UB = min(UB,UB_heur)$
%\vspace{2 mm}

\hspace{8 mm}/*výpočet vektoru subgradientu*/

\hspace{8 mm}for ( $i$ = 1 to $m$ )  $s_i = 1-\sum_{j=1}^{n}A_{i,j}x_j$ 
%\vspace{2 mm}

\hspace{8 mm}/*vypočtení subgradientu*/

\hspace{8 mm}$s=0$

\hspace{8 mm}for ( $i$ = 1 to $m$ ) $s= s+s_i^2$

\hspace{8 mm}if ( $s == 0$ ) then return
%\vspace{2 mm}

\hspace{8 mm}/*úprava koeficientu kroku*/

\hspace{8 mm}if ( $LB$ hasn't changed for $N_t$ ) then $t = t / 2$

\hspace{8 mm}if ( $t<t_{min}$) then return
%\vspace{2 mm}

\hspace{8 mm}/*výpočet kroku*/
	
\hspace{8 mm}$step=t\cdot(UB-z_{LRP})/s$

\hspace{8 mm}/*úprava hodnot multiplikátorů*/

\hspace{8 mm}for ( $i$ = 1 to $m$ ) do $\lambda_i=max(0,\lambda_i+step\cdot s_i)$

\hspace{4 mm}\}

\}

\end{algorithm}

\newpage

\subsubsection{Parametry Lagrangeovské relaxace}
\label{parametryRelaxace}
\begin{table*}[h!]
	\centering
		\begin{tabular}{|c|l|}
			\hline
			$A$ & Cyklické jádro problému velikosti $m \times n$	\\
			\hline
			$t_{init}$ & Počáteční koeficient kroku	\\
			\hline
			$t_{min}$ & Minimální koeficient kroku	\\
			\hline
			$N$ &Maximální počet iterací \\
			\hline
			$N_t$ &Počet iterací, než dojde ke snížení koeficientu kroku $t$ \\
			\hline
			$N_h$&Počet iterací, než dojde k zavolání heuristiky na vytvoření\\ 
			$$ & přípustného řešení (a potencionálnímu nastavení $UB$)\\
			\hline
		\end{tabular}
	\caption{Parametry Lagrangeovské relaxace}
	\label{tab:parametry1}
\end{table*}

Hodnoty parametrů byly zjištěny experimentálně.  Tomu se blíže věnuje kapitola ref.

\subsection{Algoritmus Duální Lagrangeovské relaxace}

\begin{algorithm}
\caption{Duální Lagrangeovská relaxace}
\label{alg:alg8}

Solve\_dual\_Lagrange ($A$,$t_{init}$,$t_{Dinit}$,$t_{min}$,$t_{Dmin}$,$N$,$N_t$,$N_{Dt}$,$N_h$) \{
\vspace{1 mm}

\hspace{4 mm}$t$=$t_{init}$

\hspace{4 mm}$t_D$=$t_{Dinit}$
\vspace{2 mm}

\hspace{4 mm}/*výpočet primárních a duálních redukovaných cen*/

\hspace{4 mm}for ( $i_t$ = 1 to $N$ ) \{
\vspace{2 mm}

\hspace{8 mm}$z_{LDP}$ = 0 

\hspace{8 mm}for ( $j$ = 1 to $n$ ) \{

\hspace{12 mm}$\tilde{c}_j=c_j-\sum_{i=1}^{m}A_{i,j}\lambda_j$ 

\hspace{12 mm}if ($\tilde{c}_j < 0$) then \{

\hspace{16 mm}$x_j = 0$ 

\hspace{16 mm}$z_{LDP} = z_{LDP} + c_j$

\hspace{12mm}\} else $x_j = 1$ 
\vspace{2 mm}

\hspace{8 mm}$w_{LDP}$ = 0 

\hspace{8 mm}for ( $i$ = 1 to $m$ ) \{

\hspace{12 mm}$\tilde{e}_i=1-\sum_{j=1}^{n}A_{i,j}\mu_i$ 

\hspace{12 mm}if ($\tilde{e}_i > 0$) then \{

\hspace{16 mm}$y_i = \bar{c}_i$ 

\hspace{16 mm}$w_{LDP} = w_{LDP} + y_i\tilde{e}_i$

\hspace{12mm}\} else $y_i = 0$ 

\hspace{8 mm}\}

\end{algorithm}
\newpage
\begin{algorithm}[H]

\vspace{2 mm}

\hspace{8 mm}/* dopočet hodnot řešení*/

\hspace{8 mm}for ( $i$ = 1 to $m$ ) $z_{LDP} = z_{LDP} + \lambda_i$

\hspace{8 mm}for ( $j$ = 1 to $n$ ) $w_{LDP} = w_{LDP} + c_j\mu_j$
\vspace{2 mm}

\hspace{8 mm}/*zjištění $UB_{heur}$*/

\hspace{8 mm}if ( $i_t$ mod $N_h$ == $0$ ) then $UB_{heur} = $ complete\_solution($x$)
\vspace{2 mm}

\hspace{8 mm}/*=uprava mezí*/

\hspace{8 mm}$LB = max(LB,z_{DUAL})$

\hspace{8 mm}$LB = min(UB,UB_{heur},w_{DUAL})$
\vspace{2 mm}

\hspace{8 mm}/*výpočet vektorů subgradientů*/

\hspace{8 mm}for ( $i$ = 1 to $m$ )  $s_i = 1-\sum_{j=1}^{n}A_{i,j}x_j$ 

\hspace{8 mm}for ( $j$ = 1 to $n$ )  $s_{Dj} = 1-\sum_{i=1}^{m}A_{i,j}y_i - c_j$ 
\vspace{2 mm}

\hspace{8 mm}/*výpočet subgradientů*/

\hspace{8 mm}$s=0$

\hspace{8 mm}$s_D=0$

\hspace{8 mm}for ( $i$ = 1 to $m$ ) $s= s+s_i^2$

\hspace{8 mm}for ( $j$ = 1 to $n$ ) $s_D= s_D+s_{Dj}^2$

\hspace{8 mm}if ( $s == 0$ and $s_D == 0$) then return
\vspace{2 mm}

\hspace{8 mm}/*úprava koeficientů kroku*/

\hspace{8 mm}if ( $LB$ hasn't changed for $N_t$ ) then $t = t / 2$

\hspace{8 mm}if ( best value of $w_{DUAL}$ hasn't changed for $N_{Dt}$ ) then $t_D = t_D / 2$

\hspace{8 mm}if ( $t<t_{min}$ and $t_D<t_{Dmin}$ ) then return
\vspace{2 mm}

\hspace{8 mm}/*výpočet kroku*/
	
\hspace{8 mm}$step=t\cdot(UB-z_{LRP})/s$

\hspace{8 mm}$step_D=t_D\cdot(w_{LRP}-LB)/s_D$
\vspace{2 mm}

\hspace{8 mm}/*úprava hodnot multiplikátorů*/

\hspace{8 mm}for ( $i$ = 1 to $m$ ) do $\lambda_i=max(0,\lambda_i+step\cdot s_i)$

\hspace{8 mm}for ( $j$ = j to $n$ ) do $\mu_j=max(0,\mu_j+step_d\cdot s_{Dj})$
\vspace{2 mm}

\hspace{4 mm}\}

\}

\end{algorithm}

\newpage

\subsubsection{Parametry Duální Lagrangeovské relaxace}

\begin{table*}[h]
	\centering
		\begin{tabular}{|c|l|}
			\hline
			$A$ & Cyklické jádro problému velikosti $m \times n$	\\
			\hline
			$t_{init}$ & Počáteční primární koeficient kroku	\\
			\hline
			$t_{Dinit}$ & Počáteční duální koeficient kroku	\\
			\hline
			$t_{min}$ & Minimální koeficient kroku	\\
			\hline
			$t_{Dmin}$ & Minimální duální koeficient kroku	\\
			\hline
			$N$ &Maximální počet iterací \\
			\hline
			$N_t$ &Počet iterací, než dojde ke snížení koeficientu kroku $t$ \\
			\hline
			$N_{Dt}$ &Počet iterací, než dojde ke snížení duálního koeficientu kroku $t$ \\
			\hline
			$N_h$&Počet iterací, než dojde k zavolání heuristiky na vytvoření\\ 
			$$ & přípustného řešení (a potencionálnímu nastavení $UB$)\\
			\hline
		\end{tabular}
	\caption{Parametry duální Lagrangeovské relaxace}
	\label{tab:parametry2}
\end{table*}

Hodnoty parametrů byly zjištěny experimentálně. Tomu se věnuje následující kapitola.

\subsubsection{Optimalizace implementace}

Přesná implementace se od algoritmu \ref{alg:alg8} liší v tom, že v každé iteraci nepřepočítává všechny relevantní parametry (redukované ceny, multiplikátory,rezervy). Používají se totiž vektory $\delta_\lambda$ a $\delta_\mu$, které označují změnu daných multiplikátorů v předešlé iteraci. Tyto vektory jsou řídké. V každé iteraci se tedy prozkoumávají tyto změnové vektory a nastavují se nové redukované ceny (primární i duální). Pokud dojde ke změnám v znaménkách cen, opraví se příslušné primární a duální rezervy $s$ (a $s_D$). Nakonec se přepočítané rezervy použijí k přepočítání multiplikátorů a nastavení rozdílových vektorů $\delta_\lambda$ a $\delta_\mu$.

\subsection{Reprezentace matice}

\label{repreLagrange}
Pro potřeby Lagrangeovských relaxací je matice reprezentována jako dvourozměrné pole. Matice je setříděna postupem popsaným v \ref{sorteni}. Pro každý řádek (sloupec) je určeno, jaké sloupce (řádky) daný řádek pokrývá. Toho je využito především při převádění řešení LRP na přípustné řešení problému pokrytí (tedy při Lagrangeovské heuristice), kdy se do řešení vybírají sloupce podle daného kritéria (viz \ref{varianty}).

\subsection{Jazyk implemetace}

Pro implemetaci byl podle zadání použit jazyk C++. Především z důvodu rychlosti a také aby byla možná snadná integrace do programu BOOM.

\cleardoublepage

%kapitola 5

\chapter{Experimentální výsledky}

\section{Testovací data a prostředí}

Testovací data byla vytvořena pomocí generátoru náhodných booleovských funkcí \cite{8} a booleovského minimalizátoru BOOM \cite{9}. Vstupem generátoru jsou parametry booleovských funkcí (počet vstupů, počet výstupů a termů) a výstupem jsou PLA tabulky. Z těchto tabulek BOOM generuje matice, na kterých řeší problém pokrytí - na základě jeho řešení BOOM generuje minimalizované tabulky PLA.

Pro účely měřený byla vygenerována sada padesáti PLA tabulek pro 25 vstupů, 25 výstupů a 25(26) termů. Z těchto tabulek byly pomocí BOOMu vygenerovány matice. Tyto matice poté byly pro účely měření upraveny tak, aby měly stejné parametry (zmenšena velikost, upravena hustota) - nejedná se tedy o reálná testovací data.

V části \ref{realneMatice} jsou pro porovnávání řešičů použity neupravené matice vygenerované nás\-tro\-jem BOOM. Část PLA tabulek, podle kterých jsou matice generovány, jsou MCNC benchmarky \cite{}. Zbytek byl vytvořen generátorem náhodných funkcí. Generování matic nástrojem BOOM proběhlo s nastavením iterací 10.

\begin{table*}[h]
\centering
\begin{tabular}{|c||c|c|c|c|c||c|c|c|}
			\hline
			&  \multicolumn{5}{|c||}{PLA Tabulka} & \multicolumn{3}{|c|}{Matice} \\
\hline
			název & vst. & výst. & termů & idc [\%] & odc [\%] & řádků &sloupců & hustota [\%] \\
\hline
			08x08x08 & 8 & 8 & 8  &0&0  & 31 & 16 & 13.5\\
\hline
			08x12x12 & 8 & 12 & 12 & 0&0  & 63 & 40 & 9.5\\
\hline
			100x01x100 & 100 & 1 & 100&0&0&  53& 209& 14.2 \\ 
\hline
			10x01x200 & 10& 1 & 200&0&0&  98 & 147 & 4.3 \\ 
\hline
			10x10x10 & 10 & 10 & 10 &0&0&   47&38 & 11.1 \\ 
\hline
			10x10x20 & 10 & 10 & 20 &0&0&   95&96 & 5.7 \\ 
\hline
			10x10x30 & 10 & 10 & 30 &0&0&   141&153 &4.4 \\ 
\hline
			12x12x12 & 12& 12 & 12&0&0&  77& 81& 10.1 \\ 
\hline
			20x05x20 & 20 & 5 & 20 &0&0&  53 & 85 & 11.4 \\ 
\hline
			20x05x20\_10  & 20 & 5 & 20 & 10& 0&  57 & 91 & 9.8 \\ 
\hline
			20x05x20\_20 & 20 & 5 & 20  & 20& 0&  50 & 77& 7.4 \\ 
\hline
			50x50x05\_10 & 50 & 50 & 5  & 10& 0&  119 &27 & 15.4  \\ 
\hline
			15x15x50\_30\_80 & 15 & 15 & 50  & 30& 80&  52 & 59 & 5.7  \\ 
\hline
			15x15x50\_50\_60 & 15 & 15 & 50  & 50& 60&  127 & 87 & 2.3  \\ 
\hline
			50x10x50\_10\_80 & 50 & 10 & 50  & 10& 80&  43 & 89 & 12.5  \\ 
\hline
			50x10x50\_50\_70 & 50 & 10 & 50  & 50 & 70&   79 & 118 & 3.4 \\ 
\hline
			50x10x50\_60\_30 & 50 & 10 & 50  & 60& 30&  197&90& 1.8\\ 
\hline
			apex3 & 54 & 50 & 1036 &89 & 93& 1022 & 601 & 0.5 \\ 
\hline
			bw & 5&28&93&27&81&247 & 79 & 8.1 \\ 
\hline
			cps & 24& 109 &855&75&94&946 & 285 & 0.8 \\ 
\hline
			ex1010 & 10& 10 &1297& 12& 84& 742 & 328 & 0.3 \\ 
\hline
			mainpla& 27& 54 &2507 &68&82& 6416 & 549 & 1.2\\ 
\hline
			pdc & 16& 40 & 822&34&79& 520 & 249 & 1.1 \\ 
\hline
			spla & 16& 46 & 837&54&90& 749 & 353 & 0.6 \\ 
\hline
			table3&14& 14 &1686& 57& 70& 643 & 264 & 0.6\\ 
\hline
			xparc & 41& 73 & 3226& 84& 85& 2653 & 508 & 0.7\\ 
\hline
			
		\end{tabular}
	\caption{Vlastnosti matic reálných dat}
	\label{tab:realData}
\end{table*}

Z tabulky je jasně vidět, že náhodně vygenerované matice mají málokdy hustotu (poměr počtu jedniček k počtu prvků matice) větší jak 15\%. Tento fakt byl zohledněn i při dalším měření, kdy se závislosti na velikosti matice měří při hustotě matice 7\%.

Veškerá měření byla prováděna na sestavě: Intel Core Duo T2400 1.83 GHz, 2 GB RAM.

Pro všechny grafy uvedené v této kapitole platí, že spojnice mezi naměřenými body jsou uvedeny z důvodu přehlednosti grafů.

\section{Chování Lagrangeovské relaxace}
\label{chovaniRelaxace}

Před zkoumáním chování celého algoritmu Branch and Bound Lagrange (\ref{alg:alg6}) byla zkoumána samotná Lagrangeovská relaxace. První měření se zabývají chováním relaxace v závislosti na jejích parametrech (viz \ref{parametryRelaxace}). Další měření se zabývají měření výkonnosti relaxace v závislosti na parametrech matice. Také byl změřen vliv odstranění dominancí z matice na výsledky relaxace.

\subsection{Vývoj horní a spodní meze}
\label{zaklHodnoty}

První graf \ref{graphVyvojSimple} zobrazuje vývoj základních hodnot při běhu Lagrangeovské relaxace. Z grafu je patrné, že při větších hodnotách koeficientu kroku dochází v každé iteraci k velkým změnám hodnot LRP (až k hodnotě -3300 - v grafu pro přehlednost není znázorněno). Z grafu je dále patrné, že změny v LB se většinou projeví brzy po změně koeficientu kroku. To vede k domněnce, že by bylo možné zkrátit výpočetní čaa nastavením menší hodnota iterací $N_t$ (pro tento případ bylo $N_t = 40$), která udává, jak kolik iterací relaxace se nesmí změnit hodnota LB než dojde ke snížení (půlení) koeficientu kroku. Naopak by mohlo být výhodné umožnit nastavení minimálního koeficientu kroku $t_{min}$ na menší hodnotu než je v tomto případě použitých 0,5. Oběma těmto úvahám se věnuje část kapitoly \ref{kroky}. Ze zdrojových dat lze dále zjistit, že k nalazení lepší hodnoty UB dochází nezávisle na hodnotě ceny řešení LRP. Toto vede k úvaze, že by výpočetní čas mohl být snížen, pokud by se Lagrangeovská heuristika nespouštěla v každé iteraci relaxace. Tomu se věnuje kapitola \ref{cetnost}. Průběh byl naměřen na matici o velikosti 150 řádků $\times$ 235 slupců o hustotě 5,5\%.

\begin{figure}[h]
\begin{center}
\includegraphics[width=1.0\textwidth]{VyvojSimple}
\end{center}
\caption{Vývoj mezí}
\label{graphVyvojSimple}
\end{figure}

\subsection{Konvergence multiplikátorů}

Tato část kapitoly se zaměří na sledování vývoje hodnot Lagrangeovských multiplikátorů v čase. Ze zřejmých důvodů nelze do grafu zahrnout průběh všech multiplikátorů pro zadaný problém.

Následující tabulka zobrazuje výsledné hodnoty multiplikátorů pro stejný problém, ale s různými hodnotami nastavení iniciálních hodnot multiplikátorů $\lambda_0$ (Pro první řádek byly hodnoty nastaveny $\lambda_0$ tak, že odpovídají nejmenší ceně sloupců pokrývající daný řádek). Z tabulky je patrné, že výsledné hodnoty se od sebe příliš neliší a relaxace nastavuje multiplikátory v závislosti na struktuře problému a nezáleží na iniciálním nastavení multiplikátorů. Hodnoty byly naměřeny na matici o velikosti 25 řádků $\times$ 25 slupců o hustotě 15\%.

\begin{table*}[h]
	\centering
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			$\lambda(1)$ & $\lambda(2)$ &$\lambda(3)$ & $\lambda(4)$ &$\lambda(5)$ & $\lambda(6)$ &$\lambda(7)$ & $\lambda(8)$ &$\lambda(9)$ & $\lambda(10)$ &$\lambda(11)$ & $\lambda(12)$ & $\lambda(13)$ \\
			\hline
			$0.43$ & $2.84$ & $3.43$ & $3.55$ & $0.52$ & $1.16$ &$0.00$ & $1.58$ & $2.35$ & $0.32$ & $0.60$ & $1.17$ & $1.08$\\
			\hline
			$0.00$ & $3.17$ & $3.14$ & $3.79$ & $0.52$ & $0.84$ &$0.00$ & $1.86$ & $1.77$ & $0.05$ & $0.85$ & $0.91$ & $1.46$\\
			\hline
			 $0.32$ & $2.80$ & $3.29$ & $3.53$ & $0.64$ & $0.86$ &$0.00$ & $1.35$ & $2.11$ & $0.02$ & $0.52$ & $1.10$ & $0.86$\\
			\hline
			$0.32$ & $2.98$ & $3.26$ & $3.53$ & $0.64$ & $0.86$ &$0.00$ & $1.35$ & $2.11$ & $0.02$ & $0.52$ & $1.10$ & $0.86$\\
			\hline
			$0.74$ & $2.92$ & $3.18$ & $3.46$ & $0.64$ & $1.94$ &$0.00$ & $1.13$ & $1.90$ & $0.00$ & $0.21$ & $0.62$ & $0.75$\\
			\hline
		\end{tabular}
	\caption{Výsledné Lagrangeovské multiplikátory}
	\label{tab:multiplikatory}
\end{table*}

Graf \ref{graphVyvojMult} zobrazuje vývoj hodnot multiplikátorů. Řada hodnot "rozdíl" označuje součet rozdílů hodnot multiplikátorů v dané iteraci k ($\lambda_k$) od konečných hodnot  ($\lambda_{final}$). Řada hodnot "rozdíl abs" bere v úvahu absolutní rozdíly hodnot multiplikátorů. Podobně jako v grafu  \ref{graphVyvojSimple} je vidět změna v chování při změně koeficientu kroku - menší krok dovolí multiplikátorům, aby se nastavily na hodnoty které vedou na hodnoty redukovaných cen, tak, že řešení LRP méně porušuje podmínky pokrytí. Pro měření byla použita stejná matice jako v předchozím měření.

\begin{figure}[h!]
\begin{center}
\includegraphics[width=1.0\textwidth]{VyvojMult}
\end{center}
\caption{Vývoj multiplikátorů}
\label{graphVyvojMult}
\end{figure}

\subsection{Multiplikátory kroku a iterace}
\label{kroky}

Na základě úvahy v části \ref{zaklHodnoty} bylo změřeno chování Lagrangeovské relaxace s různými parametry počátečního koeficientu kroku $t_{init}$, minimálního koeficientu kroku $t_{min}$ a počtu iterací změny kroku $N_t$ - viz tabulka \ref{tab:parametry1}. Následující tabulka \ref{tab:krokaiterace} ukazuje, jak se změnil výpočetní čas, počet iterací a výsledné hodnoty LB a UB vztažené k ceně optimálního řešení problému . Do časů je zahrnuto úvodní odstraňování dominancí. 

Měření byla pro každý případ provedena na 50 maticích o velikosti 150$\times$300 a hustotě 7\% (uvedené hodnoty jsou průměrné).

\begin{table*}[h!]
	\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|}
			\hline
			případ & $t_{init}$ & $t_{min}$ & $N_T$ & čas & LB(\%) & UB(\%)  & iterací  \\
			\hline
			1 & 10 & 0.1 & 40 & 0.25 & 88.62 & 103.78  & 709\\
			\hline
			2 & 5 & 0.1 & 20 & 0.19 & 88.34 & 104.14  & 356\\
			\hline
			3 & 3 & 0.1 & 10 & 0.17 & 87.71 &  105.26 & 187\\
			\hline
			4 & 3 & 0.01 &  10  & 0.19 & 88.66 & 104.08 & 310\\
			\hline
			5 & 3 & 0.01 &  5  & 0.17 & 87.96 & 104.42 & 164\\
			\hline
			6 & 2 & 0.1 & 5 & 0.15 & 87.14 & 106.06 & 88\\
			\hline
			7 & 2 & 0.01 & 20 & 0.16 & 87.93 & 105.02 & 137  \\
			\hline
			8 & 2 & 0.001 & 40 & 0.32 & 89.19 & 102.80 & 1284 \\
			\hline		
			9 & 2 & 0.001 & 5 & 0.17 & 88.03 & 104.51 & 190 \\
			\hline			
		\end{tabular}
	\caption{Multiplikátory kroku a počet iterací}
	\label{tab:krokaiterace}
\end{table*}



Z naměřených hodnot je vidět, že úvaha je pravdivá - vyplatilo se snížit počet iterací a zvýšit počet změn koeficientu kroku. Viz. případy 2 (koeficient kroku byl půlen dvakrát) a 4 (koeficient kroku byl půlen pětkrát) , kde došlo ke zvýšení spodní meze při snížení počtu iterací (obdobně případy 3 a 9). Pro další měření budou použity hodnoty z případu 7, tj. $t_{init}=2$, $t_{min}=0.01$ a $N_t=5$.

\subsection{Výběr heuristiky}
\label{vyber}

Následující tabulka udává hodnoty naměřené pro různé varianty Lagrangeovských heuristik (popsaných v \ref{varianty}), které z nepřípustného řešení LRP tvoří přípustné řešení problému pokrytí.  Do časů je zahrnuto úvodní odstraňování dominancí. Měření bylo pro každou variantu provedeno na padesáti maticích o velikosti 150$\times$300 a hustotě 7\% (uvedené hodnoty jsou průměrné).

\begin{table*}[h!]
	\centering
\begin{tabular}{|c|c|c|c|c|}
			\hline
			varianta & čas & LB(\%) & UB(\%)  & iterací  \\
			\hline
			1 & 0.17 & 87.17 & 104.10 & 137  \\
			\hline
			2 & 0.17 & 87.16 & 105.58 & 137  \\
			\hline
			3 & 0.16 & 87.14 & 103.67 & 139 \\
			\hline
			4 & 0.18 & 87.17 & 104.58 & 138 \\
			\hline
			5 & 0.17 & 87.17 & 104.67 & 136 \\
			\hline
		\end{tabular}
	\caption{Výběr heuristiky}
	\label{tab:vyberheuristiky}
\end{table*}

Z naměřených hodnot vyplývá, že na zvolené variantě heuristiky příliš nezáleží. Pro další měření byla zvolena varianta 3.

\subsection{Četnost spouštění kompletující heuristiky}
\label{cetnost}

Na základě úvahy v části \ref{zaklHodnoty} bylo změřeno chování Lagrangeovské relaxace s různými prodlevami ve spouštění Lagrangeovské heuristiky (která vylepšuje hodnotu $UB$) $N_h$. Následující tabulka \ref{tab:spusteniheuristiky} ukazuje, jak se změnil výpočetní čas a výsledné hodnoty LB a UB vztažené k ceně optimálního řešení problému.  Do časů je zahrnuto úvodní odstraňování dominancí.

\begin{table*}[h!]
	\centering
\begin{tabular}{|c|c|c|c|c|c|}
			\hline
			případ & $N_h$ & čas & LB(\%) & UB(\%)  & iterací  \\
			\hline
			1 & 1 &  0.16 & 87.17 & 104.10 & 137 \\
			\hline
			2 & 2 & 0.16 &  87.15 & 104.41 & 137 \\
			\hline
			3 & 5 & 0.16 &  87.19 & 106.33 & 139 \\
			\hline
			4 & 10 & 0.16 & 87.21 & 108.18 & 138\\
			\hline
			5 & 15 & 0.16 & 87.23 & 109.50 &139\\
			\hline
			6 & 20 & 0.16 & 87.18 & 108.92 & 137  \\
			\hline
		\end{tabular}
	\caption{Četnost spouštění Lagrangeovské heuristiky}
	\label{tab:spusteniheuristiky}
\end{table*}

Měření bylo pro každou hodnotu četnosti provedeno na padesáti maticích o velikosti 150$\times$300 a hustotě 7\% (uvedené hodnoty jsou průměrné).

Z naměřených hodnot je patrné, že pokud se heuristika nespouští v každé iteraci relaxace, jsou nalezena horší přípustná řešení (nižší hodnoty $UB$). Navíc vliv na výpočetní čas je minimální. Proto pro další měření je heuristika spouštěna v každé iteraci relaxace, tedy $N_h=1$.

\subsection{Závislost běhu relaxace na hustotě matice}
\label{zavislostHustota}
Grafy \ref{graphRelaxHustota1} a \ref{graphRelaxHustota2} zobrazují závislost trvání relaxace a kvality nalezeného heuristického řešení a spodní meze na hustotě matice. Cílem je zjistit, jestli má odstranění dominancí před začátkem relaxace vliv na celkový průběh relaxace. Pokud by vliv byl malý, mohlo by být výhodnější ve výsledném řešiči vynechat odstraňování dominancí pro každé volání rekurzivní funkce řešiče. Tím by došlo k ušetření výpočetního času. Měření bylo pro každou hodnotu hustoty provedeno na padesáti maticích o velikosti 150$\times$300 (uvedené hodnoty jsou průměrné).

\begin{figure}[h!]
\begin{center}
\includegraphics[width=1.0\textwidth]{RelaxHustota1}
\end{center}
\caption{Trvání relaxace pro různé hustoty matice}
\label{graphRelaxHustota1}
\end{figure}


Graf \ref{graphRelaxHustota1} zobrazuje, jak se s zvětšující hustotou matice roste výpočetní čas. Jelikož při vysoké hustotě jeden sloupec pokrývá mnohem více řádku, při jeho zařazení nebo nezařazení do LRP je ovlivněno mnoho multiplikátorů. To vede k tomu, že se daří často nacházet nové hodnoty LB (v některých případech docházelo ka nastavování nové hodnoty LB  v každé iteraci relaxace. Těchto iterací bylo 10000, kdy byla relaxace zastavena.). Pro matice s věští hustotou jak 60\% platí, že cena optimálního řešení je velmi nízká (pro pokrytí je potřeba málo sloupců). To vede k tomu, že k nalezení dostatečné hodnoty LB dochází dříve. Měření proběhlo na stejných maticích jako v měření pro graf \ref{graphRelaxHustota1}.

\begin{figure}[h!]
\begin{center}
\includegraphics[width=1.0\textwidth]{RelaxHustota2}
\end{center}
\caption{Výsledky relaxace pro různé hustoty matice}
\label{graphRelaxHustota2}
\end{figure}

Graf \ref{graphRelaxHustota2} zobrazuje, jak se s zvětšující hustotou matice snižuje kvalita nalezené spodní meze. Jelikož pro husté matice je cena optimálního řešení nízká a hodnota LB není celočíselná, je v grafu uvedena hodnota LB zaokrouhlená nahoru na celé číslo. Tato hodnota se totiž v relaxaci využívá k uršní, jestli se má relaxace zastavit nebo ne. Z grafu je také vidět, že odstraňování dominancí má na kvalitu nalezeného heuristického řešení a spodní meze minimální vliv.

\subsection{Závislost běhu relaxace na velikosti matice}

Grafy \ref{graphRelaxVelikost1} a \ref{graphRelaxVelikost2} zobrazují závislost trvání relaxace a kvalitu nalezených mezí na velikosti matice. Měření byla provedena na maticích o hustotě 7\% (pro každou velikost bylo vygenerováno 50 různých matic - uvedené hodnoty jsou průměrné).

\begin{figure}[h!]
\begin{center}
\includegraphics[width=1.0\textwidth]{RelaxVelikost1}
\end{center}
\caption{Trvání relaxace pro různé velikosti matice}
\label{graphRelaxVelikost1}
\end{figure}

\begin{figure}[h!]
\begin{center}
\includegraphics[width=1.0\textwidth]{RelaxVelikost2}
\end{center}
\caption{Výsledky relaxace pro různé velikosti matice}
\label{graphRelaxVelikost2}
\end{figure}


Graf \ref{graphRelaxVelikost2} zobrazuje, jak se s zvětšující velikostí matice snižuje kvalita nalezené spodní meze. Pro výsledný řešič to znamená, že pro veliké matice nebude relaxace dostatečná pro určení spodní meze a řešič tak bude muset prohledávat větší část stavového prostoru, čímž dojde ke zvýšení výpočetního času.

\section{Duální relaxace}

Tato část je věnována chování měření duální Lagrangeovské relaxace. Cílem je zjistit, o kolik je duální relaxace výpočetně náročnější než jednoduchá a jak moc se projeví použití ceny řešení duálního problému jakožto horní meze ve vztahu pro úpravu multiplikátorů na výsledné hodnotě $LB$.

\subsection{Vývoj spodní a horní meze}
\label{zaklHodnotyDual}

Z grafu \ref{graphVyvojDual1} lze vyčíst, jakým způsobem je vylepšována cena duálního řešení $w_{LDP}$ tak, aby se co nejvíce přiblížila hodnotě $LB$. Také je zřejmé, že pro iniciální duální koeficient kroku $t_{Dinit}=2$ nedošlo k nalezení koeficientů takových, aby cena duálního řešení byla nižší, než cena nejlepšího řešení nalezeného Lagrangeovskými heuristikami spouštěnými v rámci relaxace. Pro měření byla použita stejná matice jako pro měření v \ref{zaklHodnoty}.

\begin{figure}[h!]
\begin{center}
\includegraphics[width=1.0\textwidth]{VyvojDual1}
\end{center}
\caption{Vývoj mezí duální relaxace}
\label{graphVyvojDual1}
\end{figure}

\begin{figure}[h!]
\begin{center}
\includegraphics[width=1.0\textwidth]{VyvojDual2}
\end{center}
\caption{Vývoj mezí duální relaxace}
\label{graphVyvojDual2}
\end{figure}

Graf \ref{graphVyvojDual2} zobrazuje situaci, kdy byl zvolen vyšší duální koeficient kroku $t_{Dinit}=3$. Nalezené duální řešení $w_{LDP}$ poskytuje přesnější hodnotu horní meze $UB$ pro Lagrangeovskou relaxaci a díky tomu je teoreticky možné nalézt řešení $LRP$ s vyšší cenou a tak zvýšit $LB$. Hodnoty nejsou relativní vůči ceně optimálního řešení.

\subsection{Srovnání jednoduché a duální relaxace}

Následující tabulka zobrazuje srovnání vybraných případů jednoduché a duální Lagrangeovské relaxace spouštěné s různými parametry $t_{Dinit}$, $t_{Dmin}$ a $N_{Dt}$. Z hodnot lze vyčíst, že použití duální relaxace nevede k nalezení lepších hodnot $LB$. Navíc přepočítávání duálních koeficientů je výpočetně náročné a prodlužuje se tak celkový výpočetní čas. Pro další měření tedy bude použita jednoduchá Lagrandeovská relaxace bez počítání duálního problému. Měření byla pro každý případ provedena na 50 maticích o velikosti 150$\times$300 a hustotě 7\% (uvedené hodnoty jsou průměrné).

\begin{table*}[h]
	\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|}
			\hline
			případ & $t_{Dinit}$  & $t_{Dmin}$ & $N_{Dt}$ & čas & LB(\%) & BHV(\%)*  & iterací  \\
			\hline
			Simple & X  &  X  & X & 0.04 & 87.91 & 104.69 & 135 \\
			\hline
			Dual1 & 10 & 0.1 & 40 & 0.38 & 87.95 & 102.45 & 1249 \\
			\hline
			Dual2 & 10 & 0.1 & 5   & 0.09 & 87.74 & 104.06 & 209 \\
			\hline
			Dual3 & 5   & 0.1 & 40 & 0.36 & 87.85 & 102.57 & 1199 \\
			\hline
			Dual4 & 5   & 0.1 & 5   & 0.10 & 87.78 & 104.20 & 247\\
			\hline
			Dual5 & 3   & 0.1 & 40 & 0.52 & 88.02 & 102.11 & 1813  \\
			\hline
			Dual5 & 3   & 0.1 & 5   & 0.13 & 87.94 & 102.23 & 353  \\
			\hline
			Dual5 & 3  & 0.01 & 40 & 0.61 & 88.04 & 101.91 & 2134  \\
			\hline
			Dual5 & 3  & 0.01 & 5 & 0.17 & 87.97 & 102.58 & 515  \\
			\hline
		\end{tabular}
	\caption{Srovnání jednoduché a duální relaxace}
	\label{tab:srovnaniSimpleDual}
\end{table*}


* - BHV je nejnižší cena řešení nalezeného Lagrangeovskýmí heuristikami.

\section{Chování řešiče}

Tato část je věnována měření chování celkového řešiče, který využívá informace o spodní mezi problému z Lagrangeovské relaxace. 

\subsection{Závislost běhu řešiče na hustotě matice}

Grafy \ref{graphResicHustota1} a \ref{graphResicHustota2} zobrazují srovnání běhu algoritmu v šesti variantách, které se liší v četnosti odstraňování dominancí pro různé hustoty matice a ve způsobu výběru sloupce. Varianty odstraňování dominancí jsou tři. V první variantě je odstraňování dominancí provádí při každém volání metody řešiče. V druhé variantě se odstraňování dominancí provede pouze při prvním volání, v ostatních se pouze kontroluje, zda podproblém  neobsahuje esenciální sloupce. V poslední variantě k odstraňování dominancí nedochází nikdy, pouze se kontrolují esenciální sloupce. Pro měření byly použity stejné matice jako pro měření v \ref{zavislostHustota}. Tyto tři varianty jsou spouštěny se dvěma způsoby vybírání sloupců do řešení - pomocí heuristiky ContribAdd a pomocí informací získaných v Lagrangeovské relaxaci. Cílem tohoto měření je ověřit, která varianta je výhodnější a také potvrdit výsledky měření v části \ref{zavislostHustota} - tedy ukázat, že se odstraňování dominancí při každém volání rekurzivní funkce nevyplatí. 

\begin{figure}[h!]
\begin{center}
\includegraphics[width=1.0\textwidth]{ResicHustota1}
\end{center}
\caption{Závislost doby běhu řešiče na hustotě matice (Lagrange)}
\label{graphResicHustota1}
\end{figure}

\begin{figure}[h!]
\begin{center}
\includegraphics[width=1.0\textwidth]{ResicHustota2}
\end{center}
\caption{Závislost doby běhu řešiče na hustotě matice (ContribAdd)}
\label{graphResicHustota2}
\end{figure}

Pro matice s hustotou do tří procent je čas řešení nízký - to je způsobeno značným množstvím esenciálních sloupců. S přibývající hustotou se cyklické jádro matic zvětšuje, a tak se zvyšuje i doba běhu. Okolo 10\% hustoty trvá řešení nejdéle. Další zvyšování hustoty má za následek to, že každý sloupec pokrývá více řádků. Při jeho zařazení do řešení se tak problém zmenší více než pro řidší matice a je zapotřebí méně volání rekurzivní funkce. Tím se celková doba běhu algoritmu snižuje. Pro husté matice (hustota větší jak 50 \%) příliš nezáleží na volbě způsobu odstraňování dominancí a způsobu výběru sloupce. Pro řidší matice se nejvíce vyplatí způsob vybírání sloupců založený na informacích Lagrangeovské relaxace bez odstraňování dominancí.

\subsection{Závislost běhu řešiče na velikosti matice}

Graf \ref{graphResicVelikost1} zobrazuje závislost doby běhu řešiče na velikosti matice ve dvou variantách, které se stejně jako v předešlém měření liší ve způsobu výběru sloupců přidávaných do řešení. K odstraňování dominancí došlo pouze při prvním volání rekurzivní funkce řešiče. Měření byla provedena na maticích o hustotě 7\% - pro každou velikost bylo vygenerováno padesát instancí (uvedené hodnoty jsou průměrné).

\begin{figure}[h!]
\begin{center}
\includegraphics[width=1.0\textwidth]{ResicVelikost1}
\end{center}
\caption{Porovnání závislosti doby běhu řešičů na velikosti matice}
\label{graphResicVelikost1}
\end{figure}

\begin{table*}[h!]
	\centering
\begin{tabular}{|c|c|c|c|c|c|}
			\hline
			&  \multicolumn{2}{|c|}{Lagrange} & \multicolumn{2}{|c|}{ContribAdd}  \\
			\hline
			velikost matice & čas [s]& stavů & čas [s]& stavů \\
			\hline
			100x150 &  0.9 & 124 & 1.7 & 220\\
			\hline
			120x190 &  1.7 & 173 & 2.5 & 254\\
			\hline
			140x230 &  3.5 & 304 & 5.7 & 484\\
			\hline
			160x270 &  6.1 & 447 & 13.9 & 925\\
			\hline
			180x310 &  29.8 & 1962 & 43.7 & 2547 \\
			\hline
			200x350 &  69.2 & 3677 & 140.1 & 6917 \\
			\hline
			220x390 &  114.6 & 5002 & 432.0 & 18668 \\
			\hline
		\end{tabular}
	\caption{Porovnání řešičů pro různé velikosti matic}
	\label{tab:resiceVelikost1}
\end{table*}

Z grafu a tabulky je vidět, že při vybírání sloupců pomocí heuristiky ContribAdd doba běhu roste rychleji než při vybírání sloupců pomocí informací z Lagrangeovské relaxace. Také je vidět, že doba běhu řešiče B\&B Lagrange se pro danou hustotu matic (7\%) roste exponenciálně se zvětšující se maticí.

\subsection{Závislost běhu řešiče na nastavení Lagrangeovské relaxace}

Tabulka \ref{tab:nastaveniRelaxace1} zobrazuje, jak se mění výpočetní čas v závislosti na parametrech Lagrangeovské relaxace. Cílem je zjistit, jestli z hlediska celkové doby běhu řešiče není vyhodnější, pokud jsou paramtery relaxace nastaveny tak, aby proběhla v rychlejším čase za cenu nižší hodnty nalezené spodní meze. Měření byla provdena pro matice o velikosti 130$\times$260 a hustotě 7\% - pro každý případ bylo vygenerováno 50 instancí (uvedené hodnoty jsou průměrné).

\begin{table*}[h!]
\centering
\begin{tabular}{|c|c|c|c|c|c|}
			\hline
			případ & $t_{init}$  & $t_{min}$ & $N_{t}$ & čas & stavů  \\
			\hline
			1 & 10 & 0.1 & 40 & 6.54 &122 \\ 
			\hline
			2 & 10 & 0.1 & 20 & 4.37 & 142 \\
			\hline
			3 & 10 & 0.1 & 10  & 2.97 &  151 \\
			\hline
			4 & 10 & 0.1 & 5  & 2.70 & 216 \\
			\hline
			5 & 5 & 0.1 & 20 & 4.05 &  142 \\
			\hline
			6 & 5 & 0.1 & 10 & 2.85 & 151 \\
			\hline
			7 & 5 & 0.1 & 5 & 2.59 &  213  \\
			\hline
			8 & 3 & 0.1 & 20 & 3.91 & 141 \\
			\hline
			9 & 3 & 0.1 & 10 & 2.93 & 173 \\
			\hline
			10 & 3 & 0.1 & 5 & 2.27 & 197 \\
			\hline
			11 & 2 & 0.1 & 20 & 3.22 & 128  \\
			\hline
			12 & 2 & 0.1 & 10 & 2.36 &  143\\
			\hline
			13 & 2 & 0.1 & 5 & 1.96 &  171\\
			\hline
			14 & 2 & 0.01 & 20 & 4.39 & 131  \\
			\hline
			15 & 2 & 0.01 & 10 & 3.08 &  151\\
			\hline
			16 & 2 & 0.01 & 5 & 2.49 &  193\\
			\hline
			17 & 1.5 & 0.1 & 20 & 2.96 & 136\\
			\hline
			18 & 1.5 & 0.1 & 10 & 2.20 & 156\\
			\hline
			19 & 1.5 & 0.1 & 5 & 2.07 & 206 \\
			\hline
		\end{tabular}
	\caption{Vliv nastavení Lagrangeovské relaxace na dobu běhu řešiče}
	\label{tab:nastaveniRelaxace1}
\end{table*}

Z naměřených časů lze vyčíst, že parametry relaxace byly v části \ref{kroky} nejsou z hlediska výsledného řešiče optimální. Proto byly pro další měření zvoleny parametry jako pro případ 13. V jiných případech sice byla prozkoumána i menší část stavového prostoru, ale relaxace se provádí pro každý zkoumaný stav, proto se vyplatí takové nastavení relaxace, pro které tyto relaxace netrvají zbytečně dlouho. 

\section{Srovnání řešičů problému prokrytí}
\label{porovnani}

Tato část se zabývá porováním vytvořeného řešiče a Lagrangeovské relaxace s již existujícím řešičem problému pokrytí AURA II a heuristikami ContribAdd a Servítovy heuristiky. 

\subsection{Porovnání B\&B Lagrange s AURA II}

Tato část se věnuje porovnání výsledného řešiče B\&B Lagrange s AURA II.

Následující grafy \ref{graphPorovnaniResicuHustota} a \ref{graphPorovnaniResicuVelikost} zobrazují doby běhu řešičů pro různě veliké matice a pro matice s různou hustotou. Závislosti na hustotě byly měřeny pro matice o velikosti 60$\times$70. Závislosti na velikosti byly měřeny pro matice o hustotě 7\%. Pro každé měření bylo vy\-ge\-ne\-ro\-vá\-no 50 instancí matic - uvedené hodnoty jsou průměrné.

\begin{figure}[h!]
\begin{center}
\includegraphics[width=1.0\textwidth]{PorovnaniHustota1}
\end{center}
\caption{Porovnání závislostí doby běhu řešičů na hustotě matice}
\label{graphPorovnaniResicuHustota}
\end{figure}

\begin{table*}[h]
	\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|}
			\hline
			& \multicolumn{2}{|c|}{AURA II dom.}  &  \multicolumn{2}{|c|}{AURA II bez dom.} & \multicolumn{2}{|c|}{B\&B Lagrange}  \\
			\hline
			hustota [\%] & čas [s]&  stavů & čas [s]& stavů & čas [s] & stavů \\
			\hline
			2 &  $<$0.01 & 1 & $<$0.01 & 6 &$<$0.01 & 1\\
			\hline
			3 & $<$0.01 & 3 & $<$0.01 & 16 & $<$0.01 & 1\\
			\hline
			5 & $<$0.01 & 38 & 0.58 & 162 & $<$0.01 & 2\\
			\hline
			7 &  0.28 & 849 & 0.02 & 2267 & 0.01 & 6\\
			\hline
			10 &  8.10 & 15722 & 6.64 & 25516& 0.06 & 21\\
			\hline
			15 & 30.49&  57608& 20.93 & 89941 & 0.09 & 27\\
			\hline
			20 & 12.11& 25083 & 7.99 & 37554& 0.08 & 21\\
			\hline
			30 &  2.37 & 5069 & 1.59 & 7634& 0.06 & 13\\
			\hline
			40 &  0.70 &  1250 & 0.45 & 1918& 0.05 & 9\\
			\hline
			50 &  0.27 & 368 & 0.15 & 539 & 0.04 & 6\\
			\hline
		\end{tabular}
	\caption{Porovnání závislostí doby běhu řešičů na hustotě matice}
	\label{tab:resiceHustota}
\end{table*}

Z tabulky \ref{tab:resiceHustota} je vidět, jaký má hustota matice vliv na hledání minimálního pokrytí pomocí AURA II. Velikost matice je ale příliš malá na to, aby se hustota nějak projevila i na řešiči B\&B Lagrange. Pokud by ale byla zvolena větší matice, doba běhu AURA II by byla nepřijatelně veliká - jak je vidět z grafu \ref{graphPorovnaniResicuVelikost}. Z tabulky je také vidět, že odstraňování dominancí sice vede na menší počet volání rekurzivnío algoritmu (méně prozkoumaných stavů ve stavovém prostou), nicméně celkově se odstraňování dominancí nevyplatí - trvá dlouho a algoritmus je tak celkově pomalejší. Z naměřených dat pro jednotlivé instance (veškerá naměřená data jsou přiložena na CD) také vyplynulo, že AURA II v některých případech nenachází optimální řešení.

\begin{figure}[h!]
\begin{center}
\includegraphics[width=1.0\textwidth]{PorovnaniVelikost1}
\end{center}
\caption{Porovnání závislostí doby běhu řešičů na velikosti matice}
\label{graphPorovnaniResicuVelikost}
\end{figure}

\begin{table*}[h!]
	\centering
\begin{tabular}{|c|c|c|c|c|c|}
			\hline
			&  \multicolumn{2}{|c|}{AURA II bez dom.} & \multicolumn{2}{|c|}{B\&B Lagrange}  \\
			\hline
			velikost matice & čas [s]& stavů & čas [s]& stavů \\
			\hline
			50x50 & $<$0.01 & 38 &  $<$0.01 & 1 \\
			\hline
			60x70 & 0.32 & 1275 & 0.01 & 5\\
			\hline
			70x90 & 31.8 & 83 462& 0.07 & 23\\
			\hline
			75x100 & 144 & 336 481&  0.11 & 28\\
			\hline
			80x110 & - &  - & 0.20& 46\\
			\hline
			100x150 &  - & - & 0.88 & 124\\
			\hline
			120x190 &  - & - & 1.71 & 173\\
			\hline
			140x230 &  - & - & 3.47 & 304\\
			\hline
			160x270 &  - & - & 6.24 & 457\\
			\hline
			180x310 &  - & - & 29.8 & 1 962 \\
			\hline
			200x350 &  - & - & 69.2 & 3 677 \\
			\hline
			220x390 &  - & - & 117 & 5 806 \\
			\hline
			240x430 &  - & - & 172 & 6 512 \\
			\hline
		\end{tabular}
	\caption{Porovnání závislostí doby běhu řešičů na velikosti matice}
	\label{tab:resiceVelikost2}
\end{table*}

Z tabulky \ref{tab:resiceVelikost2} a grafu \ref{graphPorovnaniResicuVelikost} lze vyčíst, že doba běhu B\&B Lagrange se pro danou hustotu matic (7\%) roste exponenciálně se zvětšující se maticí. Pro B\&B Lagrange je ale tento růst podstatně pomalejší.

\subsection{Porovnání Lagrangeovské relaxace s heuristikami}
\label{srovnaniRelaxaceHeuritisky}

Tato část se věnuje porovnání Lagrangeovské relaxace s heuristikami.

Graf \ref{graphPorovnaniHeuristikHustota1} zobrazuje doby běhu heuristik a Lagrangeovské relaxace v závislosti na hustotě matice. Závislosti na hustotě byly měřeny pro matice o velikosti 150$\times$300 - pro každý případ bylo vygenerováno 50 instancí (uvedené hodnoty jsou průměrné).

\begin{figure}[h!]
\begin{center}
\includegraphics[width=1.0\textwidth]{HeuristikyHustota1}
\end{center}
\caption{Porovnání závislostí doby běhu heuristik a relaxace na hustotě matice}
\label{graphPorovnaniHeuristikHustota1}
\end{figure}

Z grafu lze vyčíst, že Lagrangeovská relaxace je rychlejší než heuristiky především pro matice řidší jak 12\%. U heuristik je klesání výpočetního času s rostoucí hustotou způsobené tím, že při vyšší hustotě se více zmenší matice problému s každým vybraným sloupcem. Chování relaxace v závislosti na hustotě matice je popsané v části \ref{zavislostHustota}.

Grafy \ref{graphPorovnaniHeuristikHustota2} a tabulka \ref{tab:heuristikyHustota} zobrazuje závislost odchylek nalezených řešení na hustotě matice. Závislosti byly měřeny pro matice o velikosti 150$\times$300 - pro každý případ bylo vygenerováno 50 instancí (uvedené hodnoty jsou průměrné).

\begin{figure}[h!]
\begin{center}
\includegraphics[width=1.0\textwidth]{HeuristikyHustota2}
\end{center}
\caption{Porovnání závislostí odchylek řešení heuristik a relaxace na hustotě matice}
\label{graphPorovnaniHeuristikHustota2}
\end{figure}

\begin{table*}[h!]
	\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|}
			\hline
			& \multicolumn{2}{|c|}{relaxace}  &  \multicolumn{2}{|c|}{ContribAdd} & \multicolumn{2}{|c|}{Servít}  \\
			\hline
			hustota matice [\%] & čas [s]&  odchylka & čas [s]& odchylka & čas [s] & odchylka \\
			\hline
			0.5 & 0.01 & 0.00 & 0.05 & 0.08 & 0.08 & 0.27\\
			\hline
			1    & 0.02 & 0.00 & 0.07 & 0.21 & 0.14 & 0.55\\
			\hline
			3    & 0.03 & 0.00 & 0.15 & 0.59 & 0.23 & 0.81\\
			\hline
			5    & 0.04 & 0.02 & 0.14 & 0.72 & 0.19 & 0.83\\
			\hline
			7    & 0.04 & 0.03 & 0.10 & 0.66 & 0.12 & 0.73\\
			\hline
			10  & 0.04 & 0.04 & 0.06 & 0.56 & 0.07 & 0.58\\
			\hline
			15  & 0.04 & 0.03 & 0.04 & 0.44 & 0.04 & 0.46\\
			\hline
			20  & 0.04 & 0.01 & 0.03 & 0.40 & 0.04 & 0.41\\
			\hline
			30  & 0.05 & 0.01 & 0.03 & 0.30 & 0.03 & 0.31\\
			\hline
			40  & 0.05 & 0.00 & 0.02 & 0.27 & 0.03 & 0.28\\
			\hline
			50  & 0.05 & 0.03 & 0.02 & 0.19  & 0.02 & 0.18\\
			\hline
		\end{tabular}
	\caption{Porovnání heuristik s relaxací pro matice s různou hustotou}
	\label{tab:heuristikyHustota}
\end{table*}

Z grafu a tabulky je patrné, že Lagrangeovská relaxace dává lepší výsledky než heuristiky především pro matice řidší jak 50\% (ale za cenu delšího trvání - viz graf  \ref{graphPorovnaniHeuristikHustota2}) . Zmenšování odchylek pro rostoucí hustotu je způsobeno tím, že v hustých maticích jeden sloupec pokrývá více řádků. Tím pádem je k pokrytí celé matice zapotřebí méně sloupců, a optimální cena je tak nižší než pro řídké matice. Chování relaxace v závislosti na hustotě matice je popsané v části \ref{zavislostHustota}.

Následující grafy a tabulky zobrazují závislosti doby běhu a odchylek nalezených řešení na velikosti matice. Měření se týkají heuristik a Lagrangeovské relaxacace.  Závislosti byly měřeny pro matice o hustotě 7\% a 20\% - pro každý případ bylo vygenerováno 50 instancí (uvedené hodnoty jsou průměrné).

\begin{figure}[h!]
\begin{center}
\includegraphics[width=1.0\textwidth]{HeuristikyVelikost1}
\end{center}
\caption{Porovnání závislostí doby běhu heuristik a relaxace na velikosti matice}
\label{graphPorovnaniHeuristikVelikost1_7}
\end{figure}

Z grafu \ref{graphPorovnaniHeuristikVelikost1_7} lze vyčíst, že výsledná odchylka nalezeného řešení heuristik i relaxace  pro danou hustotu matic není velikostí matice příliš ovlivněna. Z grafu  \ref{graphPorovnaniHeuristikVelikost2_7} je vidět, že z hlediska výpočetního času jsou heuristiky citlivější na velikost matice (pro danou hustotu 7\%). To je dáno tím, že pro větší počet sloupců trvá heuristikám déle vybírání sloupce, který bude zařazen do řešení.

\begin{figure}[h!]
\begin{center}
\includegraphics[width=1.0\textwidth]{HeuristikyVelikost2}
\end{center}
\caption{Porovnání závislostí doby běhu heuristik a relaxace na hustotě matice}
\label{graphPorovnaniHeuristikVelikost2_7}
\end{figure}

\begin{table*}[h!]
	\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|}
			\hline
			& \multicolumn{2}{|c|}{Lag. relaxace}  &  \multicolumn{2}{|c|}{ContribAdd} & \multicolumn{2}{|c|}{Servít}  \\
			\hline
			velikost matice & čas [s]&  odchylka & čas [s]& odchylka & čas [s] & odchylka\\
			\hline
			100x150 & 0.02 & 0.02 & 0.04 & 0.65 & 0.04 & 0.68\\
			\hline
			120x190 & 0.03 & 0.02 & 0.07 & 0.69 & 0.07 & 0.71\\
			\hline
			140x230 & 0.03 & 0.03 & 0.09 & 0.71 & 0.11 & 0.77\\
			\hline
			160x270 & 0.05 & 0.03 & 0.12 & 0.70 & 0.15 & 0.79\\
			\hline
			180x310 & 0.05 & 0.04 & 0.17 & 0.72 & 0.19 & 0.79\\
			\hline
			200x350 & 0.07 & 0.04 & 0.21 & 0.73 & 0.24 & 0.79\\
			\hline
			220x390 & 0.05 & 0.06 & 0.22 & 0.72 & 0.25 & 0.78\\
			\hline
		\end{tabular}
	\caption{Porovnání heuristik s relaxací pro matice s hustotou 7\%}
	\label{tab:heuristikyVelikost7}
\end{table*}

\newpage

Následující grafy zobrazují závislost doby běhu heuristik a relaxace na velikosti matice pro hustotu matic 20\%, kdy je podle grafu \ref{graphPorovnaniHeuristikHustota1} relaxace pomalejší než heuristiky. Z grafu \ref{graphPorovnaniHeuristikVelikost2_20} je vidět, že pro danou hustotu je z hlediska doby běhu Lagrangeovská relaxace citlivější na změny velikosti matice.

\begin{figure}[h!]
\begin{center}
\includegraphics[width=1.0\textwidth]{HeuristikyVelikost3}
\end{center}
\caption{Porovnání závislostí odchylek řešení heuristik a relaxace na velikosti matice}
\label{graphPorovnaniHeuristikVelikost1_20}
\end{figure}

\begin{figure}[h!]
\begin{center}
\includegraphics[width=1.0\textwidth]{HeuristikyVelikost4}
\end{center}
\caption{Porovnání závislostí doby běhu heuristik a relaxace na velikosti matice}
\label{graphPorovnaniHeuristikVelikost2_20}
\end{figure}

\begin{table*}[h!]
	\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|}
			\hline
			& \multicolumn{2}{|c|}{Lag. relaxace}  &  \multicolumn{2}{|c|}{ContribAdd} & \multicolumn{2}{|c|}{Servít}  \\
			\hline
			velikost matice & čas [s]&  odchylka [\%] & čas [s]& odchylka [\%] & čas [s] & odchylka [\%] \\
			\hline
			100x150 & 0.03 & 0.02 & 0.02 & 0.41 & 0.02 & 0.43\\
			\hline
			120x190 & 0.04 & 0.02 & 0.02 & 0.45 & 0.02 & 0.46\\
			\hline
			140x230 & 0.05 & 0.02 & 0.03 & 0.48 & 0.03 & 0.51\\
			\hline
			160x270 & 0.06 & 0.02 & 0.03 & 0.43 & 0.03 & 0.43\\
			\hline
			180x310 & 0.08 & 0.04 & 0.05 & 0.48 & 0.05 & 0.51\\
			\hline
			200x350 & 0.10 & 0.03 & 0.05 & 0.50 & 0.05 & 0.49\\
			\hline
			220x390 & 0.12 & 0.02 & 0.05 & 0.43 & 0.05 & 0.47\\
			\hline
		\end{tabular}
	\caption{Porovnání heuristik s relaxací pro matice s hustotou 20\%}
	\label{tab:heuristikyVelikost20}
\end{table*}

\newpage

\subsection{Porovnání řešičů na reálných maticích}
\label{realneMatice}

Tabulka \ref{tab:realData1} zobrazuje porovnání běhů řešičů, Lagrangeovské relaxace a heuristik na maticích, které byly vygenerovány z PLA tabulek benchmarkových obvodů, které byly dodány vedoucím práce a PLA tabulek vygenerovaných nástrojem pro tvorbu tabulek logických funkcí. Parametry matic a příslušných tabulek jsou uvedeny v tabulce \ref{tab:realData} na začátku této kapitoly.
Z naměřených hodnot vyplývá, že pro matice generované přímo nástrojem BOOM chování řešičů odpovídá chování pro uměle vytvořené matice, které byly použity pro měření v předchozích částech této kapitoly. Při bližším zkoumání je ovšem možné najít výjimky:
\newpage

\begin{table*}[h!]
\centering
\begin{tabular}{|c||c||c||c|c||c|c||}
			\hline
			 název & AURA II &  B\&B Lag & \multicolumn{2}{|c||}{Relaxace} & \multicolumn{2}{|c||}{ContribAdd} \\
\hline
			- & čas [s] & čas [s] &  čas [s] & odchylka & čas [s] & odchylka   \\
			\hline
			08x08x08 & $<$0.05   & $<$0.05   & $<$0.05 & 0.00 &$<$0.05 & 0.32  \\ 
			\hline
			08x12x12 & $<$0.05   & $<$0.05   & $<$0.05 & 0.00 & $<$0.05 & 0.59 \\ 
			\hline
			10x01x100 & 0.48        &$<$0.05   & $<$0.05 & 0.00 & 0.05 & 0.69  \\ 
			\hline
			10x01x200 & 140.4      & 0.83         & $<$0.05 & 0.01 & 0.09 & 0.78  \\ 
			\hline
			10x10x10 & $<$0.05   &$<$0.05    & $<$0.05 & 0.03 &  $<$0.05 & 0.54  \\ 
			\hline
			10x10x20 & 5.84          & 0.08         &  $<$0.05 & 0.01 & $<$0.05 & 0.55 \\ 
			\hline
			10x10x30 & 754.5        &1.55          &  $<$0.05 & 0.02 & 0.09 & 0.74 \\ 
			\hline
			12x12x12 &  2.48         &0.06          & $<$0.05 & 0.00 & $<$0.05& 0.77  \\ 
			\hline
			20x05x20 & 1446.4      & 0.17         & $<$0.05 & 0.00 & $<$0.05 & 0.84  \\ 
			\hline
			20x05x20\_10 & 2.95   & $<$0.05  & $<$0.05 & 0.00 & $<$0.05 & 0.66  \\ 
			\hline
			20x05x20\_20 & 0.25   & 0.06         & $<$0.05 & 0.00 & $<$0.05 & 0.64 \\ 
			\hline
			50x50x05\_10 & $<$0.05            & $<$0.05  & $<$0.05 & 0.00 & $<$0.05 & 0.47  \\ 
			\hline
			15x15x50\_30\_80 & $<$0.05    & $<$0.05  &  $<$0.05 & 0.00 & $<$0.05 & 0.38 \\ 
			\hline
			15x15x50\_50\_60 & $<$0.05    &  $<$0.05 &  $<$0.05 & 0.00 & $<$0.05 & 0.26\\ 
			\hline
			50x10x50\_10\_80 & 7.42           &  $<$0.05 &  $<$0.05 & 0.00 & $<$0.05 & 0.54\\ 
			\hline
			50x10x50\_50\_70 & 152.7         & $<$0.05  & $<$0.05 & 0.00 & 0.05& 0.59\\ 
			\hline
			50x10x50\_60\_30 & $<$0.05    & $<$0.05  &  $<$0.05 & 0.00 & $<$0.05 & 0.10 \\ 
			\hline
			apex3 &  $<$0.05    & 0.19        & 0.30 & 0.00 & 0.47 &0.4274  \\ 
			\hline
			bw & 0.48                 & $<$0.05  & $<$0.05  & 0.00 & $<$0.05 & 0.62  \\ 
			\hline
			cps & 140.4              &0.06          & 0.09 & 0.00 & 0.14 & 0.29  \\ 
			\hline
			ex1010 & $<$0.05   & 0.06         & 0.11 & 0.00 & 0.11 & 0.04  \\ 
			\hline
			mainpla & 2.48          & 0.84         & 1.91 & 0.00 & 1.13 & 0.61  \\ 
			\hline
			pdc & 2.95                & 0.06          & 0.08 & 0.00 & 0.09 & 0.33  \\ 
			\hline
			spla & 0.25               & 0.08          & 0.09 & 0.00 & 0.14 & 0.18  \\ 
			\hline
			table3 & 1346.4       & 0.06          & 0.08 & 0.00 & 0.08 & 0.16  \\ 
			\hline
			xparc &$<$0.05       & 0.36          & 0.64 & 0.00 & 0.55 & 0.42  \\ 
			\hline
		\end{tabular}
	\caption{Porovnání řešičů na reálných datech}
	\label{tab:realData1}
\end{table*}


\begin{itemize}
\item Pro matice apex3, ex1010 a xparc trvá nalezení optimálního pokrytí řešiči B\&B Lagrange déle než AURA II. Tyto 3 matice mají společné to, že jejich počet řádků je vyšší než počet sloupců a hustota je menší jak 1\%. Lze usoudit, že nesrovnalost v časech je dána tím, že pro B\&B Lagrange je do času započítáno tvoření přesné mapy pokrytí v matici (viz \ref{repreLagrange}).
\item Pro matice main a xparc je heuristika rychlejší než Lagrangeovská relaxace, což neodpovídá výsledkům měření v \ref{srovnaniRelaxaceHeuritisky}. Důvod je stejný jako v předchozím případě - do času je započítána i tvorba pomocných struktur, což se projeví v případě velikých matic jako tyto dvě.
\end{itemize}

\cleardoublepage
%kapitola 6
\chapter{Začlenění do programu BOOM}

Algoritmus je implementován především ve dvou třídách: 

\begin{itemize}
\item LagBaBCover - implementace algoritmu Branch and Bound Lagrange \ref{alg:alg5}.
\item LagrangeSolver -  implementace algoritmů Lagrangeovských relaxací \ref{alg:alg6} a \ref{alg:alg7}
\end{itemize}

Dále jsou využívány pomocné třídy pro třídění matic a pro reprezentaci matic.

Kód programu BOOM bylo potřeba poupravit tak, aby bylo možné parametry určit, jaký způsob řešení problému pokrytí se má použít. Seznam nových parametrů lze nalézt v příloze \ref{ovladani}.

Příklad použití v kódu:

\begin{verbatim}
CovMatrix *CM = new CovMatrix(rows,cols);
/*
* ...
* fill CM 
*...
*/
LagBaBCover* lagCover = new LagBaBCover(CM);
list<unsigned int>  sol = lagCover->Run(options);
\end{verbatim}



\cleardoublepage
%kapitola 7

\chapter{Závěr}

V této práci byl popsán rekurzivní algoritmus pro řešení problému pokrytí. Tento al\-go\-rit\-mus pracuje metodou větví a hranic a pro ořezávání větví využívá informace získané La\-gran\-geovskou heuristikou. Algoritmus byl implementován v jazyce C++ a začleněn do minimalizačního nástroje BOOM. Chování algoritmu bylo změřeno a v této práci popsáno. Také bylo provedeno měření pro nalezení optimálních parametrů nastavení Lagrangeovské relaxace. Dále byl výsledný řešič srovnán s řešičem založeným na algoritmu AURA II a Lagrangeovská relaxace byla porovnána s heuristikami ContribAdd a heuristikou dle Servíta, které jsou v této práci popsány. \\

Měřením bylo zjištěno několik faktů:
\begin{itemize}
\item Lagrangeovská relaxace nachází lepší hodnoty spodní meze než postupy používané v algoritmu AURA II, což vede k tomu, že výsledný řešič je rychlejší.
\item Duální relaxace umožňuje najít lepší hodnotu horní meze, která se používá ve vztahu pro úpravu multiplikátorů v Lagrangeovské relaxi (\ref{Supgrpostup}). Nicméně výpočet duálních multiplikátorů je časově náročný a z hlediska celkového času běhu řešiče se duální relaxace nevyplatí.
\item Pro výběr sloupce, který se při volání rekurzivního algoritmu přidává do řešení, je oproti heuristice výhodnější využít informace dodané Lagrangeovskou relaxací. 
\item Měření prokázala, že se z časového hlediska nevyplatí odstraňovat dominance při každém volání rekurzivního algoritmu - to platí pro vytvořený řešič i pro AURA II.
\item Bylo zjištěno, že Lagrangeovská heuristika oproti heuristikám nachází řešení s menší odchylkou v ceně, nicméně za cenu větší časové náročnosti pro určité matice. 
\end{itemize}

Tuto práci by bylo možno rozšířit o negativní přístup, který by spočíval ve spouštění Lagrangeovské relaxace s parametry nastavenými tak, aby bylo nalezena větší hodnota spodní meze. 

\cleardoublepage
% konec

% M. Dušek radi:
%\bibliographystyle{alpha}
% kdy citace ma tvar [AutorRok] (napriklad [Cook97]). Sice to asi neni  podle ceske normy (BTW BibTeX stejne neodpovida ceske norme), ale je to nejprehlednejsi.
% 3.5.2009 JZ polemizuje: BibTeX neobvinujte, napiste a poskytnete nam styl (.bst) splnujici citacni normu CSN/ISO. 

\begin{thebibliography}{99}
\bibitem{1} O.coudert. "Two-level logic minimization: an overview", \emph{Integration}, 1994 17-2:97-140.

\bibitem{2} Lukáš Krejčík. Moderní metody řešení problému pokrytí. 2008.

\bibitem{3} Michael Kalouš. Moderní metody řešení problému pokrytí. 2009.

\bibitem{4} CORDONE, Roberto et al. "An Efficient Heuristic Approach to Solve the Unate Covering Problem",  \emph{In Design, Automation, and Test in Europe (Paris France)}, 2000, ISBN 1-58113-244-1, s. 364 - 371. 

\bibitem{5} [CER95] CERIA, S.; NOBILI, P.; SASSANO, A. "A Lagrangian-based heuristic for large-scale set covering problems", \emph{Mathematical Programming}, 1998, 81: 215-228. 

\bibitem{6} M.Servít. "A heuristic method for solving weighted set covering problems", \emph{Digital Processes}, vol. X, 1975, pp. 177-182.

\bibitem{7} Tomáš Měchura. Parametrizovaný generátor náhodných booleovských funkcí. 2006.

\bibitem{8} Hlavička, J., Fišer, P. "BOOM, a Heuristic Boolean Minimizer" , Proc. International Conference on Computer-Aided Design ICCAD 2001, San Jose, California (USA), 4.-8.11.2001, pp. 439-442.

\bibitem{9} Robert Vanderbei Ph.D. - Linear Programming - přednáškové slajdy\\
\verb|http://www.princeton.edu/~rvdb/542/lectures/|.

\bibitem{10} \mbox{David C. Parkes.} - Linear Programming - přednáškové slajdy\\
\verb|http://www.eecs.harvard.edu/~parkes/cs286r/spring04/sections/sec1.pdf|.

\bibitem{11} Yang S. "Logic Synthesis and Optimization Benchmarks, Version 3.0" ,  \emph{Tech. Report, Microelectronics Center of North Carolina}, 1991.



\end{thebibliography}

\cleardoublepage

\appendix

\chapter{Seznam použitých zkratek}

\noindent
$LB$ -  Lower Bound (Dolní mez) \\
$UB$ - Upper Bound (Horní mez) \\
$CP$ - Covering Problem (Problém pokrytí)\\
$P$ - Problem (Problém) \\
$LP$ - Linear problem (Lineární problém) \\
$LRP$ - Lagrangean relaxation problem (Problém Lagrangeovské relaxace) \\
$DP$ -  Dual problem (Duální problém) \\
$LDP$ - Lagrangean dual problem (Lagrangeovský duální problém) \\


\cleardoublepage
\chapter{Obsah přiloženého CD}

\begin{figure}[htb!]
%\begin{left}
\includegraphics{Obsah}
%\end{left}
\end{figure}

\vspace{10mm}

Složka \texttt{Měření} obsahuje výsledky měření, matice na kterých bylo prováěno měření a dávkové soubory spouštějící měření. Ve složce \texttt{Src} je umístěn kód programu a přeložený program spolu s připraveným příkladem ke spuštění. Dokumentace je uložena ve složce \texttt{Dokumentace} -- generováno programem \emph{Doxygen}. Zdrojový kód programu se nachází ve složce \texttt{src}. Text této práce v PDF je ve složce \texttt{TextPDF}. Zdrojový kód tohoto textu ve formátu \TeX se nachází ve složce \texttt{Zdroj text}.

\cleardoublepage
\chapter{Ovládání programu BOOM}
\label{ovladani}

Program BOOM se ovládá parametry při spouštění v příkazové řádce. Stávající parametry jsou:

\noindent syntaxe: 

\begin{verbatim}
BOOM [options] source [destination] [report]
\end{verbatim}

\noindent
{\bf -source} - Vstupní PLA tabulka\\
{\bf -destination} - Výstupní PLA tabulka\\
{\bf -report} - Soubor, do kterého se vypisuje záznam průběhu běhu programu\\

\noindent Nově přidané parametry jsou: \\

\noindent
{\bf -lagN n} - Maximální počet iterací Lagrangevské relaxace\\
{\bf -lagNt n} - Počet iterací Lagrangeovské relaxace před změnou koeficientu kroku \\
{\bf -lagNh n} -Počet iterací Lagrangeovské relaxace mezi spouštěním Lagrangeovské heristiky\\
{\bf -lagTinit f} - Počáteční koeficient kroku\\
{\bf -lagTmin f} - Minimální koeficient kroku\\
{\bf -lagNtDual n} - Počet iterací Lagrangeovské relaxace před změnou duálního koeficientu kroku \\
{\bf -lagTinitDual f} - Počáteční duální koeficient kroku\\
{\bf -lagTminDual f} - Minimální duální koeficient kroku\\

\noindent Použití kteréhokoliv z předchozích parametrů znamená, že se k řešení problému pokrytí bude používat B\&B Lagrange. \\

\noindent
{\bf -noDom} -  Řešič nebude odstraňovat dominance\\
{\bf -1Dom} -  Řešič bude odstraňovat dominance pouze při prvním volání rekurzivního algoritmu\\
{\bf -ContrAdd} -  Řešič bude k výběru sloupce využívat heuristiku ContribAdd (pokud se spouští algoritmus B\&B Lagrange). Jinak tento parametr určuje, že se bude volat heuristika ContribAdd\\
{\bf -Servit} -  Bude se volat heuristika dle Servíta\\
{\bf -inputmatrix s} - Vstupní matice problému\\

Příklad použití (k nalezení na přiloženém CD):

BOOM PLA\textbackslash08x08x08.pla -i 10 vystup02.txt -lagNt 5 -lagNh 0 -lagTinit 2.0 
-lagTmin 0.01 -noDom -inputMatrix matrixPLA\textbackslash08x08x08.pla


\end{document}
