Relaxation of the knapsack constraints
-
05-11-2019 - |
题
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 ?
没有正确的解决方案