Given the vectors r $=[10,13,19,8],$ w $=[5,7,9,4]$ and B $=15,$ we consider a

knapsack problem

max

x in Sa

$4$

i$=1$

rixi $($Formuation $($a$))$

where

Sa $=$ x in $\{0,1\}4$

$4$

i$=1$

Now, we consider an alterative formulation as follows,

wixi $$B $.$

max

x in Sb

$4$

i$=1$

rixi $($Formulation $($b$))$

where

Sb $=$ x in Sa

i in S

xs $|$S$|1,$S $\{1,2,3,4\},$ S $=$such that

i in S

wi $>$ B

$2($a$)(5)$ Explicitly write down all the subset linear constraints in Formulation $($b$).$

$($Hint: Find all the set S $\{1,2,3,4\},$ S $=$such that i in S wi $>$ B first.$)$

$($b$)(5)$ Show that Sa $=$ Sb$.$

$($c$)(5)$ Which formulation is stronger? Why?