\documentclass[12pt]{amsart}
\pagestyle{empty}
\usepackage[hmargin=1in,vmargin=1in]{geometry}
\usepackage{url,  mathrsfs}
\usepackage{hyperref}
\usepackage{fancyhdr} 
\usepackage[T1]{fontenc}


\usepackage{url,  mathrsfs}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{graphicx,  epstopdf}
\usepackage{subfig}
\usepackage{color}
\usepackage{bbm}
\usepackage{subfloat}
\usepackage[draft]{fixme}
\usepackage{bm} 
\usepackage{bbm} 
\usepackage{epigraph}
\usepackage{endnotes}
\usepackage{ifpdf}
\usepackage{array}

\usepackage{multicol}
\usepackage{multirow}
\usepackage{graphicx}
\usepackage{tikz}

\newcommand{\A}{\mathbb{A}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\C}{\mathbb{C}}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\V}{\mathcal{V}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\ol}{\overline}
\newcommand{\J}{\mathcal{J}}
\newcommand{\X}{\mathcal{X}}
\theoremstyle{definition}
\newtheorem{prob}{Problem}
\newtheorem{extraProb}{Extra Problem}

\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\cone}{cone}
\DeclareMathOperator{\ext}{ext}




\begin{document}
 \thispagestyle{empty}
\begin{center} {\large \textbf{Math 409 -- Homework  9}} \smallskip \\ 
Due on Thursday, May 9\ \\ \ \\
 \end{center}

You are welcome to talk with other students in the class about problems but should write up solutions on your own. 
Solutions can be handwritten or typed but need to be legible and submitted via Gradescope by the end of the day 
on Thursday. You should justify all your answers in order to receive full credit.  


\bigskip 



\begin{prob}
Consider the linear program
\begin{eqnarray*}
{\rm (P)} \ \ \ \max \; 3x_1+4x_2 & s.t.& \\
2 x_1 + 3 x_2 &\leq& 8 \\
x_1 - 3 x_2&\leq& 6 \\
-3 x_1 - x_2 & \leq&-1 \\
3x_1  - 2x_2 &\leq& 10 
\end{eqnarray*}
\begin{itemize}
\item[(a)] Draw the feasible region of (P) in $\R^2$ and find an optimal solution $x^*$ (using any method you like).  \smallskip
\item[(b)] State the dual linear program and find an optimal solution $y^*$ for the dual. \smallskip
\item[(c)] Find a point $\tilde{x}^*\in \Z^2$ maximizing $3x_1+4x_2$ over all \emph{integer} feasible points of (P).  
\end{itemize}
\end{prob}

\bigskip 
\bigskip 



\begin{prob}
Let $G=(V,E)$ be a connected graph and consider the polytope 
\[P_G = \left\{x \in \R_{\geq 0}^E : \sum_{e\in E}x_e = |V|-1 \text{ and }  \sum_{e\in E(S)}x_e \leq |S|-1 \text{ for all } 
S\subset V \text{ with }|S|\geq 2 \right\}\]
where $E(S)$ denotes the set of edges both of whose vertices belong to $S$. For a subset $T\subseteq E$, let ${\bf 1}_T$ denote the vector in $\R^E$ with 
$({\bf 1}_T)_e = 1$ for $e\in T$ and $({\bf 1}_T)_e=0$ for $e\not\in T$. 
\begin{itemize}
\item[(a)] Show that for any spanning tree $T$ of $G$, ${\bf 1}_T$ belongs to $P_G$. \smallskip 
\item[(b)] Show that any integer point in $P_G$ has the form  ${\bf 1}_T$ for some spanning tree $T$ of $G$. \smallskip
\end{itemize}
\emph{Remark}: In fact, the vertices of $P_G$ are precisely $\{{\bf 1}_T: T\text{ is a spanning tree of } G\}$, but you do not have to prove this. 
\end{prob}


\bigskip 
\bigskip 

\emph{Problem 3 on the next page. }
\pagebreak 




\begin{prob}
We study a system of a primal and dual LP in a different form than 
the one in the lecture. Consider
\[
  \begin{array}{rclcrcl}
{\rm (P)} \ \ \  \max c^Tx &  s.t.  &	&    & {\rm (D)} \ \ \  \min b^Ty &  s.t.  &   \\
  Ax     &\leq& b &  \hspace{1.5cm} \textrm{and} \hspace{1.5cm}{} &       y^TA &\geq& c^T \\
  x      &\geq& 0 &              &        y &\geq& 0
\end{array}
\]
\begin{enumerate}
\item[(a)] Give a direct proof that (P) $\leq$ (D). That is, prove $c^Tx \leq y^Tb$  directly from the assumption that $Ax \leq b, x \geq 0, y^TA \geq c^T, y \geq 0$, without relying on any theorem from the lecture. \smallskip
\item[(b)] Show that when both systems are feasible, the optimum values for (P) and (D) are the same.\smallskip \\
\emph{Hint:} Rewrite (P) and (D) as equivalent systems of the form 
 $\max\{ \tilde{c}^T\tilde{x} \mid \tilde{A}\tilde{x} \leq \tilde{b} \}$
and $\min\{ \tilde{b}^T\tilde{y} \mid \tilde{y}^T\tilde{A} = \tilde{c}^T, \tilde{y} \geq 0 \}$ and use the result
from the lecture. 
\end{enumerate}


\end{prob}


%
%\begin{prob}
%Let $x_1,\ldots,x_k \in \R^n$ be vectors and let $P := \textrm{conv}\{ x_1,\ldots,x_k\}$. 
%Prove that if the origin $\bm{0} = (0,\ldots,0)$ is not in $P$, then there is 
%a vector $c \in \R^n$ with $c^Tx_i \geq 1$ for all $i=1,\ldots,k$. 
%\emph{Hint:} Apply the hyperplane separation theorem.
%\end{prob}
%

\end{document}