% $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}
\usepackage{times}
\usepackage{graphics}
\usepackage{lscape}
\usepackage{subfigure}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{kbordermatrix,blkarray}
\usepackage[ruled,linesnumbered,vlined]{algorithm2e} 
\pagestyle{plain}

\bibliographystyle{unsrt}   %>>>> makes bibtex use spiebib.bst

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

%\def\comment#1{$\Rightarrow${\small\em #1}}
\def\comment#1{}
\newenvironment{chapterquote}
  {\begin{quotation}
      \sf}
  {\end{quotation}}
\def\cq#1#2{\begin{chapterquote}#1\flushright\textbf{#2}\end{chapterquote}}


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

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

\SetAlgoCaptionSeparator{.1}


\begin{document}
\title{Simplex Algorithm
}
\maketitle
\begin{abstract}
  This is pseudocode for the core of the Simplex Algorithm, adapted
  from \emph{A Gentle Introduction to Optimization}.
\end{abstract}

\begin{algorithm}
\setcounter{algocf}{1}
\caption{Simplex Algorithm}
\label{algo2}

\AlgoDisplayBlockMarkers\AlgoDisplayGroupMarkers\SetAlgoBlockMarkers{ \{}{ \}\ }%
\SetAlgoNoEnd\SetAlgoNoLine

\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\Input{Linear program (P) and feasible basis $B$}
\Output{An optimal solution for (P) or a certificate proving that (P) is unbounded }
Rewrite (P) so that it is in canonical form for the basis $B$\\
Let $\vec{x}$ be the basic feasible solution for $B$\\
\If{$\vec{c_N} \le \vec{0}$}{
{\bf stop}\\
($\vec{x}$ is optimal)
}
Select $k \in N$ such that $c_k > 0$\\
\If{$A_k \le \vec{0}$}{
{\bf stop}\\
((P) is unbounded)
}
Let \emph{r} be any index \emph{i} where the following minimum is attained:\\
\begin{equation}
t = \operatorname{min}\left\{\frac{b_i}{A_{i,k}}:A_{i,k} > 0\right\}
\end{equation}
\\
Let $\iota$ be the $r^{th}$ basis element\\
Set $B:=B\cup\{k\}$\textbackslash$\{\iota\}$\\
Go to step 1

\end{algorithm}

Notes:

\begin{enumerate}
\item Recall $\vec{c}$ is the vector of coefficients in our objective
  function $z(\vec{x})$, and $c_k$ is the $k$th element of $\vec{c}$.
\item $\vec{c_N}$ is $\vec{c}$ with the columns corresponding to basis
  $B$ removed.
\item $A$ is the $m\times n$ matrix with linearly independent rows
  that comprise our constraints.  $A_k$ is the $k$th column of $A$ (a
  vector, though we aren't writing it with the arrow above), and $A_B$
  or $A_N$ is a matrix comprised of a subset of the columns of $A$,
  keeping them in the original order.
\end{enumerate}

\end{document}
