\documentclass[11pt]{article}
\input{../../preamble}
\usepackage{amsmath, latexsym}
\begin{document}
\problemset{9}{November 3, 2014}{9}{November 7, 2014}
\begin{enumerate}
\item
(10 points) Consider the following version of the cutting stock problem. There is
a demand $b_i$ for every size $s_i$ and a width $W$ for the raw material,
just in the version discussed in class. Change the method from class
to work with the following version instead: customers have a 10\% tolerance
in the order, that is, all the solution has to satisfy is a demand some place
between $.9b_i$ and $1.1b_i$ for every size $s_i$ and whatever produced
will be bought by the customers. Last time we were minimizing the number
of width $W$ raws used. Suppose you are given $N$ (the number of raws you have), and instead you want to maximize the amount of demand satisfied, i.e., if your
solution produces $p_i$ finals of size $s_i$, then you must have that
$.9b_i \le p_i \le 1.1 b_i$ and your goal is
to maximize $\sum_i p_i$. Explain how to modify the solution discussed
in class to solve this problem.
\item (15 points) Recall the maximum multicommodity flow problem given on the previous problem set. In this problem we are given a directed graph $G$ with nodes $V$ and directed arcs $A$, and $k$ source-sink pairs $(s_i,t_i)$, where $s_i, t_i \in V$ for $i = 1,\ldots, k$. We may send flow only from a source $s_i$ to the corresponding sink $t_i$. The goal is to send as much flow as possible from the sources $s_i$ to their corresponding sinks $t_i$. Each arc $a \in A$ has a capacity $u_a$; we may not send more than $u_a$ total units of flow through arc $a$.
On the last problem set, we used a linear programming formulation of the problem in which there is a variable $x_P$ for each $s_i$-$t_i$ path $P$. However, this isn't the only possible linear programming formulation of the problem.
\begin{enumerate}
\item (5 points) Give another linear programming formulation of the problem which uses variables $f^i_{uv}$ to indicate the amount of flow being sent from $s_i$ to $t_i$ using arc $(u,v) \in A$.
\item (8 points) If you've set up your linear programming formulation correctly in the part above, you'll notice that it can be solved via a Dantzig-Wolfe decomposition. What are the linking constraints? What are the associated subproblems? What is an extreme point of the subproblem? How can you tell whether the master problem has a negative reduced cost variable?
\end{enumerate}
\end{enumerate}
\end{document}