% \def\solutionMode{TRUE}
\documentclass[11pt]{article} \usepackage{573}
%
\newcommand{\PathSet}{\EuScript{P}}
% \newcommand{\Graph}{\EuScript{G}}
\newcommand{\CostX}[1]{\mathsf{c}_{#1}}
% ======================================================================
\begin{document}
% \thispagestyle{empty}
% \headers{\Course{}}{Homework 0 (due 8/30/07)}{\Semester{}}
\begin{center} {\LARGE\bf \Course{}: \CourseName{}, \Semester{}}
\\[1ex]
{\Large\bf Homework 4, due Monday, November 11, 23:59:59, \Year}
\\[0.25in]
{\Large\bf Version 1.01}
\end{center}
% ----------------------------------------------------------------------
\medskip
\noindent
Neatly print your name(s), NetID(s) on each submitted question.
Remember that you have to submit each question on a separate
page. each student should submit his own homework. If you are on
campus, submit the homework by submitting it in the homework boxes in
the basement of SC.
% ----------------------------------------------------------------------
\bigskip
% ----------------------------------------------------------------------
% \newpage \thispagestyle{empty}
\noindent\fbox{\begin{minipage}{0.99\linewidth} \footnotesize%
Shortly after the celebration of the four thousandth
anniversary of the opening of space, Angary J. Gustible
discovered Gustible's planet. The discovery turned out to be a
tragic mistake.
Gustible's planet was inhabited by highly intelligent life
forms. They had moderate telepathic powers. They immediately
mind-read Angary J. Gustible's entire mind and life history,
and embarrassed him very deeply by making up an opera
concerning his recent divorce.
$~$~~~~~~~~~~~~~ -- From Gustible's Planet, Cordwainer Smith
\end{minipage}}
\section*{Required Problems}
% \newcommand{\HWProblem}[3]{\item \textsc{#1}\\
% #2}
\newcommand{\GreedyIndep}{\Algorithm{Greedy{}I{n}d{e}p}}
\renewcommand{\th}{th\xspace}
% ======================================================================
\begin{compactenum}[\color{red} \huge \bf 1.]%
\item \HWProblem{40}{Tedious Computations}{
% \points{20}
\begin{enumerate}[(A)]
\item \points{10} Let $L$ be a linear program given in
slack form, with $n$ nonbasic variables $N$, and $m$ basic
variables $B$. Let $N'$ and $B'$ be a different partition
of $N \cup B$, such that $\cardin{N' \cup B' } = \cardin{N
\cup B}$. Show a polynomial time algorithm that computes
an equivalent slack form that has $N'$ as the nonbasic
variables and $b'$ as the basic variables. How fast is your
algorithm?
\item \points{3} You are given a weighted, directed graph
$G = (V, E)$, with weight function $w : E \rightarrow
\mathcal{R}$ mapping edges to real-valued weights, a source
vertex $s$, and a destination vertex $t$. Show how to
compute the value $d[t]$, which is the weight of the
shortest weighted path from $s$ to $t$, by using linear
programming.
\item \points{3} \\
Given a graph $G$ as in (A), write a single linear program
that by solving it you compute $d[v]$, which is the
shortest-path weight from $s$ to $v$, for ell the vertices
$v \in V$.
\item \points{4} \\
In the {\em minimum-cost multicommodity-flow problem}, we
are given a directed graph $G = (V, E)$, in which each edge
$(u, v) \in E$ has a nonnegative capacity $c(u, v) \geq 0$
and a cost $\alpha(u, v)$. As in the multicommodity-flow
problem (Chapter 29.2, CLRS), we are given $k$ different
commodities, $K_1$, $K_2$, \ldots, $K_k$, where commodity
$i$ is specified by the triple $K_i = (s_i, t_i,
d_i)$. Here $s_i$ is the source of commodity $i$, $t_i$ is
the sink of commodity $i$, and $d_i$ is the demand, which
is the desired flow value for commodity $i$ from $s_i$ to
$t_i$. We define a flow for commodity $i$, denoted by
$f_i$, (so that $f_i(u, v)$ is the flow of commodity $i$
from vertex $u$ to vertex $v$) to be a real-valued function
that satisfies the flow-conservation, skew-symmetry, and
capacity constraints. We now define $f(u, v)$, the
\emphic{aggregate flow}, to be sum of the various commodity
flows, so that $f(u, v) = \sum_{i=1}^{k}f_i(u, v) $. The
aggregate flow on edge $(u, v)$ must be no more than the
capacity of edge $(u, v)$.
The cost of a flow is $\sum_{u, v \in V} f(u, v) \alpha(u,
v) $, and the goal is to find the feasible flow of minimum
cost. Express this problem as a linear program.
\item \points{5}
Provide {\em detailed} solutions for the following
problems, showing each pivoting stage separately.
maximize $6x_1 + 8x_2 + 5x_3 + 9x_4$\\
subject to\\
$2x_1 + x_2 + x_3 + 3x_4 \leq 5$\\
$x_1 + 3x_2 + x_3 + 2x_4 \leq 3$\\
$x_1, x_2, x_3, x_4 \geq 0$.
\item \points{5}\\
maximize $2x_1 + x_2$\\
subject to\\
$2x_1 + x_2 \leq 4$\\
$2x_1 + 3x_2 \leq 3$\\
$4x_1 + x_2 \leq 5$\\
$x_1 + 5x_2 \leq 1$\\
$x_1, x_2 \geq 0$.
\item \points{5}\\
maximize $6x_1 + 8x_2 + 5x_3 + 9x_4$\\
subject to\\
$x_1 + x_2 + x_3 + x_4 = 1$\\
$x_1, x_2, x_3, x_4 \geq 0$.
\item \points{5}\\
minimize $x_{12} + 8x_{13} + 9x_{14} + 2x_{23}
+ 7x_{24} + 3x_{34}$\\
subject to\\
$x_{12} + x_{13} + x_{14} \geq 1$\\
$-x_{12} + x_{23} + x_{24} = 0$\\
$-x_{13} - x_{23} + x_{34} = 0$\\
$x_{14} + x_{24} + x_{34} \leq 1$\\
$x_{12}, x_{13}, \ldots, x_{34} \geq 0$.
\end{enumerate}%
}{}{}
\item \HWProblem{30}{Linear programming}{
% \points{20}
\begin{enumerate}[(A)]
\item \points{15} Show the following problem in NP-hard.
\NPProblem{Integer Linear Programming} {A linear program in
standard form, in which $A$ and $B$ contain only
integers.} {Is there a solution for the linear program,
in which the $x$ must take integer values?}
\item \points{5} A steel company must decide how to
allocate next week's time on a rolling mill, which is a
machine that takes unfinished slabs of steel as input and
produce either of two semi-finished products: bands and
coils. The mill's two products come off the rolling line at
different rates:
\begin{center}
Bands 200 tons/hr\\
Coils 140 tons/hr.
\end{center}
They also produce different profits:
\begin{center}
Bands \$ 25/ton\\
Coils \$ 30/ton.
\end{center}
Based on current booked orders, the following upper bounds
are placed on the amount of each product to produce:
\begin{center}
Bands 6000 tons\\
Coils 4000 tons.
\end{center}
Given that there are 40 hours of production time available
this week, the problem is to decide how many tons of bands
and how many tons of coils should be produced to yield the
greatest profit. Formulate this problem as a linear
programming problem. Can you solve this problem by
inspection?
\item \points{10} A small airline, Ivy Air, flies between
three cities: Ithaca (a small town in upstate New York),
Newark (an eyesore in beautiful New Jersey), and Boston (a
yuppie town in Massachusetts). They offer several flights
but, for this problem, let us focus on the Friday afternoon
flight that departs from Ithaca, stops in Newark, and
continues to Boston. There are three types of passengers:
\begin{enumerate}
\item Those traveling from Ithaca to Newark (god only
knows why).
\item Those traveling from Newark to Boston (a very
good idea).
\item Those traveling from Ithaca to Boston (it depends
on who you know).
\end{enumerate}
The aircraft is a small commuter plane that seats 30
passengers. The airline offers three fare classes:
\begin{enumerate}
\item Y class: full coach.
\item B class: nonrefundable.
\item M class: nonrefundable, 3-week advanced purchase.
\end{enumerate}
Ticket prices, which are largely determined by external
influences (i.e., competitors), have been set and
advertised as follows:
\begin{center}
\begin{tabular}{l|rrr|}
& Ithaca-Newark & Newark-Boston & Ithaca-Boston\\
\hline
Y & 300 & 160 & 360\\
B & 220 & 130 & 280\\
M & 100 & 80 & 140\\
\hline
\end{tabular}
\end{center}
Based on past experience, demand forecasters at Ivy Air
have determined the following upper bounds on the number of
potential customers in each of the 9 possible
origin-destination/fare-class combinations:
\begin{center}
\begin{tabular}{l|rrr|}
& Ithaca-Newark & Newark-Boston & Ithaca-Boston\\
\hline
Y & 4 & 8 & 3\\
B & 8 & 13 & 10\\
M & 22 & 20 & 18\\
\hline
\end{tabular}
\end{center}
The goal is to decide how many tickets from each of the 9
origin/destination/fare-class combinations to sell. The
constraints are that the place cannot be overbooked on
either the two legs of the flight and that the number of
tickets made available cannot exceed the forecasted maximum
demand. The objective is to maximize the revenue. Formulate
this problem as a linear programming problem.
\end{enumerate}
}{}
\item \HWProblem{30}{Strong duality.}{% \points{20}
Consider a directed graph $\Graph$ with source vertex $s$ and
target vertex $t$ and associated costs $\CostX{\cdot}\geq 0$ on
the edges. Let $\PathSet$ denote the set of all the directed
(simple) paths from $s$ to $t$ in $\Graph$.
Consider the following (very large) integer program:
\begin{align*}
\text{minimize} ~~~& \sum_{e \in E(\Graph)} \CostX{e} x_e \\
\text{subject to} ~~~& x_e \in \brc{0,1} \;\;\;\; \forall e
\in
E(\Graph)\\
& \sum_{e \in \pi} x_e \geq 1 \;\;\;\;\; \forall \pi \in
\PathSet.
\end{align*}
\begin{enumerate}[(A)]
\item \points{5} What does this IP computes?
\item \points{5} Write down the relaxation of this IP into
a linear program.
\item \points{10} Write down the dual of the LP from
(B). What is the interpretation of this new LP? What is it
computing for the graph $\Graph$ (prove your answer)?
\item \points{10} The strong duality theorem states the
following.
\centerline{\fbox{
\begin{minipage}{0.8\linewidth}
\begin{theorem}
If the primal LP{} problem has an optimal
solution
$x^{*}=\pth{x_{1}^{*},\ldots,x_{n}^{*}}$ then
the dual also has an optimal solution,
$y^{*}=\pth{y_{1}^{*}, \ldots, y_{m}^{*}}$,
such that
\[
\sum_{j}c_{j} x_{j}^{*}=
\sum_{i}b_{i}y_{i}^{*}.
\]
% \theolab{strong:duality}
\end{theorem}
\end{minipage}}}
In the context of (A)-(C) what result is implied by this
theorem if we apply it to the primal LP and its dual above?
(For this, you can assume that the optimal solution to the
LP of (B) is integral -- which is not quite true -- things
are slightly more complicated than that.)
\end{enumerate}
}{}{}
%----------------------------------------------------------------------
\end{compactenum}
\end{document}
%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------