Question $4.$ Consider the following $0-1$ knapsack problem:

$mamize12x_1+11x_2+8x_3+6x_4$

subject $to8x_1+8x_2+6x_3+5x_{4}20$

$x_1,x_2,x_3,x_{4}in\{0,1\}$

$(a)$ Solve the problem using the branch and bound method. Note that you will have $to$ solve

the linear programming relaxation $at$ each node $by$ solving a continuous knapsack problem.

$(b)$ Identify $as$ many cover inequalities $as$ you can for this problem.

$(c)$ Note that the following constraint $is$ implied $in$ the knapsack problem: $if{x}_1$ and $x_2$ are

both equal $to1,$ then both $x_3$ and $x_4$ must $be0.$ Write the corresponding constraint$(s).$