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

\def\vx{\mathbf{x}}
\def\vc{\mathbf{c}}
\def\vb{\mathbf{b}}
\def\vy{\mathbf{y}}
\def\vs{\mathbf{s}}
\def\vz{\mathbf{z}}
\def\vw{\mathbf{w}}

\begin{document}

\thispagestyle{empty}



\begin{center}
	\Large\bf MATH 482, Spring 2013 - Homework 1 - Solutions
\end{center}


\textbf{1.} (\emph{Assigned!}, 5pts)  Convert the following (general form) linear program into standard and canonical form:

\[\begin{array}{rccccccccl}
	\max & 3x_1 & - & 2x_2 & & & + & x_4 & \\
	\text{subject to} & x_1 & + & x_2 & - & x_3 & & & \geq & 1\\
	& & & 2x_2 & && + & x_4 &= & 0\\
	& && && x_3&-&3x_4& \leq & 6\\
	& x_1, & & x_2 &&&&&\geq& 0\\
&	&& && x_3 &&&\leq & 0\\
&	&& && && x_4 & & \text{free}
\end{array}\]

Canonical Form:
\[\begin{array}{rccccccccccl}
	\max & 3x_1 & - & 2x_2 & & & + & x_4^+ & - & x_4^- && \\
	\text{subject to} & x_1 & + & x_2 & + & x_3^- & & &&& \geq & 1\\
	& & & 2x_2 & && + & x_4^+ & - & x_4^- &\geq & 0\\
	& & & -2x_2 & && - & x_4^+ & - & x_4^- &\geq & 0\\
	& && && x_3^-&+&3x_4^+&-&3x_4^-& \geq & -6\\
	& x_1, & & x_2, &&x_3^-,&&x_4^+,&&x_4^-&\geq& 0
\end{array}\]
(Above, $x_3$ is replaced with $x_3^- =-x_3$ and $x_4$ is replaced with $x_4 = x_4^+-x_4^-$. The second constraint is replaced with two inequalities, and the third constraint is reversed.)\\

Standard Form:
\[\begin{array}{rccccccccccccccl}
	\max & 3x_1 & - & 2x_2 & & & + & x_4^+ & - & x_4^- && \\
	\text{subject to} & x_1 & + & x_2 & + & x_3^- & &&&& - & x_5 &&& = & 1\\
	& & & 2x_2 & && + & x_4^+ & - & x_4^- &&&&&= & 0\\
	& && && -x_3^-&-&3x_4^+&+&3x_4^-& &&+&x_6&=& 6\\
	& x_1, & & x_2, &&x_3^-,&&x_4^+,&&x_4^-,&& x_5, &&x_6 &\geq& 0
\end{array}\]
(Above, $x_3$ is replaced with $x_3^- =-x_3$ and $x_4$ is replaced with $x_4 = x_4^+-x_4^-$. The first and third constraints are given slack variables.)\\





\clearpage
\textbf{2.} Consider the linear programming formulation of the shortest paths problem \emph{with positive weights on all edges of the digraph}. (\emph{The statements below are adjusted versions of the questions asked in class.})\\

\quad\textbf{a.} Produce a digraph whose shortest paths linear program has a feasible point with $x_{i,j} > 1$ for some edge $ij$.\\


Consider a cycle graph on three vertices: $s, 2, t$ with edges $s2$, $2t$, and $ts$. 
Let $x_{s,2} = w+1$, $x_{2,t} = w+1$, and $x_{t,s} = w$, and observe that the constraints for the shortest path problem are satisfied (i.e. the amount of edges coming in and out of $2$ are equal, while one more is leaving $s$ and one more is entering $t$). Thus, for $w > 0$ this has $x_{s,2} > 1$.\\


\quad\textbf{b.} (\emph{Assigned!}, 5pts) Prove that for every digraph, every \emph{optimal} solution to the shortest paths linear program has $x_{i,j} \leq 1$ for all edges $ij$.\\

\begin{proof}
Suppose that there exists an edge $ij$ with $x_{i,j} > 1$ in an optimal solution $\vx$ to the shortest paths linear program.
\emph{The Idea:} Since $x_{i,j} > 1$ and all internal vertices have equal amounts of incoming and outgoing edges, there must be a cycle somewhere with positive values on all edges, and that value can be removed, lowering the cost of this solution (so it is not optimal!).
However, finding such a cycle is challenging in this fractional environment, where the ``excess'' value can be split among many different edges whose values are less than 1.
Instead, we will strip away the ``good'' amounts: the values that are actually along $st$-paths.

We will create a list of $st$-paths $P_1,\dots, P_k$ and weights $w_1,\dots,w_k$ with $\sum_{\ell=1}^k w_\ell = 1$ such that the feasible solution $\vx'$ defined as $x_{i,j}' = \sum_{\ell : ij \in E(P_\ell)} w_\ell$ has $x_{i,j}' \leq x_{i,j}$ for all $ij \in E(G)$ and $x_{i,j}' \leq 1$.
Thus, the solution $\vx'$ is feasible and has lower cost than the solution $\vx$ with $x_{i,j} > 1$.

Let $\vx^{(0)} = \vx$. 
For $\ell \geq 1$, if $\vx^{(\ell-1)}$ has more edge-weight leaving $s$ than entering $s$ (i.e. $\sum_{i : si \in E} x_{s,i}^{(\ell-1)} - \sum_{i : is \in E(G)} x_{i,s}^{(\ell-1)} > 0$), we will construct $\vx^{(\ell)}$ by removing weight $w_\ell$ from an $st$-path $P_\ell$.
Let $si_1$ be an edge leaving $s$ with positive value $x_{s,i_1} > 0$.
Since all vertices other than $s$ and $t$ preserve the incoming and outgoing edge weights, we can walk from $si_1$ along a path $si_1i_2i_3\dots$ using edges of positive weight until one of two stopping conditions: (1) we reach $t$, or (2) we reach a vertex already in the path.
If we reach condition (2), then there exists a cycle where every edge has weight at least $w$ for some positive $w$.
By subtracting $w$ from each edge in this cycle, we reduce the cost of the solution and find our solution is not optimal.
Thus, we must always eventually reach the vertex $t$ (our graph is finite, so we must always terminate).
This constructs the path $P_\ell$, and let $w_\ell$ be the minimum value $x_{i,j}$ for edges in $P_\ell$.
We form $\vx^{(\ell)}$ from $\vx^{(\ell-1)}$ by subtracting $w_\ell$ from every edge in $P_\ell$.

Since this process removes all value from at least one edge for each $\ell$ (and there are a finite number of edges) this process will terminate when the edge-weight entering $s$ equals the edge-weight leaving $s$.
Since we removed $\sum_{\ell=1}^k w_\ell$ from the edges leaving $s$, we have $\sum_{\ell=1}^k w_\ell = 1$.
Observe that $\vx'$ as defined above satisfies the properties above, showing that the given $\vx$ is not optimal.
\end{proof}

\clearpage
\quad\textbf{c.}  (\emph{Assigned!}, 5pts) Produce a digraph whose shortest paths linear program has an optimal point where at least one variable $x_{i,j}$ has $0 < x_{i,j} < 1$. (\emph{Hint: Consider what happens when there are multiple optimal solutions to the shortest paths problem.})\\

Consider the digraph on four vertices, $s, 2, 3, t$ and four edges $s2, s3, 2t, 3t$.
Let the weights all be unit weights: $w(s,2) = w(s,3) = w(2,t) = w(3,t) = 1$.
Then, the two paths $s2t$ and $s3t$ are both shortest paths.
Their corresponding solutions are $x_{s,2} = x_{2,t} = 1$, $x_{s,3} = x_{3,t} = 0$ and $x_{s,2}=x_{2,t} = 0$, $x_{s,3} =x_{3,t} = 1$.
Any convex combination of these solutions is an optimal solution to the linear program.
(Specifically, their average $x_{s,2} = x_{s,3} = x_{2,t} = x_{3,t} = \frac{1}{2}$ is an optimal, fractional solution.)



\quad\textbf{d.} Prove that for every digraph there exists an optimal solution to the shortest paths linear program where every variable $x_{i,j}$ has value in $\{0,1\}$. \\

See Implementation Report 0 and the discussion of the dual problem and of Dijkstra's algorithm.
The existence of an integer solution is given by the fact that Dijkstra's algorithm always presents an integer solution to the shortest paths problem with a matching dual solution, showing optimality.





\clearpage
\textbf{3.} Consider the following linear program:

\[
\begin{array}{rrcrcl}
\min & 2x_1 & + & 5x_2 & & \\
\text{subject to} & 3x_1 & + & x_2 & \geq & 6\\
& x_1 & & \geq & \frac{1}{2} \\
& x_1 & + & x_2 & \geq &1 \\
& 2x_1 & + & 5x_2 & \geq & 10 \\
& -x_1 & + & x_2 & \geq & -3\\
& -x_1 & - & x_2 & \geq & -100\\
& x_1, & & x_2 & \geq & 0
\end{array}
\]

\quad\textbf{a.} Plot the constraints and solve the problem graphically.

\vspace{4in}

\quad\textbf{b.} List all of the basic feasible solutions.

\vspace{1in}



\quad\textbf{c.} Characterize the optimal solutions in terms of optimal basic feasible solutions. 

\vspace{1in}



\clearpage
\textbf{4.} ((\emph{Assigned!}, 5pts)  Consider a standard-form linear program P
\begin{align*}
	\min \vc^\top \vx &\\
	\text{subject to } A\vx &= \vb\\
	\vx &\geq {\mathbf{0}} 
\end{align*}
Let D be the dual of P.
Prove that the dual of the dual of P is equivalent to P by forming the dual D, converting D into a standard form problem D', then forming the dual of D' (call it P') and converting P' into standard form.
Here is an outline:
\[
\xymatrix{
	\text{Standard Form problem P} \ar[rr]^{\text{take the dual}} & \qquad & \text{General problem D}\ar[dll]^<{\text{\qquad \qquad \qquad convert to standard form}}\\
	\text{Standard Form problem D'} \ar[rr]_{\text{take the dual}} & \qquad & \text{General problem P'}\ar[ull]_<{\text{\qquad \qquad \qquad convert to standard form}}
}\]

\begin{proof}
Given our standard form linear program P, its dual D is
\begin{align*}
	\max \vb^\top \vy &\\
	\text{subject to } A^{\top}\vy &\leq \vc\\
	\vy &\text{\quad free} 
\end{align*}
To convert D to standard form, we first make $\vy = \vy^+-\vy^-$ and then add slack variables $\vs$ (where $\vs$ has $n$ terms).
Also, negate $\vb$ to find a 
\begin{align*}
	\min \begin{bmatrix}-\vb^\top & \vb^{\top} & {\mathbf 0}^\top\end{bmatrix} \begin{bmatrix}\vy^+\\\vy^-\\\vs\end{bmatrix} &\\
	\text{subject to } \begin{bmatrix}A^{\top} & -A^{\top} & I_n\end{bmatrix}\begin{bmatrix}\vy^+\\\vy^-\\\vs\end{bmatrix} &= \vc\\
	\vy^+, \vy^-, \vs &\geq 0 
\end{align*}
To form the dual D', we find the program P'
\begin{align*}
	\max \vc^\top \vw &\\
	\text{subject to }\begin{bmatrix}A \\ -A\\ I_n\end{bmatrix} \vw &\leq \begin{bmatrix} -\vb \\ +\vb \\ \mathbf{0}\end{bmatrix}\\
	\vw &\text{\quad free}
\end{align*}
Observe that the last $n$ constraints in this system translate to $I_n \vx' \leq \mathbf{0}$.
This implies that $\vx'$ consists of nonpositive variables.
If we replace $\vw$ with $\vz = -\vw$, then the program is equivalent to
\begin{align*}
		\max -\vc^\top \vz &\\
	\text{subject to }\begin{bmatrix}-A \\ +A\end{bmatrix} \vz &\leq \begin{bmatrix} -\vb \\ +\vb \end{bmatrix}\\
	\vz &\geq \mathbf{0}
\end{align*}
Further, the maximization of $-\vc^\top \vz$ is equivalent to minimizing $\vc^\top \vz$.
Also, the pair of constraints $-A\vz \leq -\vb$ and $A \vz \leq \vb$ is equivalent to $A\vz = \vb$.
Thus, the linear program P' is equivalent to the standard form program
\begin{align*}
	\min \vc^\top \vz & \\
	\text{subject to} A\vz &= \vb\\
	\vz &\geq \mathbf{0}
\end{align*}
Which is equivalent to the original program P.
\end{proof}






\end{document} 