\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

\begin{description}

\item[(a)]
For the (zero-one) knapsack problem


\begin{tabular}{ll}
maximize&$z =  \displaystyle\sum\limits^n_{i=1} c_ix_i$\\ subject
to&$\displaystyle\sum\limits^n_{i=1} a_ix_i \le b $\\ &$x_i = 0$
or $ 1$ for $i=1,\ldots,n$
\end{tabular}


where $a_i$ and $c_i$ are positive for $i=1,\ldots,n$, and
$\sum^n_{i=1} a_i > b$, describe a procedure for solving the
linear programming relaxation. Also, prove that your procedure
provides an optimal solution of the linear programming relaxation.


\item[(b)]
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 + 25x_2 + 15x_3 + 8x_4 + 11x_5 + 4x_6 +
2x_7$\\subject to&$9x_1+ 13x_2  + 8x_3 + 5x_4 + 7x_5 + 5x_6 + 3x_7
\leq 28 $\\&$x_i = 0$ or $1$ for $i=1,\ldots,7$
\end{tabular}

\end{description}

ANSWER

\begin{description}

\item[(a)]
Index the variables so that
$\frac{c_1}{a_1}\geq\ldots\geq\frac{c_n}{a_n}$. Find index $k$
such that $\sum_{i=1}^ka_i<b\leq\sum_{i=1}^{k+1}a_i$.

The solution of the linear programming relaxation is

\begin{eqnarray*}
x_i&=&1\textrm{ for }i=1,\ldots,k\\
x_{k+1}&=&\frac{\left(b-\sum_{i=1}^ka_i\right)}{a_{k+1}}\\
x_i&=&0\textrm{ for }i=k+2,\ldots n
\end{eqnarray*}

The solution value is

$$z=\sum_{i=1}^kc_i+c_{k+1}\frac{\left(b-\sum_{i=1}^k\right)}{a_{k+1}}$$

The dual problem is

\begin{tabular}{ll}
Minimize&$z_D=b_y+\sum_{i=1}^nz_i$\\ subject to&$y\geq0,\
z_i\geq0\ i=1,\ldots n$\\ &$a_iy+z_i\geq c_i\ i=1,\ldots,n$
\end{tabular}

Consider the dual solution

\begin{eqnarray*}
y&=&\frac{c_{k+1}}{a_{k+1}}\\
z_i&=&c_i-\frac{a_ic_{k+1}}{a_{k+1}}\ i=1,\ldots,k\\ z_i=0\
i=k+1,\ldots,n
\end{eqnarray*}

Note that $z_i\geq0$ by the indexing of the variables

\begin{eqnarray*}
a_iy+z_i&=&c_i\textrm{ for }i=1,\ldots k\\
a_iy+z_i&=&a_i\frac{c_{k+1}}{a_{k+1}}\geq c_i\textrm{ for
}i=k+1,\ldots,n
\end{eqnarray*}

so the solution is feasible.

$$z_D=b\frac{c_{k+1}}{a_{k+1}}+\sum_{i=1}^kc_i-\frac{c_{k+1}}{a_{k+1}}\sum_{i=1}^ka_i=z$$

Therefore the primal and dual solutions are optimal.

\setlength{\unitlength}{1.2cm}

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

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

\put(4.5,10){54} \put(1.3,7){52} \put(6.4,7){54} \put(4.2,5){50}
\put(7.4,5){54} \put(5.3,3){51} \put(8.5,3){54} \put(.3,5){51}
\put(3.5,5){52} \put(4.4,3){52} \put(1.3,3){42} \put(5.5,1){inf}
\put(2.3,1){46}

\put(1.5,8.5){$x_3=0$} \put(5.5,8.5){$x_3=1$} \put(.5,6){$x_5=0$}
\put(2.5,6){$x_5=1$} \put(4.5,6){$x_2=0$} \put(6.7,6){$x_2=1$}
\put(1,4){$x_2=0$} \put(3.7,4){$x_2=1$} \put(5,4){$x_1=0$}
\put(7.5,4){$x_1=1$} \put(2.3,2){$x_1=0$} \put(5,2){$x_1=1$}

\end{picture}

\item[(b)]\ \\
\begin{tabular}{ll}
Node 1&$UB=18+25+\lfloor\frac{3}{4}15\rfloor=54$\\ &$LB=43$\\ Node
2&$UB=18+25+8+\lfloor11\frac{1}{7}\rfloor=52$\\ &$LB=51$\\ Node
3&$UB=18+\lfloor\frac{11}{13}25\rfloor+15=54$\\ &$LB=33$\\ Node
4&$UB=18+8+\lfloor\frac{6}{7}11\rfloor+15=50$\\ &$LB=41$\\ Node
5&$UB=18+8+\lfloor\frac{7}{9}18\rfloor+15=50$\\ &$LB=41$\\ Node
6&$UB=8+\lfloor\frac{2}{7}11\rfloor+25+15=51$\\ &$LB=48$\\ Node
8&$UB=18+25+8+\lfloor\frac{1}{5}4\rfloor=51$\\ &$LB=51$\\ Node
9&$UB=18+\lfloor\frac{12}{13}25\rfloor+11=52$\\ &$LB=29$\\ Node
10&$UB=18+8+4+\lfloor\frac{2}{3}2\rfloor+11=42$\\ &$LB=41$\\ Node
11&$UB=\lfloor\frac{8}{9}18\rfloor+25+11=52$\\ &$LB=36$\\ Node
12&$UB=8+\lfloor\frac{3}{5}4\rfloor+25+11=46$\\ &$LB=44$
\end{tabular}

Optimal solution $x_1=x_2=x_4=1\ x_3=x_5=x_6=0\ z+51$

\end{description}




\end{document}