<commit_before>\documentclass{beamer}

\usetheme{Antibes}
\usepackage{verbatim}
\usecolortheme[RGB={120,0,0}]{structure}
\setbeamertemplate{blocks}[rounded][shadow=true]
\usepackage[utf8]{inputenc}

\usepackage{algorithm}
\usepackage[noend]{algpseudocode}

\beamertemplateballitem
% To number the references.
\setbeamertemplate{bibliography item}{\insertbiblabel}

\begin{document}

\title{UKP5: a New Algorithm for the Unbounded Knapsack Problem}
\author{<NAME>\footnote{Universidade Federal do Rio Grande do Sul, Brazil\label{ft:ufrgs}} and <NAME>\textsuperscript{\ref{ft:ufrgs}}\\
15th International Symposium on Experimental Algorithms\\
(SEA 2016)
}
\logo{\includegraphics[scale=0.3]{inf}}
\date{Wednesday, June 8}

\frame{\titlepage}

\frame{\frametitle{Outline}\tableofcontents}

\section{Introduction}
\frame{\frametitle{What is UKP?}
\begin{itemize}
%\setlength\itemsep{1.5em}
%\item UKP is an acronym for Unbounded Knapsack Problem.
\item Very similar to BKP or 0-1 KP.
\begin{itemize}
\item But with an ``unbounded'' quantity of each item available.
\end{itemize}
\end{itemize}
\large
\begin{align}
  maximize &\sum_{i=1}^n p_i x_i\label{eq:objfun}\\
subject~to &\sum_{i=1}^n w_i x_i \leq c\label{eq:capcons}\\
            &x_i \in \mathbb{N}_0\label{eq:x_integer}
\end{align}
\normalsize
\begin{itemize}
\vspace{-7mm}
\item Subproblem of the column generation technique applied to the Cutting Stock Problem or the Bin Packing Problem.
\end{itemize}
}

%\frame{\frametitle{UKP Model}
%\LARGE
%\begin{align}
%  maximize &\sum_{i=1}^n p_i x_i\label{eq:objfun}\\
%subject~to &\sum_{i=1}^n w_i x_i \leq c\label{eq:capcons}\\
%            &x_i \in \mathbb{N}_0\label{eq:x_integer}
%\end{align}
%}

\section{Prior Work}
\frame{\frametitle{Methods on Solving UKP}
\begin{beamerboxesrounded}[shadow=true]{Dynamic Programming (DP)}
Strong correlation between variables \textbf{n} \& \textbf{c} and the time to solve.\\

\small
Ex.: Garfinkel\cite{gar72},  <NAME>\cite{tchu}, G\&G\cite{gg66}, Greenberg \& Feldman\cite{greenberg_improved_ukp5}, Greenberg\cite{greenberg_2}, EDUK\cite{eduk}.
\end{beamerboxesrounded}	
\vspace{2mm}
\begin{beamerboxesrounded}[shadow=true]{Branch and Bound (B\&B)}
Strong correlation between instance's distribution and time to solve.\\

\small
Ex.: G\&G\cite{gg63-bb}, MTU1\cite{mtu1}, MTU2\cite{mtu2}.
\end{beamerboxesrounded}	
}

\frame{\frametitle{EDUK2/PYAsUKP (State-of-art)}
\begin{beamerboxesrounded}[shadow=true]{Knapsack Problems, 2004}
``EDUK [...] seems to be the most efficient dynamic programming based method available at the moment.''\cite[p. 223]{knapsackproblems2004}
\end{beamerboxesrounded}
\begin{itemize}
\item EDUK2 is the algorithm, PYAsUKP is the only known implementation (OCaml). %(As the algorithm uses many functional concepts the authors found that it would be so much easier to implement the algorithm on a functional language. Even if c++ is the de facto language for scientific computing.)
\item \textbf{Hybrid Approach}: Tries to solve by B\&B, if it fails to solve quickly with B\&B, then switches to DP. %(Only hybrid method known.)
\end{itemize}
}

\frame{\frametitle{Symmetry Pruning}
\begin{itemize}
\item Solutions are symmetric when they are represented differently, but are equivalent.
\item For example: \(\{ 2, 1, 3, 1 \} \equiv \{ 3, 2, 1, 1 \}\)
\item Symmetry Pruning is to avoid the costs of finding the same solution by many different paths.
\end{itemize}
}

\frame{\frametitle{Sparsity}
\begin{itemize}
\item Naive DP algorithms solve the UKP for every capacity in~\([1,c]\) (or \([w_{min},c]\)).
\item Ex.: for the weights 7, 10, 5; no solution will have weight exactly: 6, 8, 9, 11, 13, 16, ...
\item The optimal solution for those capacities will be the optimal solution already found for a previous capacity.
\end{itemize}
}

\frame{\frametitle{Dominated Solutions Pruning}
\begin{itemize}
\item If \(w_s \leq w_t\) and \(p_s > p_t\) then \(s\) dominates \(t\).
\item Follows that \(s \cup \{i\}\) will dominate \(t \cup \{i\}\) for any item \(i\).
\item Therefore, we can create new solutions only from~\(s\) and ignore~\(t\).
\end{itemize}
}

\frame{\frametitle{Time/Memory Tradeoff}
\begin{itemize}
\item On many instances, 99\% of the UKP5 time is used on the inner ``for'' of a double loop.
\item Testing if the item weight is within the array boundaries is inside this ``for''.
\item This test can be removed if we use \(w_max\) extra memory.
\end{itemize}<commit_msg>Improvements on SEA 2016 slides. Added Tikz diagrams.<commit_after>\documentclass{beamer}

\usetheme{Antibes}
\usepackage{verbatim}
\usecolortheme[RGB={120,0,0}]{structure}
\setbeamertemplate{blocks}[rounded][shadow=true]
\usepackage[utf8]{inputenc}

\usepackage{algorithm}
\usepackage[noend]{algpseudocode}

\beamertemplateballitem
% To number the references.
\setbeamertemplate{bibliography item}{\insertbiblabel}

\usepackage{tikz}
\newcommand{\drawhvector}[5]{
	\edef \origin {#1}
	\edef \xmax {#2}
	\edef \rs {(#3,#4)}
	\edef \scale {#5}
	\foreach \x in {0,...,\xmax}{
		\draw [shift={\origin}] (\x,0) rectangle +\rs;
		\node [scale=\scale, shift={\origin}, font=\LARGE] at (\x + 0.5, 0.5) {\(\x\)};
	}
}

\newcommand{\drawhvectornotext}[5]{
	\edef \origin {#1}
	\edef \xmax {#2}
	\edef \rs {(#3,#4)}
	\edef \scale {#5}
	\foreach \x in {0,...,\xmax}{
		\draw [shift={\origin}] (\x,0) rectangle +\rs;
		%\node [scale=\scale, shift={\origin}, font=\LARGE] at (\x + 0.5, 0.5) {\(\x\)};
	}
}

\begin{document}

\title{UKP5: a New Algorithm for the Unbounded Knapsack Problem}
\author{<NAME>\footnote{Universidade Federal do Rio Grande do Sul, Brazil\label{ft:ufrgs}} and <NAME>\textsuperscript{\ref{ft:ufrgs}}\\
15th International Symposium on Experimental Algorithms\\
(SEA 2016)
}
\logo{\includegraphics[scale=0.3]{inf}}
\date{Wednesday, June 8}

\frame{\titlepage}

\frame{\frametitle{Outline}\tableofcontents}

\section{Introduction}
\frame{\frametitle{What is UKP?}
\begin{itemize}
%\setlength\itemsep{1.5em}
%\item UKP is an acronym for Unbounded Knapsack Problem.
\item Very similar to BKP or 0-1 KP.
\begin{itemize}
\item But with an ``unbounded'' quantity of each item available.
\end{itemize}
\end{itemize}
\large
\begin{align}
  maximize &\sum_{i=1}^n p_i x_i\label{eq:objfun}\\
subject~to &\sum_{i=1}^n w_i x_i \leq c\label{eq:capcons}\\
            &x_i \in \mathbb{N}_0\label{eq:x_integer}
\end{align}
\normalsize
\begin{itemize}
\vspace{-7mm}
\item Subproblem of the column generation technique applied to the Cutting Stock Problem or the Bin Packing Problem.
\end{itemize}
}

%\frame{\frametitle{UKP Model}
%\LARGE
%\begin{align}
%  maximize &\sum_{i=1}^n p_i x_i\label{eq:objfun}\\
%subject~to &\sum_{i=1}^n w_i x_i \leq c\label{eq:capcons}\\
%            &x_i \in \mathbb{N}_0\label{eq:x_integer}
%\end{align}
%}

\section{Prior Work}
\frame{\frametitle{Methods on Solving UKP}
\begin{beamerboxesrounded}[shadow=true]{Dynamic Programming (DP)}
Strong correlation between variables \textbf{n} \& \textbf{c} and the time to solve.\\

\small
Ex.: Garfinkel\cite{gar72},  <NAME>\cite{tchu}, G\&G\cite{gg66}, Greenberg \& Feldman\cite{greenberg_improved_ukp5}, Greenberg\cite{greenberg_2}, EDUK\cite{eduk}.
\end{beamerboxesrounded}	
\vspace{2mm}
\begin{beamerboxesrounded}[shadow=true]{Branch and Bound (B\&B)}
Strong correlation between instance's distribution and time to solve.\\

\small
Ex.: G\&G\cite{gg63-bb}, MTU1\cite{mtu1}, MTU2\cite{mtu2}.
\end{beamerboxesrounded}	
}

\frame{\frametitle{EDUK2/PYAsUKP (State-of-art)}
\begin{beamerboxesrounded}[shadow=true]{Knapsack Problems, 2004}
``EDUK [...] seems to be the most efficient dynamic programming based method available at the moment.''\cite[p. 223]{knapsackproblems2004}
\end{beamerboxesrounded}
\begin{itemize}
\item EDUK2 is the algorithm, PYAsUKP is the only known implementation (OCaml). %(As the algorithm uses many functional concepts the authors found that it would be so much easier to implement the algorithm on a functional language. Even if c++ is the de facto language for scientific computing.)
\item \textbf{Hybrid Approach}: Tries to solve by B\&B, if it fails to solve quickly with B\&B, then switches to DP. %(Only hybrid method known.)
\end{itemize}
}

\frame{\frametitle{Symmetry Pruning}
\begin{itemize}
\item Solutions are symmetric when they are equivalent, but generated or represented in different ways.
\item For example: \(\{ 5, 4, 6 \} \equiv \{ 6, 5, 4 \}\)
\item Symmetry Pruning is to avoid the costs of finding the same solution by many different paths.
\end{itemize}

\center
\edef \scale {0.5}
\begin{tikzpicture}[scale=\scale]

\edef \rx {1}
\edef \ry {1}

\edef \origin {(6,5)}
\drawhvector{\origin}{15}{\rx}{\ry}{\scale}

\draw[dashed, ultra thick] ++\origin +(0.5, 1) to [out=45,in=135] +(4.5, 1);
\draw[dashed, ultra thick] ++\origin +(0.5, 1) to [out=45,in=135] +(5.5, 1);
\draw[dashed, ultra thick] ++\origin +(0.5, 1) to [out=45,in=135] +(6.5, 1);

\draw[dashed, thick] ++\origin +(4.5, 0) to [out=315,in=225] +(9.5, 0);
\draw[dashed, thick] ++\origin +(4.5, 0) to [out=315,in=225] +(10.5, 0);

\draw[dashed, thick] ++\origin +(5.5, 0) to [out=315,in=225] +(9.5, 0);
\draw[dashed, thick] ++\origin +(5.5, 0) to [out=315,in=225] +(11.5, 0);

\draw[dashed, thick] ++\origin +(6.5, 0) to [out=315,in=225] +(10.5, 0);
\draw[dashed, thick] ++\origin +(6.5, 0) to [out=315,in=225] +(11.5, 0);

\draw[dashed] ++\origin +(9.5, 1) to [out=45,in=135] +(15.5, 1);
\draw[dashed] ++\origin +(10.5, 1) to [out=45,in=135] +(15.5, 1);
\draw[dashed] ++\origin +(11.5, 1) to [out=45,in=135] +(15.5, 1);

\def \origin {(6,1.5)}
\drawhvector{\origin}{15}{\rx}{\ry}{\scale}

\draw[dashed, ultra thick] ++\origin +(0.5, 1) to [out=45,in=135] +(4.5, 1);
\draw[dashed, ultra thick] ++\origin +(0.5, 1) to [out=45,in=135] +(5.5, 1);
\draw[dashed, ultra thick] ++\origin +(0.5, 1) to [out=45,in=135] +(6.5, 1);

\draw[dashed, thick] ++\origin +(5.5, 0) to [out=315,in=225] +(9.5, 0);

\draw[dashed, thick] ++\origin +(6.5, 0) to [out=315,in=225] +(10.5, 0);
\draw[dashed, thick] ++\origin +(6.5, 0) to [out=315,in=225] +(11.5, 0);

\draw[dashed] ++\origin +(11.5, 1) to [out=45,in=135] +(15.5, 1);

\end{tikzpicture}
}

\frame{\frametitle{Sparsity}
\begin{itemize}
\item Not every subproblem of capacity \([1,c-1]\) has to be solved.
%Naive DP algorithms solve the UKP for every capacity in~\([1,c]\) (or \([w_{min},c]\)).
\item Ex.: for the weights 7, 10, 5; no solution will weight exactly: 1-4, 6, 8, 9, 11, 13, 16, 18, 23 ...
\item The optimal solution for those capacities will be the optimal solution already found for a previous capacity.
\end{itemize}
\center
\edef \scale {0.5}
\begin{tikzpicture}[scale=\scale]

\edef \rx {1}
\edef \ry {1}

\def \origin {(0,0)}
\drawhvectornotext{\origin}{20}{\rx}{\ry}{\scale}
\node [scale=\scale, shift={\origin}, font=\LARGE] at (0.5, 0.5) {\(0\)};

\draw[dashed, thick] ++\origin +(0.5, 1) to [out=45,in=135] +(5.5, 1);
\node [scale=\scale, shift={\origin}, font=\LARGE] at (5.5, 0.5) {\(5\)};

\draw[dashed, thick] ++\origin +(0.5, 1) to [out=45,in=135] +(7.5, 1);
\node [scale=\scale, shift={\origin}, font=\LARGE] at (7.5, 0.5) {\(7\)};

\draw[dashed, thick] ++\origin +(0.5, 1) to [out=45,in=135] +(10.5, 1);
\node [scale=\scale, shift={\origin}, font=\LARGE] at (10.5, 0.5) {\(10\)};

\draw[dashed, thick] ++\origin +(5.5, 0) to [out=315,in=225] +(12.5, 0);
\node [scale=\scale, shift={\origin}, font=\LARGE] at (12.5, 0.5) {\(12\)};
\draw[dashed, thick] ++\origin +(7.5, 0) to [out=315,in=225] +(14.5, 0);
\node [scale=\scale, shift={\origin}, font=\LARGE] at (14.5, 0.5) {\(14\)};
\draw[dashed, thick] ++\origin +(7.5, 0) to [out=315,in=225] +(17.5, 0);
\node [scale=\scale, shift={\origin}, font=\LARGE] at (17.5, 0.5) {\(17\)};

\draw[dashed, thick] ++\origin +(10.5, 0) to [out=315,in=225] +(20.5, 0);
\node [scale=\scale, shift={\origin}, font=\LARGE] at (20.5, 0.5) {\(20\)};

\draw[dashed, thick] ++\origin +(5.5, 0) to [out=315,in=225] +(15.5, 0);
\node [scale=\scale, shift={\origin}, font=\LARGE] at (15.5, 0.5) {\(15\)};

\draw[dashed, thick] ++\origin +(12.5, 1) to [out=45,in=135] +(19.5, 1);
\node [scale=\scale, shift={\origin}, font=\LARGE] at (19.5, 0.5) {\(19\)};

\end{tikzpicture}
}

\frame{\frametitle{Dominated Solutions Pruning}
\begin{itemize}
\item If \(w_s \leq w_t\) and \(p_s > p_t\) then \(s\) dominates \(t\).
\item Follows that \(s \cup \{i\}\) will dominate \(t \cup \{i\}\) for any item \(i\).
\item Therefore, we can create new solutions only from~\(s\) and ignore~\(t\).
\end{itemize}
}

\frame{\frametitle{Time/Memory Tradeoff}
\begin{itemize}
\item On many instances, 99\% of the UKP5 time is used on the inner ``for'' of a double loop.
\item Testing if the item weight is within the array boundaries is inside this ``for''.
\item This test can be removed if we use \(w_{max}\) extra memory.
\end{itemize}
{'fraction_non_alphanumeric': 0.19166991047100038, 'fraction_numerical': 0.048189957181782796, 'mean_word_length': 4.438611346316681, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2751343', 'n_tokens_mistral': 5424, 'n_tokens_neox': 4934, 'n_words': 1410}