\documentclass{slides}
\pagestyle{plain}
\begin{document}
\begin{slide}{}
\begin{center}
{\Large\bf CUTTING STOCK PROBLEM }\\
{\Large\bf (CSP)}
~\\
and\\
{\Large\bf RELAXED CUTTING STOCK PROBLEM }\\
{\Large\bf (RCSP)}
\end{center}
~\\
\begin{center}
{\bf C\&O Deterministic OR Models }~~~~ 
\end{center}

(Reference: Chvatal, Linear Programming, pp. 195-211.)



\end{slide}
\begin{slide}{}

The reference contains an outstanding treatment of the (standard)
Cutting Stock Problem (CSP). Included is:
\begin{enumerate}
\item
a mathematical formulation (model) of the problem;
\item
a solution algorithm (revised simplex method with a knapsack (KP)
subroutine for determining the entering column);
\item
a branch-and-bound algorithm for solving (KP);
\item
reductions of some non-standard problem versions to instances of the
standard version;
\item
a detailed solution to a sample problem.
\end{enumerate}
\end{slide}
\begin{slide}{}
This handout contains a summary of the model formulation and solution
algorithm in a GAMS-like format together with a suggested format for a
{\em Solution Summary} display.
\end{slide}
\begin{slide}{}
\begin{center}
{\bf Model (Standard Cutting Stock Problem)}
\end{center}

\underline{Sets and Variables}\\
$I$ := finals-set $= /1,2, \ldots, m /$ \\
$J$ := cutting pattern-set $= /j(1),j(2), \ldots, j(m), \ldots /$, (implicit
input) \\
$X(J)$ := raws-requirement variable ($X(j)$ is number of raws reuired
using cutting pattern $j$)\\
$Z$ := objective (total number of raws required to meet the demand)


\end{slide}
\begin{slide}{}
\underline{Data}\\
$w(I)$ := widths (units) of finals $= /w(1),w(2), \ldots, w(m) /$ \\
$b(I)$ := demand for finals $= /b(1),b(2), \ldots, b(m) /$ \\
$C(J)$ := unit ``costs'' of raws $= /1,1, \ldots, 1 /$ \\
$W$ := width (same units as w) of each raw \\
$A(I,J)$ := cutting pattern matrix $= /a(I) \in {\cal N}^I :
  sum(I,w(I)Ia(I)) \leq W/$
(implicit input, $a_{ij}$ is the number of type-i final widths specified
by cutting pattern $j$)

\underline{Program (RCSP)}\\
minimize $Z=sum(J,C(J)*X(J))$  (total number of raws required) \\
subject to $sum(J,A(I,J)*X(J))=b(I)$ (demand for finals)\\
and $X(J) \geq 0$

\underline{Program (RCSP)}\\
solve (RCSP) subject to: $X(J)$ integral.
\end{slide}
\begin{slide}{}
\begin{center}
{\bf Solving (CSP) Approximately}
\end{center}
\begin{enumerate}
\item
Solve (RCSP) by the revised simplex method algorithm and let
$[Z^H|X(J)]=[Z^*|X^*(B)|0]$ be an optimum solution.
\item
If $[Z^*|X^*(B)$ is integral, then it solves (CSP).
\item
Otherwise, find an approximate solution to (CSP) as follows:\\
Solve (heuristically or otherwise) the much simpler (CSP) whose demands
are \\
$\bar(b)(I):=b(I)-sum(B,A(I,B)*{\rm l}\_x^*(B)\_{\rm l})  $\\
 (where ${\rm l}\_ \cdot \_{\rm l}$ denotes integer part).
And let $[\bar{z} | \bar{x} ( \bar{B})]$ be an optimum solution.
\item
Then, where $X^o(B|\bar{B}):= [ {\rm l}\_x^*(B)\_{\rm l} | \bar{x} (
\bar{B}) ]$ and $Z^o=sum(B,{\rm l}\_x^*(B)\_{\rm l} | ) + \bar{Z}$, we
get 

\end{enumerate}

\end{slide}
\begin{slide}{}
\end{slide}

\end{document}
