\documentclass[11pt]{article}
\usepackage{pictex, latexsym, graphicx,amsmath,amssymb,amsbsy,amsfonts,amsthm,verbatim}
\usepackage{fullpage}
\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}
\textbf{\large
Fall 2013 \qquad Math 566 \qquad Implementation Assignment 1 \\
\Large Linear and Integer Programs
}
\end{center}

\vspace{1em}
\textbf{\large Problem: Linear and Integer Programs}

We have discussed linear programs at length now, but have not discussed actual algorithms to \emph{solve} them! 
In this assignment, you will use a computer to solve given linear programs and find a dual solution.
You will also use the computer to set variables to be integer-valued and solve the resulting integer program.

\vspace{1em}
\textbf{\large Questions To Answer.}

\textbf{Q1.} Describe how you use the given primal problem to produce dual solution.

\textbf{Q2.} Describe what you do differently to make the problem have integer-valued variables instead of real-valued variables.

\textbf{Q3.} When the variables are set to be integer-valued, the optimal value can change from (and be worse than!) the linear solution.
	Prove that the relative gap between the optimal linear solution and optimal integer solutions can be arbitrarily large by demonstrating for every $n \geq 1$ a linear program $P_n$ whose optimal linear solution $\vx$ and optimal integer solution $\vx^{(i)}$ has $\vc^\top\cdot \vx \leq \frac{1}{n}\vc^\top \vx^{(i)}$.

\textbf{Q4.} What language, libraries, and environments did you use?

\textbf{Q5.} What challenges did you encounter during your implementation?

\textbf{Q6.} What online/library resources did you use?

\vspace{1em}
\textbf{\large Problem Instances.}

\textbf{I1 \& I2.} Solve the following programs, once with real variables and once with integer variables.
	Produce a dual solution to the linear program.

\[
\begin{array}{rrcrcrcl}
	\min & 3x_1 & - & x_2 & + & 2 x_3 & &\\
	\text{subject to} & x_1 & + & x_2 & & & = & 10 \\
	& 3x_1 & & & - & x_3 & \geq & 6 \\
	&  & & 5x_2 & + & 3x_3& \geq & 4 \\
	& x_1, & & x_2, & & x_3,&\geq & 0
\end{array}
\]
\[
\begin{array}{rrcrcrcrcrcrcrcrcrcrcrcrcl}
   	         \max & x_1 & + & x_2 & + & x_3 & + & x_4 & + & x_5 & + & x_6 & + & x_7 & + & x_8 & + & x_9 & + & x_{10} & & \\
\text{s.t.} & x_1 &+ & x_2 &    &        &    &       &     &       &     &       &    &        &     &       &     &       & + & x_{10} & \leq & 2 \\
                         &        &    & x_2 & + & x_3 &    &       &     &       &     &       &  + & x_7 &     &       &     &       &    &      & \leq & 2 \\
                         &        &    &       &    &  x_3 & + & x_4&     &       &     &       &    &        &     &       &  +&  x_9     &  & & \leq & 2 \\
                         &        &    &       &    &        &    & x_4&  + &  x_5& + & x_6 &    &        &     &       &     &       &   &      & \leq & 2 \\
                         & x_1 & +  &       &    &        &    &       &     & x_5 &     &       &    &        & + &x_8&     &       &   &      & \leq & 2 \\
                         & x_1 &    &       &    &        &    &       &     &       &  + & x_6 & + & x_7  &     &       &     &       &   &      & \leq & 2 \\
                         &        &    & x_2 &    &        &    &       &     &       &     &       &    &        &  +  & x_8 & + & x_9    &   &      & \leq & 2 \\
                         &        &    &       &    &  x_3 &    &       &     &       & + & x_6 &    &        &     &       &     &       & +  & x_{10}     & \leq & 2 \\
                         &        &    &       &    &        &    & x_4 &     &       &     &       & +& x_7  &  + & x_8&     &       &   &      & \leq & 2 \\
                         &        &    &       &    &        &    &       &     &  x_5   &     &       &    &        &     &       &   +&x_9& +& x_{10} & \leq & 2 \\
                         & x_1, & & x_2,&& x_3, && x_4,&& x_5, && x_6, && x_7, && x_8, && x_9, && x_{10} & \geq & 0
\end{array}
\]
 
\textbf{I3 \& I4.} See the files \texttt{lp3.txt} and \texttt{lp4.txt} on the course web page for a matrix $A$, and vectors $c$ and $b$.
	Solve the canonical form linear program given by these parameters and produce dual solutions.
	(\emph{Integer solutions to these problems are not required.})
\end{document} 