% { March 31 (W), 1993}
% \documentstyle[12pt]{siam}

% from stoc-94.tex
% \documentstyle[12pt,twocolumn]{article}
\documentstyle[12pt]{article}
\clubpenalty 10000
\widowpenalty 10000
\topmargin -1.2cm
\oddsidemargin -0.4cm
% \textheight 8.625in
\textheight 8.800in
\textwidth 7.26in
\columnseprule .2mm
\columnsep .5in
% \parindent=0pt
\sloppy

\input{mssymb}
\pagestyle{empty}
\setlength{\textheight}{9.30in}

\def\ov#1{\overline{#1}}
\def\wt#1{\widetilde{\mbox{\bf #1}}}

\begin{document}

% \begin{center}
% {{\Large\bf C\&O 350~~~~~Linear Programming}}
% \end{center}

% \vspace{0.10in}

\begin{center}
{{\large\bf Integer Programming and Gomory's Cutting Plane Method}}
\end{center}

\vspace{0.10in}

Given an integer linear programming problem
\[ \mbox{($IP$)}~~~~ \mbox{maximize \bf cx}~~~~
	\mbox{subject to \bf Ax=b},~~ \mbox{{\bf x $\ge$ 0,~~ x} integral},
\]
the {\it cutting plane method} takes the LP relaxation ($P$) of ($IP$),
obtained by dropping the constraints that {\bf x} be integral,
and finds an optimal dictionary for ($P$) by using the simplex method.
Let the optimal basic solution of ($P$) be $\wt{x}=(\wt{x}_B,\wt{x}_N)$;
the nonbasic variables are $x_j,~j\in N$.
If every component of $\wt{x}$ has an integer value, then $\wt{x}$ is
also the optimal solution for ($IP$) -- nothing more needs to be done.

Suppose that one of the basic variables $x_h$ in the optimal basic 
solution for ($P$) has a noninteger value $\ov{b}_h$.
We can rewrite the equation for $x_h$ in the optimal dictionary for
($P$) by splitting $\ov{b}_h$ and each $\ov{a}_{hj}$ into its integer
part and its fractional part:
\[ x_h =
\left\{ \lfloor\ov{b}_h\rfloor - \sum_{j\in N} \lfloor\ov{a}_{hj}\rfloor x_j \right\} +
\left\{ (\ov{b}_h - \lfloor\ov{b}_h\rfloor) -
	\sum_{j\in N} (\ov{a}_{hj} - \lfloor\ov{a}_{hj}\rfloor) x_j \right\}.
	\quad\quad\quad\quad   (1)
\]
({\bf Notation}: For a real number $r$, we use $\lfloor r\rfloor$ to mean
the greatest integer less than or equal to $r$,
e.g., $\lfloor 1.3\rfloor=1$ and $\lfloor  -1.3\rfloor=-2$.)
For example the equation
$  x_2  =  {9 \over 5}  -  {1 \over 10}x_3  +  {1 \over 10}x_4  $
(here, according to our notation for dictionaries
$\ov{a}_{23}= +{1 \over 10}$ and $\ov{a}_{24}= -{1 \over 10}$)
would be rewritten as
\[ x_2 = \left( 1 - 0x_3 - (-1)x_4 \right) +
	\left( {4 \over 5} - {1 \over 10}x_3 - {9 \over 10}x_4 \right).
\]

% \begin{tabular}{lcccccc}
% $x_2$ & = & ${9 \over 5}$ & $-$ & ${1 \over 10}x_3$ & $+$ & ${1 \over 10}x_4$ \\
% $x_1$ & = & 2		& &		& $-$ & $x_4$ \\
% \hline
% $z$   & = & 11		& $-$ & ${1 \over 2}x_3$ & $-$ & ${1 \over 2} x_4$
% \end{tabular}
%% \[ x_2 = {9 \over 5} - {1 \over 10}x_3 + {1 \over 10}x_4 \]

The general equation (1) has two parts on the right,
an integral part and a fractional part.
Focus on the fractional part: Since
each $(\ov{a}_{hj} - \lfloor\ov{a}_{hj}\rfloor)$ ($j\in N$) is nonnegative
(by our definition of the $\lfloor r\rfloor$ notation),
each $x_j$ is nonnegative,
and
$(\ov{b}_h - \lfloor\ov{b}_{h}\rfloor)$ is a fraction
$\underline{\mbox{strictly}}$ between 0 and 1,
either the fractional part has value $\le 0$ (at most zero)
or its value lies strictly between 0 and 1.
This brings us to the important point:
\\
For every integral solution {\bf x} of ($P$),
in equation~(1), the left hand side must have an integer value,
and the integral part on the right hand side,
$\{\lfloor\ov{b}_h\rfloor - \sum_{j\in N} \lfloor\ov{a}_{hj}\rfloor x_j\}$,
must have an integer value,
hence, the fractional part {\it must} have an integer value.
That is, the fractional part {\it must} have a value $\le 0$,
since it {\it cannot} take a nonintegral value between zero and one.

This gives us a new constraint,
\[ \left\{ (\ov{b}_h - \lfloor\ov{b}_h\rfloor) -
	\sum_{j\in N} (\ov{a}_{hj} - \lfloor\ov{a}_{hj}\rfloor) x_j \right\} \le 0,
\]
to add to ($P$).
Such constraints are called {\it Gomory cuts}.
The key property of these constraints is this:
\\
{\it
Every feasible {\it integral} solution of ($P$) satisfies
the Gomory cut, but the optimal solution $\wt{x}$ for ($P$) does {\it not}
satisfy it because
in the optimal dictionary for ($P$)
$x_j=0$ for each $j\in N$ and $(\ov{b}_h - \lfloor\ov{b}_{h}\rfloor) >0$.
}

Let the new linear programming problem be ($P'$),
i.e., ($P'$) is the LP relaxation of ($IP$)
with the Gomory cut added as a new constraint.
To find an optimal solution for ($P'$),
we use the method for adding a new constraint in sensitivity analysis,
and do dual simplex pivots until
we find an optimal solution to ($P'$)
or until we find that ($P'$) is infeasible.
Another important point is this:
\\
{\it
For every feasible {\it integral} solution {\bf x} of ($P$),
the new slack variable introduced in the Gomory cut
must have an integer value.
}

We iterate the above steps
until we find an optimal solution $x^*$ for the current
LP ($P^*$) such that every component of $x^*$ has
an integer value,
or
until we find that ($P^*$) is infeasible,

% If the variables of ($IP$) have {\it noninteger} values
% in the optimal solution $\wt{x}'$ of ($P'$),
% then we repeat the above steps.

% If in the optimal solution $\wt{x}'$ of ($P'$)
% the variables of ($IP$) have integer values,
% then we stop with an optimal solution for ($IP$).
% Otherwise, we repeat the above steps:
% we construct another Gomory cut,
% using a basic variable with a noninteger value
% in the optimal dictionary for ($P'$);
% we obtain a new linear programming problem  ($P''$)
% by adding the Gomory cut as a new constraint to ($P'$),
% and then we find an optimal solution for ($P''$).
% And so on, \dots

% \bigskip
% \hrule \hrule
% \vspace{0.03in}
% \hrule \hrule
% \bigskip

\clearpage
\twocolumn

\begin{flushleft}
{\bf Example: Cutting Plane Method}
\end{flushleft}

\begin{flushleft}
\begin{tabular}{lccccc}
($IP$)\quad \\
 maximize~& $z$ = $x_1$ & + & $5x_2$ \\
 subject~to~	& $x_1$ & + & $10x_2$ & $\le$ & 20 \\
 		& $x_1$ &   &		& $\le$ & 2 \\
 		&	$x_1,~x_2$ & $\ge$ & 0  &   & \\
 		&	$x_1,~x_2$ & & integral &   & \\
\end{tabular}
\end{flushleft}
\medskip

We introduce slack variables $x_3$ and $x_4$.
If $x_1$ and $x_2$ are integers,
then notice that $x_3$ and $x_4$ {\it must be integers},
because all coefficients $a_{ij}$ in the constraints and
all right hand side values $b_i$ are integers.

The initial dictionary for the LP relaxation ($P$) of ($IP$) is:
\medskip

\begin{tabular}{lcccccc}
$x_3$ & = & 20 & $-$ & $x_1$ & $-$ & ${10}x_2$ \\
$x_4$ & = & 2  & $-$ & $x_1$	\\
\hline
$z$   & = & 0	& $+$ & $x_1$ & $+$ & $5x_2$
\end{tabular}
\medskip

After two pivots of the simplex algorithm, we get the optimal
dictionary for ($P$):
\medskip

\begin{tabular}{lcccccc}
$x_2$ & = & ${9 \over 5}$ & $-$ & ${1 \over 10}x_3$ & $+$ & ${1 \over 10}x_4$ \\
$x_1$ & = & 2		& &		& $-$ & $x_4$ \\
\hline
$z$   & = & 11		& $-$ & ${1 \over 2}x_3$ & $-$ & ${1 \over 2} x_4$
\end{tabular}
\medskip

The optimum solution,
$\wt{x}=$$(\tilde{x}_1,$$\tilde{x}_2,$$\tilde{x}_3,$ $\tilde{x}_4)=$
$(2, {9 \over 5}, 0, 0)$, is {\it not integral}.
Therefore, the equation for $x_2$ in the optimal dictionary
is used to generate the following Gomory cut:
\[	{4 \over 5} - {1 \over 10}x_3 -{9 \over 10}x_4 \le 0.
\]
(In terms of the decision variables $x_1$ and $x_2$,
this constraint is $x_1+x_2 \le 3$,
as can be seen by substituting for $x_3$ and $x_4$ from the initial dictionary.)
\\
The slack variable $x_5$, $x_5\ge 0$, is introduced,
and the equation
\[ -{1 \over 10}x_3 - {9 \over 10}x_4 + x_5 = -{4 \over 5} 
\]
is added to the constraints of ($P$)
to give the new LP ($P'$).
\medskip

\nopagebreak[4]
{\sc Exercise}: For every feasible solution $x_1,~x_2$
of ($P$) that is integral, show that $x_5$ has an integer value.

Since the resulting dictionary
\medskip

\begin{tabular}{lcccccc}
$x_2$ & = & ${9 \over 5}$ & $-$ & ${1 \over 10}x_3$ & $+$ & ${1 \over 10}x_4$ \\
$x_1$ & = & 2		& &		& $-$ & $x_4$ \\
$x_5$ & = & $-{4 \over 5}$ & $+$ & ${1 \over 10}x_3$ & $+$ & ${9 \over 10}x_4$ \\
\hline
$z$   & = & 11		& $-$ & ${1 \over 2}x_3$ & $-$ & ${1 \over 2} x_4$
\end{tabular}
\medskip

\noindent
is dual feasible but not feasible,
we apply the dual simplex method to do a pivot.
The leaving variable is $x_5$ and the entering variable is $x_4$.
The new dictionary, which is optimal for ($P'$), is as follows.

\medskip
\begin{tabular}{lcccccc}
$x_2$ & = & ${17 \over 9}$ & $-$ & ${1 \over 9}x_3$ & $+$ & ${1 \over 9}x_5$ \\
$x_1$ & = & ${10 \over 9}$ & $+$ & ${1 \over 9}x_3$ & $-$ & ${10 \over 9}x_5$ \\
$x_4$ & = & ${8 \over 9}$ & $-$ & ${1 \over 9}x_3$ & $+$ & ${10 \over 9}x_5$ \\
\hline
$z$   & = & ${95 \over 9}$ & $-$ & ${4 \over 9}x_3$ & $-$ & ${5 \over 9}x_5$
\end{tabular}
\medskip

\noindent
The optimum basic solution is $\wt{x}'=$
$(\tilde{x}_1',$$\tilde{x}_2',$ $\tilde{x}_3',$$\tilde{x}_4',$$\tilde{x}_5') =$
$({10 \over 9}, {17 \over 9}, 0, {8 \over 9}, 0)$,
and it is {\it not integral}.
Therefore, we generate a new Gomory cut,
using the equation for $x_2$ in the optimal dictionary for ($P'$):
\[ {8 \over 9} - {1 \over 9}x_3 - {8 \over 9}x_5 \le 0.
\]
(In terms of the decision variables $x_1$ and $x_2$,
this constraint is $x_1 + 2x_2 \le 4$.)
% , by substituting for $x_3$ and $x_5$.)
\\
The slack variable $x_6$, $x_6\ge 0$, is introduced,
and the equation
\[ - {1 \over 9}x_3 - {8 \over 9}x_5 + x_6 = -{8 \over 9}
\]
is added to the constraints of ($P'$)
to give the new LP ($P''$).

The dictionary obtained by adding the equation for $x_6$
is dual feasible but not feasible, so
we apply the dual simplex method to do a pivot.
The leaving variable is $x_6$ and the entering variable is $x_5$.
The new dictionary, which is optimal for ($P''$), is as follows.

\medskip
\begin{tabular}{lcccccc}
$x_2$ & = & ${         2}$ & $-$ & ${1 \over 8}x_3$ & $+$ & ${1 \over 8}x_6$ \\
$x_1$ & = & ${         0}$ & $+$ & ${1 \over 4}x_3$ & $-$ & ${5 \over 4}x_6$ \\
$x_4$ & = & ${        2}$ & $-$ & ${1 \over 4}x_3$ & $+$ & ${5 \over 4}x_6$ \\
$x_5$ & = & ${        1}$ & $-$ & ${1 \over 8}x_3$ & $+$ & ${9 \over 8}x_6$ \\
\hline
$z$   & = & ${        10}$ & $-$ & ${3 \over 8}x_3$ & $-$ & ${5 \over 8}x_6$
\end{tabular}
\medskip

Since the optimal basic solution $\wt{x}''=$
% $(\tilde{x}_1'', \tilde{x}_2'', \tilde{x}_3'', \tilde{x}_4'', \tilde{x}_5'', \tilde{x}_6'') =$
$(0, 2, 0, 2, 1, 0)$
is {\it integral},
it follows that
$(\tilde{x}_1'', \tilde{x}_2'') = (0,2)$
is an optimal solution for ($IP$).

\end{document}