$($a$)$ Explain what an Integer Programming Problem is$.$ Explain in words what

the Knapsack Problem is$.$ Formulate the Knapsack Problem as an Integer

Programming Problem. In this integer programming formulation explain the

meaning of all parameters, variables and constraints.

$($b$)$ 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.

$($c$)$ 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 $0/$false$.$ Depict backtracking as a search tree and

provide explanation.

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

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

$F_7=x_3,F_8=not{x}_{1}vvnot{x}_3,F_9=x_1.$ can you solve this $($a$)$ Solve the following LP problem graphically. Explain how you find the solu$-$

tions and give all the optimal solutions.

minimize $x_1+x_2$

subject $to{x}_1+5x_{2}5$

$,3x_1+2x_{2}6$

$,x_1,x_{2}0$

$($b$)$ List four possible types of outcome for an LP problem.

$($c$)$ Find the optimal value of the objective function of the following LP problem

by directly solving the dual.

maxz$=,3x_1-8x_2-2x_3,$

$s.t.-3x_1+2x_2-2x_3,-15$

$,x_1,x_2,x_3,0.$

$($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}{7},\frac{1}{2},\frac{1}{4},\frac{1}{3},\frac{3}{4},\frac{1}{2}).$ Explain why First Fit Decreasing produces an

optimal solution. $($a$)$ Solve the following LP problem graphically. Explain how you find the solu$-$

tions and give all the optimal solutions.

minimize $x_1+x_2$

subject $to{x}_1+5x_{2}5$

$,3x_1+2x_{2}6$

$,x_1,x_{2}0$

$($b$)$ List four possible types of outcome for an LP problem.

$($c$)$ Find the optimal value of the objective function of the following LP problem

by directly solving the dual.

maxz$=,3x_1-8x_2-2x_3,$

$s.t.-3x_1+2x_2-2x_3,-15$

$,x_1,x_2,x_3,0.$

$($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}{7},\frac{1}{2},\frac{1}{4},\frac{1}{3},\frac{3}{4},\frac{1}{2}).$ Explain why First Fit Decreasing produces an

optimal solution.