# Relaxation of the knapsack constraints

A set $$\mathcal{A}$$ is the relaxation of another set $$\mathcal{B}$$, if $$\mathcal{B} \subseteq \mathcal{A}$$.

I have a set of points defined as the knapsack constraint

$$\mathcal{X} = \{x \in \mathcal{Z}^n: w^{\top}x \leq b \}$$ where $$\mathcal{Z}^n$$ is the n-dimensional 0-1 vectors and $$w \in \Re^n_+$$ and $$b \in \Re_+$$.

I read that one possible relaxation of the above set is $$\mathcal{X} = \{x \in \mathcal{Z}^n: \lfloor w\rfloor ^{\top}x \leq \lfloor b\rfloor \}$$

where $$\lfloor \rfloor$$ represents the floor function.

It is very counter-intuitive to me. $$w^\top x \leq b$$ represents a half space with left or lower space of the hyperplane defined by $$w^\top x = b$$. By taking the floor function, we are in fact moving the hyperplane lower and shrinking the size of the set.

Can anyone explain to me why the floor function terms represent a relaxed set ?

Let me call $$\mathcal{X}_1 = \{x \in \mathcal{Z}^n: w^{\top}x \leq b \}$$ and $$\mathcal{X}_2 = \{x \in \mathcal{Z}^n: \lfloor w\rfloor ^{\top}x \leq \lfloor b\rfloor \}$$ to avoid confusion.
Let $$x \in \mathcal{X}_1$$. Then: $$b \ge w^T x = \sum_{i : x_i = 1} w_i$$ which implies: $$\lfloor b \rfloor \ge \left\lfloor \sum_{i : x_i = 1} w_i \right\rfloor \ge \sum_{i : x_i = 1} \lfloor w_i \rfloor = \lfloor w \rfloor^T x.$$
Therefore $$x \in \mathcal{X}_2$$, and this shows that $$\mathcal{X}_1 \subseteq \mathcal{X}_2$$.