$($a$)($i$)$ Describe the Backtracking and Jumptracking strategies for branching $($to

solve Integer Programming problems$).($ii$)$ Describe at least one advantage

and one disadvantage of each of the two strategies.

$($b$)$ Using the backtracking branch$-$and$-$bound algorithm, solve the following in$-$

stance of MAX$-$SAT. In the algorithm, assign a variable the value $\frac{1}{?}$ true be$-$

fore assigning it the value $\frac{0}{?}$ false. Depict the search tree and justify your

answer.

$F_1=x_{1}vvnot{x}_2,F_2=x_{1}vv{x}_{3}vv{x}_4,F_3=not{x}_{1}vv{x}_2,$

$F_4=x_{1}vvnot{x}_{3}vvnot{x}_4,F_5=x_{2}vvnot{x}_{3}vv{x}_4,F_6=x_{1}vvnot{x}_{3}vv{x}_4,$

$F_7=x_{1}vv{x}_3,F_8=x_{1}vvnot{x}_4,F_9=not{x}_{1}vvnot{x}_3,$

$F_{10}=x_{1}vvnot{x}_3,F_{11}=not{x}_{1}vv{x}_4.,$

$($c$)$ Consider the following LP problem.

maximize $-4x_1+12x_2$

subject $to-x_1-x_2,21$

$x_1-7x_2+x_3=23$

$2x_1+3x_2,10$

$x_1,x_2,x_{3}0$

Suppose we wish to solve this problem using the Two$-$phase method. Write

down the LP problem that should be solved in the first phase of the Two$-$

phase method using the minimum number of artificial variables. $($Do not

attempt to actually solve it$.)$ What outcome of the first phase would indicate

that the LP problem has a feasible solution?

$($d$)$ State the Bin Packing Problem $($BPP$)$ and explain in words how the Next Fit,

First Fit and First Fit Decreasing heuristics work. Run each of these three

heuristics on the following example: Let $b=1$ be the capacity of each bin

and $L=(\frac{1}{2},\frac{1}{10},\frac{1}{2},\frac{1}{4},\frac{1}{3},\frac{3}{4},\frac{1}{2}).$ Which of the above heuristics can be used for

the online version of BPP$?$ Justify your answer.