1-lds.tex

% vim: set spell spelllang=en tw=100 et sw=4 sts=4 foldmethod=marker foldmarker={{{,}}} :

\documentclass{beamer}

\usepackage{tikz}
\usepackage{xcolor}
\usepackage{complexity}
\usepackage{hyperref}
\usepackage{listings}

\usetikzlibrary{shapes, arrows, shadows, calc, positioning, fit}
\usetikzlibrary{decorations.pathreplacing, decorations.pathmorphing, shapes.misc}
\usetikzlibrary{tikzmark}

\colorlet{screenverylightgrey}{black!2!white}
\colorlet{screengrey}{black!30!white}

\definecolor{uofgblue}{rgb}{0, 0.321569, 0.533333}
\colorlet{uofgblue20}{uofgblue!20!white}
\colorlet{uofgblue40}{uofgblue!40!white}
\colorlet{uofgblue60}{uofgblue!60!white}
\colorlet{uofgblue80}{uofgblue!80!white}

\definecolor{uofgstone}{rgb}{0.498039, 0.454902, 0.403922}

\definecolor{uofgtdarkgreen}{rgb}{0.380392, 0.564706, 0.501961}
\definecolor{uofgtlightgreen}{rgb}{0.615686, 0.788235, 0.729412}
\definecolor{uofgtyellow}{rgb}{0.85098, 0.827451, 0.643137}
\definecolor{uofgtorange}{rgb}{0.784314, 0.694118, 0.545098}

% {{{ theme things
\useoutertheme[footline=authortitle]{miniframes}
\useinnertheme{rectangles}

\setbeamerfont{block title}{size={}}
\setbeamercolor*{structure}{fg=uofgblue}
\setbeamercolor*{palette primary}{use=structure,fg=black,bg=white}
\setbeamercolor*{palette secondary}{use=structure,fg=black,bg=uofgblue40}
\setbeamercolor*{palette tertiary}{use=structure,fg=white,bg=uofgblue}
\setbeamercolor*{palette quaternary}{fg=white,bg=black}

\setbeamercolor*{titlelike}{parent=palette primary}

\beamertemplatenavigationsymbolsempty

\setbeamertemplate{title page}
{
    \vbox{}
    \vspace*{0.5cm}
    \begin{centering}
        {\usebeamerfont{title}\inserttitle\par}
        \vskip0.5cm\par
        \begin{beamercolorbox}[sep=8pt,center]{author}
            \usebeamerfont{author}\insertauthor
        \end{beamercolorbox}
        {\usebeamercolor[fg]{titlegraphic}\inserttitlegraphic\par}
    \end{centering}
    \vfill

    \begin{tikzpicture}[remember picture, overlay]
        \node at (current page.north west) {\begin{tikzpicture}[remember picture, overlay]\fill
        [fill=uofgblue, anchor=north west] (0, 0) rectangle (\paperwidth, -1.5cm);\end{tikzpicture}};
        \node [anchor=north west, shift={(0.2cm,-0.2cm)}] at (current page.north west) {\includegraphics*[keepaspectratio=true,scale=0.5]{UoG_keyline.eps}};
    \end{tikzpicture}
}

\newcommand{\frameofframes}{/}
\newcommand{\setframeofframes}[1]{\renewcommand{\frameofframes}{#1}}

\makeatletter
\setbeamertemplate{footline}
{%
    \begin{beamercolorbox}[colsep=1.5pt]{upper separation line foot}
    \end{beamercolorbox}
    \begin{beamercolorbox}[ht=2.5ex,dp=1.125ex,%
        leftskip=.3cm,rightskip=.3cm plus1fil]{author in head/foot}%
        \leavevmode{\usebeamerfont{author in head/foot}\insertshortauthor}%
        \hfill%
        {\usebeamerfont{institute in head/foot}\usebeamercolor[fg]{institute in head/foot}\insertshortinstitute}%
    \end{beamercolorbox}%
    \begin{beamercolorbox}[ht=2.5ex,dp=1.125ex,%
        leftskip=.3cm,rightskip=.3cm plus1fil]{title in head/foot}%
        {\usebeamerfont{title in head/foot}\insertshorttitle}%
        \hfill%
        {\usebeamerfont{frame number}\usebeamercolor[fg]{frame number}\insertframenumber~\frameofframes~\inserttotalframenumber}
    \end{beamercolorbox}%
    \begin{beamercolorbox}[colsep=1.5pt]{lower separation line foot}
    \end{beamercolorbox}
}
\makeatother

% }}}

\title{Search and Discrepancies}
\author[Ciaran McCreesh]{\textcolor{uofgblue}{Ciaran McCreesh}}

\begin{document}

{
    \usebackgroundtemplate{\includegraphics*[keepaspectratio=true, height=\paperheight]{background.jpg}}
    \begin{frame}[plain,noframenumbering]
        \titlepage
    \end{frame}
}

\begin{frame}{This Week's Lectures}
    \begin{columns}
        \column{.6\textwidth}
        \begin{itemize}
            \item \textcolor{uofgblue}{Search and Discrepancies}
                \begin{itemize}
                    \item Recap of search and heuristics
                    \item Ideas and techniques
                    \item Implementation
                \end{itemize}
            \item Parallel Constraint Programming
            \item Parallel Search
        \end{itemize}
        \column{.4\textwidth}
        \centering\includegraphics*[keepaspectratio=true,scale=0.5]{images/search-but-not-as-we-know-it.jpg}
        \begin{center}``It's search, Jim, but not\\as we know it.''\end{center}
    \end{columns}
\end{frame}

\begin{frame}{Maintaining Arc Consistency (MAC)}
    \begin{itemize}
        \item Achieve (generalised) arc consistency (AC3, etc).
        \item If we have a domain wipeout, backtrack.
        \item If all domains have one value, we're done.
        \item Pick a variable (using a heuristic) with more than one value, then branch:
            \begin{itemize}
                \item Try giving it one of its possible values (using a heuristic), and recurse.
                \item If that failed, reject that value, pick a new value, and try again.
                \item If we run out of values, backtrack.
            \end{itemize}
    \end{itemize}
\end{frame}

\begin{frame}{Search as a Tree}

    \centering
    \begin{tikzpicture}[scale=0.75]%{{{
        \coordinate (R);

        \coordinate (N) at (R);

        \coordinate (N1) at ($(N) + (-4, -1.25)$);
        \coordinate (N2) at ($(N) + ( 0, -1.25)$);
        \coordinate (N3) at ($(N) + ( 4, -1.25)$);

        \foreach \na in {1, ..., 3}{
            \coordinate (N\na 1) at ($(N\na) + (-1.25, -1)$);
            \coordinate (N\na 2) at ($(N\na) + ( 0,    -1)$);
            \coordinate (N\na 3) at ($(N\na) + ( 1.25, -1)$);

            \foreach \nb in {1, ..., 3}{
                \coordinate (N\na\nb t1) at ($(N\na\nb) + (-0.5, -1)$);
                \coordinate (N\na\nb t2) at ($(N\na\nb) + ( 0.5, -1)$);
            }
        }

        \foreach \na in {1, ..., 3}{
            \draw (N) -- (N\na);
            \foreach \nb in {1, ..., 3}{
                \draw (N\na) -- (N\na\nb);
            }
        }

        \tikzstyle{t} = [draw, fill, fill=uofgblue, rounded corners];
        \foreach \na in {1, ..., 3}{
            \foreach \nb in {1, ..., 3}{
                \draw [t] (N\na\nb) -- (N\na\nb t1) -- (N\na\nb t2) -- cycle;
            }
        }

        \tikzstyle{c} = [draw, circle, fill, fill=uofgblue];
        \node [c] at (N) { };

        \foreach \na in {1, ..., 3}{
            \node [c] at (N\na) { };

            \foreach \nb in {1, ..., 3}{
                \node [c] at (N\na\nb) { };
            }
        }
    \end{tikzpicture}%}}}

    \vspace{1em}

    \begin{itemize}
        \item Circles are recursive calls, triangles are `big' subproblems.
        \item Heuristics determine the `shape' of the tree:
            \begin{itemize}
                \item Variable-ordering heuristics determine the number of children at each level.
                \item Value-ordering heuristics determine the paths explored.
            \end{itemize}
        \item MAC is like Depth-First Search (DFS).
    \end{itemize}
\end{frame}

\begin{frame}{Heuristics and Discrepancies}

    \begin{itemize}
        \item If our value-ordering heuristics are perfect, and an instance is satisfiable, we walk
            straight to a solution by going left at every level.
        \item If an instance is unsatisfiable, perfect variable-ordering heuristics would give the
            smallest possible search tree.
        \item But heuristics aren't perfect\ldots
        \item We call going against a value-ordering heuristic choice a ``discrepancy''.
    \end{itemize}

\end{frame}

\begin{frame}{Two Claims Regarding Value-Ordering Heuristics}

    \only<1>{
        \begin{enumerate}
            \item The total number of discrepancies to find a solution is usually low (our
                value-ordering heuristics are \emph{usually} right).
            \item Value-ordering heuristics are most likely to wrong higher up in the tree (there is
                least information available when no or few choices have been made).
        \end{enumerate}

        \vspace{1em}

        \begin{columns}[T]
            \column{.33\textwidth}
            \centering\includegraphics*[keepaspectratio=true,scale=0.18]{images/lds-paper.png}
            \column{.33\textwidth}
            \centering\includegraphics*[keepaspectratio=true,scale=0.18]{images/lds-claim1.png}
            \column{.33\textwidth}
            \centering\includegraphics*[keepaspectratio=true,scale=0.18]{images/lds-claim2.png}
        \end{columns}
    }

    \only<2>{
        \begin{center}
        \includegraphics*[keepaspectratio=true,scale=0.55]{images/lds-claim1.png}
        \end{center}
    }

    \only<3>{
        \begin{center}
        \includegraphics*[keepaspectratio=true,scale=0.55]{images/lds-claim2.png}
        \end{center}
    }

\end{frame}

\begin{frame}{Limited Discrepancy Search}

    \setbeamertemplate{itemize/enumerate body begin}{\footnotesize}
    \setbeamertemplate{itemize/enumerate subbody begin}{\scriptsize}

    \begin{columns}[T]
        \column{.6\textwidth}
        \begin{itemize}
            \item First, search with no discrepancies.
            \item Then search allowing one discrepancy.
                \begin{itemize}
                    \item First try one discrepancy at the top.
                    \item Then try one discrepancy at the second level.
                    \item Then try one discrepancy at the third level.
                    \item \ldots
                \end{itemize}
            \item Then search allowing two discrepancies.
                \begin{itemize}
                    \item At the top, and at the second level.
                    \item Then at the top, and at the third level.
                    \item \ldots
                    \item Then at the second level and the third level.
                    \item \ldots
                \end{itemize}
            \item \ldots
        \end{itemize}

        \column{.4\textwidth}
        \centering\includegraphics*[keepaspectratio=true,scale=0.18]{images/lds-tree.png}
    \end{columns}

\end{frame}

\begin{frame}{Completeness}
    \begin{columns}
        \column{.75\textwidth}
        \begin{itemize}
            \item Complete: yes means yes, no means no.
            \item Incomplete: yes means yes, no means maybe.
            \item LDS is \emph{quasi-complete}: if the total number of discrepancies is allowed to go
                high enough, it is complete.
        \end{itemize}
        \column{.25\textwidth}
        \centering\includegraphics*[keepaspectratio=true,scale=0.4]{images/quasi.jpg}
    \end{columns}
\end{frame}

\begin{frame}{What About Non-Binary Trees?}
    \centering\includegraphics*[keepaspectratio=true,scale=0.4]{images/lds-binary.png}

    \vspace{1em}

    \begin{itemize}
        \item We can rewrite our search tree to be binary. Instead of branching on each value for a
            variable in a loop, pick a variable and a value, and branch twice:

            \begin{itemize}
                \item Yes, the variable takes that value.
                \item No, the variable does not take that value.
            \end{itemize}

        \item But this means that giving the 10th value to a variable counts as 9 discrepancies. Is
            this good or bad?
    \end{itemize}
\end{frame}

\begin{frame}{Improved Limited Discrepancy Search}

    \only<1>{
        \begin{itemize}
            \item LDS explores some parts of the search tree more than once.
            \item Improved Limited Discrepancy Search (ILDS) does less repeated work.
        \end{itemize}

        \begin{columns}[T]
            \column{.5\textwidth}
            \centering\includegraphics*[keepaspectratio=true,scale=0.4]{images/ilds-paper.png}
            \column{.5\textwidth}
            \centering\includegraphics*[keepaspectratio=true,scale=0.4]{images/ilds-claim.png}
        \end{columns}
    }

    \only<2>{
        \begin{center}
            \centering\includegraphics*[keepaspectratio=true,scale=0.6]{images/ilds-claim.png}
        \end{center}
    }
\end{frame}

\begin{frame}{Improved?}
    \begin{columns}
        \column{.5\textwidth}
        \centering\includegraphics*[keepaspectratio=true,scale=0.4]{images/ilds-paths.png}
        \column{.5\textwidth}
        \centering\includegraphics*[keepaspectratio=true,scale=0.18]{images/lds-tree.png}
    \end{columns}

\end{frame}

\begin{frame}{So is the Second Claim Important?}
    \centering\includegraphics*[keepaspectratio=true,scale=0.4]{images/ldsr-paper.png}

    \vspace{2em}

    \centering\includegraphics*[keepaspectratio=true,scale=0.4]{images/ldsr-conclusion.png}

    \vspace{0em}

\end{frame}

\begin{frame}{Is LDS Any Good?}
    \begin{center}
        \centering\includegraphics*[keepaspectratio=true,scale=0.3]{images/lds-car-sequencing.png}
    \end{center}
\end{frame}

\begin{frame}{Depth-Bounded Discrepancy Search}

    \only<1>{
        \begin{itemize}
            \item If the second claim \emph{is} important, why not emphasise it more?

            \item Depth-bounded discrepancy search considers $k$ discrepancies, but only at depth up
                to $k - 1$ (but in which order?).
        \end{itemize}

        \vspace{1em}

        \begin{columns}[T]
            \column{.33\textwidth}
            \centering\includegraphics*[keepaspectratio=true,scale=0.1]{images/dds-paper.png}
            \column{.33\textwidth}
            \centering\includegraphics*[keepaspectratio=true,scale=0.1]{images/dds-claim.png}
            \column{.33\textwidth}
            \centering\includegraphics*[keepaspectratio=true,scale=0.1]{images/dds-tree.png}
        \end{columns}
    }

    \only<2>{
        \begin{center}
            \centering\includegraphics*[keepaspectratio=true,scale=0.35]{images/dds-claim.png}
        \end{center}
    }

    \only<3>{
        \begin{center}
            \centering\includegraphics*[keepaspectratio=true,scale=0.35]{images/dds-tree.png}
        \end{center}
    }

\end{frame}

\begin{frame}{Is DDS Any Good?}
    \only<1>{
        \begin{center}
            \centering\includegraphics*[keepaspectratio=true,scale=0.3]{images/planning-title.png}
        \end{center}
        \begin{columns}[T]
            \column{.5\textwidth}
            \centering\includegraphics*[keepaspectratio=true,scale=0.3]{images/planning-abstract.png}
            \column{.5\textwidth}
            \centering\includegraphics*[keepaspectratio=true,scale=0.3]{images/planning-results.png}
        \end{columns}
    }

    \only<2>{
        \centering\includegraphics*[keepaspectratio=true,scale=0.6]{images/planning-abstract.png}
        \vspace{0em}
    }

    \only<3>{
        \centering\includegraphics*[keepaspectratio=true,scale=0.6]{images/lumberjack.jpg}
        \vspace{0em}
    }

    \only<4>{
        \centering\includegraphics*[keepaspectratio=true,scale=0.6]{images/planning-results.png}
        \vspace{0em}
    }
\end{frame}

\begin{frame}{What About Unsatisfiable Instances?}

    \only<2>{
        \begin{columns}[T]
            \column{.5\textwidth}
            \centering\includegraphics*[keepaspectratio=true,scale=0.2]{images/lds-unsat.png}
            \column{.5\textwidth}
            \centering\includegraphics*[keepaspectratio=true,scale=0.2]{images/dds-unsat.png}
        \end{columns}

        \vspace{2em}

        \centering\includegraphics*[keepaspectratio=true,scale=0.4]{images/ldsr-bt.png}
    }

\end{frame}

\begin{frame}{Better Stopping Conditions}

    \centering\includegraphics*[keepaspectratio=true,scale=0.2]{images/stopping-theorem.png}

    \vspace{2em}

    \centering\includegraphics*[keepaspectratio=true,scale=0.2]{images/stopping-result.png}

\end{frame}

\begin{frame}{But wait, there's more!}
    \begin{itemize}
        \item Interleaved Depth First Search
        \item Interleaved and Discrepancy Based Search
        \item Yet ImprovEd Limited Discrepancy Search
        \item Limited Discrepancy Beam Search
        \item Beam search Using Limited discrepancy Backtracking
        \item Probing and restarting
        \item \ldots
    \end{itemize}
\end{frame}

\begin{frame}{What About Optimisation Problems?}
    \begin{itemize}
        \item Discrepancy-Bounded Depth First Search
        \item Climbing Depth-Bounded Adjacent Discrepancy Search
        \item Branch and Bound (in Algorithmics 4)
        \item Russian Doll Search (FATA, 4pm on 2nd Dec, SAWB423)
        \item Dichotomic Search
        \item \ldots
    \end{itemize}
\end{frame}

\begin{frame}{Using LDS?}
    \begin{center}
        \includegraphics*[keepaspectratio=true,scale=0.2]{images/lds-patent.png}
    \end{center}
\end{frame}

\newsavebox{\mycodeboxa}
\newsavebox{\mycodeboxb}

\begin{lrbox}{\mycodeboxa}
    \tiny\ttfamily
\begin{lstlisting}
public boolean lds(DecisionVar[] v, int kMax,
        boolean lateDiscrepancies) throws ContradictionException
{
    boolean consistent = true;
    int n = v.length;
    inst = new int[n];
    nodes = 0;
    worldPush();
    try {
        super.propagate();
    }
    catch (ContradictionException e) {
        consistent = false;
    }
    if (consistent) {
        consistent = false;
        for (int k = 0 ; k <= kMax && !consistent ; k++) {
            worldPush();
            consistent = ldsProbe(v, n, k, 0, lateDiscrepancies);
            worldPop();
        }
    }
    worldPop();
    if (consistent)
        for (int i = 0 ; i < n ; i++) v[i].setVal(inst[i]);
    return consistent;
}
\end{lstlisting}
\end{lrbox}

\begin{lrbox}{\mycodeboxb}
    \tiny\ttfamily
\begin{lstlisting}
private boolean ldsProbe(DecisionVar[] v, int n, int k, int i,
        boolean lateDiscrepancies) throws ContradictionException
{
    if (i == n) return true;   // all vars instantiated
    DecVarEnumeration dve = new DecVarEnumeration(v[i]);
    boolean result = false;
    int m  = v[i].getDomainSize();
    int x  = dve.getNextValue();
    int pd = getPotentialDiscrepancies(v, n, i + 1);
    if (lateDiscrepancies && k <= pd && ! result) {
        worldPush();
        result = isConsistent(v, i, x) && ldsProbe(v, n, k, i + 1, lateDiscrepancies);
        worldPop();
    }
    for (int j = 1 ; j < m && j <= k && ! result ; j++) {
        int y = dve.getNextValue();
        worldPush();
        if (isConsistent(v, i, y))
            result = ldsProbe(v, n, k - j, i + 1, lateDiscrepancies);
        worldPop();
    }
    if (! lateDiscrepancies && k <= pd && ! result) {
        worldPush();
        result = isConsistent(v, i, x) && ldsProbe(v, n, k, i + 1, lateDiscrepancies);
        worldPop();
    }
    return result;
}
\end{lstlisting}
\end{lrbox}

\begin{frame}{Writing Our Own Search in Old Choco}
    \only<1>{\usebox{\mycodeboxa}}
    \only<2>{\usebox{\mycodeboxb}}
\end{frame}

\begin{frame}{Writing Our Own Search in the Shiny New Choco 3}
    \only<1>{
        \begin{itemize}
            \item Easy in Choco 3 due to more abstraction: it's an example in the manual. (But is
                this LDS, ILDS, or something else?)
            \item We still have to write code\ldots
        \end{itemize}

        \begin{columns}[T]
            \column{.5\textwidth}
            \centering\includegraphics*[keepaspectratio=true,scale=0.3]{images/lds-choco3-col1.png}
            \column{.5\textwidth}
            \centering\includegraphics*[keepaspectratio=true,scale=0.3]{images/lds-choco3-col2.png}
        \end{columns}
    }

    \only<2>{
        \begin{center}
            \includegraphics*[keepaspectratio=true,scale=0.5]{images/lds-choco3-col1.png}
        \end{center}
    }
\end{frame}

\begin{frame}{Search Combinators?}
    \only<1>{
        \begin{columns}[T]
            \column{.5\textwidth}
            \centering\includegraphics*[keepaspectratio=true,scale=0.12]{images/sc-title.png}
            \vspace{1em}
            \centering\includegraphics*[keepaspectratio=true,scale=0.27]{images/sc-primitives.png}

            \column{.5\textwidth}
            \centering\includegraphics*[keepaspectratio=true,scale=0.25]{images/sc-contributions.png}
            \vspace{1em}
            \centering\includegraphics*[keepaspectratio=true,scale=0.25]{images/sc-se.png}
            \vspace{1em}
            \centering\includegraphics*[keepaspectratio=true,scale=0.25]{images/sc-lds.png}
            \vspace{1em}
            \centering\includegraphics*[keepaspectratio=true,scale=0.25]{images/sc-monads.png}
        \end{columns}
    }

    \only<2->{
        \begin{center}
            \includegraphics*<2>[keepaspectratio=true,scale=0.5]{images/sc-contributions.png}
            \includegraphics*<3>[keepaspectratio=true,scale=0.5]{images/sc-se.png}
            \includegraphics*<4>[keepaspectratio=true,scale=0.5]{images/sc-lds.png}
            \includegraphics*<5>[keepaspectratio=true,scale=0.5]{images/sc-monads.png}
        \end{center}
    }
\end{frame}

\begin{frame}[b]
    \vfill
    \begin{center}
    \url{http://dcs.gla.ac.uk/~ciaran} \\
    \href{mailto:c.mccreesh.1@research.gla.ac.uk}{\nolinkurl{c.mccreesh.1@research.gla.ac.uk}}
\end{center}
\begin{tikzpicture}[remember picture, overlay]
    \node at (current page.north west) {\begin{tikzpicture}[remember picture, overlay]\fill
    [fill=uofgblue, anchor=north west] (0, 0) rectangle (\paperwidth, -1.5cm);\end{tikzpicture}};
    \node [anchor=north west, shift={(0.2cm,-0.2cm)}] at (current page.north west) {\includegraphics*[keepaspectratio=true,scale=0.5]{UoG_keyline.eps}};
\end{tikzpicture}
\end{frame}

\end{document}