\documentclass[11pt]{article}
\input{../../preamble}
\usepackage{amsmath, latexsym}
\begin{document}
\problemset{6}{October 3, 2014}{6}{October 10, 2014}
\begin{enumerate}
\item (7 points) When I was a researcher at IBM, I once needed to solve several linear programs that had a very large number of constraints relative to the number of variables\footnote{For those of you who are interested, these LPs were the basis of the paper by Trevisan, Sorkin, Sudan, and Williamson, ``Gadgets, Approximation, and Linear Programming,'' {\em SIAM Journal on Computing} 29:2074-2097, 2000.}. I was trying to solve $\min c^Tx: Ax \leq b, x \geq 0$, for $A \in \Re^{m \times n}$, where $m$ was exponential in $n$. To get this into standard form, add slack variables $s$ for each constraint, so that the problem becomes $\min c^Tx: Ax + s = b, x \geq 0, s \geq 0$. The running time for solving each LP was several hours. I wandered down the hall and asked John Forrest, the author of IBM's linear programming code (OSL), if there was anything I could do to speed up the solution time. He suggested a simple reformulation of my problem that dropped the running time to under 20 minutes. Try to explain a change such that the simplex method as we have described it (running on the primal in standard form) might run much more quickly in such a situation. Be sure to justify your answer; that is, you should explain why the reformulation would cause the simplex method to run more quickly. (Hint: think about the complexity of a pivot operation).
\item (Bertsimas and Tsitsiklis 3.6) Let $x$ be a basic feasible solution with associated basis $B$. Prove the following:
\begin{enumerate}
\item (4 points) If the reduced cost of every nonbasic variable is positive, then $x$ is the unique optimal solution.
\item (4 points) If $x$ is the unique optimal solution and is nondegenerate, then the reduced cost of every nonbasic variable is positive.
\end{enumerate}
\item Consider the linear program $\min (c x : x \ge 0, Ax=b)$.
Let $B$ denote an optimal basis. Assume that the problem is generic in
that each vertex has a unique basis for which it is the corresponding basic
solution.
Assume now that you want to solve
a {\em parametric} problem, i.e., a set of problems of the form
$\min ((c +\lambda d) x : x \ge 0, Ax=b)$, for each possible value
of $\lambda \ge 0$. The basis $B$ is a solution for the problem when
$\lambda=0$.
\begin{enumerate}
\item (7 points) Prove that the set of values of $\lambda$ for which basis $B$ is
optimal forms an interval $[0,a_1]$. Explain how to compute $a_1$.
\item (10 points) Show that there is a finite set $a_0=0 \le a_1 \le \ldots \le a_k$ and
corresponding bases $B_i$ for $i=0, \ldots, k$ such that $B_0=B$ and
$B_i$ (for $i=0,\ldots,k$) is the optimal basis if and only if
$\lambda \in [a_i,a_{i+1}]$, and $B_k$ is optimal if $\lambda \ge a_k$.
\end{enumerate}
\end{enumerate}
\end{document}