\section{The Cutting Plane Algorithm}\label{S:IP_Cutting_Plane}
\setcounter{progress_ck_counter}{0}

\noi \subsection{Motivation}\label{S:Int_Prog_Cutting_Plane_Motivation}

\noi From a graphical perspective, the branch and bound method determines an ILP's solution through a process of repeatedly subdividing the feasible region of the corresponding relaxation LP. The \emph{cutting plane algorithm}, developed by Ralph Gomory\index{Gomory, R.}, also involves an iterative process
of solving LPs. Each new LP consists of its predecessor LP, combined with an additional, cleverly constructed constraint
that ``trims'' the feasible region, so to speak, without removing feasible lattice points.

\newpar Our primary focus will be on pure ILPs (as opposed to MILPs) having the property
 that all constraint bounds and all decision variable coefficients are integer-valued. The
GLKC ILP,

\begin{align}\label{E:Cutting_Plane_kayak1}
 \mbox{maximize } z &=3x_1 +4x_2  \\
	\mbox{ subject to} \notag\\
	2x_1+x_2 &\leq 6 \notag \\
	2x_1 + 3 x_2 &\leq 9  \notag \\
	x_1, x_2 \geq 0 &; x_1,x_2 \in \Z, \notag
	\end{align}
\noi is a simple example of such a problem, and we will use it as a context
for constructing our new technique.

\subsection{The Algorithm}\label{S:Int_Prog_Cutting_Plane_Algorithm}

\noi We begin by adding slack variables, $s_1$ and $s_2$, to the constraints
in (\ref{E:Cutting_Plane_kayak1}) and performing the simplex algorithm
on the relaxation LP. The resulting final tableau is shown in Table
\ref{Ta:Cutting_Plane_kayak1_relaxation}. Note that none of the basic variables are integer-valued.
%\begin{align}\label{E:IP_Cutting_Plane}
% \mbox{maximize } z &=\vecc \cdot \vecx  \notag  \\
%	\mbox{ subject to} \notag\\
%	\left[A | I_3 \right] \begin{bmatrix}  \vecx \\ \vecs  \end{bmatrix} &= \vecb \notag \\
%	\vecx, \vecs  &\geq \zerovec, \notag
%	\end{align}
%where, $\ds A= \begin{bmatrix} 2 &  1 \\  2 & 3 \end{bmatrix}$,
%$\ds \vecc=\begin{bmatrix} 3 & 4 \end{bmatrix}$,
%$\ds \vecb= \begin{bmatrix} 6 \\ 9 \end{bmatrix}$,
%		$\ds \vecx= \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$,
%and $\ds \vecs=\begin{bmatrix} s_1 \\ s_2 \end{bmatrix}$ is a vector of slack variables.
\begin{table}[h]
\caption{Final tableau of the GLKC ILP relaxation}\label{Ta:Cutting_Plane_kayak1_relaxation}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$ &  RHS \\
\hline \hline
 1 & 0 & 0 & $\frac{1}{4}$ &  $\frac{5}{4}$ & $\frac{51}{4}$             \\ \hline
 0 & 1 & 0 & $\frac{3}{4}$ &  $-\frac{1}{4}$ & $\frac{9}{4}$   \\ \hline
  0 & 0 & 1 & $-\frac{1}{2}$ &  $\frac{1}{2}$ & $\frac{3}{2}$   \\ \hline
\end{tabular}
\end{table}

\newpar
An important tool in subsequent steps is the \emph{integer component}\index{integer component}, or \emph{floor function}\index{floor function}
of a real number. If $x$ belongs to $\R$, then the integer component of $x$, denoted by $\lfloor x \rfloor$, is the largest integer less
than or equal to $x$. For example,
$\left\lfloor \frac{9}{4} \right\rfloor=2$ and
$\left\lfloor -\frac{1}{4} \right\rfloor=-1$. Clearly, $\lfloor x \rfloor=x$
for every integer $x$. The \emph{fractional part}\index{fractional part} of $x$ is defined as the
difference $x_f=x-\lfloor x \rfloor$, which satisfies $0 \leq x_f <1$.

\newpar
We now choose a row in (\ref{Ta:Cutting_Plane_kayak1_relaxation}) for which the
 corresponding basic variable is not integer-valued.
In this particular case, any row will suffice, but as a general rule, we choose the row
whose basic variable has its fractional value closest to one-half. Thus,
in this case we select the bottom row, which corresponds to the equation
\begin{equation}\label{E: IP_Cutting_Plane_tableau_source_row}
x_2 -\frac{1}{2}s_1 +  \frac{1}{2}s_2= \frac{3}{2}.
\end{equation}

\newpar
Each variable coefficient in (\ref{E: IP_Cutting_Plane_tableau_source_row}) can
be uniquely expressed as the sum of integer and fractional components so that the equation
is the same as
\begin{equation}\label{E: IP_Cutting_Plane_tableau_integer_fractional_decomposition}
(1+0)x_2+\left(-1+\frac{1}{2}\right)s_1+\left(0+\frac{1}{2}\right)s_2
=1+\frac{1}{2}.
\end{equation}
\noi
Rewriting (\ref{E: IP_Cutting_Plane_tableau_integer_fractional_decomposition})
so that coefficients having integer components and coefficients having fractional
components are grouped on opposite sides of the equal sign, we obtain

\begin{equation}\label{E: IP_Cutting_Plane_tableau_integer_fractional_decomposition2}
x_2-s_1-1 = \frac{1}{2}-\frac{1}{2}s_1-\frac{1}{2}s_2.
\end{equation}

\newpar
The ``trimming'' of the relaxation LP's feasible region arises from the fact that whenever
terms of an equation corresponding to a row of the relaxation's final tableau are separated in this manner, with
terms having integer component coefficients on one side of the equation and terms having fractional component coefficients on the other, each side of the resulting equation is nonpositive whenever $(x_1,x_2)$ is a feasible solution of the ILP.

\newpar
To demonstrate that this assertion holds for this particular example, we first consider the constraint equations, associated with the original relaxation of (\ref{E:Cutting_Plane_kayak1}):
\begin{align}\label{E:Cutting_Plane_kayak_constraint_equations}
	2x_1+x_2 +s_1 &= 6 \notag \\
	2x_1 + 3 x_2 +s_2 &= 9.  \notag
	\end{align}

\noi
If $(x_1,x_2)$ is a feasible solution of the ILP, then the corresponding values of
$s_1$ and $s_2$ must be integer-valued. This fact follows from
the feasibility assumption, meaning $x_1$ and $x_2$ are both
integer-valued, along with our assumption that all constraint bounds and all decision variable coefficients of the ILP are integer-valued. Therefore, $\ds x_2-s_1-1$ is integer-valued, and, in light of
(\ref{E: IP_Cutting_Plane_tableau_integer_fractional_decomposition2}),
so is $\ds \frac{1}{2}-\frac{1}{2}s_1-\frac{1}{2}s_2$. But
both $s_1$ and $s_2$ are nonnegative by feasibility so that
$\ds \frac{1}{2}-\frac{1}{2}s_1-\frac{1}{2}s_2 \leq \frac{1}{2}$. Since
$\ds \frac{1}{2}-\frac{1}{2}s_1-\frac{1}{2}s_2$ is an integer bounded above by $\frac{1}{2}$, it must
be nonnegative. By (\ref{E: IP_Cutting_Plane_tableau_integer_fractional_decomposition2})
$\ds x_2-s_1-1 \leq 0$ as well. Thus,
we have established that if $(x_1,x_2)$ is feasible solution of the ILP, then the inequalities
$\ds x_2-s_1-1 \leq 0$ and $\ds \frac{1}{2}-\frac{1}{2}s_1-\frac{1}{2}s_2 \leq 0$ are both valid. This means that adding one or both of them to the original ILP will ``trim'' the feasible region, so to speak, without removing from consideration feasible solutions of the ILP.

\newpar
We now introduce a new constraint to the relaxation that incorporates the slack-variable inequality,
$\ds \frac{1}{2}-\frac{1}{2}s_1-\frac{1}{2}s_2 \leq 0$. If $s_3$ denotes a new, nonnegative slack variable and if we rearrange terms, this inequality leads to the equation

\begin{equation}\label{E: IP_Cutting_Plane_Cut_Constraint}
-\frac{1}{2}s_1-\frac{1}{2}s_2 +s_3 = -\frac{1}{2}.
\end{equation}

\noi We now add this equation to the relaxation solution tableau, (\ref{Ta:Cutting_Plane_kayak1_relaxation}),
by adding a new row and column. The result is shown in Table \ref{Ta:Cutting_Plane_kayak1_Second_Tableau}.

\begin{table}[h]
\caption{Tableau for the relaxation after a new slack variable, $s_3$, has been introduced}
\label{Ta:Cutting_Plane_kayak1_Second_Tableau}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$ & $s_3$ &   RHS \\
\hline \hline
 1 & 0 & 0 & $\frac{1}{4}$ &  $\frac{5}{4}$ & 0 & $\frac{51}{4}$             \\ \hline
 0 & 1 & 0 & $\frac{3}{4}$ &  $-\frac{1}{4}$ & 0 & $\frac{9}{4}$   \\ \hline
  0 & 0 & 1 & $-\frac{1}{2}$ &  $\frac{1}{2}$ & 0 & $\frac{3}{2}$   \\ \hline
  0 & 0 & 0 & $-\frac{1}{2}$ &  $-\frac{1}{2}$ & 1 & $-\frac{1}{2}$   \\ \hline
\end{tabular}
\end{table}

\newpar
At this stage of the algorithm, both $s_1$ and $s_2$ are nonbasic and $\ds s_3=-\frac{1}{2}$. Thus,
the current basic variables constitute a basic, but not basic feasible solution, of
the LP formed by adding constraint (\ref{E: IP_Cutting_Plane_Cut_Constraint})
to the relaxation of (\ref{E:Cutting_Plane_kayak1}). To obtain a basic feasible solution, we utilize the dual simplex algorithm\index{dual simplex method} from Section \ref{S:Dual_Simplex}.

\newpar
Since only $s_3$ is a negative basic variable, we apply
the ratio test to the bottom row of (\ref{Ta:Cutting_Plane_kayak1_Second_Tableau})
The result is that
variable $s_1$ replaces $s_3$ as a basic variable. The resulting tableau is given by
(\ref{Ta:Cutting_Plane_kayak1_Third_Tableau}).

\begin{table}[h]
\caption{Tableau after the first iteration of the cutting plane algorithm}\label{Ta:Cutting_Plane_kayak1_Third_Tableau}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$ & $s_3$ &   RHS \\
\hline \hline
 1 & 0 & 0 & 0 & 1 &  $\frac{1}{2}$ & $\frac{25}{2}$             \\ \hline
 0 & 1 & 0 & 0 & -1 &  $\frac{3}{2}$ & $\frac{3}{2}$   \\ \hline
  0 & 0 & 1 & 0 & 1 &  -1  & 2  \\ \hline
  0 & 0 & 0 & 1 &  1 & -2  & 1  \\ \hline
\end{tabular}
\end{table}

\newpar
The tableau in (\ref{Ta:Cutting_Plane_kayak1_Third_Tableau}) marks the end of the first iteration
of what we refer to as the \emph{cutting plane algorithm}\index{cutting plane algorithm}.

\newpar
The decision variable $x_1$ is not integer-valued, so we repeat the process used in
the first iteration and determine a second additional constraint, which is added to the LP relaxation. We first select
 the row containing the basic variable whose fractional part is closest to $\frac{1}{2}$, which
  in this case corresponds to $x_1$.

\newpar While we could repeat the entire process of recording
 the equation corresponding to this row, decomposing variable coefficients into their
 integer and fractional components, and grouping terms with fractional coefficients on one
 side of the equation, we see from close inspection of the first iteration that a simpler means exists. Namely, we may perform the following steps:
 \be
 \item Compute the fractional component of each entry in
 the row corresponding to $x_1$. The resulting values yield
 $\ds \left[0,0,0,0,0,\frac{1}{2} ,\frac{1}{2} \right]$.
 \item  Add to (\ref{Ta:Cutting_Plane_kayak1_Third_Tableau}) a new slack variable, $s_4$. Entries
  in its corresponding column are all zero, except in a new row added to the tableau where the entry corresponding to $s_4$ equals 1 and all other entries consist of additive inverses of the previously computed fractional
  components. The resulting tableau
  is given by (\ref{Ta:Cutting_Plane_kayak1_Fourth_Tableau}).
  \item Perform the dual simplex algorithm. The first step of this algorithm focuses
  on the new row just added to the tableau, which corresponds to the negative basic variable
  $s_4$.
 \ee

\begin{table}[h]
\caption{Tableau for the relaxation after a new slack variable, $s_4$, has been introduced}\label{Ta:Cutting_Plane_kayak1_Fourth_Tableau}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$ & $s_3$ & $s_4$ &   RHS \\
\hline
 1 & 0 & 0 & 0 & 1 &  $\frac{1}{2}$ & 0 & $\frac{25}{2}$             \\ \hline
 0 & 1 & 0 & 0 & -1 &  $\frac{3}{2}$ & 0 & $\frac{3}{2}$   \\ \hline
  0 & 0 & 1 & 0 & 1 &  -1  & 0 & 2  \\ \hline
  0 & 0 & 0 & 1 &  1 & -2  & 0 &  1  \\ \hline
  0 & 0 & 0 & 0 &  0 & $-\frac{1}{2}$ & 1 &  $-\frac{1}{2}$  \\ \hline
\end{tabular}
\end{table}

\newpar
Executing the dual simplex algorithm a second time, we see that $s_3$ replaces
$s_4$ as a basic variable. The resulting pivot leads to the result
in Table (\ref{Ta:Cutting_Plane_kayak1_Fifth_Tableau}).

\begin{table}[h]
\caption{Tableau for the GLKC ILP after second iteration of cutting plane algorithm}\label{Ta:Cutting_Plane_kayak1_Fifth_Tableau}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$ & $s_3$ & $s_4$ &   RHS \\
\hline \hline
 1 & 0 & 0 & 0 & 1 &  0 & 1 & 12             \\ \hline
 0 & 1 & 0 & 0 & -1 &  0 & 3 & 0   \\ \hline
  0 & 0 & 1 & 0 & 1 &  0  & -2 & 3  \\ \hline
  0 & 0 & 0 & 1 &  1 & 0  & -4 &  3  \\ \hline
  0 & 0 & 0 & 0 &  0 & 1 & -2 &  1  \\ \hline
\end{tabular}
\end{table}

\newpar
The tableau indicates an optimal solution to original ILP given by
\newline $\ds \vecx=\begin{bmatrix} x_1 \\ x_2 \end{bmatrix}=\begin{bmatrix} 0 \\ 3 \end{bmatrix}$
and $z=12$. In addition, all slack variables are integer-valued.

\subsection{A Step-by-Step Maple Implementation of the Cutting Plane Algorithm}
\label{SS:Maple_Implementation_Cutting Plane}\index{cutting plane algorithm!Maple implementation}

\noi The
cutting plane algorithm is easy to implement with Maple. What follows is
a portion of a worksheet, \textbf{Cutting Plane Algorithm.mw}, demonstrating how this is accomplished
for the GLKC ILP. Missing from the beginning of the worksheet
are the following:
\be
\item Contents of the worksheet \textbf{Simplex Algorithm.mw} from Section
\ref{S:Simplex}, which allows the user to solve the ILP's relaxation.
\item The \mf{ColumnRatios} procedure found at the end of Section \ref{S:Dual_Simplex}.
\ee

\noi
In addition, we have omitted from the following worksheet a new Maple procedure, called \mf{fracpart}, which computes
the fractional part of its argument. It can be defined at the start of the worksheet as follows:
\begin{equation*}
\mbox{ \mf{fracpart:=proc(x) local y, y=x-floor(x):RETURN((y)):end: }}
\end{equation*}

\noi
For example, \mf{fracpart(-.25)} returns $.75$.

\newpar
We begin this portion of the worksheet with the final tableau matrix, \mf{LPMatrix}, that
results when the simplex algorithm is used to solve the GLKC's ILP relaxation.
Recall again our numbering convention that column 0 and row 0 denote the leftmost column and top row, respectively, of the tableau matrix.

\begin{maplelist}
\item \mf{Tableau(LPMatrix);
\newline \# Display final tableau for GLKC ILP relaxation.}
\mo{\begin{bmatrix}
z & x_1 & x_2 & s_1 & s_2 & RHS \\
1 & 0 & 0 & \frac{1}{4} & \frac{5}{4} & \frac{51}{4} \\
0 & 1 & 0 & \frac{3}{4} & -\frac{1}{4} & \frac{9}{4} \\
0 & 0 & 1 & -\frac{1}{2} & \frac{1}{2} & \frac{3}{2} \\
\end{bmatrix}
}
\item \mf{evalf(\%);}
\mo{\begin{bmatrix}
z & x_1 & x_2 & s_1 & s_2 & RHS \\
1 & 0 & 0 & .25 & 1.25 & 12.75 \\
0 & 1 & 0 & .75 & -.25 & 2.25 \\
0 & 0 & 1 & -.5 & .5 & 1.5 \\
\end{bmatrix}
}
\item \mf{m:=m+1:}
\item \mf{for j from 2 to m do evalf(fracpart(LPMatrix[j,n+m+1]));end do;
\newline \# Determine basic variable whose fractional part is closest to one half.}
\mo{ \begin{matrix} .25 \\ .50 \end{matrix} }
\item \mf{k:=2:
\newline \# Basic variable corresponding to row 2
has fractional part
\newline closest to one half.}
\item \mf{NewRow:=-Vector[row]([seq(-fracpart(RowCoefficients[j]),
\newline j=1..(n+m+1)),-1,-fracpart(LPMatrix[k+1,n+m+1])]);
\newline \# Create new bottom row corresponding to added constraint.}
\mo{NewRow:=
\begin{bmatrix} 0 & 0 & 0 & -\frac{1}{2} & -\frac{1}{2} & 1 & -\frac{1}{2} \end{bmatrix}}
\item \mf{LPMatrix:=$<<$SubMatrix(LPMatrix,1..m,1..(n+m))|ZeroVector(m)| \newline
SubMatrix(LPMatrix,1..m,(m+n+1)..(m+n+1))$>$,NewRow$>$;
\newline \# Create new matrix incorporating addition of new slack variable to original LP's relaxation.}
\mo{LPMatrix:=
\begin{bmatrix}
1 & 0 & 0 & \frac{1}{4} & \frac{5}{4} & 0 & \frac{51}{4} \\
0 & 1 & 0 & \frac{3}{4} & -\frac{1}{4} & 0 &\frac{9}{4} \\
0 & 0 & 1 & -\frac{1}{2} & \frac{1}{2} & 0 &\frac{3}{2} \\
0 & 0 & 0 & -\frac{1}{2} & -\frac{1}{2} & 1 & -\frac{1}{2}
\end{bmatrix}
}
\item \mf{x:=array(1..n):s:=array(1..m):
\newline \# Create arrays of decision and slack variables.}
\item \mf{Labels:=Matrix(1,2+n+m,[z,seq(x[i],i=1..n),seq(s[j],
\newline j=1..m),RHS]):
\newline \# Create a new top row of labels.}
\item \mf{Tableau(LPMatrix);}
\mo{
\begin{bmatrix} z & x_1 & x_2 & s_1 & s_2 & s_3 & RHS \\
1 & 0 & 0 & \frac{1}{4} & \frac{5}{4} & 0 & \frac{51}{4} \\
0 & 1 & 0 & \frac{3}{4} & -\frac{1}{4} & 0 &\frac{9}{4} \\
0 & 0 & 1 & -\frac{1}{2} & \frac{1}{2} & 0 &\frac{3}{2} \\
0 & 0 & 0 & -\frac{1}{2} & -\frac{1}{2} & 1 & -\frac{1}{2}
\end{bmatrix}
}
\item \mf{ColumnRatios(LPMatrix,m);
\newline \# Perform dual simplex algorithm ratio test on row m.}
%\mo{
%\mbox{``Column 1 Ratio Undefined''}}
%\mo{
%\mbox{``Column 2 Ratio Undefined''}}
%\mo{
%\mbox{``Column 3 Ratio = -.5000000000''}}
% \mo{ \mbox{``Column 4 Ratio = -.5000000000''}}
%\mo{
%\mbox{``Column 5 Ratio = 0.''}}

\begin{table}[h]
\begin{tabular}{c}
``Column 1 Ratio Undefined'' \\
``Column 2 Ratio Undefined'' \\
``Column 3 Ratio = -.5000000000'' \\
``Column 4 Ratio =-2.5000000000'' \\
``Column 5 Ratio =0.'' \\
\end{tabular}
\end{table}

\item \mf{Iterate(LPMatrix,m,3);
\newline \# Pivot on entry in row m, column 3 so that s1 replaces 
\newline s3 as a basic variable.}
\mo{
\begin{bmatrix} z & x_1 & x_2 & s_1 & s_2 & s_3 & RHS \\
1 & 0 & 0 & 0 & 1 & \frac{1}{2} & \frac{25}{2} \\
0 & 1 & 0 & 0 & -1 & \frac{3}{2} & \frac{3}{2} \\
0 & 0 & 1 & 0 & 1 & -1 & 2  \\
0 & 0 & 0 & 1 & 1 & -2 & 1
\end{bmatrix}
}

% END OF FIRST ITERATION

\item \mf{m:=m+1: \# End of first iteration; repeat process.}
\item \mf{for j from 2 to m do evalf(fracpart(LPMatrix[j,n+m+1]));
\newline end do;
\newline \# Determine basic variable whose fractional part is 
\newline closest to one half.}
\mo{ \begin{matrix} .5 \\ 0 \\ 0  \end{matrix} }
\item \mf{k:=1:
\newline \# Basic variable corresponding to row 1
has fractional part closest to one half.}
\item \mf{NewRow:=-Vector[row]([seq(fracpart(LPMatrix[k+1,j]),\newline j=1..(n+m)),-1, fracpart(LPMatrix[k+1,n+m+1])]);
\newline \# Create new bottom row corresponding to added constraint.}
\mo{NewRow:=
\begin{bmatrix} 0 & 0 & 0 & 0 & 0 & -\frac{1}{2} & 1 & -\frac{1}{2} \end{bmatrix}}
\item \mf{LPMatrix:=$<<$SubMatrix(LPMatrix,1..m,1..(n+m))|ZeroVector(m)| \newline
SubMatrix(LPMatrix,1..m,(m+n+1)..(m+n+1))$>$,NewRow$>$;
\newline \# Create new matrix incorporating addition of new 
\newline slack variable to original LP's relaxation.}
\item \mf{x:=array(1..n):s:=array(1..m):
\newline \# Create arrays of decision and slack variables.}
\item \mf{Labels:=Matrix(1,2+n+m,[z,seq(x[i],i=1..n),
\newline seq(s[j],j=1..m),RHS]):
\newline \# Create a new top row of labels.}
\item \mf{Tableau(LPMatrix);}
\mo{
\begin{bmatrix}
z & x_1 & x_2 & s_1 & s_2 & s_3 & s_4 & RHS \\
 1 & 0 & 0 & 0 & 1 & \frac{1}{2} & 0 & \frac{25}{2} \\
0 & 1 & 0 & 0 & -1 & \frac{3}{2} & 0 & \frac{3}{2} \\
0 & 0 & 1 & 0 & 1  & -1 & 0 & 2 \\
0 & 0 & 0 & 1 & 1 & -2 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & -\frac{1}{2} & 1  & -\frac{1}{2} \end{bmatrix}
}
\item \mf{ColumnRatios(LPMatrixNew,m); \# Perform ratio test on row m.}
%\mo{
%\mbox{``Column 1 Ratio Undefined''}}
%\mo{
%\mbox{``Column 2 Ratio Undefined''}}
%\mo{
%\mbox{``Column 3 Ratio Undefined''}}
%\mo{
%\mbox{``Column 4 Ratio Undefined''}}
%\mo{
%\mbox{``Column 5 Ratio = -1.''}}
%\mo{
%\mbox{``Column 6 Ratio = 0.''}}

\begin{table}[h]
\centering
\begin{tabular}{c}
``Column 1 Ratio Undefined'' \\
``Column 2 Ratio Undefined'' \\
``Column 3 Ratio Undefined'' \\
``Column 4 Ratio Undefined'' \\
``Column 5 Ratio = -1.'' \\
``Column 6 Ratio = 0.'' \\
\end{tabular}
\end{table}


\item \mf{Iterate(LPMatrix,m,5);
\newline \# Pivot on entry in row m, column 5 to obtain final tableau.}
\mo{ \begin{bmatrix} z & x1 & x2 & s1 & s2 & s3 & s4 & RHS\\
1 & 0 & 0 & 0 & 1 & 0 & 1 & 12 \\
0 & 1 & 0 & 0 & -1 & 0 & 3 & 0  \\
0 & 0 & 1 & 0 & 1  & 0 & -2 & 3 \\
0 & 0 & 0 & 1 & 1 & 0 & -4 & 3 \\
0 & 0 & 0 & 0 & 0 & 1 & -2  & 1 \end{bmatrix}
}
\end{maplelist}

\subsection{Comparison with the Branch and Bound Method}\label{S:Int_Prog_Cutting_Plane_Branch_and_Bound_Comparison}\index{branch and bound method!comparison with cutting plane algorithm}

\noi When applied to the GLKC ILP, the cutting plane algorithm required only two iterations starting
with the relaxation LP's final tableau, whereas the branch and bound algorithm required four branching levels. On the basis of this isolated example, we might conclude that the cutting plane algorithm is the more efficient of the two algorithms. However, as a general rule, the opposite is true, and the branch and bound is the preferred technique. Contemporary methods utilize what are known as ``cut and branch'' techniques, whereby the cutting plane algorithm is used to help solve intermediate LPs that arise within a larger branch and bound framework.

\section*{Exercises Section \protect\ref{S:IP_Cutting_Plane}}

\addcontentsline{toc}{subsection}{Exercises}

\input{Exercises/Exercises_Cutting_Plane_Algorithm}	
	
\endinput
	
	