\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

\begin{description}

\item[(a)]
Use a branch and bound algorithm to solve the following (zero-one)
knapsack problem.  In your algorithm, always choose a node of the
search tree with the largest upper bound to be explored next.

\begin{tabular}{ll}
Maximize&$z =  18x_1 + 17x_2 + 11x_3 + 14x_4 + 6x_5 + 4x_6 +
5x_7$\\subject to&$8x_1+ 9x_2  + 6x_3 + 9x_4 + 4x_5 + 3x_6 + 5x_7
\leq 20 $\\&$x_i = 0\textrm{ or }1\textrm{ for }i=1,\ldots,7$.
\end{tabular}

Assume that the three following additional constraints are
imposed:

\begin{eqnarray*}
x_1&\leq& x_3\\ x_2&\leq&x_4\\ x_3&+&x_4+x_6+x_7\leq1
\end{eqnarray*}

By suitably adapting the algorithm, obtain an optimal solution to
the problem with these additional constraints.

\item[(b)]
Explain why the knapsack problem is useful in delayed column
generation.  You may explain your answer by reference to the trim
loss problem: rolls of paper are cut into smaller rolls to satisfy
customer demand, and the objective is to minimize the wasted
paper.

\end{description}


ANSWER

\begin{description}

\item[(a)]
Upper bounds found by an efficient algorithm which solves linear
programming relaxation.

\setlength{\unitlength}{1cm}

\begin{picture}(8,8)

\begin{small}

\put(4.5,7){\circle{.4}}\put(4.5,7){\makebox(0,0){1}}
\put(3,5){\circle{.4}}\put(3,5){\makebox(0,0){2}}
\put(6,5){\circle{.4}}\put(6,5){\makebox(0,0){3}}
\put(5,3){\circle{.4}}\put(5,3){\makebox(0,0){4}}
\put(7,3){\circle{.4}}\put(7,3){\makebox(0,0){5}}
\put(6,1){\circle{.4}}\put(6,1){\makebox(0,0){6}}
\put(8,1){\circle{.4}}\put(8,1){\makebox(0,0){7}}
\put(2,3){\circle{.4}}\put(2,3){\makebox(0,0){8}}
\put(4,3){\circle{.4}}\put(4,3){\makebox(0,0){9}}
\put(1,1){\circle{.4}}\put(1,1){\makebox(0,0){10}}
\put(3,1){\circle{.4}}\put(3,1){\makebox(0,0){11}}

\end{small}

\put(4.5,6.8){\line(-3,-4){1.3}}\put(4.5,6.8){\line(3,-4){1.3}}
\put(3,4.8){\line(-1,-2){.8}}\put(3,4.8){\line(1,-2){.8}}
\put(6,4.8){\line(-1,-2){.8}}\put(6,4.8){\line(1,-2){.8}}
\put(2,2.8){\line(-1,-2){.8}}\put(2,2.8){\line(1,-2){.8}}
\put(7,2.8){\line(-1,-2){.8}}\put(7,2.8){\line(1,-2){.8}}

\put(4.2,7.5){40} \put(2.7,5.5){39} \put(6.2,5.5){40}
\put(4.7,3.5){38} \put(7.2,3.5){39} \put(5.7,1.5){35}
\put(8.2,1.5){inf} \put(1.7,3.5){39} \put(4.2,3.5){37}
\put(.7,1.5){39} \put(3.2,1.5){39}

\put(2.7,6.5){$x_3=0$} \put(5.5,6.5){$x_3=1$}
\put(1.7,4.5){$x_4=0$} \put(3.5,4.5){$x_4=1$}
\put(4.7,4.5){$x_2=0$} \put(6.5,4.5){$x_2=1$}
\put(.7,2.5){$x_5=0$} \put(2.5,2.5){$x_5=1$}
\put(5.7,2.5){$x_1=0$} \put(7.5,2.5){$x_1=1$}

\end{picture}

\begin{tabular}{ll}
Node 1&$UB=18+17+\lfloor\frac{11}{2}\rfloor=40$\\ &$LB=35$\\ Node
2&$UB=18+17+\lfloor\frac{14}{3}\rfloor=39$\\ &$LB=35$\\ Node
3&$UB=18+\lfloor\frac{2}{3}17\rfloor+11=40$\\ &$LB=29$\\ Node
4&$UB=18+\lfloor\frac{2}{3}14\rfloor+11=38$\\ &$LB=29$\\ Node
5&$UB=\lfloor\frac{5}{7}18\rfloor+17+11=39$\\ &$LB=28$\\ Node
6&$UB=17+11+\lfloor\frac{5}{9}14\rfloor=35$\\ &$LB=28$\\ Node
7&infeasible\\ Node 8&$UB=18+17+\lfloor\frac{3}{4}6\rfloor=39$\\
&$LB=35$\\ Node 9&$UB=18+17+4=39$\\ &$LB=32$\\ Node
10&$UB=18+17+4=39$\\ &$LB=39$\\ Node
11&$UB=18+\lfloor\frac{8}{9}17\rfloor+6=39$\\ &$LB=24$
\end{tabular}

Optimal solution at node 10,

$x_1=x_2=x_6=1\ x_3=x_4=x_5=x_7=0\ z=39$

With the additional constraints, the upper bounds remain valid.
However, it may be possible to fix variables at some nodes of tjhe
tree,

At nodes 4 (and 3), $x_4=0,\ x_2=0,\ x_6=0,\ x_7=0$.

Thus $UB=18+11+6=35,\ LB=35$

At node 8, $x_1=x_2=0\ UB=6+4+5=15$

At node 9, $x_1=0\ UB=17+\lfloor\frac{1}{2}6\rfloor+14=34$

Optimal solution at node 4 $x_1=x_3=x_5=1\ x_2=x_4=x_6=x_7=0\
z=35$


\item[(b)]
In the trim loss problem, every column represents a cutting
combination (where the rows are the number of cuts for the
different possible widths). Initially a small subset of columns is
found and the linear programming problem is solved. Let $y_i$ be
the dual variable for row $i$. If $n_i$ is the number of cuts for
width $i$ in a particular pattern and $c$ is the cost, then the
reduced cost is

$$c-n_1y_1-n_2y_2\ldots$$

The most negative reduced cost is given for $n_i$ which minimize

$$c-n_1y_1-n_2y_2\ldots$$

or equivalently maximize

\begin{equation}
 z=n_1y_1+n_2y_2\ldots
\end{equation}

There is a constraint on the number of widths that can be cut: if
$w_i$ is the width corresponding to row $i$ and $w$ is the width
of the original roll then

\begin{equation}
w_1n_1+w_2n_2+\ldots\leq w
\end{equation}

and

\begin{equation}
n_1,n_2\ldots\textrm{are non-negative integers}
\end{equation}

Clearly, (1), (2), (3) defines a knapsack problem. If $z\leq c$,
then there are no negative reduced cost for unconsidered cutting
combinations, so the linear programming solution is optimal.
Otherwise, the solution of the knapsack problem generates a new
cutting pattern that is added as an extra column to the linear
programming problem.

\end{description}




\end{document}