\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}
\usetikzlibrary{decorations.markings,arrows}

\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  7}} \smallskip \\ 
Due on Thursday, May 23\ \\ \ \\
 \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 

\bigskip 


\begin{prob} Let $G=(V,E)$ be a graph. We say that a subset $S\subseteq V$ is a \emph{stable set} if $|e\cap S| \leq 1$ for all $e\in E$ (that is, there are no edges between vertices in $S$). \smallskip 
\begin{itemize}
\item[(a)] Show that the following integer program finds the size of the largest stable set in $G$: 
\[
\max \sum_{v\in V} x_v \ \ \text{ s.t. } x_v\in \{0,1\}  \text{ for all } v\in V \ \text{ and } \ x_u + x_v \leq 1  \text{ for all } \{u,v\} \in E. \smallskip 
\]
\item[(b)] Show that if $G$ is bipartite, the following linear program finds the size of the largest stable set in $G$: 
\[
\max \sum_{v\in V} x_v \ \ \text{ s.t. } 0 \leq x_v\leq 1 \text{ for all } v\in V \ \text{ and } \ x_u + x_v \leq 1  \text{ for all } \{u,v\} \in E.
\]
\end{itemize} 
\end{prob}

\bigskip 

\bigskip 


\begin{prob}
Run the Branch \& Bound algorithm to solve the integer program
\[
 \max \; 3x_1 + x_2 \text{ s.t. }   -2x_1+3x_2 \leq 6, \ 10x_1 + 4x_2 \leq 27, \  x_1 \geq 0, \  2x_2 \geq 1 \ \text{ and } \
 x_1, x_2 \in \Z
\]
and give the Branch \& Bound tree. You do not need to show work for solving the intermediary linear programs. 
\end{prob}





\vfill



\begin{prob}
The Branch \& Bound algorithm uses linear programming as a relaxation to solve integer linear programs. Actually, the arguments behind the algorithm would work in different settings where the ``relaxation'' is not 
in form of a linear program. 

Consider a slight variant of the TSP problem, called {\sc TSP Path}. 
For the {\sc TSP Path} problem, the input is an undirected graph $G = (V,E)$ 
with non-negative edge costs $c : E \to \R_{\geq 0}$. The cost of a set of edges $C \subseteq E$ is the sum of the individual edge costs, denoted $c(C) = \sum_{e \in C} c(e)$ 
The goal is to compute a path $P \subseteq E$ that visits each node exactly once (with any pair of vertices as end points) while minimizing the cost $c(P)$. (This problem is NP-complete!) 
We want to design a variant of the Branch \& Bound algorithm to solve it. For a subset of edges $E' \subseteq E$, let ${\rm MST}(E')$ be a minimum spanning tree in the subgraph $(V,E')$, which can be computed in polynomial time using Kruskal's algorithm.  
\pagebreak 

Consider the following algorithm:   
\begin{enumerate}
\item[(1)] Set $C^*$ as  ${\tt undefined}$
\item[(2)] Initialize a stack $\mathcal{S} = \{ E\}$ 
\item[(3)] While $\mathcal{S}$ is non-empty do:
  \begin{enumerate}
  \item[(4)] Select $E'$ from the stack $\mathcal{S}$ and remove it from $\mathcal{S}$.
  \item[(5)] If the graph $(V,E')$ is not connected, return to (3)
  \item[(6)] Compute $T := {\rm MST}(E')$ 
  \item[(7)] If $T$ is a path and $c(T) < c(C^*)$ (or $C^*$ undefined) then update $C^* := T$ and return to (3)
  \item[(8)] If  $c(T) \geq c(C^*)$ then return to (3)
  \item[(9)] Let $v \in V$ be a node that is incident to at least 3 edges in $T$. 
  \item[(10)] Let $\{ e_1,e_2,e_3\} \subseteq \delta(v) \cap T$ be 3 edges that are incident to $v$ in $T$. 
  \item[(11)] Put the sets $E' \setminus \{ e_1\}, E' \setminus \{ e_2 \}, E' \setminus \{ e_3\}$ on the stack
  \end{enumerate}
\item[(12)] Return $C^*$
\end{enumerate} 

\ \\

Do the following: 

\begin{itemize}
\item[(a)] Run this algorithm on the following graph with $c(e_j)=1$ for $j\neq 7$ and $c(e_7)=2$:
\begin{center}
\begin{tikzpicture}
\node[circle,fill=black,inner sep=2pt]  (1) at (0, 0) {};  
\node[circle,fill=black,inner sep=2pt] (2) at (1,1) {};  
\node[circle,fill=black,inner sep=2pt] (3) at (2, 1) {};  
\node[circle,fill=black,inner sep=2pt] (4) at (3, 0) {};  
\node[circle,fill=black,inner sep=2pt] (5) at (4, 0) {};  
\node[circle,fill=black,inner sep=2pt] (6) at (2, -1) {};  
\node[circle,fill=black,inner sep=2pt] (7) at (1, -1) {}; 
\draw[thick] (1)--(2)--(3)--(4)--(6)--(7)--(1);
\draw[thick] (4)--(5);
\path (1) edge node[above]  {$e_1$} (2);
\path (2) edge node[above] {$e_2$}  (3);
\path (3) edge node[above]  {$e_3$}  (4);
\path (4) edge node[above]  {$e_4$}  (5);
\path (4) edge node[below]  {$e_5$}  (6);
\path (6) edge node[below]  {$e_6$}  (7);
\path (7) edge node[below]  {$e_7$}  (1);

\end{tikzpicture}   
\end{center}

\item[(b)] Show that this algorithm computes an optimum solution to the {\sc TSP Path} problem (for general graphs). 
In particular, if an optimal TSP path is contained in $E'$, then why is it also contained in at least one of the edge sets that are added back to the stack in (11)? 
Also, why can we stop searching within $E'$ in steps (5) and (8)?
\end{itemize}
\end{prob}




%\begin{prob}[Min-cost Max-Flow]
%Given a  $G = (V,E)$ with $s,t\in V$ and edge capacities $c:E\to \Z_{\geq 0}$, let $v$ denote the
%the maximum value of an $s$-$t$ flow on $G$. 
%\begin{itemize}
%\item[(a)] Give a description of $\{s$-$t\text{ flows }f:E\to \R_{\geq 0}\text{ with }{\rm value}(f) = v\}$ as a polyhedron.\smallskip 
%\item[(b)] We can also associate a cost function $k:E\to \R_{\geq 0}$, where $k(e)$ is the cost of sending one unit across edge $e$. 
%The total cost of a flow $f:E\to \R_{\geq0}$ is $\sum_{e\in E}k(e)f(e)$. 
%Describe the problem of finding a minimum cost $s$-$t$ flow of value $v$ as a linear program.\smallskip 
%\item[(c)] Show there is an integer optimal solution to the problem from (b).  \smallskip 
%\item[(d)] Find a min-cost max-flow of the following graph. The edges are labeled with their capacities. 
%The costs are given by $k(e) = 1$ for all $e\in E$. 
%\begin{center}
%\begin{tikzpicture}[
%    decoration={markings,mark=at position 0.6 with {\arrow{triangle 60}}}, scale=1
%    ]
%\node[circle,draw] (s) at (0, 1) {$s$}; 
%\node[circle,draw] (a) at (1,2) {$a$}; 
%\node[circle,draw] (b) at (1, 0) {$b$}; 
%\node[circle,draw] (c) at (3,2) {$c$}; 
%\node[circle,draw] (d) at (3,0) {$d$}; 
%\node[circle,draw] (t) at (4,1) {$t$}; 
%\draw[postaction={decorate}] (s) -- node[above]{$2$} (a);
%\draw[postaction={decorate}] (s) -- node[below]{$2$} (b);
%\draw[postaction={decorate}] (a) -- node[right]{$1$} (b);
%\draw[postaction={decorate}] (d) -- node[left]{$1$} (c);
%\draw[postaction={decorate}] (a) -- node[above]{$1$} (c);
%\draw[postaction={decorate}] (b) -- node[above]{$1$} (d);
%\draw[postaction={decorate}] (c) -- node[above]{$1$} (b);
%\draw[postaction={decorate}] (c) -- node[above]{$2$} (t);
%\draw[postaction={decorate}] (d) -- node[above]{$2$} (t);
%\end{tikzpicture}
%\end{center}
%\end{itemize}
%\end{prob}

\end{document}