text:
\documentclass[12pt]{article}

\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{hyperref}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage[many]{tcolorbox}
\tcbuselibrary{listings}
\usepackage{listings}

\usepackage{float}
\definecolor{lg}{HTML}{f0f0f0}

\newtcblisting{pycode}{
    colback=lg,
    boxrule=0pt,
    arc=0pt,
    outer arc=0pt,
    top=0pt,
    bottom=0pt,
    colframe=white,
    listing only,
    left=15.5pt,
    enhanced,
    listing options={
        basicstyle=\small\ttfamily,
        keywordstyle=\color{blue},
        language=Python,
        showstringspaces=false,
        tabsize=2,
        numbers=left,
        breaklines=true
    },
    overlay={
        \fill[gray!30]
        ([xshift=-3pt]frame.south west)
        rectangle
        ([xshift=11.5pt]frame.north west);
    }
}

\lstset{
    language=Python,
    basicstyle=\small\ttfamily,
}

\begin{document}

\title{Exercise 1}
\author{Cristian Manuel Abrante Dorta - 888248\\
ELEC-E8125 - Reinforcement Learning}

\maketitle
\section{Reward functions}
\label{sec:reward-functions}

\subsection{Task 1}
\label{sec:task-1}
\textbf {
    Train a model with 200 time steps per episode. Then test the model for 500 time steps.
}\\

For answering this question, first of all, the model had to be trained during 500 episodes with a maximum of 200 time steps per episode. After the agent is trained with those parameters a plot was generated in order to know the performance of the agent over the episodes:

\begin{figure}[ht]
    \centering
    \includegraphics[scale=0.5]{exercise-1/report/img/task-1-training-200.png}
    \caption{Training result with 500 episodes and 200 max time steps per episode.}
    \label{fig:training-200}
\end{figure}

It is important to know that this is not a deterministic process, and that implies that the content of this plot is not the only possible training that the agent could have. But, as we can see in figure \ref{fig:training-200} the cumulative reward (equivalent to the maximum number of time steps that the pole was balanced), is increasing over the training episodes. Obtaining the maximum reward in some intervals between episodes 100 and 400. Also, the average reward has an increasing tendency over all the episodes except for the final 100 episodes. \\

After having trained the model, it was tested with a maximum of 500 timesteps per episode, and the obtained result was:

\begin{center}
    \texttt{Average test reward: 161.644 episode length: 161.644}
\end{center}

As we can see in this case, the agent did not generalized well, having an average test performance even worst than the parameter established for training which was 200 timesteps.

\subsection{Question 1.1}
\label{sec:question-1.1}
\textbf {
    Can the same model, trained to balance for 200 timesteps, also balance the pole for 500 timesteps? Briefily justify your answers.
}\\

The general answer to this question would be: yes it can. First of all, when the number of maximum time steps is increased, the main change is that the evaluation of the environment (in this case performed by \texttt{gym} using \texttt{env.step()}), is not going to consider the episode finalized (setting the \texttt{done} boolean variable to \texttt{true}) until the execution reaches 500 steps, or the pole falls.\\

So, as we previously trained the agent to balance the pole for 200 timesteps, theoretically it could continue doing it for more steps if it has generalized well during the training period. In practice, that is not happening in all the cases, mainly due to two reasons: On the one hand, the model is trained with 500 episodes, which could maybe not be enough for the generalization task, we can see that in Figure \ref{fig:training-200} where the variance between the average reward and some executions is really important. On the other hand, we have the maximum 200 train steps, which maybe is not enough too, we can see that also in the result of the test with 500 steps, which had as, a result, an average reward of 161.644. This result was even less than the 200 steps with which it was trained.

\subsection{Task 2}
\label{sec:task-2}
\textbf {
    Repeat the experiment a few times, each time training the model from scratch with 200 time steps and testing it for 500 time steps.
}\\

The experiment was executed five different times from scratch, obtaining the corresponding training plots:

\begin{figure}[H]
   \begin{minipage}{0.32\textwidth}
     \centering
     \includegraphics[width=\linewidth]{exercise-1/report/img/task-2-v1.png}
     \caption{First execution}
     \label{fig:task-2-v1}
   \end{minipage}\hfill
   \begin{minipage}{0.32\textwidth}
     \centering
     \includegraphics[width=\linewidth]{exercise-1/report/img/task-2-v2.png}
     \caption{Second execution}
     \label{fig:task-2-v2}
   \end{minipage}
   \begin{minipage}{0.32\textwidth}
     \centering
     \includegraphics[width=\linewidth]{exercise-1/report/img/task-2-v3.png}
     \caption{Third execution}
     \label{fig:task-2-v3}
   \end{minipage}
\end{figure}

\begin{figure}[ht]
    \centering
   \begin{minipage}{0.48\textwidth}
     \centering
     \includegraphics[width=0.68\linewidth]{exercise-1/report/img/task-2-v4.png}
     \caption{Fourth execution}
     \label{fig:task-2-v4}
   \end{minipage}\hfill
   \begin{minipage}{0.48\textwidth}
     \centering
     \includegraphics[width=0.68\linewidth]{exercise-1/report/img/task-2-v5.png}
     \caption{Fifth execution}
     \label{fig:task-2-v5}
   \end{minipage}
\end{figure}

Apart from the training plots, in the test phase, using 500 timesteps, we have obtained the following results stated in Table \ref{ref:rewards-table}.

\begin{table}[h]
\centering
\begin{tabular}{l|ccc}

\multicolumn{1}{l|}{Execution} & Figure                                      & \multicolumn{1}{l}{Average test reward} & \multicolumn{1}{l}{Episode length} \\ \hline
1                               & Figure \ref{fig:task-2-v1} & 497.632                                  & 497.632                             \\
2                               & Figure \ref{fig:task-2-v2} & 181.372                                  & 181.372                             \\
3                               & Figure \ref{fig:task-2-v3} & 138.476                                  & 138.476                             \\
4                               & Figure \ref{fig:task-2-v4} & 236.846                                  & 236.846                             \\
5                               & Figure \ref{fig:task-2-v5} & 299.016                                  & 299.016
\end{tabular}
\caption{Obtained rewards for the different executions}
\label{ref:rewards-table}
\end{table}

\subsection{Question 1.2}
\label{sec:question-1.2}
\textbf {
    Are the behavior and performance of the trained model the same every time? Analyze the causes briefly
}\\

As it was described in the previous section \ref{sec:question-1.1}, the system could achieve a better result than the 200 reward points that it was trained with, proof of that is the first execution, which achieved an average test reward of 497.632, which is almost the best possible reward that can be obtained. Apart from this execution, there have been others which has surpassed the barrier of the 200 reward points, such as the fifth and the sixth execution.

It is remarkable to say that the behavior of the agent is not deterministic in any sense because the initial state is random each time the environment is initialized (when the episode ends), so the training has a different evolution each time that it is executed. The same happens with the test phase, that it is almost the same as the training phase but without the update of the outcome of the agent. \\

If we evaluate the performance in the graphic mode, we can do different observations. First of all, the trained agent learns to balance the pole even going to one side or the other, and that depends on the execution. Then, we can also observe that the agent learns to take advantage of the time and move from the border of the screen to finalize the episode in the established maximum time, in order to maximize the reward. Another relevant aspect is that the agent always follows a predefined direction (either goes left or right) and never changes the direction, even though this change could lead to more promising results (Figure \ref{fig:task-2-left} and Figure \ref{fig:task-2-right}).

\begin{figure}[ht]
    \centering
   \begin{minipage}{0.48\textwidth}
     \centering
     \includegraphics[width=0.7\linewidth]{exercise-1/report/img/task-2-left.png}
     \caption{Execution where the agent balanced the pole going to the left.}
     \label{fig:task-2-left}
   \end{minipage}\hfill
   \begin{minipage}{0.48\textwidth}
     \centering
     \includegraphics[width=0.7\linewidth]{exercise-1/report/img/task-2-right.png}
     \caption{Execution where the agent balanced the pole going to the right.}
     \label{fig:task-2-right}
   \end{minipage}
\end{figure}

\section{Repeatibility}
\label{sec:repeatibility}

\subsection{Question 2}
\label{sec:question-2}
\textbf {
    Why is this the case? What are the implications of this stochasticity, when it comes to comparing reinforcement learning algorithms to each other? Please explain.
}\\

In contrast to what happens in supervised methods of machine learning, in reinforcement learning the inputs that the intelligent system received are previously unknown, having only the capacity of observing some inputs that are initialized randomly and that are changed based on the effect that the actions taken by the agent produce. \\

\begin{figure}[H]
	\centering
    \includegraphics[width=0.6\columnwidth]{img/training.pdf}
	\caption{Execution of 100 independent trainings.}
	\label{question-2:fig}
\end{figure}

We can observe in figure \ref{question-2:fig} that even though there are many executions, the variety of the rewards obtained by different agents in those executions differ in a significant way between them. This is caused by the quantity of randomness that is present in the environment, not only with the initialization but also in how the model behaves (intelligent systems based on neural networks introduce an inevitable amount of randomness).\\

Having an agent trained in such as random environment inevitably creates difficulties for them in generalizing the underlying pattern, so the only way to evaluate the performance of those systems is the reward function, which varies drastically in different episodes. \\

As it was stated in \cite{nagendra2017comparison}, when we want to compare different reinforcement learning algorithms, it is difficult to know exactly which is going to be the convergence point, where we could distinguish which noise is produced by the environment and which is produced by the results of the algorithm.

\section{Reward functions}
\label{sec:reward-functions}

\subsection{Task 2}
\label{sec:reward-task-2}
\textbf {
    Write different reward functions to incentive the agent to learn the following behaviors:
}\\

\subsubsection{Balance the pole close to the center of the screen (close to $x = 0$)}
\label{sec:center}

Solving this question is equivalent to solve what is asked in section \ref{sec:center-point}, but for the specific case of $x=0$. For doing that, we have to design the reward function that could guide the position of the agent to the desired point. For doing that the approach followed could be better described with this diagram:

\begin{figure}[h]
    \centering
    \includegraphics[scale=0.6]{exercise-1/report/img/diagrams/reward-diagram.png}
    \caption{Diagram of the reward given the position}
    \label{fig:reward}
\end{figure}

This diagram express the model that the reward will follow. When the actual position of the pole is in the interval specified between the desired point ($x_0$), and a threshold (denominated as $\epsilon$), we are going to return the maximum possible reward ($+1$). Then, when the position is in the interval between the lower bound and the beginning of the central interval, or between the end of the central interval and the upper bound, the reward is going to be obtained from the liner function proportionally specified between $0$ in the bounds and $0.75$ in the beginning of the central interval. \\

Calculating the equations of those intervals is easy, because they are simply the equation of the straight line that connects two different points, different from each interval (left and right). Those are the following equations:

\begin{minipage}{0.48\textwidth}
 \begin{center}
    \begin{equation}
         r = \frac{r_{max} \cdot (x - l)}{x_0-\epsilon-l}
    \end{equation}
 \end{center}
\end{minipage}\hfill
\begin{minipage}{0.48\textwidth}
\begin{center}
    \begin{equation}
        r = \frac{r_{max} \cdot (-x + h)}{h-(x_0 - \epsilon)}
    \end{equation}
 \end{center}
\end{minipage}
\\

It is important to mention that the parameter $r_{max}$ is the maximum reward obtained in the bounds of the central interval, in our case, this value was set to $r_{max} = 0.75$. Also, the value of $\epsilon$ established was $\epsilon=0.1$\\

This equations, should be translated to code, for this purpose, the following function was created:

\begin{pycode}
lower_bound = -1.5
higher_bound = +1.5
eps = 0.1
max_reward = 0.75

def proportional_reward(state, x0):
    x = state[0]

    if (x0 - eps) <= x <= (x0 + eps):
        return 1
    elif lower_bound <= x < (x0 - eps):
        denominator = x0 - eps - lower_bound
        return (max_reward / denominator) * x - ((max_reward * lower_bound) / denominator)
    elif (x0 + eps) < x <= higher_bound:
        denominator = higher_bound - (x0 + eps)
        return (-max_reward / denominator) * x + ((max_reward * higher_bound) / denominator)
    else:
        return 0
\end{pycode}

After have explained how the reward function was designed, we have to analyze the case of $x_0 = 0$, which is equivalent to center the pole in the screen. The training of this model was done using 500 timesteps in 1000 episodes, obtaining the following plot of the rewards:

\begin{figure}[h]
    \centering
    \includegraphics[scale=0.45]{exercise-1/report/img/rewards/center-0-500t-1000e-proportion.png}
    \caption{Reward function of the centering}
    \label{fig:rewards-1}
\end{figure}

The correspondent model obtained in this execution is \texttt{center-0-500t-1000e-proportional.ai}.

\subsubsection{Balance the pole in an arbitrary point of the screen ($x = x_0$), with $x_0$ passed as a command line argument
to the script.}
\label{sec:center-point}

The function designed for this question was already explained in section \ref{sec:center}. In this case, two different models were trained, the first one for center the model in $x = -1$ and the other for centering the model in $x=+1$. As in the previous section, both models were trained with 500 timesteps and 1000 episodes, obtaining the following plots of the rewards:

\begin{figure}[ht]
    \centering
   \begin{minipage}{0.48\textwidth}
     \centering
     \includegraphics[width=0.7\linewidth]{exercise-1/report/img/rewards/center--1-500t-1000e-proportional.png}
     \caption{Reward plot for the model when $x=-1$}
     \label{fig:reard-1}
   \end{minipage}\hfill
   \begin{minipage}{0.48\textwidth}
     \centering
     \includegraphics[width=0.7\linewidth]{exercise-1/report/img/rewards/center-1-500t-1000e.png}
     \caption{Reward plot for the model when $x=+1$}
     \label{fig:task-2-right}
   \end{minipage}
\end{figure}

As we can see, in both graphs, the average reward increases over time, following a period of stabilization in the final episodes of the training. The corresponding model files are: \texttt{center--1-500t-1000e-proportional.ai} and \texttt{center-+1-500t-1000e-proportional.ai}.

\subsubsection{Keep the cart moving from the leftmost to rightmost side of the track as fast as possible, while still
balancing the pole.}
\label{sec:balance}

The proposed solution to this reward function is inspired in the wave equation. The idea is that the velocity of the pole follows the trajectory described by the $sin$ function. In this wave function, the amplitude is by default $1$, so the objective is that given the timestamp, the function will perform which is the desired velocity. The equation is the following:

\begin{equation}
    v^* = sin(\frac{2\pi}{T}t)
\end{equation}

For achieving this, the following python function was elaborated:

\begin{pycode}
def balanced_reward(state, timesteps):
    period = 5
    eps = 0.05
    max_reward = 0.75

    v_ideal = np.sin((2 * np.pi / period) * timesteps)
    return proportional_reward(state[1], v_ideal, eps, max_reward)
\end{pycode}

This function calculates the ideal velocity that the pole should have in each time step and then compares the actual velocity following the equation described in section \ref{sec:center}. After training the model with 500 timesteps and 500 episodes, this is the obtained plot of the rewards: \\

\begin{figure}[h]
    \centering
    \includegraphics[scale=0.4]{exercise-1/report/img/rewards/balance-500t-500e.png}
    \caption{Plot of the rewards after 500 episoes of training}
    \label{fig:my_label}
\end{figure}

The graph shows a significant improvement in the reward obtained along the episodes, achieving an almost constant lines in the final episodes. The corresponding model of this function is \texttt{balanced-500t-500e.ai}.

\subsection{Task 3}
\label{sec:task-3-reward-viz}
\textbf {
    Let us visualize the third reward function
}\\

The execution of 10 parallel runs of the cart pole balance problem, shows this graph:

\begin{figure}[h]
    \centering
    \includegraphics[scale=0.5]{exercise-1/report/img/rewards/Figure_1-multiple.png}
    \caption{10 executions with the reward function described in section \ref{sec:balance}}
    \label{fig:my_label}
\end{figure}

This plot shows also the problem of the high variance between different executions of the problem, but we can also observe than in the final phases of the training the variance is becoming less and the reward function is starting to stabilize, this is because the agent is learning the underlying pattern and maximizing the reward.

\subsection{Question 3}
\label{sec:question-3}
\textbf {
    What do you observe? What is the highest velocity the agent reaches?
}\\

When observing the execution of the cart pole with the third reward function, we can obtain different conclusions. First of all, the velocity of the pole is not adequate, because it goes slow and is not able to finish a complete oscillation in the 500 timestamps used for test. This happens because during the training phase, the agent learns how to maintain an average velocity in order to prevent the pole from falling. \\

\begin{figure}[h]
    \centering
    \includegraphics[scale=0.45]{exercise-1/report/img/rewards/velocity-1.png}
    \caption{Velocity diagram of the execution when the highest velocity was reached}
    \label{fig:velocity}
\end{figure}

This could be seen if we observe the velocity plot (Figure \ref{fig:velocity}) obtained in the episode when the maximum velocity is reached (\textbb{0.410}), in the episode 309 of the test. It shows that the velocity is approximately varying between $-0.2$ and $+0.2$, which indicates that the agent is always more or less following the same velocity, and do not \textit{risk} in increasing it. \\

We can conclude that the third reward function is not enough good, because even if it perform correctly the task, it does not do it in the desired velocity, and also it possibly uses unnecessary information for the calculation such as the timestamp of the current episode.

\bibliographystyle{ieeetr}
\bibliography{template}  % Modify template with your bibliography name
\end{document}


text:
\documentclass[english]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{geometry}
\usepackage{csquotes}
\usepackage{url}
\usepackage{babel}
\usepackage[style=numeric,style=ieee]{biblatex}
\usepackage[nottoc]{tocbibind}
\usepackage{csquotes}
\usepackage{longtable}
 \usepackage{hyperref}

% bibliography
\addbibresource{bibliography.bib}

% Formatting
\setlength{\parindent}{0em}
\geometry{verbose,tmargin=3cm,bmargin=3cm,lmargin=3cm,rmargin=3cm}

\makeatletter

\title{Research Plan for Matching in Multi Agent Pathfinding using M*}
\author{Jonathan Dönszelmann}

\newcommand{\namelistlabel}[1]{\mbox{#1}\hfil}
\newenvironment{namelist}[1]{%1
\begin{list}{}
    {
        \let\makelabel\namelistlabel
        \settowidth{\labelwidth}{#1}
        \setlength{\leftmargin}{1.1\labelwidth}
    }
  }{
\end{list}}

\begin{document}
\maketitle

\begin{namelist}{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}
\item[{\bf Title:}]
	Matching in Multi Agent Pathfinding using M*
\item[{\bf Author:}]
	Jonathan Dönszelmann
\item[{\bf Responsible Professor:}]
	Mathijs de Weerdt
\item[{\bf Other Supervisor:}]
	Jesse Mulderij
% \item[{\bf (Required for final version) Examiner:}]
% 	Another Professor (\emph{interested, but not involved})
\item[{\bf Peer group members:}]
	Robbin Baauw, Thom van der Woude, Ivar de Bruin, Jaap de Jong
\end{namelist}

\tableofcontents
\noindent\rule{\textwidth}{1pt}

\section*{Introduction}

This document is a plan for research which I will do during the fourth quarter of study year 2020/2021 about adding matching to multi agent pathfinding. In this plan I will give a definition of a problem, a set of questions I will be answering, and a planning of how these questions will be answered.

\section{Background of the research}

\subsection{Definition of multi agent pathfinding}
Stern (2019) \cite{mapf_definition_stern_2019} defines a multi agent pathfinding (in this plan abbreviated to \textit{MAPF}) as a problem of $k$ so-called agents \footnote{Agents can be thought of as robots travelling through a graph} and the following tuple:

$$
\langle G, s, g \rangle
$$

\begin{itemize}
    \item $G$ is a graph $\langle V, E \rangle$
    \item $V$ is a set of vertices
    \item $E$ is a set of edges between vertices
    \item $s$ is a list of $k$ vertices where every $s_i$ is a starting position for an agent $a_i$
    \item $g$ is a list of $k$ vertices where every $g_i$ is a target position for an agent $a_i$
\end{itemize}

An algorithm to solve \textit{MAPF} finds solutions such that each agent moves from their starting position
to their target position. Each agent $a_i$ has a path $\pi_i$. Each path $\pi_i$ is a list of positions, defining where each agent $a_i$ is at a moment $t$ (referred to as $pi_i[t]$). The cost of a path $\pi_i$ is its length.

However, while moving, there are a number of conflicts that are to be avoided by the agents.

\begin{itemize}
    \item Edge conflict: two agents are on the same edge $E$ at a timestep $t$ ($\pi_i[t] = \pi_j[t]$ and $\pi_i[t+1] = \pi_j[t+1]$)
    \item Vertex conflict: two agents are on the same vertex $V$ at a timestep $t$ ($\pi_i[t] = \pi_j[t]$)
    \item Swapping: two agents swap vertices at a timestep $t$ ($\pi_i[t] = \pi_j[t+1]$ and $\pi_i[t+1] = \pi_j[t]$)
    \item Following conflict: an agent travels to a vertex from which another agent leaves in the same timestep ($\pi_i[t+1] = \pi_j[t]$)
    \item Cycle conflict: a number of agents larger than 2 all swap vertices such that each of the agents lands on a vertex another agent in the set just left.
\end{itemize}

Summarised, these conflicts define that in \textit{MAPF} it is not allowed for agents to collide in any way. Notable is that some definitions of \textit{MAPF} allow for some of the conflicts defined above to be broken. For example, in previous research that attempted to add waypoints to \textit{MAPF}, the following constraint and cycle constraint were dropped \cite{MSTAR_waypoints_van_dijk_2020}. The reasoning behind this was that when seeing agents as being point-like, and when agents are following each other, they are never actually colliding.

\paragraph{}

Algorithms solving \textit{MAPF} are minimising either the \textit{makespan}, which is the cost of the longest single path, or the \textit{sum of costs} which is the combined cost of all agents' paths. The cost for a single path is defined to be the number of time steps until the last time an agent ends on its target. This means that waiting also has a cost of 1, unless the agent is waiting on its goal location and won't move again in the simulation.

\subsection{Matching}
\textit{Matching} in a bipartite graph is the problem of finding a set of connections between two parts of a graph. No vertex in one part of the graph may be connected to another part of the graph by two edges in the \textit{matching}. Adding \textit{matching} to \textit{MAPF} (in this plan referred to as \textit{MAPFM}) alters the original problem definition in the following way:

$$
\langle G, s, g, sc, gc \rangle
$$

Two variables are added to the definition of this problem:

\begin{itemize}
    \item $sc$ is an array of colours $sc_i$ for each starting vertex $s_i$
    \item $gc$ is an array of colours $gc_i$ for each target vertex $g_i$
\end{itemize}

For a solution to \textit{MAPFM}, it does not matter which agent $a_i$ travels to which target $g_i$. Instead, an agent $a_i$ can travel to any $g_i$ as long as $sc_i = gc_i$.

However, \textit{MAPFM} is not yet fully defined. For example, is it allowed for there to be more target positions than there are agents? Or conversely, is it allowed for there to be fewer target positions than there are agents? In this research it will be assumed that the number of agents will be equal to the number of goals. However, when time permits, the other two options will also be explored.

\paragraph{}

In this research, the graph $G$ will be simplified to be a 4-connected grid.

\subsection{Algorithms}

A number of algorithms exist to solve the \textit{MAPF} problem. These include A* with operator decomposition and independence detection (\textit{A*+OD+ID}) \cite{AStarIDOD_standley_2010}, \textit{M*} \cite{mstar_wagner_2011}, \textit{Conflict based search} \cite{conflict_based_search_sharon_2015} and \textit{Branch and cut and price} \cite{bcp_lam_2019}.

However, to solve the \textit{MAPFM}, no algorithm currently exists. It is planned that each of these algorithms will be adapted to be able to solve \textit{MAPFM} through this this research, and through other similar research by peers.

\subsubsection*{M*}

\textit{M*}, as previously described, is an algorithm designed to solve \textit{MAPF}. I will briefly outline it's workings as this is the algorithm I will be proposing to adapt to be able to use matching.

\textit{M*} solves MAPF by planning paths for each agent individually using \textit{A*} pathfinding. However, when it detects that two agents will be in conflict with each other, it will for a short time, plan the paths of these two agents together in such a way that the conflict is resolved. This is very similar to what (\textit{A*+OD+ID}) does. But in (\textit{A*+OD+ID}), when two agents are in conflict their entire path will be planned together, while in \textit{M*}, paths can be planned independently again after the conflict.

\textit{M*} without extensions, guarantees to generate optimal paths for \textit{MAPF}. However, in prior research extending \textit{MAPF} to allow for waypoints to be added to  paths, optimality could no longer be guaranteed (in certain cases). \cite{MSTAR_waypoints_van_dijk_2020}

\subsection{Applications and related problems}

\textit{MAPF} is a problem which very naturally applies to railways. Trains moving around shunting yards are like agents. They cannot collide or move past each other as they are bound to the tracks they ride on. But in shunting yards, it is usually less important which exact train moves where, and more important what type of train moves somewhere. For example, if trains are the same length, then it does not matter very much which one goes where in the shunting yard as long as they both end up somewhere with enough space.

When trains are stored and serviced in a shunting yard, they need to be moved around. From their parking space, to servicing stations, and back to service to transport people. The scheduling problem that arises is called the Train unit Shunting problem (here abbreviated as \textit{TUSP}). To find relaxations to the \textit{TUSP} problem, Mulderij used \textit{MAPF} \cite{TUSS_MAPF_mulderij_2020}. In his work he describes that extensions to \textit{MAPF} (such as matching) are necessary to make this viable. That is in fact the root of this planned research.

\section*{Research Question}

During this research, I will be answering the following question:

\begin{displayquote}
    Can \textit{M*} be adapted to efficiently find optimal solutions to the \textit{MAPFM} problem?
\end{displayquote}

To answer this question, I think I will need to answer the following sub-questions. However, while researching, it is possible that more of these will arise. If so, and if they fall in the scope of the project, they may be added.

\begin{itemize}
    \item Can \textit{M*} be adapted to do matching
    \item Are \textit{M*} solutions still optimal with matching?
    \item Are there more ways to perform matching, and which way is fastest?
    \item How does the runtime cost of adding matching to \textit{M*} compare to adding matching to other base algorithms?
    \item Are there heuristics which can improve the runtime of \textit{M*} with matching?
    \item Is it possible to adapt \textit{M*} with something similar to operator decomposition.
    \item What happens when the number of agents is no longer equal to the number of target locations?
\end{itemize}

The last sub-question I find especially interesting since real life scenarios (with for example shunting yards) will certainly have situations in which the number of agents is not equal to the number of target locations.

The second to last question is an idea I myself had, it feels quite natural to combine the two but have not been able to find any literature on this. I will investigate this.

From now on, I will call the algorithm I will be developing to solve \textit{MAPFM} using \textit{M*} as base algorithm \textit{M*MAPFM}

\section{Method}

In chronological order, this is how I intend to go about researching the previously stated subquestions:

\begin{itemize}
    \item Implement \textit{M*} for plain \textit{MAPF} problems to get a starting point which can be extended to do matching.
    \item Extend this \textit{MAPF} solver to also solve \textit{MAPFM}.
    \item Create a number of benchmarks to quantitatively evaluate the performance of this algorithm.
    \item Compare \textit{M*} to the algorithms developed by peers by running them on these same benchmarks.
    \item Research ways to improve the runtime of \textit{M*MAPFM}, for example by using better heuristics.
    \item Research possibilities to allow for a different number of agents than there are
\end{itemize}

To fairly compare benchmarks, I will be working on an online system to compare \textit{MAPFM} algorithms, adapted from a similar website used in 2020 by a group researching waypoints in multi agent pathfinding. This will not be a part of the research, but I believe that it will be very valuable when comparing our algorithms.

\section{Planning of the research project}

\begin{center}
\begin{longtable}[c]{ | c | c | }
 \hline
 \multicolumn{2}{| c |}{Planning}\\
 \hline
 week 1 (ma 19 apr) & \begin{minipage}{5in}
    \vskip 4pt
    \begin{itemize}
        \item Kick off
        \item Lecture Research methods
        \item Create planning for week 1 (Monday)
        \item Assignment Information literacy (Tuesday)
        \item Distribute base algorithms
        \item Create research plan
        \item Benchmarking website
        \item Meeting with supervisor (Thursday)
    \end{itemize}
   \vskip 4pt
 \end{minipage}
 \\
  \hline
 week 2 (ma 26 apr) & \begin{minipage}{5in}
    \vskip 4pt
    \begin{itemize}
        \item Prepare presentation of research plan.
        \item Presentation of research plan (Thursday)
        \item Start implementing base algorithm
        \item Lecture responsible research
        \item Meeting with supervisor (Thursday)
    \end{itemize}
   \vskip 4pt
 \end{minipage}
 \\
  \hline
 week 3 (ma 3 may) & \begin{minipage}{5in}
    \vskip 4pt
    \begin{itemize}
        \item Lecture Academic communication skills (Friday)
        \item Implement base algorithm
        \item Research extending to \textit{MAPFM}
        \item Meeting with supervisor (Thursday)
    \end{itemize}
   \vskip 4pt
 \end{minipage}
 \\
  \hline
 week 4 (ma 10 may) & \begin{minipage}{5in}
    \vskip 4pt
    \begin{itemize}
        \item Session responsible research (Monday)
        \item Meeting with supervisor (Thursday)
        \item Extend the algorithm to be able to solve \textit{MAPFM}.
    \end{itemize}
   \vskip 4pt
 \end{minipage}
 \\
  \hline
 week 5 (ma 17 may) & \begin{minipage}{5in}
    \vskip 4pt
    \begin{itemize}
        \item Session Academic communication skills (Monday)
        \item Prepare midterm presentation (before Wednesday)
        \item Midterm presentation (Wednesday)
        \item Meeting with supervisor (Thursday)
        \item Create benchmarks and start comparing to other algorithms (made by peers).
    \end{itemize}
   \vskip 4pt
 \end{minipage}
 \\
  \hline
 week 6 (ma 24 may) & \begin{minipage}{5in}
    \vskip 4pt
    \begin{itemize}
        \item Meeting with supervisor (Thursday)
        \item Session Academic communication skills (Friday)
        \item Find ways to improve runtime performance of \textit{M*MAPF}
        \item Start working on the basics of the final paper.
    \end{itemize}
   \vskip 4pt
 \end{minipage}
 \\
  \hline
 week 7 (ma 31 may) & \begin{minipage}{5in}
    \vskip 4pt
    \begin{itemize}
        \item Quantitative evaluation and comparison with other algorithms.
        \item Possibly extend to solve \textit{MAPFM} with a different number of agents than targets.
        \item Work on paper for draft deadline.
        \item Meeting with supervisor (Thursday)
    \end{itemize}
   \vskip 4pt
 \end{minipage}
 \\
  \hline
 week 8 (ma 7 jun) & \begin{minipage}{5in}
    \vskip 4pt
    \begin{itemize}
        \item Paper draft v1 (Monday)
        \item Peer review paper draft v1 (Thursday)
        \item Meeting with supervisor (Thursday)
        \item Improve paper for draft 2.
        \item Find more ways to improve \textit{M*MAPFM}
    \end{itemize}
   \vskip 4pt
 \end{minipage}
 \\
  \hline
   week 9 (ma 14 jun) & \begin{minipage}{5in}
    \vskip 4pt
    \begin{itemize}
        \item Paper draft v2 (Wednesday)
        \item Final work on paper.
    \end{itemize}
   \vskip 4pt
 \end{minipage}
 \\
  \hline
   week 10 (ma 21 jun) & \begin{minipage}{5in}
    \vskip 4pt
    \begin{itemize}
        \item Submit final paper version (day tbd?)
        \item Create poster and work on poster presentation.
        \item Meeting with supervisor (Thursday)
    \end{itemize}
   \vskip 4pt
 \end{minipage}
 \\
  \hline
   week 11 (ma 28 jun) & \begin{minipage}{5in}
    \vskip 4pt
    \begin{itemize}
        \item Session Academic communication skills (Monday)
        \item submission poster (Tuesday)
        \item poster presentation (Thursday or Friday)
        \item Meeting with examiner
    \end{itemize}
   \vskip 4pt
 \end{minipage}
 \\
  \hline
\end{longtable}
\end{center}

\medskip
\printbibliography

\end{document}

ext: tex

max_stars_repo_name: tbvanderwoude/research-project

max_issues_repo_name: tbvanderwoude/research-project

max_forks_repo_name: tbvanderwoude/research-project


text:
% Options for packages loaded elsewhere
\PassOptionsToPackage{unicode}{hyperref}
\PassOptionsToPackage{hyphens}{url}
%
\documentclass[
]{article}
\usepackage{amsmath,amssymb}
\usepackage{lmodern}
\usepackage{ifxetex,ifluatex}
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
  \usepackage{textcomp} % provide euro and other symbols
\else % if luatex or xetex
  \usepackage{unicode-math}
  \defaultfontfeatures{Scale=MatchLowercase}
  \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
\fi
% Use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
\IfFileExists{microtype.sty}{% use microtype if available
  \usepackage[]{microtype}
  \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\makeatletter
\@ifundefined{KOMAClassName}{% if non-KOMA class
  \IfFileExists{parskip.sty}{%
    \usepackage{parskip}
  }{% else
    \setlength{\parindent}{0pt}
    \setlength{\parskip}{6pt plus 2pt minus 1pt}}
}{% if KOMA class
  \KOMAoptions{parskip=half}}
\makeatother
\usepackage{xcolor}
\IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
\IfFileExists{bookmark.sty}{\usepackage{bookmark}}{\usepackage{hyperref}}
\hypersetup{
  hidelinks,
  pdfcreator={LaTeX via pandoc}}
\urlstyle{same} % disable monospaced font for URLs
\usepackage[margin=1in]{geometry}
\usepackage{color}
\usepackage{fancyvrb}
\newcommand{\VerbBar}{|}
\newcommand{\VERB}{\Verb[commandchars=\\\{\}]}
\DefineVerbatimEnvironment{Highlighting}{Verbatim}{commandchars=\\\{\}}
% Add ',fontsize=\small' for more characters per line
\usepackage{framed}
\definecolor{shadecolor}{RGB}{248,248,248}
\newenvironment{Shaded}{\begin{snugshade}}{\end{snugshade}}
\newcommand{\AlertTok}[1]{\textcolor[rgb]{0.94,0.16,0.16}{#1}}
\newcommand{\AnnotationTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textbf{\textit{#1}}}}
\newcommand{\AttributeTok}[1]{\textcolor[rgb]{0.77,0.63,0.00}{#1}}
\newcommand{\BaseNTok}[1]{\textcolor[rgb]{0.00,0.00,0.81}{#1}}
\newcommand{\BuiltInTok}[1]{#1}
\newcommand{\CharTok}[1]{\textcolor[rgb]{0.31,0.60,0.02}{#1}}
\newcommand{\CommentTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textit{#1}}}
\newcommand{\CommentVarTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textbf{\textit{#1}}}}
\newcommand{\ConstantTok}[1]{\textcolor[rgb]{0.00,0.00,0.00}{#1}}
\newcommand{\ControlFlowTok}[1]{\textcolor[rgb]{0.13,0.29,0.53}{\textbf{#1}}}
\newcommand{\DataTypeTok}[1]{\textcolor[rgb]{0.13,0.29,0.53}{#1}}
\newcommand{\DecValTok}[1]{\textcolor[rgb]{0.00,0.00,0.81}{#1}}
\newcommand{\DocumentationTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textbf{\textit{#1}}}}
\newcommand{\ErrorTok}[1]{\textcolor[rgb]{0.64,0.00,0.00}{\textbf{#1}}}
\newcommand{\ExtensionTok}[1]{#1}
\newcommand{\FloatTok}[1]{\textcolor[rgb]{0.00,0.00,0.81}{#1}}
\newcommand{\FunctionTok}[1]{\textcolor[rgb]{0.00,0.00,0.00}{#1}}
\newcommand{\ImportTok}[1]{#1}
\newcommand{\InformationTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textbf{\textit{#1}}}}
\newcommand{\KeywordTok}[1]{\textcolor[rgb]{0.13,0.29,0.53}{\textbf{#1}}}
\newcommand{\NormalTok}[1]{#1}
\newcommand{\OperatorTok}[1]{\textcolor[rgb]{0.81,0.36,0.00}{\textbf{#1}}}
\newcommand{\OtherTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{#1}}
\newcommand{\PreprocessorTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textit{#1}}}
\newcommand{\RegionMarkerTok}[1]{#1}
\newcommand{\SpecialCharTok}[1]{\textcolor[rgb]{0.00,0.00,0.00}{#1}}
\newcommand{\SpecialStringTok}[1]{\textcolor[rgb]{0.31,0.60,0.02}{#1}}
\newcommand{\StringTok}[1]{\textcolor[rgb]{0.31,0.60,0.02}{#1}}
\newcommand{\VariableTok}[1]{\textcolor[rgb]{0.00,0.00,0.00}{#1}}
\newcommand{\VerbatimStringTok}[1]{\textcolor[rgb]{0.31,0.60,0.02}{#1}}
\newcommand{\WarningTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textbf{\textit{#1}}}}
\usepackage{graphicx}
\makeatletter
\def\maxwidth{\ifdim\Gin@nat@width>\linewidth\linewidth\else\Gin@nat@width\fi}
\def\maxheight{\ifdim\Gin@nat@height>\textheight\textheight\else\Gin@nat@height\fi}
\makeatother
% Scale images if necessary, so that they will not overflow the page
% margins by default, and it is still possible to overwrite the defaults
% using explicit options in \includegraphics[width, height, ...]{}
\setkeys{Gin}{width=\maxwidth,height=\maxheight,keepaspectratio}
% Set default figure placement to htbp
\makeatletter
\def\fps@figure{htbp}
\makeatother
\setlength{\emergencystretch}{3em} % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{-\maxdimen} % remove section numbering
\ifluatex
  \usepackage{selnolig}  % disable illegal ligatures
\fi

\author{}
\date{\vspace{-2.5em}}

\begin{document}

\hypertarget{operations-research}{%
\section{Operations Research}\label{operations-research}}

\hypertarget{laboratory-session-3-solving-linear-models-with-r}{%
\section{Laboratory Session 3: Solving linear models with
R}\label{laboratory-session-3-solving-linear-models-with-r}}

\textbf{by Josu Ceberio and Ana Zelaia}

The aim of this laboratory session is to implement some functions in R
to solve linear models.

\hypertarget{solving-linear-models}{%
\section{Solving linear models}\label{solving-linear-models}}

The graphical solution of linear models shows in a very intuitive way
that the optimal solution of a linear model is an extreme point of the
convex set of feasible solutions. If the problem has multiple optimal
solutions, at least one of them is an extreme point of the set. However,
the graphical solution cannot be used to solve linear models with more
than three variables and linear models normally have a large number of
variables.

In the process of developing an algebraic method to solve linear models,
we analyzed two theorems that demonstrate that, if a linear model is
feasible, it is possible to solve it in an algebraic way. They both
consider a linear model in maximization standard form
(\({\bf b}\geq {\bf 0}\)):

\vspace{-0.5cm}

\begin{eqnarray*}
\max\ \ z= \ \ {\bf c}^{T}{\bf x} \\
\mbox{subject to}\hspace{1cm}\\
{\bf A}{\bf x} = {\bf b} \\
{\bf x} \geq {\bf 0}
\end{eqnarray*}

\vspace{-0.5cm}

and state the following:

\begin{itemize}
\item An optimal solution to a linear model is an extreme point of the feasible region.
\item Every extreme point corresponds to a basic feasible solution, and conversely, every basic feasible solution corresponds to an extreme point.
\end{itemize}

Linear models have a finite number of basic solutions at most and,
therefore, it is possible to compute all of them, select only the
feasible ones and check the objective function to see which is the
optimal. However, it is clear that this is not an efficient method.
Moreover, the analysis of all the basic feasible solutions does not
allow to detect unbounded problems.

In 1947 George Dantzig, the ``Father of Linear Programming'' developed
the simplex algorithm to solve linear problems. It has been declared to
be one of the Top 10 algorithms of the 20th century, because of its
great influence on the development and practice of science and
engineering. The simplex algorithm computes basic feasible solutions and
finds the optimal in a very efficient way. Moreover, it handles
unbounded problems appropriately.

In this 3rd lab session, we will implement R functions to solve linear
models as if the simplex algorithm did not exist: given a linear model
written in maximization standard form, we will compute all the basic
solutions. Checking their feasibility and choosing the optimal one will
be the tasks to work in the 4th lab session. In both lab sessions, we
will not consider unbounded problems.

\hypertarget{some-interesting-r-built-in-functions}{%
\section{Some interesting R built-in
functions}\label{some-interesting-r-built-in-functions}}

Given the \(Ax=b\) system of linear equations, the R functions below
will be useful, during the implementation process, to verify whether a
set of columns of the matrix form a basis, to calculate a basic solution
or to find linear combinations of the columns in the matrix.

\textbf{Function \texttt{det(B)}}. A system of linear equations may be
inconsistent. To check if some columns in matrix \({\bf A}\) form a
basis, function \texttt{det} can be used. If the system is consistent, a
solution can be computed.

\begin{Shaded}
\begin{Highlighting}[]
\FunctionTok{det}\NormalTok{(A[,}\FunctionTok{c}\NormalTok{(}\DecValTok{1}\NormalTok{,}\DecValTok{2}\NormalTok{)])}\SpecialCharTok{!=}\DecValTok{0}
\end{Highlighting}
\end{Shaded}

\textbf{Function \texttt{solve(B,b)}}. This function can be used to
solve systems of linear equations that are consistent.

\begin{Shaded}
\begin{Highlighting}[]
\FunctionTok{solve}\NormalTok{(A[,}\FunctionTok{c}\NormalTok{(}\DecValTok{1}\NormalTok{,}\DecValTok{2}\NormalTok{)], b)}
\end{Highlighting}
\end{Shaded}

\textbf{Function \texttt{combn(x,m)}}. Given a system of linear
equations, to compute all the basic solutions, we will have to analyze
all the combinations of columns of matrix \({\bf A}\) that may form a
basis. Function \texttt{combn(x,m)} generates all combinations of the
elements of vector \(x\) taking \(m\) at a time and returns a matrix
with a column for each combination generated.

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{x }\OtherTok{\textless{}{-}} \FunctionTok{c}\NormalTok{(}\DecValTok{1}\SpecialCharTok{:}\DecValTok{4}\NormalTok{)}
\NormalTok{x}
\CommentTok{\# [1] 1 2 3 4}
\FunctionTok{combn}\NormalTok{(x, }\DecValTok{2}\NormalTok{)}
\CommentTok{\#     [,1] [,2] [,3] [,4] [,5] [,6]}
\CommentTok{\# [1,]  1    1    1    2    2    3}
\CommentTok{\# [2,]  2    3    4    3    4    4}
\FunctionTok{combn}\NormalTok{(x, }\DecValTok{2}\NormalTok{)[,}\DecValTok{1}\NormalTok{]}
\CommentTok{\# [1] 1 2}
\NormalTok{A[,}\FunctionTok{combn}\NormalTok{(x, }\DecValTok{2}\NormalTok{)[,}\DecValTok{1}\NormalTok{]]}
\FunctionTok{solve}\NormalTok{(A[,}\FunctionTok{combn}\NormalTok{(x, }\DecValTok{2}\NormalTok{)[,}\DecValTok{1}\NormalTok{]], b)}
\end{Highlighting}
\end{Shaded}

\hypertarget{exercises}{%
\section{Exercises}\label{exercises}}

\textbf{Exercise 1.} The \texttt{basic.solution} function.

Given a matrix \({\bf A}\), a vector
\({\bf b}\)(\({\bf b}\geq {\bf 0}\)) and a vector of column-indices for
\({\bf A}\), define a function that extracts those columns from
\({\bf A}\) and checks if they form a basis. If they do, the function
returns the corresponding basic solution: a vector with the values for
all the variables of the system. If they don't, the function returns a
vector with the values for all the variables of the system set to -1.

To check the correctness of the functions implemented, let us consider
the following linear model: \vspace{-0.5cm} \begin{eqnarray*}
\max\ z=3x_{1}+4x_{2}+5x_3+6x_4 \\
\mbox{subject to}\hspace{3.5cm}\\
2x_{1}+x_{2}+x_3+8x_4 = 6    \\
x_{1}+x_{2}+2x_3+x_{4}=4 \\
x_{1},x_{2},x_{3},x_{4}\geq 0  \\
\end{eqnarray*}

\vspace{-0.5cm}

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{A }\OtherTok{\textless{}{-}} \FunctionTok{matrix}\NormalTok{(}\FunctionTok{c}\NormalTok{(}\DecValTok{2}\NormalTok{, }\DecValTok{1}\NormalTok{, }\DecValTok{1}\NormalTok{, }\DecValTok{8}\NormalTok{, }\DecValTok{1}\NormalTok{, }\DecValTok{1}\NormalTok{, }\DecValTok{2}\NormalTok{, }\DecValTok{1}\NormalTok{), }\AttributeTok{nrow=}\DecValTok{2}\NormalTok{, }\AttributeTok{byrow=}\ConstantTok{TRUE}\NormalTok{)}
\NormalTok{b }\OtherTok{\textless{}{-}} \FunctionTok{c}\NormalTok{(}\DecValTok{6}\NormalTok{, }\DecValTok{4}\NormalTok{)}
\NormalTok{c }\OtherTok{\textless{}{-}} \FunctionTok{c}\NormalTok{(}\DecValTok{3}\NormalTok{, }\DecValTok{4}\NormalTok{, }\DecValTok{5}\NormalTok{, }\DecValTok{6}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{basic.solution }\OtherTok{\textless{}{-}} \ControlFlowTok{function}\NormalTok{(A, b, column.ind.vector)\{}
  \CommentTok{\# We initialize an array with zeros 1...ncol(A) positions}
\NormalTok{  x }\OtherTok{\textless{}{-}} \FunctionTok{double}\NormalTok{(}\FunctionTok{ncol}\NormalTok{(A))}

  \CommentTok{\# Check if the system of linear equations is consistent}
  \ControlFlowTok{if}\NormalTok{(}\FunctionTok{det}\NormalTok{(A[,column.ind.vector]) }\SpecialCharTok{!=} \DecValTok{0}\NormalTok{)\{}
    \CommentTok{\# Solve the system using the solve() method}
\NormalTok{    x[column.ind.vector] }\OtherTok{\textless{}{-}} \FunctionTok{solve}\NormalTok{(A[,column.ind.vector], b)}
\NormalTok{  \} }\ControlFlowTok{else}\NormalTok{ \{}
    \CommentTok{\# Not consistent =\textgreater{} return array with all "{-}1" elements}
\NormalTok{    x }\OtherTok{\textless{}{-}} \FunctionTok{rep}\NormalTok{(}\SpecialCharTok{{-}}\DecValTok{1}\NormalTok{, }\AttributeTok{times =} \FunctionTok{ncol}\NormalTok{(A))}
\NormalTok{  \}}
  \FunctionTok{return}\NormalTok{(x)}
\NormalTok{\}}

\FunctionTok{basic.solution}\NormalTok{(A, b, }\FunctionTok{c}\NormalTok{(}\DecValTok{1}\NormalTok{, }\DecValTok{2}\NormalTok{))}
\CommentTok{\# x1=0.0000000, x2=0.0000000, x3=1.7333333, x4=0.5333333}
\end{Highlighting}
\end{Shaded}

\textbf{Exercise 2.} The \texttt{all.basic\_solutions} functions: with
\texttt{for} and \texttt{apply} loops (two versions).

Given a matrix \({\bf A}\) and a vector \({\bf b}\)
(\({\bf b}\geq {\bf 0}\)), compute all the basic feasible solutions.
Propose two different implementations: using the \texttt{for} loop(s)
and with the \texttt{apply} functions.

\textbf{2.1.} Using \texttt{for} loops. Try returning the solutions in a
list. To test your implementation, you can use the same linear model as
in Exercise 1.

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{all.basic\_solutions\_for }\OtherTok{\textless{}{-}} \ControlFlowTok{function}\NormalTok{(A, b)\{}
  \CommentTok{\# Generate all combinations of the elements of c(1...ncol(A)) taking nrow(A) at a time,}
  \CommentTok{\# this generates a matrix with columns for each combination.}
\NormalTok{  comb }\OtherTok{\textless{}{-}} \FunctionTok{combn}\NormalTok{(}\FunctionTok{c}\NormalTok{(}\DecValTok{1}\SpecialCharTok{:}\FunctionTok{ncol}\NormalTok{(A)), }\FunctionTok{nrow}\NormalTok{(A))}

  \CommentTok{\# List for the result return}
\NormalTok{  lst }\OtherTok{\textless{}{-}} \FunctionTok{list}\NormalTok{()}

  \CommentTok{\# Iterate from 1...ncol(comb), for each iteration,}
  \CommentTok{\# compute the solution using previously coded method and passing}
  \CommentTok{\# the combination (column vector) at position c of the comb matrix.}
  \CommentTok{\# Save the result in the created list.}
  \ControlFlowTok{for}\NormalTok{ (c }\ControlFlowTok{in} \DecValTok{1}\SpecialCharTok{:}\FunctionTok{ncol}\NormalTok{(comb)) \{}
\NormalTok{    lst[[c]] }\OtherTok{\textless{}{-}} \FunctionTok{basic.solution}\NormalTok{(A, b, comb[, c])}
\NormalTok{  \}}
  \FunctionTok{return}\NormalTok{(lst)}
\NormalTok{\}}
\CommentTok{\# This function returns a list.}
\FunctionTok{all.basic\_solutions\_for}\NormalTok{(A,b)}
\DocumentationTok{\#\# [[1]]}
\DocumentationTok{\#\# [1] 2 2 0 0}
\DocumentationTok{\#\#}
\DocumentationTok{\#\# [[2]]}
\DocumentationTok{\#\# [1] 2.6666667 0.0000000 0.6666667 0.0000000}
\DocumentationTok{\#\#}
\DocumentationTok{\#\# [[3]]}
\DocumentationTok{\#\# [1] 4.3333333  0.0000000  0.0000000 {-}0.3333333}
\DocumentationTok{\#\#}
\DocumentationTok{\#\# [[4]]}
\DocumentationTok{\#\# [1] 0 8 {-}2 0}
\DocumentationTok{\#\#}
\DocumentationTok{\#\# [[5]]}
\DocumentationTok{\#\# [1] 0.0000000 3.7142857 0.0000000 0.2857143}
\DocumentationTok{\#\#}
\DocumentationTok{\#\# [[6]]}
\DocumentationTok{\#\# [1] 0.0000000 0.0000000 1.7333333 0.5333333}
\end{Highlighting}
\end{Shaded}

\textbf{2.2.} Using \texttt{apply} loops. Try returning the solutions in
a matrix. To test your implementation, you can use the same linear model
as in Exercise 1.

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{all.basic\_solutions\_apply }\OtherTok{\textless{}{-}} \ControlFlowTok{function}\NormalTok{(A,b)\{}
  \CommentTok{\# As in the previous exercise, create a combinations matrix.}
\NormalTok{  comb }\OtherTok{\textless{}{-}} \FunctionTok{combn}\NormalTok{(}\FunctionTok{c}\NormalTok{(}\DecValTok{1}\SpecialCharTok{:}\FunctionTok{ncol}\NormalTok{(A)), }\FunctionTok{nrow}\NormalTok{(A))}

  \CommentTok{\# This apply loop, iterates over the columns of the comb matrix,}
  \CommentTok{\# and for each column vector, calls the basic.solution using that column to }
  \CommentTok{\# calculate the solution.}
  \CommentTok{\# Returns a matrix with the basic solutions as columns.}
  \FunctionTok{return}\NormalTok{(}\FunctionTok{apply}\NormalTok{(comb, }\DecValTok{2}\NormalTok{, basic.solution, }\AttributeTok{A=}\NormalTok{A, }\AttributeTok{b=}\NormalTok{b))}
\NormalTok{\} }

\CommentTok{\# This function returns a matrix. Basic solutions are shown in columns}
\FunctionTok{all.basic\_solutions\_apply}\NormalTok{(A,b) }

\DocumentationTok{\#\#    [,1]      [,2]       [,3] [,4]      [,5]      [,6]}
\DocumentationTok{\#\#[1,]    2 2.6666667  4.3333333    0 0.0000000 0.0000000}
\DocumentationTok{\#\#[2,]    2 0.0000000  0.0000000    8 3.7142857 0.0000000}
\DocumentationTok{\#\#[3,]    0 0.6666667  0.0000000   {-}2 0.0000000 1.7333333}
\DocumentationTok{\#\#[4,]    0 0.0000000 {-}0.3333333    0 0.2857143 0.5333333}
\end{Highlighting}
\end{Shaded}

\textbf{Exercise 3.} The \texttt{basic.feasible.solutions} functions:
with \texttt{for} and \texttt{apply} functions (two versions).

Adapt the implementations in exercise 2 to return only the basic
solutions that are feasible.

\textbf{3.1.} Adaptation of the functions using \texttt{for} loops. Try
returning the solutions in a list. To test your implementation, you can
use the same linear model as in Exercise 1.

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{basic.feasible.solutions\_for }\OtherTok{\textless{}{-}} \ControlFlowTok{function}\NormalTok{(A, b)\{}
  \CommentTok{\# With the previous exercises we get the basic solutions, but}
  \CommentTok{\# we dont know if all of them are feasible.}
  \CommentTok{\# To check it, we iterate over the solution and if all element are }
  \CommentTok{\# greater or equal to 0 =\textgreater{} add to result list.}
\NormalTok{  lst }\OtherTok{\textless{}{-}} \FunctionTok{list}\NormalTok{()}
\NormalTok{  x }\OtherTok{\textless{}{-}} \FunctionTok{all.basic\_solutions\_for}\NormalTok{(A, b)}
\NormalTok{  i }\OtherTok{\textless{}{-}} \DecValTok{1}
  \ControlFlowTok{for}\NormalTok{ (t }\ControlFlowTok{in}\NormalTok{ x) \{}
    \ControlFlowTok{if}\NormalTok{ (}\FunctionTok{all}\NormalTok{(t }\SpecialCharTok{\textgreater{}=} \DecValTok{0}\NormalTok{)) \{ }\CommentTok{\# Check if all elements in t are \textgreater{}= 0.}
\NormalTok{      lst[[i]] }\OtherTok{\textless{}{-}}\NormalTok{ t}
\NormalTok{      i }\OtherTok{\textless{}{-}}\NormalTok{ i }\SpecialCharTok{+} \DecValTok{1}
\NormalTok{    \}}
\NormalTok{  \}}
  \FunctionTok{return}\NormalTok{(lst)}
\NormalTok{\}}
\CommentTok{\# This function returns a list.}
\FunctionTok{basic.feasible.solutions\_for}\NormalTok{(A,b)}
\DocumentationTok{\#\# [[1]]}
\DocumentationTok{\#\# [1] 2 2 0 0}
\DocumentationTok{\#\# }
\DocumentationTok{\#\# [[2]]}
\DocumentationTok{\#\# [1] 2.6666667 0.0000000 0.6666667 0.0000000}
\DocumentationTok{\#\# }
\DocumentationTok{\#\# [[3]]}
\DocumentationTok{\#\# [1] 0.0000000 3.7142857 0.0000000 0.2857143}
\DocumentationTok{\#\# }
\DocumentationTok{\#\# [[4]]}
\DocumentationTok{\#\# [1] 0.0000000 0.0000000 1.7333333 0.5333333}
\CommentTok{\#}
\CommentTok{\# Interpretation: There are four basic feasible solutions. }
\CommentTok{\# x1=2, x2=2, x3=0, x4=0}
\CommentTok{\# x1=2.6666667, x2=0.0000000, x3=0.6666667, x4=0.0000000}
\CommentTok{\# x1=0.0000000, x2=3.7142857, x3=0.0000000, x4=0.2857143}
\CommentTok{\# x1=0.0000000, x2=0.0000000, x3=1.7333333, x4=0.5333333}
\end{Highlighting}
\end{Shaded}

\textbf{3.2.} Adaptation of the functions using \texttt{apply} loops.
Try returning the solutions in a matrix. To test your implementation,
you can use the same linear model as in Exercise 1.

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{basic.feasible.solutions\_apply }\OtherTok{\textless{}{-}} \ControlFlowTok{function}\NormalTok{(A,b)\{}
  \CommentTok{\# The same as the 3.1 exercise, but in this case we use apply loops.}
  \CommentTok{\# {-} First of all, we take all the basic solutions with the method}
  \CommentTok{\# implemented in the exercise 2.2.}
\NormalTok{  x }\OtherTok{\textless{}{-}} \FunctionTok{all.basic\_solutions\_apply}\NormalTok{(A, b)}

  \CommentTok{\# {-} To filter this matrix and remove the columns (solutions) that are not }
  \CommentTok{\# feasible (not all elements in the vector is \textgreater{}= 0), we do not select the }
  \CommentTok{\# columns with a number of negative elements (x \textless{} 0) greater or equal to 1.}
  \FunctionTok{return}\NormalTok{(x[, }\SpecialCharTok{!}\FunctionTok{apply}\NormalTok{(x, }\DecValTok{2}\NormalTok{, }\ControlFlowTok{function}\NormalTok{(x) }\FunctionTok{sum}\NormalTok{( x }\SpecialCharTok{\textless{}} \DecValTok{0}\NormalTok{ ) }\SpecialCharTok{\textgreater{}=} \DecValTok{1}\NormalTok{)])}
\NormalTok{\} }
\CommentTok{\# This function returns a matrix. Basic solutions are shown in columns}
\FunctionTok{basic.feasible.solutions\_apply}\NormalTok{(A,b)  }
\DocumentationTok{\#\#      [,1]      [,2]      [,3]      [,4]}
\DocumentationTok{\#\# [1,]    2 2.6666667 0.0000000 0.0000000}
\DocumentationTok{\#\# [2,]    2 0.0000000 3.7142857 0.0000000}
\DocumentationTok{\#\# [3,]    0 0.6666667 0.0000000 1.7333333}
\DocumentationTok{\#\# [4,]    0 0.0000000 0.2857143 0.5333333}

\CommentTok{\# Interpretation: There are four basic feasible solutions. }
\CommentTok{\# x1=2, x2=2, x3=0, x4=0}
\CommentTok{\# x1=2.6666667, x2=0.0000000, x3=0.6666667, x4=0.0000000}
\CommentTok{\# x1=0.0000000, x2=3.7142857, x3=0.0000000, x4=0.2857143}
\CommentTok{\# x1=0.0000000, x2=0.0000000, x3=1.7333333, x4=0.5333333}
\end{Highlighting}
\end{Shaded}

\hypertarget{linear-problems-for-testing}{%
\section{Linear problems for
testing}\label{linear-problems-for-testing}}

Solve the following linear models using the functions defined, and check
the solution.

\textbf{System of linear equations from exercise 6 of the unit ``Linear
Algebra''.}

Let us consider the following system of linear equations:

\[
\begin{array}{l}
      \ \ 2x_{1}+3x_{2}-x_3 \hspace{2cm}= 1    \\
      \ \ \ x_{1}+\ \ x_{2} \hspace{1cm}+x_{4}\hspace{1cm}=3 \\
      -x_{1}+2x_{2}\hspace{2cm}+x_{5}=5 \\
      \end{array}
\]

Definition of matrix A and vector b:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{A }\OtherTok{\textless{}{-}} \FunctionTok{matrix}\NormalTok{(}\FunctionTok{c}\NormalTok{(}\DecValTok{2}\NormalTok{, }\DecValTok{3}\NormalTok{, }\SpecialCharTok{{-}}\DecValTok{1}\NormalTok{, }\DecValTok{0}\NormalTok{, }\DecValTok{0}\NormalTok{, }\DecValTok{1}\NormalTok{, }\DecValTok{1}\NormalTok{, }\DecValTok{0}\NormalTok{, }\DecValTok{1}\NormalTok{, }\DecValTok{0}\NormalTok{, }\SpecialCharTok{{-}}\DecValTok{1}\NormalTok{, }\DecValTok{2}\NormalTok{, }\DecValTok{0}\NormalTok{, }\DecValTok{0}\NormalTok{, }\DecValTok{1}\NormalTok{), }\AttributeTok{nrow=}\DecValTok{3}\NormalTok{, }\AttributeTok{byrow=}\ConstantTok{TRUE}\NormalTok{)}
\NormalTok{b }\OtherTok{\textless{}{-}} \FunctionTok{c}\NormalTok{(}\DecValTok{1}\NormalTok{, }\DecValTok{3}\NormalTok{, }\DecValTok{5}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

\textbf{1.} Calculate the basic solutions one by one using the function
\texttt{basic.solution}.

\begin{Shaded}
\begin{Highlighting}[]
\CommentTok{\# Implement here (10 lines)}
\FunctionTok{basic.solution}\NormalTok{(A, b, }\FunctionTok{c}\NormalTok{(}\DecValTok{1}\NormalTok{, }\DecValTok{2}\NormalTok{, }\DecValTok{3}\NormalTok{))}
\FunctionTok{basic.solution}\NormalTok{(A, b, }\FunctionTok{c}\NormalTok{(}\DecValTok{1}\NormalTok{, }\DecValTok{2}\NormalTok{, }\DecValTok{4}\NormalTok{))}
\FunctionTok{basic.solution}\NormalTok{(A, b, }\FunctionTok{c}\NormalTok{(}\DecValTok{1}\NormalTok{, }\DecValTok{2}\NormalTok{, }\DecValTok{5}\NormalTok{))}
\FunctionTok{basic.solution}\NormalTok{(A, b, }\FunctionTok{c}\NormalTok{(}\DecValTok{1}\NormalTok{, }\DecValTok{3}\NormalTok{, }\DecValTok{4}\NormalTok{))}
\FunctionTok{basic.solution}\NormalTok{(A, b, }\FunctionTok{c}\NormalTok{(}\DecValTok{1}\NormalTok{, }\DecValTok{3}\NormalTok{, }\DecValTok{5}\NormalTok{))}
\FunctionTok{basic.solution}\NormalTok{(A, b, }\FunctionTok{c}\NormalTok{(}\DecValTok{1}\NormalTok{, }\DecValTok{4}\NormalTok{, }\DecValTok{5}\NormalTok{))}
\FunctionTok{basic.solution}\NormalTok{(A, b, }\FunctionTok{c}\NormalTok{(}\DecValTok{2}\NormalTok{, }\DecValTok{3}\NormalTok{, }\DecValTok{4}\NormalTok{))}
\FunctionTok{basic.solution}\NormalTok{(A, b, }\FunctionTok{c}\NormalTok{(}\DecValTok{2}\NormalTok{, }\DecValTok{3}\NormalTok{, }\DecValTok{5}\NormalTok{))}
\FunctionTok{basic.solution}\NormalTok{(A, b, }\FunctionTok{c}\NormalTok{(}\DecValTok{2}\NormalTok{, }\DecValTok{4}\NormalTok{, }\DecValTok{5}\NormalTok{))}
\FunctionTok{basic.solution}\NormalTok{(A, b, }\FunctionTok{c}\NormalTok{(}\DecValTok{3}\NormalTok{, }\DecValTok{4}\NormalTok{, }\DecValTok{5}\NormalTok{))}
\end{Highlighting}
\end{Shaded}

\textbf{2.} Calculate all the basic solutions using the function
\texttt{all.basic\_solutions}.

\textbf{2.1.} Use the \texttt{for} version calling to the function
\texttt{all.basic\_solutions\_for}:

\begin{Shaded}
\begin{Highlighting}[]
\CommentTok{\# Implement here (1 line)}
\FunctionTok{all.basic\_solutions\_for}\NormalTok{(A, b)}
\end{Highlighting}
\end{Shaded}

\textbf{2.2.} Use the \texttt{apply} version calling to the function
\texttt{all.basic\_solutions\_apply}:

\begin{Shaded}
\begin{Highlighting}[]
\CommentTok{\# Implement here (1 line)}
\FunctionTok{all.basic\_solutions\_apply}\NormalTok{(A, b)}
\end{Highlighting}
\end{Shaded}

\textbf{3.} Return exclusively the basic solutions that are feasible. To
that end, use the function \texttt{basic.feasible.solutions}.

\textbf{3.1.} Use the \texttt{for} version calling to the function
\texttt{basic.feasible.solutions\_for}:

\begin{Shaded}
\begin{Highlighting}[]
\CommentTok{\# Implement here (1 line)}
\FunctionTok{basic.feasible.solutions\_for}\NormalTok{(A, b)}
\end{Highlighting}
\end{Shaded}

\textbf{3.2.} Use the \texttt{apply} version calling to the function
\texttt{basic.feasible.solutions\_applyr}:

\begin{Shaded}
\begin{Highlighting}[]
\CommentTok{\# Implement here (1 line)}
\FunctionTok{basic.feasible.solutions\_apply}\NormalTok{(A, b)}
\end{Highlighting}
\end{Shaded}

\textbf{System of linear equations from exercise 2 of the list of
exercises of the unit ``The simplex method''.}

Let us consider the following system of linear equations: \[
\begin{array}{l}
      -x_{1}+\ \ x_{2}+x_3 \hspace{2cm}= \ \ 4    \\
      \ \ 2x_{1}+5x_{2} \hspace{1cm}+x_{4}\hspace{1cm}=20 \\
      \ \ 2x_{1}-\ x_{2}\hspace{2cm}+x_{5}=\ \ 2 \\
      \end{array}
\] Definition of matrix A and vector b:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{A }\OtherTok{\textless{}{-}} \FunctionTok{matrix}\NormalTok{(}\FunctionTok{c}\NormalTok{(}\SpecialCharTok{{-}}\DecValTok{1}\NormalTok{, }\DecValTok{1}\NormalTok{, }\DecValTok{1}\NormalTok{, }\DecValTok{0}\NormalTok{, }\DecValTok{0}\NormalTok{, }\DecValTok{2}\NormalTok{, }\DecValTok{5}\NormalTok{, }\DecValTok{0}\NormalTok{, }\DecValTok{1}\NormalTok{, }\DecValTok{0}\NormalTok{, }\DecValTok{2}\NormalTok{, }\SpecialCharTok{{-}}\DecValTok{1}\NormalTok{, }\DecValTok{0}\NormalTok{, }\DecValTok{0}\NormalTok{, }\DecValTok{1}\NormalTok{), }\AttributeTok{nrow=}\DecValTok{3}\NormalTok{, }\AttributeTok{byrow=}\ConstantTok{TRUE}\NormalTok{)}
\NormalTok{b }\OtherTok{\textless{}{-}} \FunctionTok{c}\NormalTok{(}\DecValTok{4}\NormalTok{, }\DecValTok{20}\NormalTok{, }\DecValTok{2}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

\textbf{1.} Calculate the basic solutions one by one using the function
\texttt{basic.solution}..

\begin{Shaded}
\begin{Highlighting}[]
\CommentTok{\# Implement here (10 lines)}
\FunctionTok{basic.solution}\NormalTok{(A, b, }\FunctionTok{c}\NormalTok{(}\DecValTok{1}\NormalTok{, }\DecValTok{2}\NormalTok{, }\DecValTok{3}\NormalTok{))}
\FunctionTok{basic.solution}\NormalTok{(A, b, }\FunctionTok{c}\NormalTok{(}\DecValTok{1}\NormalTok{, }\DecValTok{2}\NormalTok{, }\DecValTok{4}\NormalTok{))}
\FunctionTok{basic.solution}\NormalTok{(A, b, }\FunctionTok{c}\NormalTok{(}\DecValTok{1}\NormalTok{, }\DecValTok{2}\NormalTok{, }\DecValTok{5}\NormalTok{))}
\FunctionTok{basic.solution}\NormalTok{(A, b, }\FunctionTok{c}\NormalTok{(}\DecValTok{1}\NormalTok{, }\DecValTok{3}\NormalTok{, }\DecValTok{4}\NormalTok{))}
\FunctionTok{basic.solution}\NormalTok{(A, b, }\FunctionTok{c}\NormalTok{(}\DecValTok{1}\NormalTok{, }\DecValTok{3}\NormalTok{, }\DecValTok{5}\NormalTok{))}
\FunctionTok{basic.solution}\NormalTok{(A, b, }\FunctionTok{c}\NormalTok{(}\DecValTok{1}\NormalTok{, }\DecValTok{4}\NormalTok{, }\DecValTok{5}\NormalTok{))}
\FunctionTok{basic.solution}\NormalTok{(A, b, }\FunctionTok{c}\NormalTok{(}\DecValTok{2}\NormalTok{, }\DecValTok{3}\NormalTok{, }\DecValTok{4}\NormalTok{))}
\FunctionTok{basic.solution}\NormalTok{(A, b, }\FunctionTok{c}\NormalTok{(}\DecValTok{2}\NormalTok{, }\DecValTok{3}\NormalTok{, }\DecValTok{5}\NormalTok{))}
\FunctionTok{basic.solution}\NormalTok{(A, b, }\FunctionTok{c}\NormalTok{(}\DecValTok{2}\NormalTok{, }\DecValTok{4}\NormalTok{, }\DecValTok{5}\NormalTok{))}
\FunctionTok{basic.solution}\NormalTok{(A, b, }\FunctionTok{c}\NormalTok{(}\DecValTok{3}\NormalTok{, }\DecValTok{4}\NormalTok{, }\DecValTok{5}\NormalTok{))}
\end{Highlighting}
\end{Shaded}

\textbf{2.} Calculate all the basic solutions using the function
\texttt{all.basic\_solutions}.

\textbf{2.1.} Use the \texttt{for} version calling to the function
\texttt{all.basic\_solutions\_for}:

\begin{Shaded}
\begin{Highlighting}[]
\CommentTok{\# Implement here (1 line)}
\FunctionTok{all.basic\_solutions\_for}\NormalTok{(A, b)}
\end{Highlighting}
\end{Shaded}

\textbf{2.2.} Use the \texttt{apply} version calling to the function
\texttt{all.basic\_solutions\_apply}:

\begin{Shaded}
\begin{Highlighting}[]
\CommentTok{\# Implement here (1 line)}
\FunctionTok{all.basic\_solutions\_apply}\NormalTok{(A, b)}
\end{Highlighting}
\end{Shaded}

\textbf{3.} Return exclusively the basic solutions that are feasible. To
that end, use the function \texttt{basic.feasible.solutions}.

\textbf{3.1.} Use the \texttt{for} version calling to the function
\texttt{basic.feasible.solutions\_for}:

\begin{Shaded}
\begin{Highlighting}[]
\CommentTok{\# Implement here (1 line)}
\FunctionTok{basic.feasible.solutions\_for}\NormalTok{(A, b)}
\end{Highlighting}
\end{Shaded}

\textbf{3.2.} Use the \texttt{apply} version calling to the function
\texttt{basic.feasible.solutions\_apply}:

\begin{Shaded}
\begin{Highlighting}[]
\CommentTok{\# Implement here (1 line)}
\FunctionTok{basic.feasible.solutions\_apply}\NormalTok{(A, b)}
\end{Highlighting}
\end{Shaded}

\end{document}

max_stars_repo_name: usainzg/EHU

max_issues_repo_name: usainzg/EHU

max_forks_repo_name: usainzg/EHU


text:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Beamer Presentation
% LaTeX Template
% Version 1.0 (10/11/12)
%
% This template has been downloaded from:
% http://www.LaTeXTemplates.com
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND THEMES
%----------------------------------------------------------------------------------------

\documentclass{beamer}

\mode<presentation> {

% The Beamer class comes with a number of default slide themes
% which change the colors and layouts of slides. Below this is a list
% of all the themes, uncomment each in turn to see what they look like.

%\usetheme{default}
%\usetheme{AnnArbor}
%\usetheme{Antibes}
%\usetheme{Bergen}
%\usetheme{Berkeley}
%\usetheme{Berlin}
%\usetheme{Boadilla}
%\usetheme{CambridgeUS}
%\usetheme{Copenhagen}
%\usetheme{Darmstadt}
% \usetheme{Dresden}
%\usetheme{Frankfurt}
%\usetheme{Goettingen}
%\usetheme{Hannover}
%\usetheme{Ilmenau}
%\usetheme{JuanLesPins}
%\usetheme{Luebeck}
\usetheme{Madrid}
%\usetheme{Malmoe}
%\usetheme{Marburg}
%\usetheme{Montpellier}
%\usetheme{PaloAlto}
%\usetheme{Pittsburgh}
%\usetheme{Rochester}
%\usetheme{Singapore}
%\usetheme{Szeged}
%\usetheme{Warsaw}

% As well as themes, the Beamer class has a number of color themes
% for any slide theme. Uncomment each of these in turn to see how it
% changes the colors of your current slide theme.

% \usecolortheme{albatross}
% \usecolortheme{beaver}
%\usecolortheme{beetle}
%\usecolortheme{crane}
%\usecolortheme{dolphin}
% \usecolortheme{dove}
%\usecolortheme{fly}
%\usecolortheme{lily}
%\usecolortheme{orchid}
%\usecolortheme{rose}
%\usecolortheme{seagull}
%\usecolortheme{seahorse}
%\usecolortheme{whale}
%\usecolortheme{wolverine}

%\setbeamertemplate{footline} % To remove the footer line in all slides uncomment this line
\setbeamertemplate{footline}[page number] % To replace the footer line in all slides with a simple slide count uncomment this line

\setbeamertemplate{navigation symbols}{} % To remove the navigation symbols from the bottom of all slides uncomment this line
}

\usepackage{graphicx} % Allows including images
\usepackage{booktabs} % Allows the use of \toprule, \midrule and \bottomrule in tables
%\usepackage {tikz}
\usepackage{physics}
\usepackage{mathtools}
\usepackage{tkz-graph}
\usepackage[round]{natbib}
\GraphInit[vstyle = Shade]
\tikzset{
  LabelStyle/.style = { rectangle, rounded corners, draw,
                        minimum width = 2em, fill = yellow!50,
                        text = red, font = \bfseries },
  VertexStyle/.append style = { inner sep=5pt,
                                font = \normalsize\bfseries},
  EdgeStyle/.append style = {->, bend left} }
\usetikzlibrary {positioning}
%\usepackage {xcolor}
\definecolor {processblue}{cmyk}{0.96,0,0,0}
%----------------------------------------------------------------------------------------
%	TITLE PAGE
%----------------------------------------------------------------------------------------

\title[Short title]{AI Based Lecture Summarization Tool} % The short title appears at the bottom of every slide, the full title is only on the title page

\author{
  Team 9\\
} % Your name
\institute[IIIT-H] % Your institution as it will appear on the bottom of every slide, may be shorthand to save space
{
IIIT Hyderabad\\ % Your institution for the title page
\medskip
}
\date{\today} % Date, can be changed to a custom date

\begin{document}

\begin{frame}
\titlepage % Print the title page as the first slide
\end{frame}

\begin{frame}
\frametitle{Overview} % Table of contents slide, comment this block out to remove it
\tableofcontents % Throughout your presentation, if you choose to use \section{} and \subsection{} commands, these will automatically be printed on this slide as an overview of your presentation
\end{frame}

%----------------------------------------------------------------------------------------
%	PRESENTATION SLIDES
%----------------------------------------------------------------------------------------

%------------------------------------------------
\section{Problem Statement}
\begin{frame}{Problem Statement}
Despite the many advantages of online learning, it faces some severe disadvantages such as:
    \begin{itemize}
        \item Lack of accessibility due to internet connectivity issues
        \item Low attention span of students as compared to physical learning in classroom settings
        \item Uploaded videos are difficult to revise as compared to class notes
    \end{itemize}
\end{frame}

\begin{frame}{Problem Statement}
As part of our end semester project in Software Engineering, we aim to address a few of
the above problems by using AI to automatically summarize lecture videos. Our solution would
leverage the latest advancements in machine learning and computer vision to make it very easy for users to revise using the uploaded videos.
\end{frame}

\section{Our Solution}
\begin{frame}{Our Solution}
    We have developed our software using a client-server architecture and the user interacts with our product using a web application.
    \begin{itemize}
        \item The client side provide the user with a UI where they are able to login, and add, search and summarize the videos
        \item The server deal with all the client side requests such as:
            \begin{itemize}
                \item Provide authentication methods for login
                \item Summarize a given uploaded video
                \item Return the most relevant clips for a given search query
            \end{itemize}
        \item Our solution uses a combination of video processing, machine learning and summarization techniques to solve the problem in a fast and efficient manner.
    \end{itemize}
\end{frame}

\section{High Level Design of our algorithm}
\begin{frame}{High Level Design}
\begin{figure}
    \centering
    \includegraphics[scale=0.11]{Block Level Diagram.png}
    \caption{High Level Design of our algorithm}
    \label{fig:HLD}
\end{figure}
\end{frame}

\section{Coding Principles and Design Patterns}
\begin{frame}{Coding Principles and Design Patterns}
    \begin{itemize}
        \item We have followed Model View Template \textbf{Design Patterns}. The Model is the logical data structure behind the entire application and is represented by a database. The View is the user interface and template consists of static parts of the HTML output as well as describes how dynamic content will be inserted.

        \item Follows object oriented paradigm, which is a sub category of imperative programming paradigm.

        \item Interfaces and objects are created for each of the sub modules.
        \item Functions names are self-explanatory and small in size (7-10) lines.
        \item Exceptions are handled by using try except blocks.
        \item The code of different sub modules is easily \textbf{extendable} to other APIs and libraries.
        \item Followed \textbf{SOLID} design principles.
    \end{itemize}
\end{frame}

\section{Software Development Model}
\begin{frame}{Software Development Model}
    \begin{itemize}
        \item Agile SDLC Model
        \item Feature Driven Development (FDD) Agile methodologies
        \item Great solution to maintain control for incremental Agile project management
    \end{itemize}
\end{frame}

\section{Integration and Testing}
\begin{frame}{Integration and Testing Process}
    \begin{itemize}
        \item Unit Testing
            \begin{itemize}
                \item Each module has its test files in its respective folder.
            \end{itemize}
        \item After Unit Testing we have performed \textbf{Incremental Integration Testing}.
            \begin{itemize}
                \item Integrate the modules one by one using stubs or drivers to uncover the defects.
                \item We have used \textbf{Functional} incremental testing methodologies as integration and testing takes place on the basis of the functionalities as per the requirement specifications in design document.
            \end{itemize}
        \item We have used this because the defects are found early in a smaller assembly when it is relatively easy to detect the root cause of the same.
    \end{itemize}
\end{frame}

% \begin{frame}{References}
% % \bibliographystyle{acm}
% \bibliographystyle{unsrt}
% \bibliography{references}
% \end{frame}

% \begin{frame}
% \begin{figure}
%     \includegraphics[scale=0.3]{withthanks.jpg}
% \end{figure}
% \end{frame}

\end{document}

max_stars_repo_name: talsperre/LectureSummarizer

max_issues_repo_name: talsperre/LectureSummarizer

max_forks_repo_name: talsperre/LectureSummarizer


text:
\par
\section{Prototypes and descriptions of {\tt BPG} methods}
\label{section:BPG:proto}
\par
This section contains brief descriptions including prototypes
of all methods that belong to the {\tt BPG} object.
\par
\subsection{Basic methods}
\label{subsection:BPG:proto:basics}
\par
As usual, there are four basic methods to support object creation,
setting default fields, clearing any allocated data, and free'ing
the object.
\par
%=======================================================================
\begin{enumerate}
%-----------------------------------------------------------------------
\item
\begin{verbatim}
BPG * BPG_new ( void ) ;
\end{verbatim}
\index{BPG_new@{\tt BPG\_new()}}
This method simply allocates storage for the {\tt BPG} structure
and then sets the default fields by a call to
{\tt BPG\_setDefaultFields()}.
%-----------------------------------------------------------------------
\item
\begin{verbatim}
void BPG_setDefaultFields ( BPG *bpg ) ;
\end{verbatim}
\index{BPG_setDefaultFields@{\tt BPG\_setDefaultFields()}}
This method sets the fields of the structure to their default values:
{\tt nX = nY = 0} and {\tt graph = NULL}.
\par \noindent {\it Error checking:}
If {\tt bpg} is {\tt NULL},
an error message is printed and the program exits.
%-----------------------------------------------------------------------
\item
\begin{verbatim}
void BPG_clearData ( BPG *bpg ) ;
\end{verbatim}
\index{BPG_clearData@{\tt BPG\_clearData()}}
This method releases the storage for {\tt graph} via a call
to {\tt Graph\_clearData()}, and
then the structure's fields are then set to their default values
with a call to {\tt BPG\_setDefaultFields()}.
\par \noindent {\it Error checking:}
If {\tt bpg} is {\tt NULL},
an error message is printed and the program exits.
%-----------------------------------------------------------------------
\item
\begin{verbatim}
void BPG_free ( BPG *bpg ) ;
\end{verbatim}
\index{BPG_free@{\tt BPG\_free()}}
This method releases any storage by a call to
{\tt BPG\_clearData()} then free's the storage for the
structure with a call to {\tt free()}.
\par \noindent {\it Error checking:}
If {\tt bpg} is {\tt NULL},
an error message is printed and the program exits.
%-----------------------------------------------------------------------
\end{enumerate}
\par
\subsection{Initializer methods}
\label{subsection:BPG:proto:initializers}
\par
There are two initializer methods.
\par
%=======================================================================
\begin{enumerate}
%-----------------------------------------------------------------------
\item
\begin{verbatim}
void BPG_init ( BPG *bpg, int nX, int nY, Graph *graph ) ;
\end{verbatim}
\index{BPG_init@{\tt BPG\_init()}}
This method initializes the {\tt BPG} object when all three of its
fields are given in the calling sequence.
The {\tt Graph} object has {\tt nX + nY} vertices.
Note, the {\tt BPG} object now ``owns'' the {\tt Graph} object and
so will free the {\tt Graph} object when it is free'd.
The {\tt Graph} object may contains edges between nodes in {\tt X}
and {\tt Y}, but these edges are swapped to the end of each
adjacency list and the size of each list is then set.
\par \noindent {\it Error checking:}
If {\tt bpg} or {\tt graph} are {\tt NULL},
or if ${\tt nX} \le 0$,
or if ${\tt nY} \le 0$,
an error message is printed and the program exits.
%-----------------------------------------------------------------------
\item
\begin{verbatim}
void BPG_initFromColoring ( BPG *bpg, Graph *graph, int colors[], int cX,
                            int cY, int cmap[], int indX[], int indY[] ) ;
\end{verbatim}
\index{BPG_initFromColoring@{\tt BPG\_initFromColoring()}}
This method extracts a bipartite graph from a {\tt Graph} object where
the {\tt X} vertices are those with {\tt cmap[]} value
equal to {\tt cX} and the {\tt Y} vertices are those
with {\tt cmap[]} value equal to {\tt cY}.
The vectors {\tt indX[]} and {\tt indY[]} hold the global vertex
ids of the {\tt X} and {\tt Y} vertices respectively.
\par \noindent {\it Error checking:}
If {\tt bpg}, {\tt graph}, {\tt colors} or {\tt cmap} are {\tt NULL},
or if ${\tt cX} \le 0$,
or if ${\tt cY} \le 0$,
or if ${\tt cX} = {\tt cY}$,
an error message is printed and the program exits.
%-----------------------------------------------------------------------
\end{enumerate}
\par
\subsection{Generate induced graphs}
\label{subsection:BPG:proto:induced-graphs}
\par
Sometimes we need to know which {\tt X} or {\tt Y} vertices
share an edge,
e.g., in the {\tt BKL} object we need the domain-domain adjacency
graph (the domains are the {\tt X} vertices)
to efficiently implement the Fiduccia-Mattheyses algorithm.
We have two methods to generate the two induced graphs.
\par
%=======================================================================
\begin{enumerate}
%-----------------------------------------------------------------------
\item
\begin{verbatim}
Graph * BPG_makeGraphXbyX ( BPG *bpg ) ;
\end{verbatim}
\index{BPG_makeGraphXbyX@{\tt BPG\_makeGraphXbyX()}}
This method constructs and returns a {\tt Graph} object whose
vertices are {\tt X} and an edge {\tt (x1,x2)} is in the graph
when there is a {\tt Y} vertex {\tt y} such that {\tt (x1,y)}
and {\tt (x2,y)} are in the bipartite graph.
\par \noindent {\it Error checking:}
If {\tt bpg} is {\tt NULL},
an error message is printed and the program exits.
%-----------------------------------------------------------------------
\item
\begin{verbatim}
Graph * BPG_makeGraphYbyY ( BPG *bpg ) ;
\end{verbatim}
\index{BPG_makeGraphYbyY@{\tt BPG\_makeGraphYbyY()}}
This method constructs and returns a {\tt Graph} object whose
vertices are {\tt Y} and an edge {\tt (y1,y2)} is in the graph
when there is a {\tt X} vertex {\tt x} such that {\tt (x,y1)}
and {\tt (x,y2)} are in the bipartite graph.
\par \noindent {\it Error checking:}
If {\tt bpg} is {\tt NULL},
an error message is printed and the program exits.
%-----------------------------------------------------------------------
\end{enumerate}
\par
\subsection{Utility methods}
\label{subsection:BPG:proto:utilities}
\par
%=======================================================================
\begin{enumerate}
%-----------------------------------------------------------------------
\item
\begin{verbatim}
int BPG_pseudoperipheralnode ( BPG *bpg, int seed ) ;
\end{verbatim}
\index{BPG_pseudoperipheralnode@{\tt BPG\_pseudoperipheralnode()}}
This method finds and returns a pseudoperipheral node for the
bipartite graph.
\par \noindent {\it Error checking:}
If {\tt bpg} is {\tt NULL},
an error message is printed and the program exits.
%-----------------------------------------------------------------------
\item
\begin{verbatim}
int BPG_levelStructure ( BPG *bpg, int root, int list[], int dist[],
                         int mark[], int tag ) ;
\end{verbatim}
\index{BPG_levelStructure@{\tt BPG\_levelStructure()}}
This method drops a level structure from vertex {\tt root}, fills
the {\tt dist[]} vector with the distances from {\tt root},
and returns the number of levels created.
The {\tt mark[]} vector is used to mark nodes with the {\tt tag}
value as they are placed in the level structure.
The {\tt list[]} vector is used to accumulate the nodes as they are
placed in the level structure.
\par \noindent {\it Error checking:}
If {\tt bpg}, {\tt list}, {\tt dist} or {\tt mark} is {\tt NULL},
or if {\tt root} is not in {\tt [0, nX+nY)},
an error message is printed and the program exits.
%-----------------------------------------------------------------------
\end{enumerate}
\par
\subsection{Dulmage-Mendelsohn decomposition method}
\label{subsection:BPG:proto:DM}
\par
There is one method to find the Dulmage-Mendelsohn decomposition that
uses matching when the graph is unit weight and a generalized
matching technique otherwise.
There is a second method to find the decomposition using a
Ford-Fulkerson algorithm to find a max flow and a min-cut on a
bipartite network.
This has largely been superceded by the {\tt Network} object.
\par
%=======================================================================
\begin{enumerate}
%-----------------------------------------------------------------------
\item
\begin{verbatim}
void BPG_DMdecomposition ( BPG *bpg, int dmflags[], int stats[],
                           int msglvl, FILE *msgFile )
\end{verbatim}
\index{BPG_DMdecomposition@{\tt BPG\_DMdecomposition()}}
This method constructs and returns the Dulmage-Mendelsohn
decomposition for a unit weight graph and its generalization for a
non-unit weight graph.
On return, the {\tt dmflags[]} vector is filled with the following
values:
\begin{displaymath}
\mbox{\tt dmflags[x]} =
\begin{cases}
0 & \text{if \texttt{x} $\in X_R$} \\
1 & \text{if \texttt{x} $\in X_I$} \\
2 & \text{if \texttt{x} $\in X_E$}
\end{cases}
\qquad
\mbox{\tt dmflags[y]} =
\begin{cases}
0 & \text{if \texttt{y} $\in Y_R$} \\
1 & \text{if \texttt{y} $\in Y_I$} \\
2 & \text{if \texttt{y} $\in Y_E$}
\end{cases}
\end{displaymath}
The set $X_I \cup Y_E$ contains all nodes that are reachable via
alternating paths starting from exposed nodes in $X$.
The set $Y_I \cup X_E$ contains all nodes that are reachable via
alternating paths starting from exposed nodes in $Y$.
The remaining two sets are $X_R = X \setminus (X_I \cup X_E)$
and $Y_R = Y \setminus (Y_I \cup Y_E)$.
On return, the {\tt stats[]} vector is filled with the following
values:
\begin{center}
\begin{tabular}{lllllll}
{\tt stats[0]} & --- & weight of $X_I$
& \qquad & {\tt stats[3]} & --- & weight of $Y_I$ \\
{\tt stats[1]} & --- & weight of $X_E$
& \qquad & {\tt stats[4]} & --- & weight of $Y_E$ \\
{\tt stats[2]} & --- & weight of $X_R$
& \qquad & {\tt stats[5]} & --- & weight of $Y_R$
\end{tabular}
\end{center}
\par \noindent {\it Error checking:}
If {\tt bpg}, {\tt dmflags} or {\tt stats} is {\tt NULL},
or if {\tt msglvl > 0} and {\tt msgFile} is {\tt NULL},
an error message is printed and the program exits.
%-----------------------------------------------------------------------
\item
\begin{verbatim}
void BPG_DMviaMaxFlow ( BPG *bpg, int dmflags[], int stats[],
                        int msglvl, FILE *msgFile ) ;
\end{verbatim}
\index{BPG_DMviaMaxFlow@{\tt BPG\_DMviaMaxFlow()}}
This method has the same functionality, calling sequence and
returned values as the preceding {\tt BPG\_DMdecomposition()} method.
\par \noindent {\it Error checking:}
If {\tt bpg}, {\tt dmflags} or {\tt stats} is {\tt NULL},
or if {\tt msglvl > 0} and {\tt msgFile} is {\tt NULL},
an error message is printed and the program exits.
%-----------------------------------------------------------------------
\end{enumerate}
\par
\subsection{IO methods}
\label{subsection:BPG:proto:IO}
\par
There are the usual eight IO routines.
The file structure of a {\tt BPG} object is simple:
the two scalar fields {\tt nX} and {\tt nY}
come first and the {\tt Graph} object follows.
\par
%=======================================================================
\begin{enumerate}
%-----------------------------------------------------------------------
\item
\begin{verbatim}
int BPG_readFromFile ( BPG *bpg, char *fn ) ;
\end{verbatim}
\index{BPG_readFromFile@{\tt BPG\_readFromFile()}}
\par
This method reads a {\tt BPG} object from a file.
The method tries to open the file and if it is successful,
it then calls {\tt BPG\_readFromFormattedFile()} or
{\tt BPG\_readFromBinaryFile()},
closes the file
and returns the value returned from the called routine.
\par \noindent {\it Error checking:}
If {\tt bpg} or {\tt fn} is {\tt NULL},
or if {\tt fn} is not of the form
{\tt *.bpgf} (for a formatted file)
or {\tt *.bpgb} (for a binary file),
an error message is printed and the method returns zero.
%-----------------------------------------------------------------------
\item
\begin{verbatim}
int BPG_readFromFormattedFile ( BPG *bpg, FILE *fp ) ;
\end{verbatim}
\index{BPG_readFromFormattedFile@{\tt BPG\_readFromFormattedFile()}}
\par
This method reads a {\tt BPG} object from a formatted file.
If there are no errors in reading the data,
the value {\tt 1} is returned.
If an IO error is encountered from {\tt fscanf}, zero is returned.
\par \noindent {\it Error checking:}
If {\tt bpg} or {\tt fp} is {\tt NULL}
an error message is printed and zero is returned.
%-----------------------------------------------------------------------
\item
\begin{verbatim}
int BPG_readFromBinaryFile ( BPG *bpg, FILE *fp ) ;
\end{verbatim}
\index{BPG_readFromBinaryFile@{\tt BPG\_readFromBinaryFile()}}
\par
This method reads a {\tt BPG} object from a binary file.
If there are no errors in reading the data,
the value {\tt 1} is returned.
If an IO error is encountered from {\tt fread}, zero is returned.
\par \noindent {\it Error checking:}
If {\tt bpg} or {\tt fp} is {\tt NULL}
an error message is printed and zero is returned.
%-----------------------------------------------------------------------
\item
\begin{verbatim}
int BPG_writeToFile ( BPG *bpg, char *fn ) ;
\end{verbatim}
\index{BPG_writeToFile@{\tt BPG\_writeToFile()}}
\par
This method writes a {\tt BPG} object to a file.
The method tries to open the file and if it is successful,
it then calls {\tt BPG\_writeFromFormattedFile()} or
{\tt BPG\_writeFromBinaryFile()},
closes the file
and returns the value returned from the called routine.
\par \noindent {\it Error checking:}
If {\tt bpg} or {\tt fn} is {\tt NULL},
or if {\tt fn} is not of the form
{\tt *.bpgf} (for a formatted file)
or {\tt *.bpgb} (for a binary file),
an error message is printed and the method returns zero.
%-----------------------------------------------------------------------
\item
\begin{verbatim}
int BPG_writeToFormattedFile ( BPG *bpg, FILE *fp ) ;
\end{verbatim}
\index{BPG_writeToFormattedFile@{\tt BPG\_writeToFormattedFile()}}
\par
This method writes a {\tt BPG} object to a formatted file.
If there are no errors in writing the data,
the value {\tt 1} is returned.
If an IO error is encountered from {\tt fprintf}, zero is returned.
\par \noindent {\it Error checking:}
If {\tt bpg} or {\tt fp} is {\tt NULL},
an error message is printed and zero is returned.
%-----------------------------------------------------------------------
\item
\begin{verbatim}
int BPG_writeToBinaryFile ( BPG *bpg, FILE *fp ) ;
\end{verbatim}
\index{BPG_writeToBinaryFile@{\tt BPG\_writeToBinaryFile()}}
\par
This method writes a {\tt BPG} object to a binary file.
If there are no errors in writing the data,
the value {\tt 1} is returned.
If an IO error is encountered from {\tt fwrite}, zero is returned.
\par \noindent {\it Error checking:}
If {\tt bpg} or {\tt fp} is {\tt NULL},
an error message is printed and zero is returned.
%-----------------------------------------------------------------------
\item
\begin{verbatim}
int BPG_writeForHumanEye ( BPG *bpg, FILE *fp ) ;
\end{verbatim}
\index{BPG_writeForHumanEye@{\tt BPG\_writeForHumanEye()}}
\par
This method writes a {\tt BPG} object to a file
in a human readable format.
The method {\tt BPG\_writeStats()}
is called to write out the
header and statistics.
Then the {\tt bpg->graph} object is written via a call to
{\tt Graph\_writeForHumanEye()}.
The value {\tt 1} is returned.
\par \noindent {\it Error checking:}
If {\tt bpg} or {\tt fp} is {\tt NULL},
an error message is printed and zero is returned.
%-----------------------------------------------------------------------
\item
\begin{verbatim}
int BPG_writeStats ( BPG *bpg, FILE *fp ) ;
\end{verbatim}
\index{BPG_writeStats@{\tt BPG\_writeStats()}}
\par
This method writes a header with statistics to a file.
A header is written and the value {\tt 1} is returned.
\par \noindent {\it Error checking:}
If {\tt bpg} or {\tt fp} is {\tt NULL},
an error message is printed and zero is returned.
%-----------------------------------------------------------------------
\end{enumerate}

max_stars_repo_name: alleindrach/calculix-desktop

max_issues_repo_name: alleindrach/calculix-desktop

max_forks_repo_name: alleindrach/calculix-desktop


text:
% Noah Scarbrough, Samuel Dunn
% CS 483, Fall 2019
% Group project proprosal.

\documentclass{article}

\title{CS 483 Project Proposal}
\author{Noah Scarbrough, Samuel Dunn}
\date{10-17-2019}

\begin{document}
\maketitle

\section{Data Set}
Our data set for this project will be the cards used in trading card game,
Magic: The Gathering. The card text will be treated as a document.
With nearly 20,000 unique cards in existence, there is a wealth of data available.
If this proves to bee too large to process within the scope of this assignment we will
trim our scraping to be the subset of cards that are legal in the modern format.
Along with the document, each tuple will additionally contain other attributes for the card, such as its mana cost and rarity.
This data will be scraped from the official database site for the game.

\section{Feature: Advanced Search}
Our first feature will be an advanced search engine.
The user will have the option of using the standard search or the advanced search.
The standard search will simply return the cards most relevant to the keyword query across all components of the card.
Advanced search will be more intricate and designed to assist with deck building. The advanced search will allow the
user to hone in on matching particular aspects of a card. The elements that advanced search will include the user
to restrict searches over include the card's color identity, converted mana cost, type, supported formats and so forth.

\section{Feature: Related Cards}
Another feature we plan to include is a display of relevant cards.
When a card is chosen from the results, it will open a page that
contains not only information about the card, but also give a list
of links for related cards. Related cards will be determined by mining
information from popular deckbuilding sites, such as tappedout.net, for
cards commonly used in conjunction to the card the user has selected.
If unable to glean precise information from mining, we may fall back
to suggesting cards with similar features, mana cost, set legality, and so forth.

\end{document}


text:
\documentclass[openany,11pt]{homework}

\coursename{ELEN 4903 Machine Learning (Spring 2018)} % DON'T CHANGE THIS

\studname{Pratyus Pati}    % YOUR NAME GOES HERE
\studmail{pp2636@columbia.edu}% YOUR UNI GOES HERE
\hwNo{5}                   % THE HOMEWORK NUMBER GOES HERE

% Uncomment the next line if you want to use \includegraphics.
\usepackage{graphicx}

\begin{document}
\maketitle

\section*{Problem 1(a)}

\begin{center}
	\centering
	\includegraphics[width = 0.70\textwidth]{1b-10.png}
	\\
	\textbf{Top 25 Teams after $10$ iterations}
\end{center}

\begin{center}
	\centering
	\includegraphics[width = 0.70\textwidth]{1b-100.png}
	\\
	\textbf{Top 25 Teams after $100$ iterations}
\end{center}

\begin{center}
	\centering
	\includegraphics[width = 0.70\textwidth]{1b-1000.png}
	\\
	\textbf{Top 25 Teams after $1000$ iterations}
\end{center}

\begin{center}
	\centering
	\includegraphics[width = 0.70\textwidth]{1b-10000.png}
	\\
	\textbf{Top 25 Teams after $10000$ iterations}
\end{center}

\section*{Problem 1(b)}
\begin{center}
	\centering
	\includegraphics[width = 0.70\textwidth]{1b-inf.png}
	\\
	\textbf{Top 25 Teams based on the stationary distribution}
\end{center}

\begin{center}
	\centering
	\includegraphics[width = \textwidth]{1a.png}
	\textbf{$\|\|w_t - w_{\infty}\|\|$ vs. Iterations t}
\end{center}

\section*{Problem 2(a)}

\begin{center}
	\centering
	\includegraphics[width = \textwidth]{2a.png}
	\textbf{Divergence Penalty vs Iterations}
\end{center}

\newpage

\section*{Problem 2(b)}

\begin{center}
	\centering
	\includegraphics[width = \textwidth]{topics.png}
	\\
	\textbf{Top 10 Words (with scores) per Topic}
\end{center}

\end{document}

max_stars_repo_name: prtyspt/ml-course


text:
\section{Purpose}
Currently, a problem with dating sites are the lack of genuine connections. Using heteronormative examples,

\subsection{Mens' issues with online dating}

\begin{itemize}
    \item Suffering from poor picture quality
    \item Lack of ability to leverage vocal tonality, body language, and eye contact
\end{itemize}

\subsection{Womens' issues with online dating}
\begin{itemize}
    \item Safety concerns
    \item An overwhelming number of suitors to choose from
    \item An apparent lack of substance from said options
\end{itemize}

\section{Scope}
The scope of this project thus far is to be used as a way to allow men and women to connect based on genuine attributes,
spearheaded by the use of content uploaded by trusted friends.
Specifically, the product would allow friends of a user to upload content such as videos, voice recordings, pictures that describe
how the friend feels about the user, what the friend thinks, etc.

\section{Overview}
A representative use-case for the product is given below:

\begin{enumerate}
    \item The user signs into \serviceName with their email address and password.
    \item The user defines a list of people that they would like to get references from.
    \item The references receive an email asking them to upload content onto the requester's profile.
    \item The reference uploads the content.
    \item The reference sees profiles that may be good fits for the requester and makes recommendations.
    \item The recommendee's references get notifications that one of their friends may have a match.
    \item The recommendee's reference confirms the mutual fit.
    \item The user and the match can now message each other.
\end{enumerate}

\section{Reference Material}
\section{Definitions and Acronyms}
\begin{table}[ht]
    \centering
    \begin{tabular}{l | l}
        Term & Definition \\
        \hline
        MVP & Minimum Viable Product \\
        LDA & Leading Dating apps \\
        MS & Matrimony Sites \\
        UGC & User Generated Content \\
    \end{tabular}
    \caption{Table of Definitions and acronyms used}
    \label{tab: def_ac}
\end{table}
% \blindtext[6]

max_stars_repo_name: steevejoseph/twine

max_issues_repo_name: steevejoseph/twine

max_forks_repo_name: steevejoseph/twine