(0-1) knapsack polytope

61 Views Asked by At

$$P = \{x \in \{0,1\}^4 : 4x_1 + 3x_2 + 2x_3 + x_4 \leq 4\}$$

I have to disaggregate the main constraint in $P$ by using minimal cover extension procedure. I have found that minimal cover is: $\{2,3,4\}$, $\{1, 2\}$, $\{1,3\}$, $\{1,4\}$? I'm not sure if I'm correct so far, please help!

1

There are 1 best solutions below

8
On

You want to find minimal solutions that satisfy $4x_1 + 3x_2 + 2x_3 + x_4 > 4$. Your last three are correct, but $\{2,3,4\}$ is not minimal.