We have a knapsack of size $b=12$ and four items. Let the values $(v_i)$ and sizes $(b_i)$ of the four items be as follows: $v_1=1,v_2=v_3=3,v_4=10,b_1=1,b_2=b_3=2,b_4=11.$ Describe the heuristics $H_1$ and $H_2$ introduced in the lectures for the Knapsack Problem and the combined heuristic $H$ and use the three heuristics to obtain solutions for the above instance of the Knapsack Problem.

Solve the following Integer Programming problem to optimality using the branchand$-$bound algorithm.

$\{\begin{array}{ccc}\text{:}[& \text{m}\text{a}\text{x}\text{i}\text{m}\text{i}\text{z}\text{e},& z=x_1+3x_2+3x_3+10x_4]\\ & \text{s}\text{u}\text{b}\text{j}\text{e}\text{c}\text{t}to,& x_1+2x_2+x_3+11x_4\\ ,& x_1,x_2,x_3,x_4=0or& 1\end{array},12$

Consider the $3-$tree problem for the graph $G$ in Figure $2.$ Let the initial solution be the tree $T_0$ with edges $ae,af,ab.$ Starting from $T_0,$ carry out five iterations of the basic tabu search algorithm. The tabu times for deleted and added edges are $2$ and $1,$ respectively. Construct a table, where for each iteration, list the edges with tabu time $1,$ the edge with tabu time $2,$ and the edges of the current tree.