% $Header: /home/rdv/quantum/genetic-paper/RCS/eaqc-paper.tex,v 1.12 2005/05/29 21:34:00 rdv Exp rdv $
% now how do I set the paper size?
% \documentclass[twocolumn]{article}

\documentclass[onecolumn,doublespace]{article}
%\documentclass{acm_proc_article-sp-no-copyright}
% \usepackage{usenix,times}
\usepackage{times}
%\usepackage{times}
\usepackage{graphics}
\usepackage{lscape}
\usepackage{subfigure}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsmath,amsfonts,amssymb}
%\setlength{\textwidth}{6in}
%\setlength{\textheight}{9in}
%\setlength{\oddsidemargin}{0.25in}

\pagestyle{plain}

\bibliographystyle{unsrt}

% \input{psfig}
\input{epsf}
% \epsfverbosetrue

\newcommand{\icol}[1]{% inline column vector
  \left(\begin{smallmatrix}#1\end{smallmatrix}\right)%
}

\newcommand{\irow}[1]{% inline row vector
  \begin{smallmatrix}(#1)\end{smallmatrix}%
}

\begin{document}
\title{Optimization Theory (DS2) HW\#3\\
  Polytopes, Bases, and Canonical Form (\emph{Almost} to the Full
  Simplex Algorithm!)}
\maketitle

Problems and page numbers from the paperback edition of \emph{A Gentle
  Introduction to Optimization}, by B. Guenin \emph{et al.}


\begin{enumerate}
\item Consider the polytope:
  \begin{enumerate}
    \item If we have a two-variable (two-dimensional) problem with $k$
      constraints, what is the maximum number of vertices and edges of
      our polygon?  (Easy.)
    \item If we have a three-variable (three-dimensional) problem with
      $k$ constraints, what is the maximum number of faces, vertices
      and edges of our polyhedron?  (Still pretty easy, please do this
      yourself, not google it.)
    \item If we have an $n$-variable ($n$-dimensional) problem with
      $k$ constraints, what is the maximum number of vertices and
      edges of our polytope?  (Yes, this requires you to think in more
      than three dimensions a bit.  See if you can figure this out,
      rather than just googling the answer.  If you \emph{must} google
      up the answer -- or, better yet, go to the library and look in
      an actual book -- be sure to cite where you got it.)
  \end{enumerate}
\item Canonical form: In Secs. 3.1 and 3.2 of the lecture notes for
  Lecture \#4, we had the R and Octave code for changing the
  \emph{constraint matrix} on our problem.  Your goal here is to
  produce the equivalent code (in R, Octave, Mathematica, or some
  other language I can read) to complete this transformation of our
  problem.
  \par
  This should be done just for the same problem in Eqs. 2-4 of the
  lecture notes, showing me that you know how to get Eqs. 11-13.  Just
  solving this single problem ad hoc using the interpreter is fine,
  you don't need to write fully general functions here.
  \par
  Please show me that your code works!  Capturing a screen shot is a
  reasonable thing to do, or copy-paste into a document (submit PDF,
  not Word) or even copy-paste directly into SFS will probably be
  adequate for this problem (but not for most of the others in this
  homework set).
  \begin{enumerate}
  \item We already did the constraint matrix, but not the constraint
    values vector $\vec{b}$.  Calculate the new $\vec{b'}$, following
    Eq. 28.
  \item Calculate the new objective function
    $\operatorname{max}\{\vec{z'}\}$ following Eq. 21, using
    Eqs. 24-27 from the lecture notes.
  \item Now write out the new, complete LP, including the objective
    function, constraint equations, and non-negativity constraints.
    (You'll need math markup for this, so no pure text -- i.e., you
    can't submit this one directly in SFS.)
  \end{enumerate}
\item (Problem 2 in Sec. 2.4 of the textbook.)\\
  The following LP is in SEF:
\begin{align}
  & \operatorname{max}\{(1, -2, 0, 1, 3)\vec{x}\} \\
  \textrm{subject to} & \nonumber\\
  & \left(
    \begin{array}{ccccc}
      1 & -1 & 2 & -1 & 0 \\
      2 & 0 & 1 & -1 & 1
    \end{array}
  \right)\vec{x} = 
 \left(
    \begin{array}{c}
      1 \\
      -1
    \end{array}
  \right) \\
  & \vec{x} \ge \vec{0}
\end{align}
Find an equivalent LP in canonical form for:
  \begin{enumerate}
    \item the basis \{1, 4\}.
    \item the basis \{3, 5\}.
    \end{enumerate}
In each case, state whether the basis (i.e., the corresponding basic
solution) is feasible.
\end{enumerate}

\end{document}
