\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

\begin{description}

\item[(a)]
By means of a diagram, write down the facet defining constraints
for the integer programming problem with the following
constraints:

\begin{eqnarray*}
x_1,x_2\textrm{ integer}\\ 6x_1-4x_2&\leq&15\\ 2x_1+4x_2&\geq&5\\
6x_1+2x_2&\geq&5\\ 2x_1-6x_2&\geq&-15\\ 6x_1+8x_2&\leq&33
\end{eqnarray*}

State the advantage of such a reformulation.

\item[(b)]
A factory is potentially able to make up to two types of product
(A and B). The production of any units of type A, however,
requires the purchase of a machine P at a fixed cost of 8,
allowing the manufacture of up to 6 units of type A. For product
B, it is necessary to purchase a machine Q at a fixed cost of 5,
with the capacity to manufacture up to 12 units of type B.
However, not more than 10 products can be made in total.

The unit profits for types A and B are 6 and 5, respectively.

There is also an overall limit of 24 kilos of raw material. Each
unit of type A requires 3 kilos of this raw material, and each
unit of type B requires 2 kilos.

\begin{description}

\item[(i)]
 Build an integer programming model
which would enable one to determine which machines to buy and the
quantities to be manufactured.

\item[(ii)]
 The solution of the linear programming
relaxation of the standard formulation of this problem is:

 Make 4 units of type A and 6 units of type B using
${{2}\over{3}}$ of machine P and ${{1}\over{2}}$ of machine Q. The
total profit would be $46{{1}\over{6}}$.

Using this solution as the starting point of the branch-and-bound
algorithm, solve the problem. You should be able to spot the
solutions to any required linear programming problems by
inspection.  There is no need to use the simplex algorithm.

\end{description}

\end{description}


ANSWER


\begin{description}

\item[(a)]

\setlength{\unitlength}{2cm}

\begin{picture}(6,5)

\put(.75,1){\vector(1,0){5}} \put(1,.75){\vector(0,1){4}}
\put(2,.75){1} \put(3,.75){2} \put(4,.75){3} \put(6,1){$x_1$}
\put(.75,1.9){1} \put(.75,2.9){2} \put(.75,3.9){3}
\put(.9,4.75){$x_2$}

\put(1,3.5){\line(3,1){1.5}}\put(2.5,4){\line(4,-3){2}}
\put(4.5,2.5){\line(-2,-3){1}}\put(3.5,1){\line(-2,1){2}}
\put(1.5,2){\line(-1,3){.5}}

\put(2,3){\line(1,0){1}} \put(3,3){\line(1,-1){1}}
\put(4,2){\line(-1,0){2}} \put(2,2){\line(0,1){1}}

\end{picture}

Facet density constraints:

\begin{eqnarray*}
x_1&\geq&1\\ x_2&\geq&1\\ x_2&\leq&2\\ x_1+x_2&\leq&4
\end{eqnarray*}

The advantage is that the LP relaxation solution would yield
optimal integer solution for any objective.

\item[(b)]

\begin{description}

\item[(i)]
Let the quantities of $A$ and $B$ to be made to be $a$ and $b$
respectively.

Let
\begin{tabular}{lll}
$P$&=1&if and only if machine $P$ purchased\\ &=0&otherwise
\end{tabular}

Let
\begin{tabular}{lll}
$q$&=1&if and only if machine $Q$ purchased\\ &-0&otherwise
\end{tabular}

\begin{tabular}{ll}
Maximize&$6a+5b-8p-5q$\\ subject to&$a-6p\leq0$\\ &$b-12q\leq0$\\
&$3a+2b\leq24$\\ &$a+b\leq10$\\ &$a,\ b\geq0\ p,q\in\{0,1\}$
\end{tabular}

\item[(ii)]

\setlength{\unitlength}{1.2cm}

\begin{picture}(9,8)

\put(5,7){\circle{.3}}\put(5,7){\makebox(0,0){0}}
\put(3,4){\circle{.3}}\put(3,4){\makebox(0,0){1}}
\put(7,4){\circle{.3}}\put(7,4){\makebox(0,0){2}}
\put(2,1){\framebox(.3,.3)}\put(2,1){\makebox(.3,.3){3}}
\put(3.7,1){\framebox(.3,.3)}\put(3.7,1){\makebox(.3,.3){4}}

\put(5,6.8){\line(-2,-3){1.8}}\put(5,6.8){\line(2,-3){1.8}}
\put(3,3.8){\line(-1,-3){.8}}\put(3,3.8){\line(1,-3){.8}}

\put(6.2,5.1){$p=1$} \put(2.7,5.1){$p=0$} \put(1.5,2){$q=0$}
\put(4,2){$q=1$}

\begin{small}
\put(6,6){\begin{tabular}{ll}$a=4$&$p=\frac{2}{3}$\\
$b=6$&$q=\frac{1}{2}$\\ Objective&=$46\frac{1}{6}$\end{tabular}}

\put(7.5,3.5){\begin{tabular}{ll}$a=4$&$p=1$\\
$b=6$&$q=\frac{1}{2}$\\Objective&=$43\frac{1}{2}$\end{tabular}}

\put(0,3.5){\begin{tabular}{ll}$a=10$&$p=0$\\
$b=10$&$q=\frac{5}{6}$\\ Objective&$=45\frac{5}{6}$\end{tabular}}

\put(0,.5){$=q=0$} \put(0,1.){$a=b=p$} \put(0,0){Objective=0}
\put(4.2,.5){\begin{tabular}{ll}$a=0$&$p=0$\\ $b=10$&$q=1$\\
Objective&=45 \end{tabular}}

\end{small}

\end{picture}

NB At node 1 we can only make 10 of $B$ for which we would only
need $\frac{5}{6}$ of $q$ giving objective value of
$45\frac{5}{6}$. This solution must be better than that at node 2
for which we would need an extra $\frac{1}{3}$ of $P$ at a cost of
$2\frac{2}{3}$.

At nodes 3 and 4 the optimal solutions are obvious.

Hence optimal solution is that at node 4.

An alternative tree is possible from branching on $q$ at node 0.

\end{description}

\end{description}



\end{document}