Recall the discounted knapsack problem from HW$6($Q$1).$ In this homework, we$$ll develop valid

inequalities to improve its LP relaxation.

max $6($x$11+$ x$12)+4($x$21+$ x$22)+8($x$31+$ x$32)+2($x$41+$ x$42)$

s$.$t$.$

$10$x$11+10$x$12+12$x$21+12$x$22+2$x$31+2$x$32+4$x$41+4$x$42<=23$

$5$x$11+2\mathrm{.}5$x$12+4$x$21+2$x$22+3$x$31+1\mathrm{.}5$x$32+3$x$41+1\mathrm{.}5$x$42<=9$

x$12<=$ x$11$

x$22<=$ x$21$

x$32<=$ x$32$

x$42<=$ x$41$

x$11,$ x$12,$ x$21,...,$ x$42$ in $\{0,1\}$

a$)$ Focusing on the first constraint, use the process we learned in Lecture $19$ on slide

$$Extending the logic$$ to find a valid inequality. Show work.

b$)$ Focusing on the second constraint, find a valid inequality using logical relationships of

the variables $($similar to slide $$Example: Logical Constraints$).$ Briefly explain why this

is inequality is valid