\documentclass[11pt]{article}
\usepackage{pictex, latexsym, graphicx,amsmath,amssymb,amsbsy,amsfonts,amsthm,verbatim}
\usepackage{fullpage}
\usepackage{etex}
\usepackage[all]{xypic}
\usepackage{lpic}
\usepackage{lscape}
\setlength{\parindent}{0em}

\def\vx{\mathbf{x}}
\def\vc{\mathbf{c}}
\def\vb{\mathbf{b}}
\def\vy{\mathbf{y}}

\begin{document}

\thispagestyle{empty}



\begin{center}
	\Large\bf MATH 482, Spring 2013 - Homework 5
	
	\large Assigned Monday 11/04. Due Monday 11/11.
\end{center}

\emph{For this homework, solve four of the following five problems, but definitely complete problems 4 and 5. Each is worth 5 points. Problem 1 has a point breakdown for the parts, should you choose to do that problem.}

\emph{Complete AT MOST four problems. If you complete all five, then your top score will be dropped!}


\textbf{1.}  Determine which of the matrices below are (i) unimodular, (ii) totally unimodular, or (iii) neither.
Be sure to explain your answer.

\begin{center}
\begin{tabular}[h]{c@{\qquad}c@{\qquad}c}
$\left[\begin{array}{rrrr}
1 & -1 & -1 & 0\\
-1 & 0 & 0 & 1\\
0 & 1 & 0 & -1\\
0 & 0 & 1 & 0\end{array}\right]$ & 
$\left[\begin{array}{cccc}
1 & 0 & 1 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 1\\
1 & 1 & 0 & 1\end{array}\right]$ &
$\left[\begin{array}{ccccc}
0 & 1 & 0 & 0 & 0  \\
1 & 0 & 1 & 0  & 0 \\
0 & 1 & 0 & 1 & 1\\
0 & 0 & 1 & 0 & 1\\
0 & 0 & 1 & 1 & 0\end{array}\right] $
\\
\textbf{a.} (\emph{1.5pts}) &
\textbf{b.} (\emph{1.5pts}) &
\textbf{c.}  (\emph{2pts})
\end{tabular}
\end{center}

\textbf{2.} An $(n,k,\lambda,\mu)$ \emph{strongly regular graph} is an undirected graph with vertex set $\{v_1,\dots,v_n\}$ where every vertex is incident to $k$ edges and for every pair $v_i, v_j$:
\begin{itemize}
\item If $v_iv_j$ is an edge, then $v_i$ and $v_j$ have exactly $\lambda$ common neighbors.
\item If $v_iv_j$ is not an edge, then $v_i$ and $v_j$ have exactly $\mu$ common neighbors.
\end{itemize}
For arbitrary $n, k, \lambda, \mu$, construct an integer program encoding the constraints of an $(n,k,\lambda,\mu)$ strongly regular graph. Prove that the feasible integer solutions are in bijection with the $(n,k,\lambda,\mu)$ strongly regular graphs on vertex set $v_1,\dots,v_n$. (For this last part, we consider the graphs to be \emph{labeled} and so do not worry about isomorphism.)

\textbf{3.} Solve the following integer linear program using branch-and-bound. Use the graphical method to solve each linear program relaxation. Plot your branch-and-bound cuts in the $x_1,x_2$-plane.
\[
\begin{array}{rrcrcl}
\min & x_{1} & +&x_{2} & = & z\\
\textrm{subject to } & x_{1} & +&2x_{2} & \ge & 2\\
 & -x_{1} & +&4x_{2} & \le & 3\\
 & x_{1}, && x_{2} & \ge & 0,\textrm{ integer}\end{array}\]

\textbf{4.} (\emph{Assigned!}) Using the following set of points on the integer grid, compute a heuristic TSP using the Nearest Neighbor heuristic, then locally improve it using 2-switches until it is locally optimal.

\begin{center}
\includegraphics[height=1.5in]{tspgrid}\\
\emph{\footnotesize A larger version is on the next page. Feel free to print multiple copies and work directly on those copies.}
\end{center}

\textbf{5.} (\emph{Assigned!}) Using the above set of points on the integer grid, compute a heuristic TSP using the Farthest Insertion heuristic, then locally improve it using 2-switches until it is locally optimal.

\clearpage
\thispagestyle{empty}
\begin{landscape}
\includegraphics[height=0.65\textwidth]{tspgrid}
\end{landscape}


\end{document} 